PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear kernels and single-exponential algorithms via protrusion decompositions

Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, Somnath Sikdar

arXiv:1207.0835v2cs.DScs.DMmath.CO

TL;DR

A prior 2^O(k) · n log^2 n algorithm for Planar-F-Deletion assumed every graph in F was connected, while broader linear-kernel results on sparse graphs motivate extending the available graph classes. The paper computes protrusion decompositions from treewidth modulators and uses branching, rather than protrusion replacement, for general Planar-F-Deletion. The parameterized Planar-F-Deletion problem can be solved in time 2^O(k) · n^2.

  • Problem

    A prior 2^O(k) · n log^2 n algorithm for Planar-F-Deletion assumed every graph in F was connected, while broader linear-kernel results on sparse graphs motivate extending the available graph classes.

    Source: §1 · pp. 2, 5

  • Method

    The paper computes protrusion decompositions from treewidth modulators and uses branching, rather than protrusion replacement, for general Planar-F-Deletion.

    Source: §1 · p. 3

  • Results

    The parameterized Planar-F-Deletion problem can be solved in time 2^O(k) · n^2.

    Source: §1 · p. 5

  • Takeaways & Limitations

    The decomposition is a building block for linear-kernel results on topological-minor-free graphs and a single-exponential algorithm for Planar-F-Deletion.

    Source: §6 · p. 34

    When F contains no planar graph, no single-exponential algorithm is known for Planar-F-Deletion, according to the paper.

    Source: §6 · p. 35

Abstract

from arXiv · show

A \emph{$t$-treewidth-modulator} of a graph $G$ is a set $X \subseteq V(G)$ such that the treewidth of $G-X$ is at most some constant $t-1$. In this paper, we present a novel algorithm to compute a decomposition scheme for graphs $G$ that come equipped with a $t$-treewidth-modulator. This decomposition, called a \emph{protrusion decomposition}, is the cornerstone in obtaining the following two main results. We first show that any parameterized graph problem (with parameter $k$) that has \emph{finite integer index} and is \emph{treewidth-bounding} admits a linear kernel on $H$-topological-minor-free graphs, where $H$ is some arbitrary but fixed graph. A parameterized graph problem is called treewidth-bounding if all positive instances have a $t$-treewidth-modulator of size $O(k)$, for some constant $t$. This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus [Bodlaender et al., FOCS 2009] and $H$-minor-free graphs [Fomin et al., SODA 2010]. Our second application concerns the Planar-$\mathcal{F}$-Deletion problem. Let $\mathcal{F}$ be a fixed finite family of graphs containing at least one planar graph. Given an $n$-vertex graph $G$ and a non-negative integer $k$, Planar-$\mathcal{F}$-Deletion asks whether $G$ has a set $X\subseteq V(G)$ such that $|X|\leq k$ and $G-X$ is $H$-minor-free for every $H\in \mathcal{F}$. Very recently, an algorithm for Planar-$\mathcal{F}$-Deletion with running time $2^{O(k)} n \log^2 n$ (such an algorithm is called \emph{single-exponential}) has been presented in [Fomin et al., FOCS 2012] under the condition that every graph in $\mathcal{F}$ is connected. Using our algorithm to construct protrusion decompositions as a building block, we get rid of this connectivity constraint and present an algorithm for the general Planar-$\mathcal{F}$-Deletion problem running in time $2^{O(k)} n^2$.

1 Introduction

The paper develops protrusion decompositions for graphs with a treewidth modulator, using them to obtain linear kernels on graphs excluding a fixed topological minor and a single-exponential algorithm for Planar-F-Deletion. The latter removes the earlier requirement that every graph in F be connected.

