Problem
LongestCommonSubsequence -> MaximumIndependentSet<SimpleGraph, One> is registered for an unrestricted number of input strings, but its constructor can produce an exponentially large graph relative to the encoded source input.
The single-instance reduction contract requires polynomial-time construction and recovery. This issue records the mismatch without choosing a replacement or restriction.
Symbolic evidence
Let k be the number of strings and L their common length. For a family in which every string consists of the same repeated symbol:
- Source content contains
kL symbols.
- The constructor enumerates every matching position tuple, producing exactly
L^k vertices.
- Even with fixed
L > 1, the vertex count grows exponentially in k, while the encoded source size grows linearly in k.
Materializing those vertices alone prevents a polynomial-time construction over the unrestricted source domain. The constructor also examines every vertex pair to build conflict edges.
Relevant code at current main (f11b2a48):
Why the formulas do not expose the violation
The metadata declares vertices <= P and edges <= P^2, where P = cross_frequency_product. Those bounds can correctly describe the constructed graph. However, P itself can grow exponentially in encoded input size.
Polynomial expressions in registered parameters therefore do not, by themselves, establish a polynomial-time reduction. Small closed-loop tests and output-count checks establish different properties.
Published construction and history
The implementation follows the published conflict-graph construction in Blum et al., Solving Longest Common Subsequence Problems via a Transformation to the Maximum Clique Problem, §2. Section 3 explicitly gives graph-size growth O(L^k) for classical LCS and reports severe graph expansion.
The construction is polynomial for a fixed number of strings; the current model and registration do not impose that restriction. The issue is the registered complexity scope, rather than the basic solution correspondence.
Related history: original proposal #109, implementation #804, and recent parameter/reduction work #1174 and #1190. Path-selection discussions: #1179 and #1187.
Impact and decisions to resolve
A polynomial-only path selector must not infer eligibility from polynomial formula syntax and include this unrestricted edge on that basis.
Maintainers should decide whether to replace the unrestricted construction, introduce an explicit restricted domain, or otherwise remove it from polynomial-only routing. Any retained polynomial-eligible rule needs a construction-time/output-size bound in encoded source input size, alongside solution-preservation evidence.
The overhead formula engine can remain polynomial-only; adding variable-exponent support or merely tightening the existing formulas would not fix this construction's complexity.
Problem
LongestCommonSubsequence -> MaximumIndependentSet<SimpleGraph, One>is registered for an unrestricted number of input strings, but its constructor can produce an exponentially large graph relative to the encoded source input.The single-instance reduction contract requires polynomial-time construction and recovery. This issue records the mismatch without choosing a replacement or restriction.
Symbolic evidence
Let
kbe the number of strings andLtheir common length. For a family in which every string consists of the same repeated symbol:kLsymbols.L^kvertices.L > 1, the vertex count grows exponentially ink, while the encoded source size grows linearly ink.Materializing those vertices alone prevents a polynomial-time construction over the unrestricted source domain. The constructor also examines every vertex pair to build conflict edges.
Relevant code at current main (
f11b2a48):cross_frequency_productdefinition.Why the formulas do not expose the violation
The metadata declares
vertices <= Pandedges <= P^2, whereP = cross_frequency_product. Those bounds can correctly describe the constructed graph. However,Pitself can grow exponentially in encoded input size.Polynomial expressions in registered parameters therefore do not, by themselves, establish a polynomial-time reduction. Small closed-loop tests and output-count checks establish different properties.
Published construction and history
The implementation follows the published conflict-graph construction in Blum et al., Solving Longest Common Subsequence Problems via a Transformation to the Maximum Clique Problem, §2. Section 3 explicitly gives graph-size growth
O(L^k)for classical LCS and reports severe graph expansion.The construction is polynomial for a fixed number of strings; the current model and registration do not impose that restriction. The issue is the registered complexity scope, rather than the basic solution correspondence.
Related history: original proposal #109, implementation #804, and recent parameter/reduction work #1174 and #1190. Path-selection discussions: #1179 and #1187.
Impact and decisions to resolve
A polynomial-only path selector must not infer eligibility from polynomial formula syntax and include this unrestricted edge on that basis.
Maintainers should decide whether to replace the unrestricted construction, introduce an explicit restricted domain, or otherwise remove it from polynomial-only routing. Any retained polynomial-eligible rule needs a construction-time/output-size bound in encoded source input size, alongside solution-preservation evidence.
The overhead formula engine can remain polynomial-only; adding variable-exponent support or merely tightening the existing formulas would not fix this construction's complexity.