PaperlayerView exact revision on arXiv

Source-linked AI summary

Hitting Minors: Stronger Lower Bounds

Jongseo Lee, Roohani Sharma, Sebastian Wiederrecht

arXiv:2610.17664v1cs.DScs.CC

TL;DR

The paper asks whether the known super-exponential treewidth dependence for minor-free deletion persists under more restrictive structural parameters. It proves a path-deletion lower bound for fvs+td and gives a single-exponential algorithm for arbitrary finite forbidden families parameterized by vc.

  • Problem

    The paper asks whether the super-exponential treewidth barrier for F-Minor-Free Deletion persists under feedback vertex set and vertex cover parameterizations.

    Source: §1 · p. 2

  • Method

    A reduction from k × k-Permutation Independent Set uses shared vertices and tree gadgets to encode choices while bounding fvs and treedepth together.

    Source: §1.2 · p. 5

  • Results

    For h≥6, ETH rules out 2^o(t log t)n^O(1) time for {P_h}-deletion, while every finite F admits a 2^O(vc)n^O(1)-time algorithm.

    Source: §1.1 · pp. 3–4, §5 · p. 19

  • Takeaways & Limitations

    For paths on at least six vertices, the transition from single-exponential to slightly super-exponential complexity lies between vc and fvs+td.

    Source: §5 · p. 19

    The lower-bound construction requires h≥6; repeated consistent gadget choices can create a K2,3 containing P5.

    Source: §1.2 · p. 5

Abstract

from arXiv · show

For a fixed finite collection of graphs $\mathcal{F}$, the $\mathcal{F}$-Minor-Free Deletion problem asks, given a graph $G$ and an integer $k$, whether there is a set $S\subseteq V(G)$ with $|S|\leq k$ such that $G-S$ contains no graph of $\mathcal{F}$ as a minor. This generalizes Vertex Cover, Feedback Vertex Set, and Vertex Planarization, among many others. Baste, Sau, and Thilikos [JCSS 2020, SICOMP 2023] showed that, assuming the Exponential Time Hypothesis (ETH), there are collections $\mathcal{F}$ for which the problem cannot be solved in time $2^{o(\mathrm{tw}\log\mathrm{tw})}n^{O(1)}$ on $n$-vertex graphs of treewidth $\mathrm{tw}$, and gave a matching algorithm. We ask whether this super-exponential dependence persists under more restrictive structural parameters. First, we strengthen their lower bound. Assuming ETH, for every fixed $h\geq 6$, $\{P_h\}$-Minor-Free Deletion, where $P_h$ is the path on $h$ vertices, cannot be solved in time $2^{o(t\log t)}n^{O(1)}$, where $t=\mathrm{fvs}+\mathrm{td}$ is the sum of the feedback vertex set number and treedepth of the input graph. These two parameters are incomparable, but both individually upper bound the treewidth. Together with the $2^{O(\mathrm{tw}\log\mathrm{tw})}n^{O(1)}$-time algorithm of Baste, Sau, and Thilikos [SICOMP 2023], our lower bound is tight. In contrast, we show that asymptotically faster algorithms are possible when parameterized by the vertex cover number $\mathrm{vc}$. Specifically, for any finite family $\mathcal{F}$, $\mathcal{F}$-Minor-Free Deletion can be solved in time $2^{O(\mathrm{vc})}n^{O(1)}$. Taken together, our results show that the boundary between single-exponential and super-exponential complexity for this problem lies between the vertex cover number and the feedback vertex set number (plus treedepth).

1 Introduction

The paper asks whether the super-exponential treewidth barrier persists under feedback vertex set and vertex cover parameterizations. It proves a lower bound for the sum of feedback vertex set number and treedepth, while vertex cover permits a single-exponential algorithm.

1 Introduction

  • Baste, Sau, and Thilikos gave a 2^O(tw log tw)-time algorithm and, under ETH, matching lower bounds for many forbidden-minor families, motivating finer parameterized bounds.The paper asks whether this barrier persists for feedback vertex set number or vertex cover.Source: §1 · pp. 2–3

1.1 Our contributions

  • For every fixed h ≥6, {P_h}-Minor-Free Deletion has no 2^o(t log t)-time algorithm under ETH, where t is the sum of feedback vertex set number and treedepth.The lower bound holds even when a minimum feedback vertex set is given; it also implies separate 2^o(fvs log fvs) and 2^o(td log td) lower bounds.Source: §1.1 · pp. 3–4
  • The lower bound is tight for the feedback vertex set and treedepth bounds, while the tight parameterized complexity for {P5}-Minor-Free Deletion by feedback vertex set remains open.For 1 ≤h ≤4, the problem has a single-exponential treewidth algorithm and hence one parameterized by feedback vertex set.Source: §1.1 · p. 4
  • For every fixed finite family F, F-Minor-Free Deletion has a 2^O(vc) n^O(1)-time algorithm.Unlike feedback vertex set and treedepth, vertex cover removes the super-exponential dependence.Source: §1.1 · p. 4

