Treewidth and pathwidth parameterized by the vertex cover number

DOI10.1016/J.DAM.2014.12.012MaRDI QIDQ344839zbMATHOpenAlexFDO

Authors Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca, Yngve Villanger

Publication date 24 November 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.0433

zbMATH Keywords

treewidthpathwidthvertex coverparameterized algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: After the number of vertices, Vertex Cover is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover. Here we consider the TREEWIDTH and PATHWIDTH problems parameterized by k, the size of a minimum vertex cover of the input graph. We show that the PATHWIDTH and TREEWIDTH can be computed in O*(3^k) time. This complements recent polynomial kernel results for TREEWIDTH and PATHWIDTH parameterized by the Vertex Cover.

Recommendations

• Treewidth and Pathwidth Parameterized by the Vertex Cover Number
• Treedepth Parameterized by Vertex Cover Number.
• Fixed-parameter tractability of treewidth and pathwidth
• Two fixed-parameter algorithms for vertex covering by paths on trees
• On the vertex cover \(P_3\) problem parameterized by treewidth
• On cutwidth parameterized by vertex cover
• On cutwidth parameterized by vertex cover
• The pathwidth and treewidth of cographs
• The Pathwidth and Treewidth of Cographs
• Tree-width and circumference of graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• A Dynamic Programming Approach to Sequencing Problems
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A note on exact algorithms for vertex ordering problems on graphs
• A parameterized algorithm for chordal sandwich
• Computing Directed Pathwidth in O(1.89 n ) Time
• Exact exponential algorithms.
• Finding induced subgraphs via minimal triangulations
• Fourier meets M\"{o}bius: fast subset convolution
• Graph Layout Problems Parameterized by Vertex Cover
• Improved upper bounds for vertex cover
• Kernel bounds for structural parameterizations of pathwidth
• On cutwidth parameterized by vertex cover
• On exact algorithms for treewidth
• Preprocessing for treewidth: a combinatorial analysis through kernelization
• The vertex separation number of a graph equals its path-width
• Treewidth and Pathwidth Parameterized by the Vertex Cover Number

Cited in

(9)

• On cutwidth parameterized by vertex cover
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Finding optimal triangulations parameterized by edge clique cover
• scientific article; zbMATH DE number 7764113 (Why is no real title available?)
• The parameterized complexity of maximum betweenness centrality
• Treewidth and Pathwidth Parameterized by the Vertex Cover Number
• Maximum minimal vertex cover parameterized by vertex cover
• On cutwidth parameterized by vertex cover
• Treedepth Parameterized by Vertex Cover Number.

This page was built for publication: Treewidth and pathwidth parameterized by the vertex cover number

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