Treewidth and pathwidth parameterized by the vertex cover number

DOI10.1016/J.DAM.2014.12.012zbMATH Open1350.68136arXiv1305.0433OpenAlexW2027513055MaRDI QIDQ344839FDOQ344839

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

Publication date: 24 November 2016

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

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.

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

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

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)

Cites Work

• On exact algorithms for treewidth
• A Dynamic Programming Approach to Sequencing Problems
• Title not available (Why is that?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Exact exponential algorithms.
• A note on exact algorithms for vertex ordering problems on graphs
• Title not available (Why is that?)
• Computing Directed Pathwidth in O(1.89 n ) Time
• Improved upper bounds for vertex cover
• The vertex separation number of a graph equals its path-width
• Finding induced subgraphs via minimal triangulations
• Graph Layout Problems Parameterized by Vertex Cover
• Fourier meets M\"{o}bius: fast subset convolution
• On cutwidth parameterized by vertex cover
• Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
• On sparsification for computing treewidth
• Treewidth and Pathwidth Parameterized by the Vertex Cover Number
• Kernel bounds for structural parameterizations of pathwidth
• A parameterized algorithm for chordal sandwich
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization

Cited In (7)

• Title not available (Why is that?)
• Treewidth and Pathwidth Parameterized by the Vertex Cover Number
• Treedepth Parameterized by Vertex Cover Number.
• Finding optimal triangulations parameterized by edge clique cover
• The parameterized complexity of maximum betweenness centrality
• On cutwidth parameterized by vertex cover
• Maximum Minimal Vertex Cover Parameterized by Vertex Cover

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)