1.2 Overview of Our Techniques

  • The lower-bound reduction encodes permutation choices with row and edge gadgets that interact through 2k shared vertices, keeping feedback vertex set plus treedepth Θ_h(k).The restriction h ≥6 is necessary for this construction: three repeated consistent choices can create a K2,3 containing P5.Source: §1.2 · p. 5
  • The vertex-cover algorithm guesses deletions inside a minimum cover, groups outside vertices by neighborhoods, and reduces to an O_F(vc)-vertex graph for enumeration and minor testing.Edge sparsity bounds vertices with large neighborhoods, while linear neighborhood complexity bounds the number of remaining neighborhood types.Source: §1.2 · p. 5

2 Preliminaries

The preliminaries define the graph parameters and minor models used throughout, and establish basic testing tools and sparsity properties for minor-free graphs.

2 Preliminaries

  • The vertex cover number is the minimum size of a vertex set whose deletion leaves an edgeless graph; the feedback vertex set number leaves a forest.Deleting a vertex set X is denoted G − X.Source: §2 · p. 6
  • A minor model uses pairwise disjoint, nonempty connected branch sets, with an edge between the sets for each edge of the modeled graph.A graph is F-minor-free if it contains no member of F as a minor.Source: §2 · p. 6
  • Treedepth is the minimum height of an elimination forest in which every graph edge joins an ancestor and descendant.The forest height is the maximum number of vertices on a root-to-leaf path.Source: §2 · p. 6
  • A graph contains P_h as a minor exactly when it has a path on at least h vertices.A path of length k has k edges and k + 1 vertices.Source: §2 · p. 6
  • For fixed finite F, testing whether an m-vertex graph contains a member of F as a minor takes 2^O_F(m) time.The proof enumerates vertex-to-branch-set mappings and checks connectivity and required adjacencies.Source: §2 · p. 6
  • Every F-minor-free graph has O_F(|V|) edges and at most c2|X| distinct neighborhoods into any nonempty X, among vertices outside X.The bounds follow from Mader’s theorem [27] and bounded expansion with linear neighborhood complexity [28, 31].Source: §2 · p. 7
  • If G contains H as a minor, it has a subgraph containing that minor whose maximum degree is at most Δ(H).This is the stated part of Fomin, Jansen, and Pilipczuk’s result [13].Source: §2 · p. 7

3 Superexponential Lower Bound for FVS Parameterization

This section proves that, for every fixed h ≥ 6, ETH rules out a 2^{o(t log t)} n^{O(1)}-time algorithm for {P_h}-Minor-Free Deletion, where t = fvs(G) + td(G), even when a minimum feedback vertex set is supplied. In the construction, deleting Sj from Th,q leaves components that are paths on at most h − 1 vertices, making the graph P_h-minor-free.

3 Superexponential Lower Bound for FVS Parameterization

  • For every fixed h ≥ 6, ETH rules out a 2^{o(t log t)} n^{O(1)}-time algorithm for {P_h}-Minor-Free Deletion, where t = fvs(G) + td(G), even if a minimum feedback vertex set is given.Here fvs(G) is the feedback vertex set number and td(G) is treedepth.Source: §3 · p. 7

3.1 A Tree Used in the Reduction

  • The tree gadget T_{h,q} forces every P_h-deletion set to use at least 4q − 2 vertices, and any set of that size can leave any chosen output as its only surviving output.The chosen output is isolated within the tree.Source: §3.1 · p. 7

3.2 The Construction

  • The reduction uses one row gadget per row and one edge gadget per input edge, with labeled outputs encoding choices and edge gadgets excluding simultaneous selection of edge endpoints.The deletion threshold is B = k(4k − 2) + m(8k − 10), where m is the number of input edges.Source: §3.2 · p. 8

3.3 Correctness

  • The constructed graph G has a P_h-deletion set of size at most B exactly when the input graph Γ has a permutation independent set.A feasible deletion set must meet each gadget at its minimum deletion size, avoid R ∪ C and their pendant paths, and leave an output in every gadget.Source: §3.3 · p. 9

3.3.1 Soundness

  • Any deletion set of size at most B yields one surviving output label per row, forming a permutation, and the edge gadgets ensure this permutation selects no adjacent pair in Γ.Pendant paths make two surviving outputs in the same row or column create a path on at least h vertices.Source: §3.3.1 · p. 10

3.3.2 Completeness

  • If Γ has a permutation independent set, then G has a P_h-deletion set of size B; in the constructed graph, each gadget’s only remaining output is isolated, and components without it are P_h-minor-free.Source: §3.3.2 · p. 10

3.4 Size and Parameter Bounds of the Constructed Graph

  • The reduction graph has N = O_h(k^5), k ≤ fvs(G) ≤ 2k, and td(G) ≤ 2k + O_h(log k), so t = Θ_h(k).A minimum feedback vertex set can be computed in 2^{O(k)}N^{O(1)} time; the assumed faster algorithm would contradict ETH.Source: §3.4 · p. 11

