Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
| Autor: | Włodarczyk, Michał |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
Theory of computation → Graph algorithms analysis fixed-parameter tractability Computer Science - Data Structures and Algorithms treewidth Theory of computation → Parameterized complexity and exact algorithms Data Structures and Algorithms (cs.DS) interval graphs chordal graphs representative families matroids |
| Popis: | 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)} \cdot |V(G)|$, improving upon the running time $2^{O(tw^2)} \cdot |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}\cdot 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)} \cdot |V(G)|$-time algorithm for Interval Vertex Deletion cannot be improved assuming Exponential Time Hypothesis. Comment: To appear at ICALP'23 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|