1 Introduction

  • Protrusion replacement underlies prior sparse-graph kernel meta-theorems: finite integer index lets large protrusions be replaced by small equivalent gadgets.Kernelization is polynomial-time preprocessing to an equivalent instance whose size is bounded by a function of k; kernels are not necessarily linear.Source: §1 · p. 2
  • The decomposition algorithm takes a treewidth modulator X and returns a superset Y0 such that every component of G − Y0 is a protrusion.For the stated problem and graph-class conditions, the decomposition is linear: |Y0| and the number of protrusions are O(k).Source: §1 · p. 3
  • Treewidth-bounding problems with finite integer index admit linear kernels on graphs excluding any fixed graph H as a topological minor.Treewidth-bounding means positive instances have a t-treewidth-modulator of size O(k) for some constant t.Source: §1 · p. 3
  • The paper also gives an explicit linear kernel for Edge Dominating Set on H-topological-minor-free graphs, without generic protrusion replacement.Earlier known linear kernels for this problem on H-minor-free and H-topological-minor-free graphs relied on generic replacement.Source: §1 · p. 3
  • Planar-F-Deletion asks whether at most k vertices can be deleted so the remaining graph excludes every graph in finite F as a minor.Vertex Cover and Feedback Vertex Set are special cases, and earlier single-exponential results covered several particular families.Source: §1 · p. 4
  • The parameterized Planar-F-Deletion problem is solvable in 2^O(k) · n^2 time, without requiring every graph in F to be connected, unlike the earlier 2^O(k) · n log^2 n algorithm that required connectivity.Source: §1 · p. 5
  • Disconnected planar obstructions occur in natural minor-closed classes, including the obstruction set for graphs embeddable in the torus.For example, two disjoint copies of K5 form an obstruction for torus embeddability; related lower-ideal obstruction families can also contain disconnected planar graphs.Source: §1 · p. 5
  • Iterative compression reduces Planar-F-Deletion to a disjoint version, then branching constructs a linear protrusion decomposition and identifies O(k) candidate vertices for a solution.The algorithm uses three branching steps, each compatible with single-exponential time, and is fully constructive.Source: §1 · p. 6

2 Preliminaries

This section sets out the parameterized-complexity, treewidth, and CMSO foundations for protrusions, then develops finite-integer-index replacement machinery to find and replace equivalent protrusions, shrinking instances without increasing the parameter.

2.1 Parameterized problems, kernels and treewidth

  • The preliminaries define parameterized graph problems, fixed-parameter tractability, kernelization and linear kernels, and treewidth through tree decompositions.Source: §2.1 · pp. 7–8

2.2 (Counting) Monadic Second Order Logic

  • CMSO extends MSO with modular cardinality predicates, and the stated min-, max-, and exact-CMSO problems ask for a bounded, lower-bounded, or exact-size set satisfying an expressible predicate.Source: §2.2 · p. 8

2.3 Protrusions, t-boundaried graphs, and finite integer index

  • A t-protrusion W has |∂G(W)| ≤ t and tw(G[W]) ≤ t − 1; a protrusion decomposition partitions V(G) into Y0,...,Yℓ, with each Yi ∪ N_Y0(Yi) a t-protrusion.For fixed t, a decomposition is linear when α = O(k) and quadratic when α = O(k²).Source: §2.3 · pp. 9–10
  • A t-boundaried graph labels its t boundary vertices, and gluing identifies equally labeled terminals; replacing a protrusion swaps its boundaried subgraph for another along that interface.Source: §2.3 · p. 9
  • Finite integer index guarantees finitely many t-boundaried representatives, including one equivalent to each graph with a nonnegative parameter shift.The paper motivates using these representatives to replace large protrusions with smaller gadgets.Source: §2.3 · p. 10
  • For problems with finite integer index, applying the protrusion reduction rule preserves whether an instance is a Yes-instance.The stated safety result concerns an instance obtained by one application of the rule.Source: §2.3 · pp. 11–12
  • Representatives are assumed available and chosen so replacements do not increase the parameter, making the resulting algorithms non-uniform.The paper notes that this non-uniformity is also implicit in earlier work using protrusion machinery.Source: §2.3 · p. 12
  • If a t-protrusion exceeds a problem-dependent threshold, an O(|X|)-time procedure finds a bounded-size 2t-protrusion within it.The construction uses a nice tree-decomposition of the protrusion’s induced graph.Source: §2.3 · pp. 12–13
  • Replacing a protrusion by a representative of size at most ρΠG(2t) strictly shrinks the graph without increasing the parameter, yielding a polynomial-time reduction after at most n applications.The protrusion limit is the maximum vertex count among the chosen representatives for the relevant boundary size.Source: §2.3 · pp. 12–13
  • A maximum-size t-protrusion can be found in O(n^(t+1)) time by enumerating candidate boundaries of size at most t and testing their components.For each boundary, the method forms protrusions from components whose union with the boundary has treewidth at most t−1.Source: §2.3 · p. 13
  • Given the representatives and a fixed-size t-protrusion, the equivalent representative can be identified in constant time.The test compares optimal solution-size differences on extensions by each representative.Source: §2.3 · p. 13

