On the complexity of edge subdivision to $H$-free graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913064918450176 |
|---|---|
| author | Piecyk, Marta Sandeep, R. B. |
| author_facet | Piecyk, Marta Sandeep, R. B. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_24228 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the complexity of edge subdivision to $H$-free graphs Piecyk, Marta Sandeep, R. B. Data Structures and Algorithms Combinatorics 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. |
| title | On the complexity of edge subdivision to $H$-free graphs |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2604.24228 |