{"id":"726c7adb-772d-4727-a61b-6fa39bdc8f07","arxiv_id":"1908.01223","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New branching algorithms solve Cograph Deletion in O*(2.303^k) time and Cograph Editing in O*(4.329^k) time, improving the previous best bounds of O*(2.562^k) and O*(4.612^k).","lead":"This paper gives faster algorithms for two problems where a graph is repaired by deleting or editing edges until no induced four-vertex path remains. The improved worst-case time bounds beat the previous best results and set the new reference numbers for these two problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Editing base-case classification in Section 3 item 3 is asserted, not proved; if it fails, Theorem 6's O*(4.329^k) algorithm has no guaranteed polynomial base case.","rationale":"The reader's weakest_assumption focuses on the transfer of Jamison-Olariu observations into Theorem 4 for Cograph Deletion. That is a real gap: the proof paraphrases and refers to [3] rather than deriving the needed properties in the non-P4-sparse setting. However, I see an even more explicit and more directly load-bearing gap in the editing section: Section 3, item 3, simply asserts the structural dichotomy for irreducible editing instances, with no proof at all. This dichotomy is essential because the editing algorithm's running-time analysis assumes that every leaf of the search tree can be solved in polynomial time. If the dichotomy is false, Theorem 6 does not follow, regardless of the branching factor computations. The concern is not that the result is known to be wrong; it is that a central correctness condition for one of the two headline results is unsupported. The concrete test I propose would at least expose a counterexample on small graphs, and the analytical check on the deletion Case-4 graphs would test the most likely source of a counterexample. Since the reader already gave a CONDITIONAL verdict and flagged the editing base case in passing, my read does not move the verdict; it sharpens the condition.","tokens_in":6467,"tokens_out":22841,"duration_ms":233184,"concrete_test":"Enumerate all connected, co-connected graphs on 7 and 8 vertices (unlabeled; nauty/trace or networkx) and check whether any avoids the editing versions of Rules B1-B4 while not being a spider and having more than 5 vertices. Since the editing B1/B3 fire on Figures 2 and 3, the check is mechanical: for each graph and each induced P4 A, test all listed conditions. A counterexample refutes Section 3 item 3; absence is support, and the proof still needs to be supplied for all n. Analytically, first verify that every bipartite Case-4 graph of Theorem 4 with at least 6 vertices triggers the strengthened B1, since that is the only deletion-base case that the editing variant must eliminate.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The editing algorithm inherits the branch rules from Section 2, but its only base-case statement is the bullet in Section 3: 'If G is a graph in which Rules (B1)-(B4) cannot be applied, either G contains at most 5 vertices, G is not connected, G is not connected, or G is a spider. Therefore, the minimum size of an editing set of G can be computed in polynomial time using the algorithm for P4-sparse graphs of Liu et al.' No proof of this dichotomy is given. It is not a formal corollary of Theorem 4, because the editing variant strengthens B1 and B3 (they now fire also on the Figure 2 and Figure 3 graphs) and removes the bipartite Case 4 that appears in the deletion analogue. The correctness and polynomial-time solvability of the base case is load-bearing: every execution of the editing algorithm terminates at such a graph, and the stated O*(4.329^k) bound assumes these graphs are solved in polynomial time. If a connected, co-connected, irreducible graph with at least 6 vertices that is not a spider exists, Theorem 6 has no valid base case. The reader's transfer concern about Theorem 4 is related, but this is more direct: one of the paper's two central theorems rests on an unproven structural claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents improved fixed-parameter algorithms for Cograph Deletion and Cograph Editing. The deletion algorithm branches on small induced subgraphs related to the structural analysis of P4-sparse graphs by Jamison and Olariu, and claims a worst-case running time of O*(2.303^k). The editing algorithm adapts the same rules and claims O*(4.329^k). Both algorithms rely on a polynomial-time base case for irreducible instances, with the editing base case asserted in Section 3. The improvements over the previous bounds of O*(2.562^k) and O*(4.612^k) are obtained through new branching rules (B1)-(B4) and an automated enumeration of branching vectors.","tokens_in":6650,"tokens_out":2522,"duration_ms":26050,"significance":"If the claims are correct, the paper gives the fastest known FPT algorithms for two well-studied graph modification problems, with a concrete improvement over previously published bounds. The paper is transparent about its use of exhaustive enumeration for the constants, which is a strength in principle, but the enumeration script is not included and the constants are not independently verifiable from the text. The structural base-case theorems are the central load-bearing contribution: Theorem 4 for deletion and the unproved editing analogue in Section 3. The intended audience will find the algorithmic idea appealing, but the manuscript currently does not supply enough proof to certify the stated running times.","major_comments":[{"comment":"The proof transfers structural observations from the P4-sparse decomposition theorem of Jamison and Olariu to the larger class of graphs in which Rules (B1)-(B4) cannot be applied. The two sentences 'Since Rule (B4) cannot be applied, the observations mentioned above remain true' and 'These properties are also true here, since the proof of these properties does not rely on the emptiness of Pother(A)' are assertions that need justification. In particular, the proof of Theorem 2 in [3] may use the P4-sparse assumption globally, and the paper does not isolate which arguments remain valid under the weaker rule-inapplicability condition. Without a self-contained proof or a precise lemma-by-lemma transfer, Theorem 4 is not established, and the polynomial base case for the deletion algorithm is not guaranteed.","section":"Section 2, proof of Theorem 4"},{"comment":"The editing base case is asserted without proof: 'If G is a graph in which Rules (B1)-(B4) cannot be applied, either G contains at most 5 vertices, G is not connected, G is not connected, or G is a spider.' This is not a corollary of Theorem 4, because the editing variant strengthens Rules (B1) and (B3) and drops Case 4 of the deletion theorem. A graph that is connected, co-connected, irreducible, and not a spider would break the base case of the O*(4.329^k) editing algorithm. The paper must prove this dichotomy or provide a counterexample.","section":"Section 3, item 3"},{"comment":"The claimed branching numbers, including the critical 2.303 for Rule (B1) and 4.329 for Rule (B4) in the editing variant, are obtained from an unspecified Python script. The script is not included, its output is not supplied, and no verification method is described. Because these constants are exactly what the running-time claims depend on, the manuscript should either include the script as supplementary material, provide a machine-checkable certificate of the worst-case branching vectors, or state the enumeration in full detail in the paper.","section":"Section 2, paragraph 'To bound the branching number of Rule (B1)'"},{"comment":"In the case I(A)=empty, the proof states that 'since Rule (B1) cannot be applied, without loss of generality N(p) = {a,c} for every p in P(A) and P(A) is an independent set.' This step hides a substantial case analysis: Rule (B1) involves pairs (p,p') and a condition on whether G[A union {p,p'}] is isomorphic to one of the graphs in Figure 2. It is not immediate that this forces a single possible neighborhood shape for all vertices in P(A). The argument should be made explicit, or the claimed enumeration should be presented.","section":"Section 2, proof of Theorem 4, case I(A)=empty"}],"minor_comments":[{"comment":"Items 1 and 2 in both theorems both say 'G is not connected'; the second item should presumably say 'G is not connected' (the complement is disconnected).","section":"Theorem 2 and Theorem 4"},{"comment":"Two graphs in Figure 1 are both labeled P5; likely one is meant to be the complement of P5 (co-P5). This is confusing and should be corrected.","section":"Figure 1"},{"comment":"There are typographical inconsistencies in the problem names, e.g., 'Cogaph Deletion' and 'Cogaph Editing' in the Introduction and Abstract, which should be fixed to 'Cograph'.","section":"Throughout"},{"comment":"The phrase 'not isomorphic to either of the graphs in in Figure 2' has a duplicated 'in' and should be corrected.","section":"Section 2, Rule (B1)"},{"comment":"The sentence 'the minimum size of an editing set of G can be computed in polynomial time using the algorithm for P4-sparse graphs of Liu et al.' cites [4] without specifying whether that algorithm handles graphs that are not P4-sparse; if the base-case graphs are not P4-sparse, the citation is insufficient.","section":"Section 3, item 3"},{"comment":"The statement 'The worst case of Rule (B0) is when X induces a pan' and the following branching vector are useful context, but the notation 'e1,...,e5' is not defined precisely; it should refer to an explicit labeling of the edges in Figure 1(b).","section":"Section 2, paragraph after Lemma 3"}],"recommendation":"major_revision","confidential_remarks":"The paper's central claims are plausible but rest on two separable pillars: the correctness of the branching-vector enumeration and the correctness of the structural base-case theorems. The enumeration can be made verifiable by shipping the script or results; the structural transfer from [3] needs a real proof, not a reference to 'the proof of Theorem 2'. The editing base case is the weakest point because it is simply asserted. If the author can supply a rigorous proof of the editing dichotomy and a complete or certifiable enumeration, the paper would be a strong contribution. As it stands, the published version would not allow a reader to verify the stated running times."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a close read. The paper improves the best known FPT bounds for Cograph Deletion and Cograph Editing, from 2.562^k to 2.303^k and from 4.612^k to 4.329^k. The core idea is real: instead of branching on the seven forbidden subgraphs of P4-sparse graphs, the algorithm branches on the 6-to-8-vertex configurations that appear inside the Jamison-Olariu decomposition proof, and uses a new device F*(H) -- the induced subgraph of H with the best branching number -- to pick the cheapest safe branch. That is a genuine twist on the Nastos-Gao algorithm and it explains why the constants drop.\n\nThe deletion half (Theorem 4) is mostly convincing. The proof is sketchy where it transfers Observations 2.3-2.15 from [3], but the argument is at least present, and the base cases (including the bipartite Case 4 with alpha=1) are stated precisely. If I had to bet, the deletion algorithm is correct.\n\nThe editing half (Section 3) is where the paper gets fragile. Item 3 of the editing algorithm is a single bullet: if Rules (B1)-(B4) cannot be applied, either the graph has at most 5 vertices, is disconnected, has disconnected complement, or is a spider. That is asserted, not proved. And it is not a corollary of Theorem 4, because the editing variant strengthens Rules (B1) and (B3) and drops the bipartite Case 4. If a connected, co-connected, irreducible graph with at least 6 vertices that is not a spider exists, Theorem 6 has no polynomial base case and the stated bound collapses. The stress-test note is right to put its finger here.\n\nThe other soft spot is reproducibility. The constants 2.303 and 4.329 come from a Python script that is not included, and the branching numbers for Rules (B2)-(B4) are quoted without tables. I have no reason to think they are wrong, but I cannot check them from the text. The paper should ship the script or its output.\n\nOverall, this is a solid improvement by an author who knows the area, with one honest gap in the editing proof. It deserves a serious referee, but the referee should ask for the enumeration data and a proper proof of the editing base-case dichotomy before accepting.\n\nWho is this for: parameterized complexity people working on graph modification and branching algorithms. They will want to verify the constants and the base case. I would bring it up in a reading group to discuss the F* trick, but not as a canonical paper.","headline":"Genuine constant-factor improvements for two FPT problems, with a load-bearing unproven base case in the editing algorithm and unshipped enumeration code.","tokens_in":7292,"tokens_out":2965,"would_cite":true,"duration_ms":27330,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","05C85","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Cograph deletion and cograph editing admit parameterized algorithms with running times $O^*(2.303^k)$ and $O^*(4.329^k)$, the best known for both.","keywords":["cograph deletion","cograph editing","fixed-parameter tractability","branching algorithms","P4-sparse graphs","spider graphs","edge modification","parameterized complexity"],"falsifier":"Search all graphs on 7--9 vertices for one whose graph and complement are connected, which is not a spider and not the special bipartite graph of Theorem 4, and on which none of the rules (B1)--(B4) fires; such a graph would be a counterexample to Theorem 4 and to the stated running time. A weaker check is to re-enumerate rule (B1) for every possible adjacency pattern of $A\\cup\\{p,p'\\}$ and look for a branching vector worse than $(1,2,2,2)$; even one such pattern would break the $O^*(2.303^k)$ bound.","tokens_in":6203,"feed_emoji":"🧩","tokens_out":11602,"duration_ms":106619,"temperature":0.7,"pith_summary":"The paper gives faster fixed-parameter algorithms for two edge-modification problems: making a graph into a cograph (no induced path on four vertices) by deleting at most $k$ edges, or by deleting and adding at most $k$ edges. It claims running times $O^*(2.303^k)$ for Cograph Deletion and $O^*(4.329^k)$ for Cograph Editing, improving the previous $O^*(2.562^k)$ and $O^*(4.612^k)$ bounds. The improvement comes from a new branching strategy: instead of branching on the forbidden induced subgraphs that characterize $P_4$-sparse graphs (every five vertices induce at most one $P_4$), the algorithm branches on the larger six- to eight-vertex configurations that appear in the proof of the structural decomposition of those graphs. A graph on which the new rules cannot fire is shown to fall into one of a few simple classes, so the base case is polynomial. If the claims are right, these are the fastest known parameterized algorithms for both problems.","feed_headline":"Cograph deletion solved in O*(2.303^k) time","feed_subtitle":"New branching rules beat earlier O*(2.562^k) and O*(4.612^k) bounds for both problems.","key_machinery":"The machinery is a family of branching rules centred on a chosen induced path $A$ on four vertices. The remaining vertices are split into $I(A)$ (no neighbours in $A$), $T(A)$ (all four neighbours), and $P(A)$ (one to three neighbours), with $P_{\\mathrm{other}}(A)$ consisting of the vertices of $P(A)$ that are not adjacent to the two internal vertices of the path. Rules (B1)--(B3) branch on pairs consisting of a vertex from $P_{\\mathrm{other}}(A)$ and one from $P(A)$, $T(A)$, or $I(A)$; rule (B4) branches on the three- and four-vertex patterns that the structural decomposition of $P_4$-sparse graphs forbids. For each small induced subgraph, the algorithm tries every inclusion-minimal deletion or editing set and recurses, and the worst-case branching vector of rule (B1), $(1,2,2,2)$, gives the exponential base $2.303$; the corresponding vectors for the other rules are no worse. The branching number of a rule is the largest root of the polynomial governing the recursion, and it determines the constant in the exponential running time. The rules are designed so that when none applies, the structural facts needed for the polynomial base case still hold.","core_discovery":"The central claim is that the hard part of both problems can be pushed into a small set of branching rules, after which every remaining instance is easy. For Cograph Deletion, the paper proves (Theorem 4) that a graph with at least seven vertices on which rules (B1)--(B4) cannot be applied is disconnected, has a disconnected complement, is a spider (a standard split into an independent set and a clique of equal size), or is a specific bipartite graph with one part of size two; in each case the minimum deletion set can be computed in polynomial time. Combined with the fact that every branch removes at least one edge and the worst branching rule has branching number at most $2.303$, this gives the claimed deletion algorithm (Theorem 5). For Cograph Editing, the same rule set, adapted to editing sets and run until no rule fires, leaves only small graphs, disconnected graphs, complement-disconnected graphs, or spiders, and the worst branching number is at most $4.329$ (Theorem 6).","pith_inferences":["The same design principle---branch on the configurations appearing inside a structural proof rather than on the class's own forbidden induced subgraphs---could be tried for other hereditary graph classes with similar decomposition theorems, such as $P_4$-tidy graphs or distance-hereditary graphs, and might yield faster edge-modification algorithms there.","Because the exact constants depend on an enumeration script described in the paper, an independent reimplementation of that enumeration would settle the numerical claims without needing new theoretical ideas.","The ratio between the deletion and editing bounds (about $2.303$ vs $4.329$) suggests that symmetric branch rules for additions roughly double the search cost; designing editing-specific rules that avoid this doubling is a natural target for further improvement."],"forward_implications":["Cograph Deletion is solvable in $O^*(2.303^k)$ time, beating the previous $O^*(2.562^k)$ algorithm.","Cograph Editing is solvable in $O^*(4.329^k)$ time, beating the previous $O^*(4.612^k)$ algorithm.","Any instance left after the branching rules is either small, disconnected, complement-disconnected, a spider, or a special bipartite graph with one part of size two, which makes the polynomial base case genuinely simple.","The branching analysis is automated: the worst-case vectors for rules (B1)--(B4) were obtained by enumerating all adjacency patterns for the involved vertices, so the constants are tied to a finite, checkable case analysis."],"supporting_citations":[{"why":"Supplies the structural decomposition theorem for $P_4$-sparse graphs and the observations about $I(A)$, $T(A)$, and $P(A)$ that rules (B1)--(B4) replace or transfer.","marker":"[3]"},{"why":"Provides the previous cograph editing algorithm and the polynomial algorithm for computing minimum editing sets on $P_4$-sparse graphs used in the editing base case.","marker":"[4]"},{"why":"Provides the previous cograph deletion algorithm and its branching rule on forbidden induced subgraphs, which the new rules improve.","marker":"[5]"}],"fun_headline_variants":["Cograph deletion in O*(2.303^k), editing in O*(4.329^k)","Faster cograph edge modification: new branching rules","Cograph edge problems: deletion and editing speedups","New records: cograph deletion and editing times","Cograph editing drops to O*(4.329^k) time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that when none of the four branching rules applies, the structural facts originally proved for $P_4$-sparse graphs still hold for the graph at hand, so Theorem 4's polynomial base case covers every irreducible instance; the exact constants additionally depend on the paper's enumeration script being correct.","fun_headline_variants_meta":{"raw":{"variants":["Cograph deletion in O*(2.303^k), editing in O*(4.329^k)","Faster cograph edge modification: new branching rules","Cograph edge problems: deletion and editing speedups","New records: cograph deletion and editing times","Cograph editing drops to O*(4.329^k) time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002,"raw_usage":{"total_tokens":7753,"prompt_tokens":843,"completion_tokens":6910,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":459,"completion_tokens_details":{"reasoning_tokens":6823}},"tokens_in":459,"tokens_out":6910,"duration_ms":49546,"temperature":1.0,"reasoning_tokens":6823,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:20:59.279464+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search all graphs on 7--9 vertices for one whose graph and complement are connected, which is not a spider and not the special bipartite graph of Theorem 4, and on which none of the rules (B1)--(B4) fires; such a graph would be a counterexample to Theorem 4 and to the stated running time. A weaker check is to re-enumerate rule (B1) for every possible adjacency pattern of $A\\cup\\{p,p'\\}$ and look for a branching vector worse than $(1,2,2,2)$; even one such pattern would break the $O^*(2.303^k)$ bound.","supporting_citations":[{"cited_title":"Jamison and S","cited_arxiv_id":null,"evidence_quote":"Supplies the structural decomposition theorem for $P_4$-sparse graphs and the observations about $I(A)$, $T(A)$, and $P(A)$ that rules (B1)--(B4) replace or transfer."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the previous cograph editing algorithm and the polynomial algorithm for computing minimum editing sets on $P_4$-sparse graphs used in the editing base case."},{"cited_title":"Nastos and Y","cited_arxiv_id":null,"evidence_quote":"Provides the previous cograph deletion algorithm and its branching rule on forbidden induced subgraphs, which the new rules improve."}],"review_version":1}