3 Constructing protrusion decompositions

The bag-marking algorithm uses a treewidth-modulator to construct a separating set whose remaining components have small boundaries. Grouping those components by their neighborhoods yields a protrusion decomposition.

3 Constructing protrusion decompositions

  • Given X with tw(G − X) ≤ t − 1 and a threshold r, the algorithm decomposes components of G − X having at least r neighbors in X and processes their rooted tree-decompositions bottom-up.It selects the farthest unprocessed bag and marks it when it is the least common ancestor of two marked bags or its remaining graph contains a connected component with at least r neighbors in X.Source: §3 · p. 14
  • The marked bags, together with X, form Y₀; closing the marked set under least common ancestors ensures each unmarked tree-decomposition subtree is adjacent to at most two marked bags.This property bounds every component C of G − Y₀ by |N_X(C)| < r and |N_Y₀(C)| < r + 2t.Source: §3 · pp. 14, 16
  • The large-subgraph marking test uses dynamic programming to track connected components intersecting each bag and their neighborhoods in X, marking when a component reaches the threshold r.The algorithm runs in O(n) time, with the hidden constant depending only on t and r.Source: §3 · p. 15
  • The algorithm outputs a (max{ℓ, |Y₀|}, 2t + r)-protrusion decomposition by grouping components of G − Y₀ into clusters with identical neighborhoods in Y₀.Each cluster is a restricted (2t + r)-protrusion.Source: §3 · p. 16
  • Each cluster of G − Y₀ is a restricted (2t + r)-protrusion, but this proposition alone does not bound the number of clusters or the size of Y₀.Later applications establish those bounds for linear kernels and a single-exponential Planar-F-Deletion algorithm.Source: §3 · p. 16

4 Linear kernels on graphs excluding a topological minor

This section establishes kernelization results for finite-integer-index, treewidth-bounding problems on graphs excluding a fixed topological minor and identifies concrete problems covered by them. It also examines the structural conditions behind earlier results, the approach’s limits, and an Edge Dominating Set example.

4 Linear kernels on graphs excluding a topological minor

  • Replacing a sufficiently large protrusion by a finite-integer-index representative preserves whether the instance is a Yes-instance and does not increase its parameter.The rule adjusts the parameter by the representative’s equivalence offset.Source: §4 · p. 17
  • The proof bounds the reduced instance’s core by xk = s(k) + 2fE(s(k)) · t, then bounds its clusters to obtain the kernel-size bound.The core bound follows from limiting the number of marked bags; cluster sizes are controlled using protrusion reduction and clique counts.Source: §4 · pp. 19–21
  • Finite-integer-index, treewidth-bounding problems on H-topological-minor-free graphs have kernels of size O(sΠ,GH(k)), linear when the treewidth-modulator size is linear.Theorem I follows when the treewidth bound is linear.Source: §4 · p. 22

4.1 Problems affected by our result

  • Vertex Cover, Cluster Vertex Deletion, Feedback Vertex Set, Chordal Vertex Deletion, Interval and Proper Interval Vertex Deletion, Cograph Vertex Deletion, and Edge Dominating Set have linear kernels.These problems are linearly treewidth-bounding and have finite integer index on H-topological-minor-free graphs.Source: §4.1 · p. 22
  • Chordal Vertex Deletion and Interval Vertex Deletion are solvable in single-exponential time on H-topological-minor-free graphs.The passage also gives an O(c^k · poly(n)) running time for these problems.Source: §4.1 · p. 22
  • Connected Vertex Cover, Connected Cograph Vertex Deletion, and Connected Cluster Vertex Deletion have linear kernels when graphs exclude a fixed topological minor.Source: §4.1 · p. 23
  • Width-b Vertex Deletion has a linear kernel on H-topological-minor-free graphs for treewidth, clique-width, branchwidth, and rankwidth.Finite integer index follows from strong monotonicity, and branchwidth differs from treewidth by a constant factor.Source: §4.1 · p. 23

