Approximation algorithms for digraph width parameters

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 treewidt...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2015, Vol.562, p.365-376
Main Authors: Kintali, Shiva, Kothari, Nishad, Kumar, Akash
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Approximation algorithms
Arboreal decomposition
Construction
DAG-decomposition
DAG-width
Decomposition
Directed path decomposition
Directed pathwidth
Directed treewidth
Directed vertex separators
Graph theory
Graphs
Kelly decomposition
Kelly-width
Mathematical analysis
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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(log⁡n)-approximation algorithm for directed treewidth, and an O(log3/2⁡n)-approximation algorithm for directed pathwidth, DAG-width and Kelly-width. Our algorithms construct the corresponding decompositions whose widths agree with the above mentioned approximation factors.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2014.10.009