Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms

DOI10.1007/S00453-019-00579-4MaRDI QIDQ2272595zbMATH OpenOpenAlexWikidataFDO

Authors Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx

Publication date 10 September 2019

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.06757, https://drops.dagstuhl.de/opus/volltexte/2018/8565/

zbMATH Keywords

chordal graphfeedback vertex setparameterized complexitytreewidth

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: It has long been known that Feedback Vertex Set can be solved in time $2^{mathcalO(wlogw)}{n}^{mathcalO(1)}$ on $n$-vertex graphs of treewidth $w$, but it was only recently that this running time was improved to $2^{mathcalO(w)}{n}^{mathcalO(1)}$, that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class $mathcalP$ of graphs, the Bounded $mathcalP$-Block Vertex Deletion problem asks, given a graph~$G$ on $n$ vertices and positive integers~$k$ and~$d$, whether $G$ contains a set~$S$ of at most $k$ vertices such that each block of $G-S$ has at most $d$ vertices and is in $mathcalP$. Assuming that $mathcalP$ is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of $d$: if $mathcalP$ consists only of chordal graphs, then the problem can be solved in time $2^{mathcalO(w{d}^2)}{n}^{mathcalO(1)}$, and if $mathcalP$ contains a graph with an induced cycle of length $ellge4$, then the problem is not solvable in time $2^{o(wlogw)}{n}^{mathcalO(1)}$ even for fixed $d=ell$, unless the ETH fails. We also study a similar problem, called Bounded $mathcalP$-Component Vertex Deletion, where the target graphs have connected components of small size rather than blocks of small size, and we present analogous results. For this problem, we also show that if $d$ is part of the input and $mathcalP$ contains all chordal graphs, then it cannot be solved in time $f(w)n^{o(w)}$ for some function $f$, unless the ETH fails.

Recommendations

• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs
• Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth
• An exact algorithm for subset feedback vertex set on chordal graphs
• Fixed parameterized algorithms for generalized feedback vertex set problems
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
• Parameterized algorithms for generalizations of directed feedback vertex set
• Parameterized algorithms for generalizations of directed feedback vertex set
• On directed feedback vertex set parameterized by treewidth
• Faster fixed parameter tractable algorithms for finding feedback vertex sets

Cites work

• A c^k n 5-approximation algorithm for treewidth
• A complexity dichotomy for hitting small planar minors parameterized by treewidth
• Can you beat treewidth?
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Known algorithms on graphs of bounded treewidth are probably optimal
• Lower bounds based on the exponential time hypothesis
• On the complexity of some colorful problems parameterized by treewidth
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• Parameterized algorithms
• Parameterized vertex deletion problems for hereditary graph classes with a block property
• Slightly superexponential parameterized problems
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(13)

• Parameterized vertex deletion problems for hereditary graph classes with a block property
• More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth
• Digraph coloring and distance to acyclicity
• AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)
• Parameterized max min feedback vertex set
• Anti-factor is FPT parameterized by treewidth and list size (but counting is hard)
• Destroying densest subgraphs is hard
• Digraph coloring and distance to acyclicity
• On bounded-degree vertex deletion parameterized by treewidth

This page was built for publication: Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272595)