4.2 A comparison with earlier results

  • For bounded-genus graphs, treewidth-bounding is stronger than quasi-compactness, while bidimensionality and separation for H-minor-free graphs imply treewidth-bounding.The authors identify treewidth-bounding as a recurring condition in known linear-kernel results on sparse graph classes.Source: §4.2 · pp. 23–24

4.3 The limits of our approach

  • The approach does not generally extend to classes that locally exclude a minor, because constrictions can increase clique number; slowly growing forbidden-minor sizes still permit polynomial kernels.The required growth condition involves ρ′, whose growth the authors do not know; they note bounded-expansion classes face the same issue.Source: §4.3 · pp. 24–25
  • For locally minor-excluding classes, finite-integer-index problems that are (s(k), tΠ)-treewidth-bounding admit kernels of size O(s(k)r0) under the stated lower bound on g(r).The condition is g(r) ≥ ρ′(2tΠ + r) + 1 for all r ≥ n0.Source: §4.3 · p. 25

4.4 An illustrative example: Edge Dominating Set

  • The Edge Dominating Set example uses a handcrafted twin-elimination rule on a protrusion decomposition to obtain an explicit linear kernel, and the procedure runs in linear time.The rule safely keeps |N_Y0(Yi)| vertices when |Yi| exceeds that number.Source: §4.4 · pp. 26–27
  • A 2-approximation for Edge Dominating Set supplies a modulator X of size at most 4k, leaving an independent set after deletion.The twin-elimination rule preserves the parameter k while reducing oversized clusters in the protrusion decomposition.Source: §4.4 · p. 26

5 Single-exponential algorithm for Planar-F-Deletion

The section develops a 2^O(k)n^2-time algorithm for Planar-F-Deletion by reducing to its disjoint variant, constructing a linear protrusion decomposition and representative sets for restricted protrusions, and solving the problem by enumerating finite representatives.

5 Single-exponential algorithm for Planar-F-Deletion

  • Iterative compression reduces Planar-F-Deletion to Disjoint Planar-F-Deletion; a c^k p(n)-time disjoint solver lifts to (c+1)^k p(n)n time.Source: §5 · pp. 27–28

5.1 Analysis of the bag marking algorithm

  • At most (1+α_r)k pairwise disjoint connected sets can each have at least r neighbors in X, and the marked set Y0 has size at most k+2t_F(1+α_r)k.The marked-set bound applies to a Yes-instance of Disjoint Planar-F-Deletion.Source: §5.1 · p. 29

5.2 Branching step and linear protrusion decomposition

  • For Yes-instances, branching on I⊆Y0\X in 2^O(k) time yields an (O(k), r+2t_F)-protrusion decomposition of G−I with residual solution budget k−|I|.The decomposition has a set I of size at most k, and its residual solution lies outside Y0 and has size at most k−|I|.Source: §5 · p. 28, §5.2 · p. 31

5.3 Solving Planar-F-Deletion with a linear protrusion decomposition

  • Given a linear protrusion decomposition, finite minimum-size representatives preserve solution feasibility, leaving at most 2^O(ℓ) candidates to test in O(h(t_F)n) each.A solution of size at most k exists if and only if a decomposable solution of size at most k exists.Source: §5.3 · pp. 31–32
  • Finite MSO-based equivalence classes of bounded-boundary contexts yield a computable representative family, and bounded-treewidth dynamic programming constructs representatives for each protrusion.This makes the algorithm constructive and uniform over the family F.Source: §5.3 · pp. 32–33
  • For each of 2^M context-behavior vectors, an optimal solution is computed; these solutions form minimum-sized representatives, constructible in O(|Yi|) time and O(n) total.Source: §5.3 · pp. 33–34

5.4 Proof of Theorem II

  • Planar-F-Deletion can be solved in time 2^O(k) · n^2.Source: §5.4 · p. 34
  • The proof solves Disjoint Planar-F-Deletion in time 2^O(k) · n using a protrusion decomposition, then applies the reduction back to Planar-F-Deletion.Source: §5.4 · p. 34

6 Conclusions and further research

The paper concludes that its modulator-based protrusion decomposition supports linear kernels on H-topological-minor-free graphs and a single-exponential algorithm for Planar-F-Deletion. It also identifies open questions about extending these results and generalizing the technique.