3.5 Construction of T_{h,q}

  • The explicit T_{h,q} construction chains 2q − 1 copies of a tree to form a subcubic tree of O_h(q) vertices with the required deletion properties.The proof exhibits 4q − 2 vertex-disjoint P_h copies, shows a deletion set of that size cannot delete all outputs, and constructs a set isolating any chosen output.Source: §3.5 · pp. 12–13

3.5 Construction of Th,q

  • Deleting Sj leaves every component of Th,q as a path on at most h − 1 vertices, making the graph Ph-minor-free.When i ≠ j, the path to ei has d + 1 = h − 1 vertices; when i = j, it has d = h − 2 vertices and yj is isolated.Source: §3.5 · p. 14

4 Algorithm Parameterized by Vertex Cover Number

The algorithm uses a minimum vertex cover to split the graph into a small cover and an independent set, then searches bounded representatives of neighborhood groups. For every fixed finite family of graphs, it decides F-Minor-Free Deletion in single-exponential time in the vertex cover number.

4.1 Overview and Setup

  • The algorithm computes a minimum vertex cover X, guesses its deleted subset D, and groups independent-set vertices by their neighborhoods in the remaining cover Y.If k is at least |X|, deleting X suffices when every forbidden graph has an edge; otherwise the algorithm searches branches with |D| ≤ k.Source: §4.1 · p. 14

4.2 Bounding the Search Space

  • Feasible branches have only O_F(t) vertices with large neighborhoods and O_F(t) neighborhood types, and some optimal solution deletes at most |Q| − 1 vertices from each nonempty type Q.The bounds are |I1| ≤ c1|Y| + b and |NY| ≤ c2|Y| + b; an optimal solution deletes none from the empty-neighborhood bucket.Source: §4.2 · pp. 15–16
  • Keeping |Q|∆F + h false twins from each bucket preserves F-minor-freeness, so arbitrarily large buckets can be represented by bounded subsets.A forbidden-minor witness can use at most |Q|∆F + h vertices from a bucket, allowing its vertices to be replaced by retained twins.Source: §4.2 · p. 16

4.3 The Algorithm

  • For each surviving branch, the algorithm constructs a smaller graph from Y, the large-neighborhood vertices, and bounded representatives of each bucket, then enumerates deletions from those vertices.It accepts when the resulting graph is F-minor-free and maps an accepted deletion set back to the original graph.Source: §4.3 · pp. 16–17

4.4 Correctness and Running Time

  • The reduced graph preserves F-minor-freeness in both directions because omitted bucket vertices can be added back using the retained false twins.For a feasible instance, an optimal solution is represented by an enumerated pair of deletion sets, yielding the stated decision and running-time bounds.Source: §4.4 · p. 17
  • For every fixed finite collection F, F-Minor-Free Deletion is solvable in 2^O(vc) n^O(1) time.The algorithm is correct and its running time follows from enumerating bounded deletion sets and testing minor-freeness on a graph of size O_F(vc).Source: §4.4 · pp. 17, 19

5 Conclusion

The paper establishes a tight ETH lower bound for {P_h}-Minor-Free Deletion parameterized by feedback vertex set number plus treedepth when h ≥ 6, alongside a single-exponential vertex-cover algorithm for every fixed finite family. It identifies unresolved cases and asks whether related dichotomies hold for other parameters.

5 Conclusion

  • For every h ≥ 6, {P_h}-Minor-Free Deletion has no 2^o(t log t) n^O(1)-time algorithm under ETH for t = fvs(G) + td(G), while every fixed finite F admits a 2^O(vc) n^O(1)-time algorithm.The lower bounds are tight with the algorithm of Baste, Sau, and Thilikos [4]; the vertex-cover dependence cannot generally be improved to 2^o(vc) under ETH.Source: §5 · p. 19
  • The tight parameterized complexity of {P5}-Minor-Free Deletion with respect to fvs remains open, while paths with h ≤ 4 admit single-exponential algorithms in treewidth and hence fvs [2, 4].The paper asks whether the P5 problem has a 2^O(fvs) algorithm or requires 2^Ω(fvs log fvs) time under ETH.Source: §5 · pp. 19–20
  • The paper leaves open a feedback-vertex-set dichotomy for connected forbidden graphs and asks whether lower bounds extend to deletion distances to linear forests or star forests.Those two distances lie between fvs and vc.Source: §5 · p. 20

A Why the Construction Does Not Extend to P5

The construction’s h=5 case fails even on a yes-instance: repeated output labels create a P5, while the construction avoids this obstruction for h≥6 by using pendant paths.

A Why the Construction Does Not Extend to P5

B Computable Upper Bounds of Constants in Theorem 9

The section gives computable upper bounds for constants c1 and c2 used in Theorem 9, deriving c1 from a minor-free edge bound and c2 from shallow-minor sparsity.

B Computable Upper Bounds of Constants in Theorem 9

Loading 2610.17664v1…