On the complexity of edge subdivision to H H -free graphs
Marta Piecyk, R. B. Sandeep · 2026
Read On the complexity of edge subdivision to H H -free graphs by Marta Piecyk, R. B. Sandeep (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-24228.txt.
Introduction
Piecyk and Sandeep establish a complexity dichotomy for edge subdivision to H-free graphs: whether k subdivisions can remove every induced copy of a fixed H. It is polynomial-time solvable when every component of H is a subdivided star or subdivided bistar, with at most one bistar. Otherwise it is NP-complete, and the Exponential Time Hypothesis rules out subexponential-in-k algorithms in hard cases. For every fixed H, a singly exponential-in-k polynomial-time algorithm exists.
Catalog record
| CREATOR | Marta Piecyk, R. B. Sandeep |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 100387 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.24228
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the complexity of edge subdivision to H H -free graphs Marta Piecyk, R. B. Sandeep Abstract Subdividing an edge u v uv in a graph G G is the operation in which the edge u v uv is deleted, and a new vertex w w together with two edges u w uw and v w vw is introduced. A k k -subdivision of a graph G G is a graph obtained from G G by applying k k subdivisions successively. For a graph H H , the H H -free Subdivision problem is defined as follows: given a graph G G and an integer k k , decide whether G G can be transformed into a graph without any induced copy of H H by performing at most k k edge subdivisions. We first observe that if H H is a subdivided star, that is, a tree with at most one vertex of degree at least 3 3 , or a subdivided bistar, that is, a tree with exactly two adjacent vertices of degree at least 3 3 , then the problem is trivially solvable in polynomial time. This observation can be easily extended to show that if every component of H H is either a subdivided star or a subdivided bistar, and at most one component of H H is a subdivided bistar, then H H -free Subdivision is polynomial-time solvable. On the negative side, we prove that H H -free Subdivision is NP-complete and, assuming the Exponential Time Hypothesis, cannot be solved in time 2 o ( k ) ⋅ n O ( 1 ) 2^{o(k)}\cdot n^{O(1)} if H H satisfies any of the following properties: • H H has minimum degree at least 2 2 , and the neighborhood of every degree- 2 2 vertex induces a K 2 K_{2} ; • the vertices of degree at least 3 3 in H H induce a graph with at least two edges; • H H has a triangle with two vertices of degree at least 3 3 ; • H H contains, as an induced subgraph, the 6 6 -vertex graph obtained from two vertex-disjoint triangles by adding an edge between them; • H H contains exactly one triangle; • H H has girth at least 4 4 ; • H H is a tree with exactly two vertices of degree at least 3 3 which are at distance 2 2 or at least 4 4 . A simple bounded search-tree algorithm gives a 2 O ( k ) ⋅ n O ( 1 ) 2^{O(k)}\cdot n^{O(1)} -time fixed-parameter tractable algorithm for the problem. Our lower bound shows that, for the cases in which we prove hardness, this running time cannot be substantially improved, assuming the Exponential Time Hypothesis. CISPA Helmholtz Center for Information Security, [email protected] Indian Institute of Technology Dharwad, [email protected] by Anusandhan National Research Foundation (India) grant MTR/2022/000692 The project was initiated at STRUG: Structural Graph Theory Bootcamp, funded by the “Excellence initiative – research university (2020–2026)” of University of Warsaw. We are grateful to Erik Jan van Leeuwen for stimulating discussions on the topic. ccs Theory of computation Graph algorithms analysis ccs Theory of computation Problems, reductions and completeness ccs Theory of computation Parameterized complexity and exact algorithms keywords Edge subdivision, H -free graphs, Parameterized lower bound † † runningauthor: M. Piecyk and R. B. Sandeep † † copyright: Marta Piecyk and R. B. Sandeep † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction A typical graph modification problem is characterized by one or more graph operations and a target graph class. The input consists of a graph and a budget, and the objective is to decide whether the graph can be transformed into a graph belonging to the target class by applying the operation or operations within the given budget. Many well-known computational graph problems, such as Vertex Cover and Feedback Vertex/Arc Set , can be stated as graph modification problems. We initiate the computational study of graph modification problems based on a very familiar graph operation: edge subdivision. An edge subdivision of an edge uv of a graph G is the operation that removes the edge uv , adds a new vertex w , and adds the two edges uw and wv . A k -subdivision of G is a graph obtained from G by applying k edge subdivisions successively. For a graph class or property \Pi , we consider the following problem. \Pi -Subdivision : Given a graph G and an integer k , decide whether G can be transformed into a graph with property \Pi by applying at most k edge subdivisions. It is easy to observe that edge subdivisions do not destroy minors of the input graph. Therefore, \Pi -Subdivision is trivial when \Pi is a minor-closed graph class, such as the class of planar graphs or the class of forests: if the input graph contains a forbidden minor for \Pi , then it is a no-instance, and otherwise it is a yes-instance. The same argument applies to induced-minor-closed graph classes, such as the class of chordal graphs. A hereditary graph class is a graph class closed under vertex deletion. It is well known that every hereditary graph class can be characterized by a (possibly infinite) set of forbidden induced subgraphs. Hereditary graph classes are standard target classes for graph modification problems. Thus, it is natural to consider the class of H -free graphs, that is, graphs with no induced copy of a fixed graph H , as a target class. Indeed, such classes have been studied as target classes for a wide range of graph modification problems; see Table 1 . Operation P NP-complete vertex deletion H=K_{1} [trivial] otherwise [ 9 ] edge deletion |E(H)|\leq 1 [trivial] otherwise [ 3 ] edge completion at most 1 nonedge [trivial] otherwise [ 3 ] edge editing |V(H)|\leq 2 [trivial] otherwise [ 3 ] edge contraction H\in\{K_{1},K_{2}\} [trivial] otherwise [ 4 ] subgraph complementation paths on at most four vertices, complete graphs, paw [ 2 ] K_{1,t} for t\geq 5 , P_{t} and C_{t} for t\geq 7 , etc. [ 2 ] switching |V(H)|\leq 2 , paw [ 1 ] P_{t} for t\geq 10 , C_{t} for t\geq 7 , etc. [ 1 ] vertex splitting |V(H)|\leq 2 , K_{1}+K_{2} [ 6 ] 2 -connected graphs, etc. [ 6 ] Table 1: Summary of complexity results on graph modification to H -free graphs. We study the complexity of the following problem. H -free Subdivision : Given a graph G and an integer k , decide whether G can be transformed into an H -free graph by applying at most k edge subdivisions. A star is a connected graph with at most one vertex of degree at least 2 . A bistar is a connected graph with exactly two vertices of degree at least 3 ,