6 Conclusions and further research

  • The decomposition algorithm supports linear kernels on H-topological-minor-free graphs and a single-exponential Planar-F-Deletion algorithm.The decomposition is computed for graphs equipped with a set whose deletion leaves bounded treewidth.Source: §6 · p. 34
  • Whether linear-kernel results extend to broader sparse graph classes or more problems on H-topological-minor-free graphs remains open.The paper specifically asks about extending to larger sparse classes and other problems, including Connected Dominating Set.Source: §6 · p. 35
  • The kernelization algorithm's polynomial running-time degree depends linearly on the size of the excluded topological minor H.The authors suggest a fast protrusion replacer might remove this dependence.Source: §6 · p. 35
  • For families F containing no planar graph, no single-exponential Planar-F-Deletion algorithm is known, and optimizing the 2^O(k) constants remains open.The paper also raises whether such an algorithm exists or can be ruled out under a complexity assumption.Source: §6 · p. 35
  • The single-exponential approach for disjoint Planar-F-Deletion may extend to CMSO-expressible vertex-deletion problems, while bounded treewidth may be needed for constructivity.Extensions to p-max-CMSO, p-eq-CMSO, and edge-subset problems are suggested as future work.Source: §6 · p. 35
  • Deterministic constant-factor approximation and linear or polynomial kernels for Planar-F-Deletion remain open directions; Fomin et al. gave a randomized constant-factor approximation.The paper also notes a polynomial kernel for general F-Deletion parameterized by vertex-cover size.Source: §6 · p. 35
  • For parameterized dual F-Deletion, the paper asks whether any non-trivial choice of F admits a single-exponential algorithm.For F = {K3}, the problem is k-Disjoint Cycle Packing, which has no polynomial kernel on general graphs unless co-NP ⊆ NP/poly.Source: §6 · p. 35

A Edge modification problems are not minor-closed

F-Edge-Contraction and F-Edge-Removal are not minor-closed: a minor operation can turn an instance solvable within budget into one that requires more modifications.

A Edge modification problems are not minor-closed

  • Minor-closedness requires every minor of a yes-instance to remain a yes-instance, a property the edge-modification variants fail.F-(Vertex-)Deletion is minor-closed, unlike F-Edge-Contraction and F-Edge-Removal.Source: A Edge modification problems are not… · p. 40
  • F-Edge-Contraction is not minor-closed: deleting edge e from the constructed graph changes a one-contraction planarization into one requiring at least k + 1 contractions.The graph is formed from K5 by subdividing every edge k times and adding e between two original vertices.Source: A Edge modification problems are not… · p. 40
  • F-Edge-Removal is not minor-closed: deleting e makes G H-minor-free, but contracting e yields G′, which needs at least two edge deletions.Figure 4 depicts the example.Source: A Edge modification problems are not… · p. 40, Figure 4 · p. 40

B Disconnected Planar-F-Deletion has not finite integer index

For families containing disconnected graphs, F-Deletion need not have finite integer index; in particular, Planar-F-Deletion can fail to have it when the family contains a disconnected planar graph.

B Disconnected Planar-F-Deletion has not finite integer index

  • For incomparable forbidden minors F1 and F2, the construction takes F as their disjoint union and builds 1-boundaried graphs Gi and Hj from repeated copies of each.For a planar example, F1 = K4 and F2 = K2,3.Source: B Disconnected Planar-F-Deletion has… · p. 41
  • For i, j ≥ 1, gluing Gi and Hj gives optimal deletion value min{i, j}.This value is used to compare the behavior of graphs with different copy counts under extensions.Source: B Disconnected Planar-F-Deletion has… · p. 41
  • Choosing 1 ≤ n < m yields distinct equivalence classes because the constructed graphs cannot have a fixed offset in optimal values across extensions.The proof uses the equivalence relation on boundaried graphs, where equivalence requires an integer offset that works for every glued graph.Source: B Disconnected Planar-F-Deletion has… · p. 41
  • If F contains a disconnected planar graph H, Planar-F-Deletion does not have finite integer index in general.More generally, F-Deletion lacks finite integer index in general when F contains a disconnected graph, planar or not.Source: B Disconnected Planar-F-Deletion has… · pp. 40–41

C MSO formula for topological minor containment

For fixed H, the paper describes an MSO1 formula that detects whether a graph contains H as a topological minor, then negates it to express exclusion.

C MSO formula for topological minor containment

Loading 1207.0835v2…