Pith. sign in

REVIEW 4 major objections 6 minor 5 references

Faster algorithms for cograph edge modification problems

T0 review · 4 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict Genuine constant-factor improvements for two FPT problems, with a load-bearing unproven base case in the editing algorithm and unshipped enumeration code. read the letter →

arxiv 1908.01223 v3 pith:GG6VPX2U submitted 2019-08-03 cs.DS cs.DMmath.CO

Dekel Tsur This is my paper · ORCID
classification cs.DScs.DMmath.CO MSC 68Q2505C8568R10
keywords cographdeletioneditingfixed-parametertractabilitybranchingalgorithmsP4-sparsegraphsspideredgemodificationparameterizedcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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).

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

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.

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 (4)
  1. [Section 2, proof of Theorem 4] 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.
  2. [Section 3, item 3] 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.
  3. [Section 2, paragraph 'To bound the branching number of Rule (B1)'] 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.
  4. [Section 2, proof of Theorem 4, case I(A)=empty] 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.
minor comments (6)
  1. [Theorem 2 and Theorem 4] 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).
  2. [Figure 1] 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.
  3. [Throughout] 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'.
  4. [Section 2, Rule (B1)] The phrase 'not isomorphic to either of the graphs in in Figure 2' has a duplicated 'in' and should be corrected.
  5. [Section 3, item 3] 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.
  6. [Section 2, paragraph after Lemma 3] 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).

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation identified; the running-time bounds come from explicit case analysis and external structural theorems.

full rationale

No load-bearing circular step was found. The claimed O*(2.303^k) and O*(4.329^k) bounds are derived from explicit branching rules (B1)-(B4); safety of each rule follows from the definition of F*, namely the sets of inclusion-minimal solution sets for the relevant induced subgraph, and the worst-case branching numbers are computed by exhaustive enumeration over finitely many induced subgraphs via a Python script, not by fitting the stated running times. The polynomial-time base case for Cograph Deletion (Theorem 4) is argued by transferring the structural observations of Jamison and Olariu [3] to graphs where Rules (B1)-(B4) are inapplicable; [3] is an external published decomposition theorem, and the transfer is a proof obligation rather than a definitional equivalence. There is no self-citation chain: the foundational references [1]-[5] are all by other authors. The editing base-case assertion in Section 3 item 3 is stated without a proof and may be a correctness gap, and the exact constants depend on an unshipped enumeration script, but neither is circular in the sense of a prediction being equal to its input by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

Everything the central claim rests on is either standard cograph and P4-sparse theory imported from [3]-[5] or the paper's own finite case analysis. No numbers are fitted to data: the constants 2.303, 4.329, 2.21, and 4.313 are presented as outputs of exhaustive finite-case enumeration and as roots of the associated branching-vector polynomials. No new entities are postulated; F*(H) is a new combinatorial device (choose the induced subgraph with minimum branching number) but not an entity requiring independent evidence. The two genuinely fragile inputs are the transfer of the Jamison-Olariu observations to the weaker B1-B4 regime and the correctness of the unshipped enumeration script that yields the headline constants.

assumptions (4)
  • domain assumption Cographs are exactly the graphs with no induced P4, and P4-sparse graphs are characterized by the seven forbidden induced subgraphs in Figure 1 (Jamison-Olariu [3]).
    This characterization drives the choice of branching subgraphs. Imported from [3] without reproof; it is standard background in this literature.
  • domain assumption Connected and co-connected P4-sparse graphs decompose as spiders, with the minimum deletion size computable by the recursion in Lemma 3.
    The polynomial base case of the algorithm for irreducible instances, and the spider handling in Theorem 4, rely on this decomposition from [3] and on Lemma 3, whose proof is referenced to [3] and [5].
  • domain assumption The structural observations 2.3, 2.4, 2.6, 2.7, 2.14, and 2.15 of Jamison-Olariu [3] remain valid when Rules (B1)-(B4) are inapplicable, without full P4-sparseness.
    This is the load-bearing transfer step in the proof of Theorem 4 (Section 2: 'Since Rule (B4) cannot be applied, the observations mentioned above remain true'); it is argued by paraphrasing the [3] proof, not by a full derivation.
  • standard math Branching on the family F*(H) of inclusion-minimal deletion or editing sets of a small induced subgraph containing a P4 preserves at least one optimal solution.
    Used as the safety argument for every rule; stated in the proof of Theorem 5 as 'the safeness of the rules (which follows from the definition of F*(H))'. This is a standard exchange argument for hereditary properties, though it is not written out.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster algorithms for cograph edge modification problems." pith.science (2026). https://pith.science/paper/GG6VPX2U

@misc{pith2026190801223,
  author       = {Pith},
  title        = {Pith review of: Faster algorithms for cograph edge modification problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GG6VPX2U}},
  note         = {Machine review of arXiv:1908.01223}
}
abstract

In the Cograph Deletion (resp., Cograph Editing) problem the input is a graph $G$ and an integer $k$, and the goal is to decide whether there is a set of edges of size at most $k$ whose removal from $G$ (resp., removal and addition to $G$) results in a graph that does not contain an induced path with four vertices. In this paper we give algorithms for Cograph Deletion and Cograph Editing whose running times are $O^*(2.303^k)$ and $O^*(4.329^k)$, respectively.

Figures

Figures reproduced from arXiv: 1908.01223 by the authors.

Figure 1
Figure 1. Forbidden induced subgraphs for P4-sparse graphs. Definition 1. A graph G is a spider if the vertices of G can be partitioned into disjoint sets S, K, and R such that 1. |S| = |K| ≥ 2. 2. S is an independent set and K is a clique. 3. Every vertex in R is adjacent to all the vertices in K and not adjacent to all the vertices in S. 4. There is a bijection ϕ: S → K such that one of the following two cases occurs. (a) N… view at source ↗
Figure 2
Figure 2. For every F ∈ F∗ (G[A ∪ {p, p0}]), recurse on the instance (G − F, k − |F|). To bound the branching number of Rule (B1), we used a Python script. The script enumerates all possible cases for the graph G[A ∪ {p, p0}]. Denote by a, b, c, d the path induced by A. For the vertex p, the script enumerates all possible cases for N(p) ∩ A. After removing symmetric cases, there are 7 possible cases for N(p) ∩ A: {a}, {b}, {a… view at source ↗
Figure 2
Figure 2. Unallowed induced subgraphs for Rule (B1). [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figures from the paper (1 more)
Figure 3
Figure 3. Figure 3: 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 …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages

  1. [3]

    Jamison and S

    B. Jamison and S. Olariu. A tree representation for p4-sparse graphs. Discrete Applied Mathematics, 35(2):115–129, 1992

    work page 1992

  2. [1]

    L. Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58(4):171–176, 1996

    work page 1996

  3. [2]

    Cygan, F

    M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized algorithms. Springer, 2015

    work page 2015

  4. [4]

    Y. Liu, J. Wang, J. Guo, and J. Chen. Complexity and parameterized algorithms for cograph editing. Theoretical Computer Science, 461:45–54, 2012

    work page 2012

  5. [5]

    Nastos and Y

    J. Nastos and Y. Gao. Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes. Discrete Mathematics, Algorithms and Applications , 4(01), 2012. 7

    work page 2012

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.