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...
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 ...
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...
Parameterized Strings: Algorithms and Applications
Parameterized Strings: Algorithms and Applications
The parameterized string (p-string), a generalization of the traditional string, is composed of constant and parameter symbols. A parameterized match (p-match) exists between two p...
The prognostic significance of XL DLEU/LAMP (13q14 deletion) in CCL patients: a cross section study
The prognostic significance of XL DLEU/LAMP (13q14 deletion) in CCL patients: a cross section study
Background: Many cytogenetic abnormalities were detected in CLL, one of them. Deletion of 13q14 region which is found in more than 50% of CLL patient. 13q deletion is the most comm...
A Vertex Translation Algorithm for Adaptive Modification of STL File in Layered Manufacturing
A Vertex Translation Algorithm for Adaptive Modification of STL File in Layered Manufacturing
Rapid Prototyping (RP)/Layered Manufacturing (LM) machines typically use a Stereolithography (STL) file as a basis to manufacture parts. However, the conversion of the part CAD fil...
On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
AbstractWe study the parameterized complexity of the Bounded-Degree Vertex Deletion problem (BDD), where the aim is to find a maximum induced subgraph whose maximum degree is below...