{"id":"7afde4ec-f3b1-42f8-9dba-acd351e7d745","arxiv_id":"2506.21216","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For edge clique partition and cover parameterized above the independence number, the paper gives an FPT algorithm for the partition variant, an NP-completeness dichotomy for the cover variant, and FPT algorithms on bounded-clique, degenerate, and minor-free graphs.","lead":"These authors study two classical graph problems, edge clique cover and edge clique partition, when the allowed number of cliques is only k above the size of the largest independent set. They prove the partition version is fixed-parameter tractable, while the cover version is NP-complete for every k ≥ 2 yet polynomial for k=0,1, with additional algorithms on sparse graph classes.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5's reduction defines B too narrowly; on the P4 path it declares a no-instance to be a yes-instance, invalidating the proofs of Theorems 3 and 4.","rationale":"The reader's weakest assumption was the 'well-known' fact in Lemma 3 that a maximum independent set contains one chosen simplicial vertex from each simplicial clique. That fact is true and provable by a standard exchange argument, so it does not create a correctness problem. However, a more serious flaw appears in Lemma 5, the central reduction for the ECC/α side. The set B is defined as E(G') \\ E(G'[F]), where F is the set of vertices adjacent to at least one simplicial vertex. This definition excludes edges whose endpoints are both in F, but such an edge need not lie in any simplicial clique when the endpoints are adjacent to different simplicial vertices. The P4 path is a concrete counterexample: the edge bc is excluded from B, yet it is not covered by any simplicial clique, so a valid ECC of G must cover it with a non-simplicial clique. Claim 8 then asserts ecc(G) = aecc_B(G') + |S'|, which evaluates to 2 on P4 while the true value is 3. The reduction consequently reports a yes-instance for (P4, 0), which is actually a no-instance of ECC/α. Because Theorem 3 (polynomial cases k ∈ {0, 1}) and Theorem 4 (algorithms on sparse graph classes) are built directly on Lemma 5/Corollary 1, those results are not established as written. The main dichotomy between Theorems 1 and 2 appears sound and may survive a corrected reduction, but the submitted paper contains a false central lemma. I therefore recommend rejection, with the expectation that a revised version that corrects the definition of B could restore the affected results.","tokens_in":28117,"tokens_out":24875,"duration_ms":285563,"concrete_test":"Recompute the reduction of Lemma 5 on the 4-vertex path P4 with k = 0. If the reduction outputs 'yes' (as the printed B does), the lemma is false because ecc(P4) = 3 > α(P4) = 2. A second check: replace B by E(G') minus edges contained in some simplicial clique, re-run Claim 8 on P4, and verify the equality becomes 3 = 1 + 2.","verdict_should_be":"REJECT","load_bearing_attack":"Lemma 5 (Section 4.1) reduces ECC/α to Annotated ECC using B = E(G') \\ E(G'[F]), where G' = G − S and F are the vertices of G' adjacent to at least one simplicial vertex. This set is not, as Claim 8 asserts, the edges of G not contained in simplicial cliques. Counterexample: G = P4 (a-b-c-d). The simplicial vertices are a and d, so S' = {a, d}, G' is the single edge bc, F = {b, c}, and B = {bc} \\ {bc} = ∅. But edge bc is contained in no simplicial clique, since b and c are adjacent to different simplicial vertices (a and d). The true ecc(P4) is 3, while Claim 8 would give aecc_∅(G') + |S'| = 0 + 2 = 2. For k = 0, α(P4) = 2 and no 2-clique edge cover exists, so (P4, 0) is a no-instance of ECC/α; the reduction sets k' = 0, t = α(G' − F) = 0, and since 0 ≤ 0 + 0 it reports yes. The error propagates to Theorem 3 and to the ECC/α algorithms of Theorem 4, which all pipeline through Lemma 5 or Corollary 1. The intended assertion requires B = {xy ∈ E(G') : no simplicial vertex is adjacent to both x and y}; with the printed B the reduction is unsound.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies two natural above-guarantee parameterizations of edge clique cover and partition: ECC/α and ECP/α, where the goal is to use at most α(G)+k cliques. The main results are: Theorem 1 gives a 2^{O(k^{3/2} log k)} n^{O(1)} FPT algorithm for ECP/α; Theorem 2 shows ECC/α is NP-complete for every k≥2 even on perfect graphs; Theorem 3 claims polynomial-time algorithms for k=0,1; Theorem 4 claims FPT algorithms for ECC/α on graphs of bounded clique number, bounded degeneracy, and H-minor-free graphs, with subexponential running times; Proposition 5 gives ETH-based lower bounds. The proofs for ECP/α are detailed and appear technically sound, relying on a new way to compute α(G) using the FPT algorithm for ECP. The results for ECC/α, however, are obtained through a Turing reduction to Annotated ECC that contains a concrete error.","tokens_in":28423,"tokens_out":29670,"duration_ms":304388,"significance":"If correct, the dichotomy between ECP/α (FPT) and ECC/α (para-NP-complete for k≥2) would be a clean and interesting contribution, and the FPT algorithms for sparse graph classes would be useful. The paper is honest in its use of black-box algorithms and gives explicit running times. The proof of Theorem 1 and the reduction for Theorem 2 appear sound. Unfortunately, the reduction in Lemma 5, which is the engine behind Theorems 3 and 4, defines the edge set B incorrectly, and the counterexample in the report shows the reduction is unsound. As a result, several of the paper's central claims are not supported as written, although the error appears fixable.","major_comments":[{"comment":"The definition B = E(G') \\ E(G'[F]) in Lemma 5 is not the set of edges of G that are not contained in simplicial cliques, as Claim 8 asserts. For G = P4 on vertices a-b-c-d, the simplicial vertices are a and d, so S' = {a,d}, G' is the edge bc, F = {b,c}, and B = {bc} \\ {bc} = ∅. The edge bc is contained in no simplicial clique of G, so the claimed equality ecc(G) = aecc_B(G') + |S'| would give 3 = 0 + 2, which is false. Consequently, the reduction declares the no-instance (P4, 0) of ECC/α (since ecc(P4) = 3 > α(P4) + 0) to be a yes-instance: it sets k' = 0, computes t = α(G'-F) = 0, and reports yes because 0 ≤ 0 + 0. This error propagates to Theorem 3 (the k = 1 case) and to all four algorithms in Theorem 4, since those results are proved by pipelining Lemma 5 or Corollary 1. The intended definition should be B = {uv ∈ E(G') : no simplicial vertex s satisfies u,v ∈ N[s]}; with this definition the equality in Claim 8 and the correctness proof of the reduction can be repaired.","section":"Section 4.1, Lemma 5 (Claim 8)"},{"comment":"The proof of the 2-degenerate lower bound states that 'Independent Set does not admit subexponential algorithms for connected graphs of maximum degree three and, consequently, 2-degenerate graphs.' The 'consequently' is unjustified: connected graphs of maximum degree three are 3-degenerate, not 2-degenerate. The reduction that follows in the same paragraph assumes an NP-hardness base for Independent Set on 2-degenerate graphs, but no proof or reference for such hardness is given. As written, the claimed 2^{o(k)} lower bound for ECC/α on 2-degenerate graphs is unsupported. Separately, the transfer of the ECC lower bounds to ECC/α should be stated as an explicit parameter-preserving reduction (e.g., add a pendant neighbor to every vertex and keep the same parameter), since Observation 2, to which the proof refers, is an NP-completeness statement rather than an ETH-lower-bound transfer.","section":"Section 5.4, Proposition 5"}],"minor_comments":[{"comment":"The 'well-known' assertion that there is a maximum independent set containing the chosen simplicial vertices X (one from each simplicial clique) is used to compute α(G) in the FPT algorithm, but no proof or citation is given. The statement is true and can be shown by the standard exchange argument for simplicial vertices, applied sequentially to the pairwise non-adjacent vertices of X; the proof should be included.","section":"Section 3, Lemma 3"},{"comment":"As noted in the major comments, the parameter-preserving transfer of ETH lower bounds from ECC to ECC/α should be written out explicitly rather than deferred with 'similarly to Observation 2'.","section":"Section 5.4, Proposition 5"},{"comment":"There are several typos and inconsistent notations: 'cannon' for 'cannot' (Section 2), 'reposts' for 'reports' (Theorem 1 proof), 'wtith' for 'with' (Claim 5), 'of of' (Observation 3), 'simlicial' for 'simplicial' (Claim 3), 'de Brujin' for 'de Bruijn' (Proposition 1), 'prefect' for 'perfect' (Section 1.1), and the statement of Lemma 5 uses R' where the body uses B. These should be fixed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The error in Lemma 5 is localized and the corrected definition of B is apparent from the text's own explanatory sentence; I therefore view a major revision as appropriate rather than rejection. The authors should also double-check the status of Independent Set on 2-degenerate graphs. The ECP/α part of the paper appears sound and could be published independently if the ECC/α parts are repaired."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's ECP/α algorithm (Theorem 1) and the ECC/α NP-completeness for k ≥ 2 (Theorem 2) look like real contributions, but Lemma 5, which drives the polynomial cases (Theorem 3) and all the sparse-graph algorithms (Theorem 4), is wrong. The stress-test counterexample is correct: on P4, with B = E(G') \\ E(G'[F]), the reduction declares a no-instance to be a yes-instance for k = 0. The printed B is not the set of edges omitted by simplicial cliques; that set should be {xy ∈ E(G') : no simplicial vertex is adjacent to both x and y}. The proof of Claim 8 conflates 'adjacent to some simplicial vertex' with 'contained in a simplicial clique.' So Theorems 3 and 4 currently rest on an unsound reduction.\n\nWhat is good: the above-α parameterization is new and well motivated. Lemma 1 is clean and useful. The ECP/α algorithm is a creditable piece of work; it combines existing ECP machinery with a careful analysis of simplicial cliques. Theorem 2 appears to avoid Lemma 5 entirely, and its reduction from Annotated ECC seems sound.\n\nMinor concerns: Lemma 3 invokes a 'well-known' fact about maximum independent sets containing all chosen simplicial vertices; that deserves a proof or citation. The lower-bound section has an under-justified step about transferring hardness from cubic to 2-degenerate graphs, and the degeneracy bound for H-minor-free graphs seems to misquote Kostochka's bound. These are fixable and secondary.\n\nBottom line: the main ideas are worth publishing, but not in this form. The authors need to correct Lemma 5 and re-verify the derived theorems. I would send it to review, with the expectation of major revision. I would not cite the sparse-graph or polynomial-time results until the reduction is fixed.","headline":"New parameterization, useful framework, but the central reduction (Lemma 5) is wrong, invalidating the polynomial and sparse-graph results as stated.","tokens_in":28987,"tokens_out":4423,"would_cite":false,"duration_ms":41593,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q27","05C69","05C85","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a complexity dichotomy for edge clique partition and cover parameterized above the independence number: partition with α(G)+k cliques is fixed-parameter tractable, while cover with the same budget is NP-complete for every…","keywords":["edge clique cover","edge clique partition","above-guarantee parameterization","simplicial cliques","fixed-parameter tractable","para-NP-complete","perfect graphs","H-minor-free graphs"],"falsifier":"Run an exhaustive search over small graphs: list all simplicial cliques, choose one simplicial vertex per clique, and test whether some maximum independent set contains all chosen vertices; the first counterexample would invalidate Lemma 3 and with it Theorem 1. Separately, any algorithm deciding in $f(k)\\cdot n^{O(1)}$ time whether α(G)+2 cliques suffice to cover the edges of a perfect graph would refute Theorem 2.","tokens_in":2200,"feed_emoji":"⚖️","tokens_out":2527,"duration_ms":114241,"temperature":0.7,"pith_summary":"The paper studies two classical problems — covering or partitioning a graph's edges with cliques — under a new budget: at most α(G)+k cliques, where α(G) is the size of the largest independent set, a natural lower bound because one clique can hold at most one vertex of an independent set. The central finding is that the two problems diverge at this parameterization: Edge Clique Partition above α is fixed-parameter tractable in k, solvable in $2^{O(k^{3/2}\\log k)}\\cdot n^{O(1)}$ time, while Edge Clique Cover above α is NP-complete for every fixed k ≥ 2, even on perfect graphs where α(G) itself is easy to compute. The boundary is tight: for k = 0 and k = 1 the cover problem is polynomial-time solvable. On sparse graph classes the cover problem regains tractability, with FPT algorithms depending on clique number, degeneracy, and a subexponential $f(H)^{\\sqrt{k}}$ bound on H-minor-free graphs. If correct, this gives a complete complexity dichotomy for the above-α parameterization and shows that the regime real-world instances occupy — covers very close to α(G) — is algorithmically meaningful.","feed_headline":"Partition above α(G) is FPT; covering is NP-complete","feed_subtitle":"Covering edges within α(G)+k cliques is NP-complete for every k ≥ 2, while partitioning them stays FPT in k.","key_machinery":"The load-bearing mechanism is Lemma 1: any cover (or partition) using at most α(G)+k cliques can contain at most 2k non-simplicial cliques, and any maximum independent set can contain at most k non-simplicial vertices — so near-optimal solutions are almost entirely built from simplicial cliques, the closed neighborhoods of simplicial vertices. This observation turns the unknown quantity α(G) into a computational handle: Lemma 3 computes α(G) itself in $2^{O(k^{3/2}\\log k)}\\cdot n^{O(1)}$ time by counting simplicial cliques and invoking the de Bruijn–Erdős theorem (an edge clique partition of $K_n$ into smaller cliques needs at least $n$ cliques) to bound the residual graph. Lemma 4 then uses critical cliques — maximal true-twin cliques — to extract every large forced clique of a solution in polynomial time, and Lemma 5 factors ECC/α through Annotated ECC by deleting simplicial vertices, which is how k-coloring supplies the hardness.","core_discovery":"The paper's central claim is a dichotomy between the two above-α variants. ECP/α is FPT: a subexponential routine first computes α(G) or certifies a no-instance from the simplicial cliques alone, then polynomial-time preprocessing identifies every clique of size at least 6k+1 that any valid partition must contain, and after branching over which simplicial cliques are 'broken' the remaining problem reduces to standard Edge Clique Partition on a residual graph with $O(k^2)$ vertices, solvable by the best known ECP algorithm. ECC/α, by contrast, is para-NP-complete: for every k ≥ 2, deciding coverability with α(G)+k cliques is NP-complete, and the hardness survives on perfect graphs; the reduction routes through Annotated Edge Clique Cover, descending from the NP-completeness of k-coloring via co-bipartite graphs. The polynomial algorithms for k = 0 and k = 1 close the dichotomy in k, and the sparse-graph theorems show that on minor-free and low-degeneracy graph classes the hardness dissolves into fixed-parameter algorithms.","pith_inferences":["The contrast suggests that the partition requirement itself is what buys tractability above α: a partition is forced to mirror the simplicial skeleton of the graph, while a cover may hide arbitrary non-simplicial cliques — and that freedom carries the k-coloring hardness.","Because hardness survives on perfect graphs, where α(G) is polynomial-time computable, future algorithmic progress on ECC/α cannot come from computing α; it has to come from sparsity, as the degenerate and minor-free FPT results indicate.","A testable extension is to apply the same above-α lens to vertex clique cover and partition; the split may persist, with the vertex versions' different counting of independent sets in cliques changing which side stays tractable.","For practical instances near the α-boundary, the paper implies a certificate-friendly workflow: find a large independent set, then run the k-parameterized cover algorithms on the residual graph, since the small-parameter regime is exactly where real-world covers are reported to sit."],"forward_implications":["The k = 0 cases of both problems are polynomial: any cover of size α(G) must consist only of simplicial cliques, which can be listed and checked directly.","No faster algorithm for ECP/α can exist than for the underlying ECP, and any improved ECP algorithm immediately speeds up Theorem 1 — the two running-time problems are the same up to a $k^{O(k)}$ factor.","On graphs of degeneracy d ≥ 3, ECC/α is solvable in $2.081^{(d-1)k}\\cdot n^{O(1)}$ time, and on 2-degenerate graphs in $1.619^k\\cdot n^{O(1)}$ time; under the Exponential Time Hypothesis the $2^{o(k)}$ barrier for the latter cannot be broken.","On H-minor-free graphs, ECC/α runs in $f(H)^{\\sqrt{k}}\\cdot n^{O(1)}$ time without being told H, bundling planar and bounded-treewidth graphs into one subexponential regime.","The ECC/α dichotomy in k is complete: NP-complete for every k ≥ 2, polynomial for k ∈ {0, 1}."],"supporting_citations":[{"why":"Supplies the de Bruijn–Erdős fact that partitioning $K_n$ into smaller cliques needs at least $n$ cliques, which forces every large clique into any near-optimal partition in Lemma 4.","marker":"[14]"},{"why":"Provides the $2^{O(k^{3/2}\\log k)}$ FPT algorithm for standard Edge Clique Partition used as a black box on the residual graph in Lemma 3 and Theorem 1.","marker":"[18]"},{"why":"Introduces Annotated ECC and the covering-by-cliques hardness template on which the ECC/α reductions of Lemma 5 and Theorem 2 build.","marker":"[48]"},{"why":"Defines critical cliques and gives the linear-time algorithm that Lemma 4 uses to find all large cliques forced into any solution.","marker":"[41]"},{"why":"Supplies the polynomial-time listing of simplicial cliques used by Observation 3, Lemma 3, Lemma 4, and Lemma 5.","marker":"[37]"},{"why":"Source of the k-coloring and vertex-clique-cover NP-completeness that Lemma 7 reduces from.","marker":"[23]"},{"why":"Shows α(G) is polynomial-time computable on perfect graphs, so the Theorem 2 hardness on perfect graphs is not an artifact of computing α.","marker":"[28]"},{"why":"Provides the inclusion–exclusion set-cover algorithm that finishes Lemma 8's FPT algorithm for Annotated ECC with bounded clique number.","marker":"[5]"},{"why":"Documents real-world instances whose clique covers sit within a small margin of α(G), the motivating observation for the above-α parameterization.","marker":"[31]"}],"fun_headline_variants":["Partition above α is FPT, cover is NP-complete","Above-α cliques: partition FPT, cover NP-complete","Dichotomy: ECP/α FPT, ECC/α NP-complete for any k≥2","Covering edges with α+k cliques is NP-complete; partitioning is FPT","Sparse-edge insight: partition above α easy, cover hard"],"cache_read_input_tokens":31104,"weakest_assumption_plain":"Lemma 3 leans on an unproved 'well-known' fact: from each simplicial clique one can pick a simplicial vertex so that all chosen vertices lie together in some maximum independent set; if any graph violates this, the computed α(G) is wrong and the ECP/α algorithm collapses with it.","fun_headline_variants_meta":{"raw":{"variants":["Partition above α is FPT, cover is NP-complete","Above-α cliques: partition FPT, cover NP-complete","Dichotomy: ECP/α FPT, ECC/α NP-complete for any k≥2","Covering edges with α+k cliques is NP-complete; partitioning is FPT","Sparse-edge insight: partition above α easy, cover hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000904,"raw_usage":{"total_tokens":3982,"prompt_tokens":1133,"completion_tokens":2849,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":749,"completion_tokens_details":{"reasoning_tokens":2744}},"tokens_in":749,"tokens_out":2849,"duration_ms":22971,"temperature":1.0,"reasoning_tokens":2744,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:35:27.953598+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exhaustive search over small graphs: list all simplicial cliques, choose one simplicial vertex per clique, and test whether some maximum independent set contains all chosen vertices; the first counterexample would invalidate Lemma 3 and with it Theorem 1. Separately, any algorithm deciding in $f(k)\\cdot n^{O(1)}$ time whether α(G)+2 cliques suffice to cover the edges of a perfect graph would refute Theorem 2.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the de Bruijn–Erdős fact that partitioning $K_n$ into smaller cliques needs at least $n$ cliques, which forces every large clique into any near-optimal partition in Lemma 4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the $2^{O(k^{3/2}\\log k)}$ FPT algorithm for standard Edge Clique Partition used as a black box on the residual graph in Lemma 3 and Theorem 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces Annotated ECC and the covering-by-cliques hardness template on which the ECC/α reductions of Lemma 5 and Theorem 2 build."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines critical cliques and gives the linear-time algorithm that Lemma 4 uses to find all large cliques forced into any solution."},{"cited_title":"Kloks, D","cited_arxiv_id":null,"evidence_quote":"Supplies the polynomial-time listing of simplicial cliques used by Observation 3, Lemma 3, Lemma 4, and Lemma 5."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source of the k-coloring and vertex-clique-cover NP-completeness that Lemma 7 reduces from."},{"cited_title":"Gr ¨otschel, L","cited_arxiv_id":null,"evidence_quote":"Shows α(G) is polynomial-time computable on perfect graphs, so the Theorem 2 hardness on perfect graphs is not an artifact of computing α."},{"cited_title":"Bj ¨orklund, T","cited_arxiv_id":null,"evidence_quote":"Provides the inclusion–exclusion set-cover algorithm that finishes Lemma 8's FPT algorithm for Annotated ECC with bounded clique number."},{"cited_title":"Hevia, B","cited_arxiv_id":null,"evidence_quote":"Documents real-world instances whose clique covers sit within a small margin of α(G), the motivating observation for the above-α parameterization."}],"review_version":1}