Approximation algorithms for digraph width parameters

DOI10.1016/J.TCS.2014.10.009zbMATH Open1303.68157arXiv1107.4824OpenAlexW2018558025MaRDI QIDQ476883FDOQ476883

Authors: Shiva Kintali, Nishad Kothari, A. Kumar 

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Several problems that are NP-hard on general graphs are efficiently solvable on graphs with bounded treewidth. Efforts have been made to generalize treewidth and the related notion of pathwidth to digraphs. Directed treewidth, DAG-width and Kelly-width are some such notions which generalize treewidth, whereas directed pathwidth generalizes pathwidth. Each of these digraph width measures have an associated decomposition structure. In this paper, we present approximation algorithms for all these digraph width parameters. In particular, we give an O(sqrt{logn})-approximation algorithm for directed treewidth, and an O({log}^{3/2}{n})-approximation algorithm for directed pathwidth, DAG-width and Kelly-width. Our algorithms construct the corresponding decompositions whose widths are within the above mentioned approximation factors.

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

Recommendations

• Digraph width measures in parameterized algorithmics
• On digraph width measures in parameterized algorithmics
• On the algorithmic effectiveness of digraph decompositions and complexity measures
• Approximation algorithms for treewidth
• On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures

zbMATH Keywords

approximation algorithmsdirected pathwidthdirected treewidthDAG-widtharboreal decompositionDAG-decompositiondirected path decompositiondirected vertex separatorsKelly decompositionKelly-width

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Graph searching and a min-max theorem for tree-width
• A partial k-arboretum of graphs with bounded treewidth
• Searching and pebbling
• Directed tree-width
• Directed path-width and monotonicity in digraph searching
• Introducing directed tree width
• Are there any good digraph width measures?
• Complexity of Finding Embeddings in a k-Tree
• The dag-width of directed graphs
• On the algorithmic effectiveness of digraph decompositions and complexity measures
• Digraph measures: Kelly decompositions, games, and orderings
• Approximation algorithms for treewidth
• Treewidth. Computations and approximations
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Fugitive-search games on graphs and related parameters
• Intractability of clique-width parameterizations
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• DAG-Width and Parity Games
• DAG-width
• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• On digraph width measures in parameterized algorithmics
• On treewidth approximations.
• Inapproximability of treewidth, one-shot pebbling, and related layout problems

Cited In (9)

• On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
• Width-restricted layering of acyclic digraphs with consideration of dummy nodes
• On the algorithmic effectiveness of digraph decompositions and complexity measures
• On tradeoffs between width- and fill-like graph parameters
• A linear-time parameterized algorithm for computing the width of a DAG
• Parameterized Approximation Schemes Using Graph Widths
• Title not available (Why is that?)
• Digraphs of bounded width
• Directed pathwidth and palletizers

This page was built for publication: Approximation algorithms for digraph width parameters

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