Complexity metadata correctness review: best-known algorithm complexities and reduction overheads

[GiggleLiu]

Systematic Complexity Correctness Review

A systematic review of all declare_variants! complexity expressions and #[reduction(overhead)] formulas. The complexity field represents the worst-case time complexity of the best known algorithm for each problem variant.

Methodology: For each variant, the declared complexity was compared against the best known exact algorithm from the literature. For each reduction, the overhead formula was compared against the actual code that constructs the target problem. All claims include algorithm name, author(s), year, and citation.

Summary

Category	Correct	Wrong	Acceptable (conservative)	Total
Variant complexity	8	7	12	27
Reduction overhead	3	4	—	7

---

Part 1: Variant Complexity — WRONG (7 items)

1. MaximumMatching<SimpleGraph, i32> — src/models/graph/maximum_matching.rs:223

Declared	2^num_vertices
Best known	O(V³) — polynomial time
Algorithm	Blossom algorithm (Gabow's implementation)
Authors	Jack Edmonds (1965); Harold Gabow (1990)
Fix	num_vertices^3
Source	Edmonds, "Paths, Trees, and Flowers," Canadian J. Math. 17:449–467, 1965. DOI:10.4153/CJM-1965-045-4

2. KColoring<K2> — src/models/graph/kcoloring.rs

Declared	2^num_vertices
Best known	O(V+E) — polynomial time (linear)
Algorithm	BFS/DFS bipartiteness check
Authors	Textbook (Cormen et al.)
Fix	num_vertices + num_edges or num_vertices
Source	Standard textbook result; 2-coloring = bipartiteness testing

3. KSatisfiability<K2> — src/models/satisfiability/ksat.rs

Declared	2^num_variables
Best known	O(n+m) — polynomial time (linear)
Algorithm	Implication graph SCC decomposition
Authors	Aspvall, Plass, Tarjan (1979)
Fix	num_variables + num_clauses or num_variables
Source	Aspvall, Plass, Tarjan, "A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas," IPL 8(3):121–123, 1979. DOI:10.1016/0020-0190(79)90002-4

4. KColoring<K3> — src/models/graph/kcoloring.rs

Declared	3^num_vertices
Best known	O*(1.3289ⁿ)
Algorithm	Constraint satisfaction reduction
Authors	Beigel and Eppstein (2005)
Fix	1.3289^num_vertices
Source	Beigel & Eppstein, "3-Coloring in Time O(1.3289ⁿ)," J. Algorithms 54(2):168–204, 2005. DOI:10.1016/j.jalgor.2004.06.008. arXiv: cs/0006046

5. KColoring<K4> — src/models/graph/kcoloring.rs

Declared	4^num_vertices
Best known	O*(1.7159ⁿ)
Algorithm	Measure and conquer
Authors	Wu, Gu, Jiang, Shao, Xu (2024)
Fix	1.7159^num_vertices
Source	Wu et al., "A Faster Algorithm for the 4-Coloring Problem," ESA 2024, LIPIcs Vol. 308, pp. 103:1–103:16. DOI:10.4230/LIPIcs.ESA.2024.103

6. KColoring<K5> — src/models/graph/kcoloring.rs

Declared	5^num_vertices
Best known	O*((2−ε)ⁿ) for some ε > 0
Algorithm	Breaking the 2ⁿ barrier
Authors	Zamir (2021)
Fix	2^num_vertices (simplified upper bound)
Source	Zamir, "Breaking the 2ⁿ Barrier for 5-Coloring and 6-Coloring," ICALP 2021, LIPIcs Vol. 198, pp. 113:1–113:20. DOI:10.4230/LIPIcs.ICALP.2021.113. arXiv: 2007.10790

7. KColoring<KN> — src/models/graph/kcoloring.rs

Declared	k^num_vertices
Best known	O*(2ⁿ) — independent of k
Algorithm	Inclusion-exclusion / set partitioning via zeta transform
Authors	Björklund, Husfeldt, Koivisto (2009)
Fix	2^num_vertices
Source	Björklund, Husfeldt, Koivisto, "Set Partitioning via Inclusion-Exclusion," SIAM J. Comput. 39(2):546–563, 2009. DOI:10.1137/070683933

---

Part 2: Variant Complexity — ACCEPTABLE but conservative (12 items)

These use 2^n as a generic exponential bound. The true best-known bounds are tighter, but 2^n is at least exponential in the right parameter. Whether to update depends on desired precision.

Problem	Declared	Best Known	Algorithm	Authors, Year	Source
MIS/SimpleGraph (7 variants)	2^n	O*(1.1996ⁿ)	Measure & Conquer	Xiao & Nagamochi, 2017	DOI:10.1016/j.ic.2017.06.001
MIS/TriangularSubgraph	2^n	O*(1.1893ⁿ)	Degree-6 MIS	Xiao & Nagamochi, 2017	Same paper
MVC/SimpleGraph	2^n	O*(1.1996ⁿ)	Via MIS complement	Xiao & Nagamochi, 2017	Same paper
MaxClique/SimpleGraph	2^n	O*(1.1892ⁿ) exp space	Backtracking+DP	Robson, 2001	DOI:10.1016/0196-6774(86)90032-5
MDS/SimpleGraph	2^n	O*(1.4969ⁿ)	Measure & Conquer	van Rooij & Bodlaender, 2011	DOI:10.1016/j.dam.2011.07.001
MaximalIS/SimpleGraph	2^n	O*(3^{n/3}) ≈ O*(1.4423ⁿ)	MIS enumeration	Moon-Moser 1965 / Tomita 2006	Tomita et al., TCS 363(1):28–42, 2006
TSP/SimpleGraph	n!	O*(2ⁿ · n²)	Held-Karp DP	Held & Karp, 1962	DOI:10.1137/0110015
MaxCut/SimpleGraph	2^n	O*(2^{ωn/3}) exp space	2-CSP optimization	Williams, 2005	DOI:10.1016/j.tcs.2005.09.023
K3-SAT	2^n	O*(1.307ⁿ)	Biased-PPSZ	Hansen, Kaplan, Zamir & Zwick, 2019	DOI:10.1145/3313276.3316359
ILP	exp(n)	O*(nⁿ · 2^{O(n)}) = exp(O(n log n))	FPT algorithm	Dadush, 2012	Thesis
Factoring	exp(√n)	exp(O(n^{1/3} (log n)^{2/3}))	GNFS	Lenstra et al., 1993	Springer

Note on Factoring: The declared exp(sqrt(num_bits)) corresponds to the Quadratic Sieve (Pomerance, 1981), not the GNFS which is asymptotically faster. Whether this is "acceptable" or "wrong" depends on whether you want the best known classical algorithm (GNFS) or a simpler expression.

Note on TSP: num_vertices! is technically a valid upper bound but far looser than Held-Karp's O*(2ⁿ).

---

Part 3: Variant Complexity — CORRECT (8 items)

Problem	Declared	Best Known	Justification
SAT (general)	2^num_variables	O*(2ⁿ)	SETH-tight; no sub-2ⁿ algorithm known for unbounded clause width
KSatisfiability	2^num_variables	O*(2ⁿ)	PPSZ base approaches 2 as k→∞
CircuitSAT	2^num_inputs	O*(2ⁿ)	SETH-tight (Williams 2010). Note: num_inputs() getter is missing on CircuitSAT; only num_variables() exists
QUBO	2^num_vars	O*(2ⁿ)	NP-hard, no known sub-2ⁿ algorithm
SpinGlass (both variants)	2^num_vertices	O*(2ⁿ)	NP-hard on general graphs (Barahona, 1982)
MaxSetPacking (all variants)	2^num_sets	O*(2^m)	Brute-force, no known improvement
MinSetCovering	2^num_sets	O*(2^m)	Brute-force, no known improvement

CircuitSAT note: The complexity expression 2^num_inputs is theoretically correct but references a getter (num_inputs()) that does not exist on CircuitSAT. The struct only has num_variables(). This is a code-level issue, not a complexity issue.

---

Part 4: Reduction Overhead — WRONG (4 items)

1. MIS → MaxSetPacking — src/rules/maximumindependentset_maximumsetpacking.rs:39

Declared	universe_size = "num_vertices"
Actual	Universe elements are edge indices (0..num_edges−1)
Fix	universe_size = "num_edges"
Source	Code at line 49: sets[u].push(edge_idx). Karp (1972), DOI:10.1007/978-1-4684-2001-2_9

2. MaxSetPacking → MIS — src/rules/maximumindependentset_maximumsetpacking.rs:90

Declared	num_edges = "num_sets"
Actual	Intersection graph — edges connect all overlapping set pairs. Worst case: C(n,2) = O(n²)
Fix	num_edges = "num_sets * num_sets" (or "num_sets^2")
Source	Code at lines 100–108. Gavril (1972), DOI:10.1137/0201013; McKee & McMorris (1999), Topics in Intersection Graph Theory

3. SAT → k-SAT — src/rules/sat_ksat.rs:114-117

Declared	num_clauses = "num_clauses + num_literals", num_vars = "num_vars + num_literals"
Issue	Recursive padding for short clauses (L < k) doubles clauses per missing literal. For k=3 and a unit clause: 4 output clauses, 3 ancilla vars. Formula underestimates.
Fix	num_clauses = "4 * num_clauses + num_literals", num_vars = "num_vars + 3 * num_clauses + num_literals"
Note	Alternative: adopt Sipser's padding approach (repeat literals instead of ancillas) to avoid exponential blowup entirely. Then num_clauses = "num_literals" and num_vars = "num_vars" would be valid.
Source	Sipser (2012), Introduction to the Theory of Computation, 3rd ed., Theorem 7.32, pp. 283–286

4. Factoring → CircuitSAT — src/rules/factoring_circuit.rs:177-180

Declared	num_variables = "num_bits_first * num_bits_second", num_assignments = "num_bits_first * num_bits_second"
Actual	Each of m×n cells creates 6 assignments and 6 variables via build_multiplier_cell(). Plus m+n inputs and m+n output constraints.
Fix	"6 * num_bits_first * num_bits_second + num_bits_first + num_bits_second" for both fields
Source	Verified against code. Paar & Pelzl (2010), Understanding Cryptography, Ch. 6.3. DOI:10.1007/978-3-642-04101-3

---

Part 5: Reduction Overhead — CORRECT (3 items)

Reduction	Declared Overhead	Source
MIS ↔ MVC	num_vertices = "num_vertices", num_edges = "num_edges"	Gallai (1959); Garey & Johnson (1979), pp. 54–55
k-SAT → SAT	num_clauses = "num_clauses", num_vars = "num_vars", num_literals = "num_literals"	Trivial embedding
Factoring → ILP	num_vars = "2m + 2n + mn", num_constraints = "3mn + m + n + 1"	McCormick (1976), DOI:10.1007/BF01580665; verified exact match against code

[GiggleLiu]

Paper status: algorithm complexity descriptions

Cross-referenced all problem descriptions in docs/paper/reductions.typ against this issue's data. Here's the current state:

Properly cited with algorithm name (13 entries)

Problem	Algorithm	Citation
MIS	Measure-and-conquer branching	@xiao2017
Vertex Cover	MIS complement	@xiao2017
Max-Cut	Algebraic 2-CSP techniques	@williams2005
KColoring k=2	Bipartiteness testing (BFS)	textbook
KColoring k=3	Constraint satisfaction reduction	@beigel2005
KColoring k=4	Measure and conquer	@wu2024
KColoring k=5	Breaking the 2^n barrier	@zamir2021
KColoring general	Inclusion-exclusion	@bjorklund2009
Dominating Set	Measure-and-conquer	@vanrooij2011
TSP	Held-Karp DP	@heldkarp1962
Maximum Clique	Complement reduction to MIS	@xiao2017
Maximum Clique (alt)	Robson's backtracking	@Robson2001
ILP	FPT via lattice techniques	@dadush2012
k-SAT (k=3)	Biased-PPSZ	@hansen2019

Brute-force with footnote warning (8 entries)

These have no known algorithm improving on brute-force enumeration. Each has a footnote stating this explicitly:

• MaxSetPacking: O*(2^m)
• MinSetCovering: O*(2^m)
• SpinGlass: O*(2^n)
• QUBO: O*(2^n)
• SAT: O*(2^n) — footnote references SETH
• CircuitSAT: O*(2^n)
• BMF: O*(2^(mk+kn))
• PaintShop: O*(2^n)
• BicliqueCover: O*(2^(|L|+|R|))

Fixes applied in this batch

1. Replaced all terse "Best known: O*(...)" patterns with natural prose
2. Added algorithm names and citations where available
3. Added footnote warnings for brute-force entries
4. Fixed DomSet: "branch-and-reduce" → "measure-and-conquer"
5. Fixed Clique/Robson: updated to O*(1.1888^n) @Robson2001 (was O*(1.2109^n) @robson1986)
6. Fixed ILP: added "FPT algorithm based on lattice techniques"

Still to do (code-level, from this issue)

The variant complexity and reduction overhead fixes in declare_variants! and #[reduction(overhead)] are code-level changes not addressed here (paper text only).