Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
View through CrossRef
Abstract
In Chordal/Interval Vertex Deletion we ask how many vertices one needs to remove from a graph to make it chordal (respectively: interval). We study these problems under the parameterization by treewidth (tw) of the input graph G. On the one hand, we present an algorithm for Chordal Vertex Deletion with running time 2^O(tw)*|V(G)|, improving upon the running time 2^O(tw^2)*|V(G)|^O(1) by Jansen, de Kroon, and Wlodarczyk (STOC'21). When a tree decomposition of width tw is given, then the base of the exponent equals 2^(omega-1)*3+1. Our algorithm is based on a novel link between chordal graphs and graphic matroids, which allows us to employ the framework of representative families. On the other hand, we prove that the known 2^O(tw log tw)*|V(G)|-time algorithm for Interval Vertex Deletion cannot be improved assuming Exponential Time Hypothesis.
Title: Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
Description:
Abstract
In Chordal/Interval Vertex Deletion we ask how many vertices one needs to remove from a graph to make it chordal (respectively: interval).
We study these problems under the parameterization by treewidth (tw) of the input graph G.
On the one hand, we present an algorithm for Chordal Vertex Deletion with running time 2^O(tw)*|V(G)|, improving upon the running time 2^O(tw^2)*|V(G)|^O(1) by Jansen, de Kroon, and Wlodarczyk (STOC'21).
When a tree decomposition of width tw is given, then the base of the exponent equals 2^(omega-1)*3+1.
Our algorithm is based on a novel link between chordal graphs and graphic matroids, which allows us to employ the framework of representative families.
On the other hand, we prove that the known 2^O(tw log tw)*|V(G)|-time algorithm for Interval Vertex Deletion cannot be improved assuming Exponential Time Hypothesis.
Related Results
Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
Abstract
Chordal graphs are characterized as the intersection graphs of subtrees in a tree and such a representation is known as the tree model. Restricting the characteriz...
DynASP2.5: Dynamic Programming on Tree Decompositions in Action
DynASP2.5: Dynamic Programming on Tree Decompositions in Action
Efficient exact parameterized algorithms are an active research area. Such algorithms exhibit a broad interest in the theoretical community. In the last few years, implementations ...
Hardness and algorithmic results for Roman \{3\}-domination
Hardness and algorithmic results for Roman \{3\}-domination
A Roman $\{3\}$-dominating function on a graph $G = (V, E)$ is a function $f: V \rightarrow \{0, 1, 2, 3\}$ such that for each vertex $u \in V$, if $f(u) = 0$ then $\sum\limits_{v ...
Treewidth : algorithmic, combinatorial, and practical aspects
Treewidth : algorithmic, combinatorial, and practical aspects
Treewidth : aspects algorithmiques, combinatoires et pratiques
Dans cette thèse, nous étudions la complexité paramétrée de problèmes combinatoires dans les graphes....
Minimum Stable Cut and Treewidth
Minimum Stable Cut and Treewidth
A stable or locally-optimal cut of a graph is a cut whose weight cannot be increased by changing the side of a single vertex. In this paper we study Minimum Stable Cut, the problem...
Advanced tools and methods for treewidth-based problem solving
Advanced tools and methods for treewidth-based problem solving
Abstract
Computer programs, so-called solvers, for solving the well-known Boolean satisfiability problem (Sat) have been improving for decades. Among the reasons, wh...
Characterization of Super Strongly Perfect Graphs in Chordal and Strongly Chordal Graphs
Characterization of Super Strongly Perfect Graphs in Chordal and Strongly Chordal Graphs
A Graph G is Super Strongly Perfect Graph if every induced sub graph H of G possesses a minimal dominating set that meets all the maximal complete sub graphs of H. In this paper, w...
Differential graded vertex Lie algebras
Differential graded vertex Lie algebras
This is the continuation of the study of differential graded (dg) vertex algebras defined in our previous paper [Caradot et al., “Differential graded vertex operator algebras and t...