{"id":"3a7566a5-1d08-49d3-8f29-2a16e3fb9bff","arxiv_id":"2501.05570","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new 'partition sieving' technique solves Edge Coloring and List Edge Coloring in O*(2^{m-3n/5}) time and polynomial space, the first polynomial-space algorithms faster than O*(2^m).","lead":"This paper presents faster exponential-time algorithms for the classic Edge Coloring and List Edge Coloring problems, running in roughly 2^(m-3n/5) time while using only polynomial memory. For sparse graphs this is the first time polynomial-space algorithms beat the previous 2^m barrier.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.1 literally states a squarefree x-product, but the Pfaffian expansion yields x_e with multiplicity equal to the number of matchings containing e; taken verbatim this breaks Claim 4.3, though the multiset correction repairs the proof.","rationale":"The reader's weakest_assumption is correct and is the same concern I would flag. The false squarefree product appears verbatim; without the multiset reading the compatibility argument in Claim 4.3 does not follow. However, the proof's own Pfaffian derivation supports the multiset reading, and the coefficient extraction used to define Q forces the previously problematic E\\E' exponents to be exactly one, so the degree computation that establishes compatibility becomes valid. I checked the surrounding machinery: Theorem 3.5's compatibility-to-basis argument is sound; Lemma 4.2's composition of coefficient extraction with partition sieving has the right exponent count; the dominating-set lemma's reduction preserves the quantity m−3n/5 (each tree pruning removes equally many vertices and edges when the connection edge is re-added), so the WLOG reduction in Section 6.1 does not inflate the runtime; and the extension-matroid argument in Lemma 6.4 correctly encodes star colorability. Thus I see no reason to move beyond conditional acceptance; the paper needs a corrected Lemma 4.1 and a sentence making explicit that the product is taken with multiplicity, after which the central claim is supported.","tokens_in":26093,"tokens_out":57929,"duration_ms":563203,"concrete_test":"Re-derive the expansion of PfBAB^T for the 4-cycle with D={a,b}, V'={u,v}, and the tuple M1=M2={uv,ab}; the Pfaffian term contains x_uv^2 x_ab^2, contradicting the squarefree union formula in Lemma 4.1. Then state Lemma 4.1 with ∏_{i}∏_{e∈M_i} x_e and verify Claim 4.3 for an arbitrary monomial of Q: because Q is the coefficient of ∏_{e∈E\\E'} x_e, every such edge has exponent exactly one, so for v∈V' the degree on ∂(v) equals deg_G(v)−|{e∉E':e∋v}|=deg_{E'}(v).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing issue is the statement of Lemma 4.1 (Section 4.1). The displayed formula writes the X-factor as ∏_{e∈M1∪...∪Mk} x_e, i.e., squarefree. The actual expansion via Proposition 2.8 and equation (3) gives ∏_{i∈[k]} ∏_{e∈Mi} x_e y_{ei}, so an edge lying in several matchings contributes x_e with exponent equal to its multiplicity. The squarefree version is false for any tuple in C with overlapping matchings, and it is exactly what Claim 4.3 uses to conclude that each monomial of Q has degree deg_{E'}(v) on ∂(v). With the squarefree statement, the degree on ∂(v) would be deg_G(v)−|{e∉E′: e∋v}| only when every such edge has multiplicity one, which is not guaranteed for arbitrary tuples in C. The fix is to replace the union product by the multiset product; then the homogeneity of P and the fact that Q is the coefficient of one copy of every edge in E\\E′ (so those edges have exponent exactly one in any contributing monomial) make Claim 4.3 correct. This is a genuine correctness gap in the written proof, but it is local and clearly repairable; I did not find a further flaw in partition sieving, the dominating-set routine, or the list-coloring extension after this correction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a technique called partition sieving, which extends prior determinantal sieving to detect multilinear monomials in a polynomial P that are bases of a partition matroid in O*(2^{d-p}) time and polynomial space, where d is the degree and p is the number of partition classes. It applies this to Edge Coloring and List Edge Coloring by constructing a Pfaffian-based polynomial whose monomials enumerate tuples of matchings with prescribed vertex-degree multiplicities, then using dominating sets to define a compatible partition matroid. The main results are randomized O*(2^{m-3n/5}) time and polynomial-space algorithms for both problems, with an improved bound for regular graphs and a simpler O*(2^{m-3n/5}) bound for list coloring after a tree-pruning reduction.","tokens_in":30,"tokens_out":33760,"duration_ms":440722,"significance":"If the technical issues identified below are repaired, these would be the first algorithms for Edge Coloring and List Edge Coloring that run in faster than O*(2^m) time while using only polynomial space, which is a substantial improvement over the previous state of the art. The partition sieving theorem (Theorem 3.5) is a clean, parameter-free contribution to algebraic monomial-detection techniques, and the extension-matroid construction for handling low-degree vertices in list edge coloring is elegant. The paper is largely well organized, with concrete runtime bounds and a clear separation between the edge-coloring and list-edge-coloring proofs. The central ideas are plausible and the remaining issues are local, but they are load-bearing and require correction before the proofs can be considered complete.","major_comments":[{"comment":"The displayed formula in Lemma 4.1 writes the X-factor as the squarefree product over M_1 ∪ ... ∪ M_k, but the Pfaffian expansion via Proposition 2.8 and equation (3) yields a factor x_e whose exponent is the number of matchings M_i containing e. The squarefree statement is false for any tuple in C with overlapping matchings, and the compatibility proof in Claim 4.3 depends on the degree of a monomial on edges incident to v being deg_G(v), which is only correct under the multiset reading. The statement should be corrected to use ∏_{i∈[k]} ∏_{e∈M_i} x_e, and the proof of Lemma 4.1 should be adjusted accordingly; with that correction, the subsequent arguments in Lemma 4.2 go through.","section":"Section 4.1, Lemma 4.1"},{"comment":"Lemma 6.6 is stated for graphs with n1 unit-degree vertices, but its proof uses mnew = m - n1 and nnew = n - n1, which hold only after the tree-pruning reduction of Section 6.1 has been applied, so that the vertices deleted to obtain Gnew are exactly the unit-degree vertices. The proof of Theorem 1.3 in the case n1 ≥ n/5 should explicitly say that the pruning is performed first, and should then show that the runtime O*(2^{m* - (n*+n1*)/2}) on the pruned graph is at most O*(2^{m-3n/5}) in the original parameters. As written, the application of Lemma 6.6 to the original unpruned graph is not justified.","section":"Section 6, Lemma 6.6 and Theorem 1.3"},{"comment":"The proof writes V' = V\\D, but when Lemma 4.2 is applied to the polynomial built from Gnew, the relevant partition size is |Vnew\\D|, not |V\\D|. Moreover, the inequality 'Since mnew ≤ m' is too weak to conclude O*(2^{m-3n/5}); the intended argument should use mnew = m - n1 and |Vnew\\D| ≥ 3(n - n1)/5, which gives the stated bound after simplification.","section":"Section 6, Theorem 1.3 proof, second case"}],"minor_comments":[{"comment":"The symbol W is used both for the disjoint union of vertex copies and for the direct-sum matroid in equation (4); renaming one of these would avoid confusion.","section":"Section 2 and Section 4.1"},{"comment":"There is a typo: 'nonzeo' should be 'nonzero'.","section":"Section 4.1, Lemma 4.1 proof"},{"comment":"The phrase 'outEdge Coloring algorithms' should be 'our Edge Coloring algorithms'.","section":"Section 5, Theorem 1.1 proof"},{"comment":"The uniqueness of the connecting edge e from a tree T_v to v is used implicitly in the discussion of (T_v + e); it would be helpful to state explicitly that a component of G[V1] has at most one edge to any vertex of Gnew, since otherwise (T_v + e) need not be a tree.","section":"Section 6.1"}],"recommendation":"major_revision","confidential_remarks":"The main correctness issues are local and appear repairable within the scope of the manuscript: Lemma 4.1 needs a multiset product, and the runtime accounting in Theorem 1.3 needs to be stated with respect to the pruned graph and Gnew. The partition sieving idea is novel and the claimed results are strong. I would encourage the editor to send the revision back to the same referees to verify the corrected statements."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper answers a real open question and introduces a technique worth knowing. The main results are the first algorithms for Edge Coloring and List Edge Coloring that run in faster than 2^m time with polynomial space—specifically 2^{m-3n/5} with high probability and one-sided error. The average-degree exponent improves from (1/d)^{Theta(d^3)} to 6/(5d), and the regular-graph case gets a further saving. The key new idea, partition sieving, is a natural and useful generalization of determinantal sieving: for a polynomial compatible with a partition matroid with p parts, multilinear basis detection drops from O*(2^k) to O*(2^{k-p}). That is a real contribution in its own right, not a repackaging.\n\nThe paper also does the work properly. The polynomial construction via Pfaffians and the Ishikawa-Wakayama formula is coherent, the reduction to dominating sets is elegant, and the list-coloring extension uses extension matroids in a genuinely nontrivial way. I found no fitted parameters and no circularity concerns; the dependence on prior work is transparent.\n\nThe soft spot is real but local. Lemma 4.1 as written states the X-factor as a squarefree product over the union of matchings. The Pfaffian expansion actually yields x_e with multiplicity equal to the number of matchings containing e. As stated, the lemma is false for tuples with overlapping matchings, and Claim 4.3 needs the multiset reading for the degree computation on ∂(v) to work. The fix is to write the product over the multiset union, i.e., ∏_i ∏_{e in M_i} x_e. Once that is done, the homogeneity argument goes through and I did not find any further break. This is a proof-exposition bug, not a flaw in the method, but it does need correcting before the paper is published; a referee should ask for it.\n\nOne other place I would want a little more care is the tree-pruning argument in Section 6.1, where the reduction from forests to stars is explained tersely. I do not think it is wrong, but it deserves a more explicit statement. The citation pattern is fine.\n\nBottom line: this is a strong paper that advances exact exponential algorithms on a classic problem. It deserves a serious referee and, after a minor revision, publication.","headline":"Resolves a real open question with a genuinely new technique; the only real problem is a fixable typo in Lemma 4.1, and the paper deserves a rigorous but fair referee.","tokens_in":26900,"tokens_out":2816,"would_cite":true,"duration_ms":25596,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C70","05B35","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Edge Coloring and List Edge Coloring can be solved exactly in O*(2^{m−3n/5}) time using only polynomial space, the first faster-than-2^m algorithms for these problems to do so.","keywords":["edge coloring","chromatic index","list edge coloring","exact exponential algorithms","polynomial space","partition sieving","Pfaffian","dominating set"],"falsifier":"Expand the polynomial Pf(BA B^T) from Section 4 on K_4 with k=3 and uniform matroids of rank 3 for each vertex. The tuple M_1=M_2={uv,xy}, M_3={ux,vy} meets the degree constraints defining the collection C, so the expansion must contain a monomial with x_{uv}^2 x_{xy}^2; finding that monomial would refute the squarefree product stated in Lemma 4.1 and force the multiset reading the rest of the proof relies on.","tokens_in":25911,"feed_emoji":"🎨","tokens_out":13740,"duration_ms":128430,"temperature":0.7,"pith_summary":"Edge Coloring — deciding whether a graph's edges can be colored with Δ colors, where Δ is the maximum degree — is NP-hard, and previous exact algorithms either ran in O*(2^m) time with polynomial space or ran faster only with exponential space. This paper gives a randomized, one-sided-error algorithm that runs in O*($2^{{m−3n/5}}$) time and polynomial space, and extends the same bound to the harder List Edge Coloring problem. These are the first algorithms for either problem that are simultaneously faster than O*(2^m) and use only polynomial space. The speed-up comes from a new monomial-detection technique called partition sieving, applied to a Pfaffian-based polynomial that encodes tuples of matchings.","feed_headline":"Edge coloring breaks the 2^m barrier using only polynomial space","feed_subtitle":"A partition-sieving method plus small dominating sets yields the first faster-than-2^m exact edge-coloring algorithms.","key_machinery":"The main object is the polynomial P = Pf(BA B^T), built from a block-diagonal skew-symmetric matrix A that assigns a variable to each edge–color pair and from a matrix B representing a matroid whose ranks encode vertex degrees; by the Ishikawa–Wakayama formula, monomials of P enumerate k-tuples of matchings whose combined vertex incidences match the degree sequence. The runtime engine is partition sieving: if a polynomial P is compatible with a partition matroid having p parts, a multilinear monomial whose support is a basis can be detected in O*($2^{{deg P − p}}$) time and polynomial space, improving the O*($2^{{deg P}}$) of prior basis sieving. The partition is obtained from a dominating set D: each vertex outside D gives one part, so p = n − |D|, and the existence of dominating sets of size at most 2n/5 in minimum-degree-two graphs yields the m − 3n/5 exponent.","core_discovery":"The paper's central claim is that the classical question of whether a graph's edges split into Δ matchings can be answered algebraically in O*($2^{{m−3n/5}}$) time, with high probability and one-sided error, using only polynomial space. The same method solves List Edge Coloring, where each edge has a list of allowed colors, in the same time bound. In graphs of average degree d the exponent becomes (1−6/(5d))m, and for d-regular graphs with d≥6 the exponent improves further to m−α_d n with α_d = 1−H_{d+1}/(d+1), approaching m−n as d grows. The proof constructs a polynomial whose multilinear monomials correspond exactly to proper Δ-colorings, then detects such a monomial by sieving over a partition matroid derived from a small dominating set.","pith_inferences":["The partition-sieving speed-up from 2^d to 2^{d−p} is stated for arbitrary polynomials compatible with a partition matroid; if it extends to other polynomial encodings, the same technique could give faster exact algorithms for other packing and covering problems whose solutions can be enumerated with degree constraints.","The paper's bottleneck is the 2n/5 dominating-set bound; if degree-two vertices could be removed as freely as degree-one vertices, the known 3n/8 bound for minimum-degree-three graphs would improve the exponent to m−5n/8 — a direction the authors note in their conclusion.","A concrete stress test of the proof is to symbolically expand the Pfaffian on small instances to check the multiset reading of Lemma 4.1; such a check would clarify which version of the encoding lemma the later compatibility argument requires.","The extension-matroid construction used for List Edge Coloring turns the star of unit-degree neighbors at each vertex into a matroid constraint, an idea that may transfer to other extension problems where a partial coloring must be extended to a low-degree subgraph."],"forward_implications":["If the bound is correct, Edge Coloring in graphs of average degree d runs in O*(2^{(1−6/(5d))m}) time, replacing the previous exponential-space bound with exponent (1/d)^{Θ(d^3)}.","List Edge Coloring is solvable in O*(2^{m−3n/5}) time and polynomial space; when all lists draw from k colors, this gives O*(2^{(1−6/(5k))m}) time.","For d-regular graphs with d≥6, the exponent improves to m−α_d n with α_d = 1−H_{d+1}/(d+1), so for large degree the runtime approaches O*(2^{m−n}).","The framework turns improved dominating-set bounds directly into faster coloring algorithms: any graph class with dominating sets of size at most c n for c<2/5 would immediately give an O*(2^{m−(1−c)n}) algorithm under the same machinery.","A vertex of degree one can be deleted without changing whether a Δ-coloring exists, so the core algorithm only needs to handle minimum-degree-two graphs."],"supporting_citations":[{"why":"Supplies the Ishikawa–Wakayama formula used to construct the enumerating polynomial P.","marker":"[25]"},{"why":"Supplies the determinantal sieving and odd sieving subroutines that partition sieving builds on.","marker":"[18]"},{"why":"Supplies the 2n/5 dominating-set bound for minimum-degree-two graphs that yields the m−3n/5 exponent.","marker":"[38]"},{"why":"Supplies the dense-graph dominating-set bound cited for Lemma 2.2 together with [38].","marker":"[13]"},{"why":"Gives the previous O*(2^m) polynomial-space algorithm and the regular-graph O*(2^{m−n/2}) result that this paper improves.","marker":"[11]"},{"why":"Supplies the exact dominating-set algorithm used to find a minimum dominating set in the Lemma 2.4 time bound.","marker":"[46]"},{"why":"Supplies the polynomial-time list edge coloring on trees used for the tree-pruning step in the List Edge Coloring algorithm.","marker":"[35]"}],"fun_headline_variants":["Partition sieving cracks edge coloring's 2^m barrier in polynomial space","Edge coloring exact: 2^(m-3n/5) time, polynomial space","New edge-coloring algorithm beats 2^m using only polynomial space","Faster edge coloring via partition sieving, no exponential space needed","Polynomial-space edge coloring breaks the 2^m barrier"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole speed-up depends on the Pfaffian polynomial recording each edge with multiplicity equal to the number of matchings containing it, because only then does the compatibility step that makes partition sieving apply go through.","fun_headline_variants_meta":{"raw":{"variants":["Partition sieving cracks edge coloring's 2^m barrier in polynomial space","Edge coloring exact: 2^(m-3n/5) time, polynomial space","New edge-coloring algorithm beats 2^m using only polynomial space","Faster edge coloring via partition sieving, no exponential space needed","Polynomial-space edge coloring breaks the 2^m barrier"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000526,"raw_usage":{"total_tokens":2619,"prompt_tokens":1103,"completion_tokens":1516,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":719,"completion_tokens_details":{"reasoning_tokens":1417}},"tokens_in":719,"tokens_out":1516,"duration_ms":12034,"temperature":1.0,"reasoning_tokens":1417,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:17:43.266812+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Expand the polynomial Pf(BA B^T) from Section 4 on K_4 with k=3 and uniform matroids of rank 3 for each vertex. The tuple M_1=M_2={uv,xy}, M_3={ux,vy} meets the degree constraints defining the collection C, so the expansion must contain a monomial with x_{uv}^2 x_{xy}^2; finding that monomial would refute the squarefree product stated in Lemma 4.1 and force the multiset reading the rest of the proof relies on.","supporting_citations":[{"cited_title":"Minor summation formula of pfaffians","cited_arxiv_id":null,"evidence_quote":"Supplies the Ishikawa–Wakayama formula used to construct the enumerating polynomial P."},{"cited_title":"Determinantal sieving","cited_arxiv_id":null,"evidence_quote":"Supplies the determinantal sieving and odd sieving subroutines that partition sieving builds on."},{"cited_title":"Domination in graphs with minimum degree two","cited_arxiv_id":null,"evidence_quote":"Supplies the 2n/5 dominating-set bound for minimum-degree-two graphs that yields the m−3n/5 exponent."},{"cited_title":"An estimate of the external stability number of a graph without suspended vertices","cited_arxiv_id":null,"evidence_quote":"Supplies the dense-graph dominating-set bound cited for Lemma 2.2 together with [38]."},{"cited_title":"Narrow sieves for parameterized paths and packings","cited_arxiv_id":null,"evidence_quote":"Gives the previous O*(2^m) polynomial-space algorithm and the regular-graph O*(2^{m−n/2}) result that this paper improves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the exact dominating-set algorithm used to find a minimum dominating set in the Lemma 2.4 time bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the polynomial-time list edge coloring on trees used for the tree-pruning step in the List Edge Coloring algorithm."}],"review_version":1}