Source-linked AI summary
NP-Hardness of the $H$-Free Edge-Deletion Problem
Lior Gishboliner, Ethan Honest
TL;DR
The paper asks which graphs H make computing the minimum edge deletions to achieve H-freeness NP-hard. It reduces from vertex cover and proves hardness for every H containing a cycle, resolving the star-forest conjecture and answering Alon, Shapira and Sudakov’s question.
Problem
The complexity question is which graphs H make computing the minimum edge deletions needed for H-freeness polynomial-time solvable, particularly beyond the already established non-bipartite cases.
Source: §1 · p. 1Method
The proof reduces vertex cover to H-freeness edge deletion using special edges for input vertices and copies of H associated with input edges.
Source: §1 · p. 2Results
For every graph H containing a cycle, computing Rem_H(G) is NP-hard.
Source: §1 · p. 2Takeaways & Limitations
For graphs H with at least one edge, the problem is polynomial-time solvable exactly for star forests, completing the stated complexity characterization.
Source: §1 · p. 2The construction requires an appropriate choice of s, a, and b in most cases.
Source: §3 · p. 5
Abstract
from arXiv · showhide
For a graph $H$, the $H$-freeness edge-deletion problem is the algorithmic problem of finding, for an input graph $G$, the minimum number of edges of $G$ whose deletion turns $G$ into an $H$-free graph. We show that for every graph $H$ containing a cycle, this problem is NP-hard. This proves a conjecture of Gishboliner, Levanzov and Shapira, and completes the characterization of the complexity of the $H$-freeness edge-deletion problem, answering a question of Alon, Shapira and Sudakov.
1 Introduction
The paper addresses which graphs H make the H-freeness edge-deletion problem NP-hard, proving hardness whenever H contains a cycle. This proves the conjecture that star forests are the only polynomial-time cases and answers Alon, Shapira and Sudakov’s question.
1 Introduction
- Edge-deletion problems seek the minimum number of edge removals needed to make an input graph satisfy a specified property.Source: §1 · p. 1
- Alon, Shapira and Sudakov showed RemH(·) is NP-hard when H is non-bipartite, though their technique does not apply to bipartite H; [7] showed RemH is polynomial-time solvable for star forests and NP-hard otherwise among forests.Yannakakis proved NP-hardness when H is a cycle.Source: §1 · p. 1
- For every graph H containing a cycle, computing Rem_H(G) is NP-hard, proving the conjecture and answering Alon, Shapira and Sudakov’s question.The paper also states that, for graphs H with at least one edge, the problem is polynomial-time solvable exactly when H is a star forest.Source: §1 · pp. 1–2
- For every graph H with at least one edge, computing Rem_H(G) is polynomial-time solvable if H is a star forest and NP-hard otherwise.Source: §1 · p. 2
- The analogous induced H-freeness problems were previously solved by Aravind, Sandeep and Sivadasan, using different methods.These problems allow edge deletions, additions, or both to make the input induced H-free.Source: §1 · p. 2
- The reduction from vertex cover creates special edges for input vertices, with each input edge generating a copy of H involving its endpoints’ special edges.The proof’s main challenge is controlling all copies of H so that deleting special edges for a vertex cover makes the constructed graph H-free.Source: §1 · p. 2
2 Preliminaries
The preliminaries establish tools for the reduction, including hard vertex-cover instances of large girth, separators, and k-connectivity. They also record path characterizations and a union property of k-connected graphs.
2 Preliminaries
- Vertex cover remains NP-hard on input graphs whose girth is at least any fixed g ≥3.Source: §2 · p. 2
- A set S separates A from B when G − S has no A,B-path; S is a separator of G when its removal disconnects G.A separator may be empty.Source: §2 · p. 3
- A graph is k-connected if it has at least k+1 vertices and no set of fewer than k vertices separates it.Source: §2 · p. 3
- Menger’s theorem characterizes k-connectivity by k internally vertex-disjoint paths between each vertex pair; the fan lemma gives k paths from a vertex to a size-k set meeting only at that vertex.Source: §2 · p. 3
- The union of two k-connected graphs is k-connected when they share at least k vertices.After deleting fewer than k vertices, each graph remains connected and their surviving intersection is nonempty.Source: §2 · p. 3
3 The main construction
This section develops a construction encoding graphs G and H in A to relate the minimum H-removal cost to the vertex-cover number of G, proving a lower bound and, for forests when H is 3-connected or a cycle, a reverse bound using structural tools. Its final step shows that Q contains a vertex of f_ij(S).
The main construction
- Construction 3.1 builds A from a central vertex joined to one vertex per G-vertex, adding a basic copy of H for each G-edge.The construction is used in a reduction from vertex cover; each copy identifies s with the center and a,b with the corresponding endpoint vertices.Source: §3 · p. 3
- Rem_H(A) ≥ τ(G): any edge set making A H-free can be converted into a vertex cover of G of no greater size.For each deleted edge inside a basic copy, the proof selects one endpoint’s center edge; the selected endpoints cover every G-edge.Source: §3 · p. 5
- The paper next treats 2-connected H, then connected H with minimum degree at least 2, and extends hardness to graphs with leaves or disconnected graphs without Construction 3.1.For connected H with minimum degree 1, the reduction is through its 2-core.Source: §3 · p. 5
- When girth(G) > 2v(H), the subgraph F ⊆ G given by Lemma 3.6 is a forest, enabling the authors, for most subsequent arguments, to assume G itself is a forest.Source: §3 · p. 5
- Separators of G induce separators in A, and separators of a minimal support P separate K while K intersects the regions corresponding to every component of P minus the separator.These properties connect the component structure of the support graph to paths and disconnection inside the constructed graph.Source: §3 · pp. 6–7
- A minimal support P for a subgraph K requires each support edge to contribute to K, and isolated support vertices can occur only when K contains a degree-at-most-one endpoint vertex.In particular, if K has minimum degree at least 2, P has no isolated vertices; for a surviving H-copy when δ(H) ≥ 2, its support has at least two edges and the copy is not contained in one basic copy.Source: §3 · pp. 6–7
- For forest G and 3-connected or cycle H, deleting center edges for a vertex cover makes A H-free, giving the reverse bound.The proof rules out a surviving H-copy using minimal supports and separators; for cycles it also uses the fact that an H-copy cannot lie wholly among the center and endpoint vertices.Source: §3 · p. 8
- When G is a forest, paths between vertices of a basic copy can be confined to that copy, supporting transfer of connectivity and separators from H to its copies in A.The section establishes this path property and uses it to show that intersections with basic copies preserve k-connectivity when they contain more than k vertices.Source: §3 · pp. 8–9
3 The main construction
- Q contains a vertex of f_ij(S).This follows from V(Q′) ∩ f_ij(S) ≠ ∅.Source: §3 · p. 9
4 2-connected H
This section extends the construction to every 2-connected graph H, proving inductively that deleting edges indexed by a vertex cover of a forest makes the resulting graph H-free. The proof applies induction to proper subgraphs and handles the case F = H separately by deriving a contradiction from H′ having more 2-cuts than H.
4 2-connected H
- For every 2-connected H, suitable adjacent vertices s, a, b make A − {s′wi : i ∈ C} H-free for any forest G and vertex cover C, with s choosable distinct from any prescribed z.The proof form requires s, a, b to lie in a common leaf away from its separator when H is neither 3-connected nor a cycle.Source: §4 · p. 9, §4.2 · p. 13
4.1 The structure of H
- Tutte’s decomposition gives every 2-connected H a tree-decomposition of adhesion 2 whose torsos are 3-connected or cycles; non-3-connected, non-cycle H has at least two leaves with disjoint interiors.A leaf is separated from the rest by two vertices, and its torso is 3-connected or a triangle.Source: §4.1 · pp. 9–11
- For a leaf with separator {x, y}, every outside vertex has paths to x and y avoiding the opposite leaf interior; a 3-connected leaf also supplies three internally vertex-disjoint paths between each pair of its vertices.Such a leaf also ensures that {s, v} and, for a neighbor a of s in the leaf, {s, a} are not separators of H.Source: §4.1 · pp. 11–12
4.2 Proof of Theorem 4.1
- The proof uses induction on |V(H)|, reducing to Theorem 3.7 when H is 3-connected or a cycle and otherwise using a leaf containing s, a, b away from its separator.Theorem 4.11 states that under these conditions, deleting the cover-indexed edges leaves A H-free.Source: §4.2 · p. 13
- The induction constructs a smaller graph F from the leaf and the preimages of vertices in the alleged copy of H, then establishes that F is 2-connected.The proof combines 2-connected subgraphs corresponding to edges of a minimal support in the forest.Source: §4.2 · p. 14
- When F is a proper subgraph of H, the induction hypothesis applies unless V(F) = L and L is 3-connected; if L ⊊ V(F) or L is a triangle, L remains a leaf of F.The exceptional case is handled separately because L need not be a leaf of F.Source: §4.2 · p. 15
- In the exceptional case, a minimal support for L′ has at least two edges, enabling a separator argument that contradicts the three internally vertex-disjoint paths guaranteed by 3-connectivity.The paths cannot all pass through the set R′ = {s′, wi}, which has size at most two.Source: §4.2 · pp. 15–16
- When F = H, each 2-cut of H maps injectively to a 2-cut of H′, which also has an additional 2-cut, contradicting H′ ≅ H.The additional cut is {s′, wi} for a vertex i of P with degree at least two.Source: §4.2 · p. 16
5 Connected H with δ(H) ≥2
The section extends the edge-deletion construction to connected graphs H with minimum degree at least 2, using a leaf biconnected component to identify when the original construction or a variant yields an H-free graph after deleting edges indexed by a vertex cover. In Case 2, it rules out isomorphism between H and H′ by deriving a strict imbalance in their copies of M.
5 Connected H with δ(H) ≥2
- When the leaf component’s cut vertex z is not a or b, deleting s′wi for each i in a vertex cover of forest G makes A(G,H,s,a,b) H-free.Theorem 5.4 assumes s,a,b is a good choice for M and s ≠ z.Source: §5 · p. 17
- The original construction can fail when z equals a or b, so the variant hangs one copy of H − (M \ {z}) on each wi.In the two-triangle example, multiple hanging triangles can form H without using any deletable s′wi edge.Source: §5 · p. 18
- For B, the minimum number of edge deletions needed to make it H-free is at least τ(G) when M = H or z ∈ {a,b}.Any copy of H in B is contained in a subgraph B(F,H,M,s,a,b) for some F ⊆ G with v(F) ≤ 2v(H).Source: §5 · p. 19
- When z is a or b, deleting the corresponding s′wi edges from the variant B makes B H-free for any vertex cover of forest G.Theorem 5.12 assumes s,a,b is a good choice for M and s ≠ z.Source: §5 · p. 20
5.1 Proof of Theorem 5.4
- Claim 5.13 states that F is connected and has minimum degree at least 2; Claim 5.15 states that |M(H)| > |M(H′)|, contradicting H′ being isomorphic to H and completing the theorem’s proof.Source: §5.1 · pp. 20, 22
5.2 Proof of Theorem 5.12
- The proof of Theorem 5.12 likewise inducts on |V(H)| and constructs a connected induced subgraph F with minimum degree at least 2 from intersections with the hanging copies.When F is proper, it satisfies the theorem’s conditions and the proof applies induction.Source: §5.2 · pp. 22–23
- Claim 5.17 shows that at most one index i has gi(V(H) \ M) intersecting V(H′), since two such indices would yield too many cut vertices.H′ has at least (|W| − 1) + |I| distinct cut vertices but exactly |W|, so |I| ≤ 1.Source: §5.2 · p. 23
- Claim 5.18 gives |M(H)| > |M(H′)|, contradicting H′ ≅ H and completing the proof of Theorem 5.12.The proof uses that A′ is M-free and that M is 2-connected to bound the copies of M in H′.Source: §5.2 · p. 24
6 Putting it all together
The section completes the hardness proof by reducing connected cyclic targets to their 2-cores, then extending hardness to disconnected targets through a repeated cyclic component. The reductions preserve the edge-deletion distance or transfer polynomial-time solvability as required.
6 Putting it all together
- For connected H with δ(H)≥2, high-girth vertex-cover instances reduce to Rem_H using constructions tailored to the cut-vertex case.The constructions establish Rem_H(A)=τ(G) or Rem_H(B)=τ(G).Source: §6 · p. 24
6.1 Theorem 1.1 for connected graphs H
- For connected cyclic H, attaching e(G)+1 copies of each rooted tree in H's 2-core construction yields G' with Rem_H(G')=Rem_H*(G).This gives a polynomial reduction from computing Rem_H* to computing Rem_H.Source: §6.1 · p. 25
6.2 Disconnected graphs
- If connected H contains a cycle, computing Rem_kH is NP-hard for every k≥1; for k≥2, Lemma 6.6 transfers polynomial-time solvability back to Rem_H.The proof uses the hardness for connected H and the reduction in Lemma 6.6.Source: §6.2 · p. 26
- For H with a cycle, choosing C1 as a maximum-edge cyclic component and C1,...,Ck isomorphic copies, adding e(G)+1 copies of each Ci for i>k yields Rem_H(G')=Rem_kC1(G).The construction has v(G')=O(n2).Source: §6.2 · pp. 26–27