On the complexity of edge subdivision to H-free graphs
Pith reviewed 2026-05-08 01:54 UTC · model grok-4.3
The pith
H-free Subdivision by edge subdivisions is polynomial-time solvable when H consists of subdivided stars and at most one bistar.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The H-free Subdivision problem asks whether a graph G can be made free of induced H by performing at most k edge subdivisions. The problem is solvable in polynomial time whenever every component of H is a subdivided star or a subdivided bistar and at most one component is a bistar. In all other cases covered by the seven listed conditions on H, the problem is NP-complete and, under the Exponential Time Hypothesis, admits no 2^{o(k)} n^{O(1)}-time algorithm. The paper supplies a bounded search-tree algorithm that always runs in 2^{O(k)} n^{O(1)} time and is therefore essentially optimal for every hardness case.
What carries the argument
The structural classification of the forbidden graph H into tractable cases (subdivided stars and at most one bistar) versus the seven hardness-triggering conditions on minimum degree, neighborhoods, triangles, girth, and branch-vertex distances.
If this is right
- When H has only subdivided-star components or at most one subdivided-bistar component, an efficient algorithm exists to decide if k subdivisions suffice.
- For every H meeting any of the seven conditions the decision problem is NP-complete.
- Under the Exponential Time Hypothesis no algorithm faster than 2^{o(k)} n^{O(1)} exists for any of the hardness cases.
- The bounded search-tree procedure gives a uniform 2^{O(k)} n^{O(1)}-time algorithm for all inputs.
- The hardness conditions cover trees, graphs containing triangles, and graphs of girth at least four.
Where Pith is reading between the lines
- The same structural lens on H may separate tractable from intractable instances for other modification operations such as vertex deletion or edge deletion to avoid induced H.
- The key role played by distances between high-degree vertices and by local triangle configurations suggests that further boundary cases between stars and bistars could be tested for membership in the polynomial class.
- The single-exponential upper bound implies that any future improvement for the general problem would automatically improve the hard cases as well.
- These results indicate that approximation or kernelization questions for the NP-hard variants may be worth studying separately.
Load-bearing premise
The seven listed structural conditions on H exactly mark the boundary between polynomial-time solvability and NP-hardness with no exceptions or hidden cases.
What would settle it
An explicit graph H that satisfies one of the seven hardness conditions yet admits a polynomial-time algorithm for H-free Subdivision, or conversely an H outside the allowed star-bistar form that is still polynomial-time solvable, would disprove the classification.
read the original abstract
Subdividing an edge $uv$ in a graph replaces it by a path $u w v$ with one new vertex. For a graph $H$, the \textsc{$H$-free Subdivision} problem asks whether, given a graph $G$ and an integer $k$, one can destroy all induced copies of $H$ in $G$ by at most $k$ edge subdivisions. We show that the problem is polynomial-time solvable when every component of $H$ is a subdivided star or a subdivided bistar, and at most one component is a subdivided bistar. On the other hand, we prove that \textsc{$H$-free Subdivision} is NP-complete and, assuming the Exponential Time Hypothesis, admits no $2^{o(k)} n^{O(1)}$-time algorithm whenever $H$ satisfies any of the following conditions: \begin{itemize} \item $H$ has minimum degree at least $2$, and the neighborhood of every degree-$2$ vertex induces a $K_2$; \item the vertices of degree at least $3$ in $H$ induce a graph with at least two edges; \item $H$ has a triangle with two vertices of degree at least $3$; \item $H$ contains, as an induced subgraph, the graph obtained from two vertex-disjoint triangles by adding one edge between them; \item $H$ contains exactly one triangle; \item $H$ has girth at least $4$; \item $H$ is a tree with exactly two vertices of degree at least $3$ at distance $2$ or at least $4$. \end{itemize} A simple bounded search-tree algorithm for the problem runs in $2^{O(k)} n^{O(1)}$ time. Thus, for all hardness cases above, this running time is essentially optimal under ETH.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the H-free Subdivision problem: given G and k, can at most k edge subdivisions eliminate all induced copies of a fixed graph H? It claims that the problem is polynomial-time solvable when every component of H is a subdivided star or subdivided bistar (with at most one bistar component). It also claims NP-completeness and no 2^{o(k)} n^{O(1)} algorithm under ETH whenever H satisfies any of seven structural conditions, including that H is a tree with exactly two vertices of degree at least 3 at distance 2 or at least 4. A simple 2^{O(k)} n^{O(1)} search-tree algorithm is given, shown to be tight for the hard cases.
Significance. If the stated dichotomy is correct, the results give a useful partial complexity classification for H-free Subdivision, identifying broad polynomial cases and matching ETH-tight hardness for several natural families of H. The explicit algorithmic and reduction-based approach, together with the bounded-search-tree upper bound, strengthens the contribution.
major comments (1)
- [Abstract] Abstract (and the corresponding theorem statements): the polynomial-time case includes any subdivided bistar in which the central edge has been subdivided once. Such an H is a tree whose two degree-≥3 vertices lie at distance exactly 2. This H simultaneously satisfies the seventh hardness condition (H is a tree with exactly two vertices of degree at least 3 at distance 2 or at least 4). The two claims are therefore contradictory for this H: the problem cannot be both in P and NP-complete. The load-bearing assumption that the polynomial structural class and the seven hardness conditions are disjoint must be verified or repaired by precise definitions of “subdivided bistar” and the distance-2 case.
Simulated Author's Rebuttal
We thank the referee for their careful reading of the manuscript and for identifying this inconsistency between the polynomial-time cases and the hardness conditions. We address the comment below.
read point-by-point responses
-
Referee: [Abstract] Abstract (and the corresponding theorem statements): the polynomial-time case includes any subdivided bistar in which the central edge has been subdivided once. Such an H is a tree whose two degree-≥3 vertices lie at distance exactly 2. This H simultaneously satisfies the seventh hardness condition (H is a tree with exactly two vertices of degree at least 3 at distance 2 or at least 4). The two claims are therefore contradictory for this H: the problem cannot be both in P and NP-complete. The load-bearing assumption that the polynomial structural class and the seven hardness conditions are disjoint must be verified or repaired by precise definitions of “subdivided bistar” and the distance-2 case.
Authors: We agree that the current formulation creates an overlap: a subdivided bistar with its central edge subdivided once yields a tree in which the two vertices of degree at least 3 are at distance exactly 2, which falls under both the polynomial-time structural class (every component is a subdivided star or subdivided bistar, with at most one bistar) and the seventh hardness condition. This renders the claims contradictory. To repair the manuscript we will (i) supply formal definitions of “subdivided star” and “subdivided bistar” that make the allowed subdivision patterns explicit, (ii) revise the seventh hardness condition so that it applies only to trees that are not subdivided bistars (equivalently, we will restrict the distance-2 case to trees whose two high-degree vertices are not joined by a single subdivided edge with pending leaves), and (iii) update the abstract, the statement of the main theorems, and the surrounding discussion to guarantee that the polynomial class and the seven hardness conditions are disjoint. These changes will be incorporated in the revised version. revision: yes
Circularity Check
No circularity; explicit algorithms and reductions separate cases
full rationale
The paper derives its polynomial-time cases from an explicit algorithm for subdivided stars and bistars (with the stated restriction on bistar components) and its hardness cases from direct NP-completeness reductions plus ETH lower bounds for each of the seven listed structural conditions on H. These steps rely on case analysis, gadget constructions, and bounded search trees rather than any self-definition, fitted parameter renamed as prediction, or load-bearing self-citation. The derivation chain is therefore self-contained against external benchmarks and does not reduce to its own inputs by construction.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Exponential Time Hypothesis (ETH)
- standard math Standard definitions of induced subgraphs, edge subdivision, and graph components
Reference graph
Works this paper leans on
-
[1]
Switching classes: Characterization and computation
Dhanyamol Antony, Yixin Cao, Sagartanu Pal, and RB Sandeep. Switching classes: Characterization and computation. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) , pages 11--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2024
work page 2024
-
[2]
On subgraph complementation to h-free graphs
Dhanyamol Antony, Jay Garchar, Sagartanu Pal, RB Sandeep, Sagnik Sen, and R Subashini. On subgraph complementation to h-free graphs. Algorithmica , 84(10):2842--2870, 2022
work page 2022
-
[3]
N. R. Aravind, R. B. Sandeep, and Naveen Sivadasan. Dichotomy results on the hardness of h-free edge modification problems. SIAM J. Discret. Math. , 31(1):542--561, 2017. https://doi.org/10.1137/16M1055797 doi:10.1137/16M1055797
-
[4]
Contracting edges to destroy a pattern: A complexity study
Dipayan Chakraborty and RB Sandeep. Contracting edges to destroy a pattern: A complexity study. In International Symposium on Fundamentals of Computation Theory , pages 118--131. Springer, 2023
work page 2023
-
[5]
Parameterized algorithms , volume 5
Marek Cygan, Fedor V Fomin, ukasz Kowalik, Daniel Lokshtanov, D \'a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh. Parameterized algorithms , volume 5. Springer, 2015
work page 2015
-
[6]
On the complexity of establishing hereditary graph properties via vertex splitting
Alexander Firbas and Manuel Sorge. On the complexity of establishing hereditary graph properties via vertex splitting. In 35th International Symposium on Algorithms and Computation, ISAAC 2024 . Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2024
work page 2024
-
[7]
Tight running time lower bounds for vertex deletion problems
Christian Komusiewicz. Tight running time lower bounds for vertex deletion problems. ACM Transactions on Computation Theory (TOCT) , 10(2):1--18, 2018
work page 2018
-
[8]
A note on stable sets and colorings of graphs
Svatopluk Poljak. A note on stable sets and colorings of graphs. Commentationes Mathematicae Universitatis Carolinae , 15(2):307--309, 1974
work page 1974
-
[9]
Node-and edge-deletion NP -complete problems
Mihalis Yannakakis. Node-and edge-deletion NP -complete problems. In Proceedings of the tenth annual ACM symposium on Theory of computing , pages 253--264, 1978
work page 1978
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.