Approximation Algorithms for Directed Width Parameters
Shiva Kintali, Nishad Kothari, Akash S. Kumar · 2011
Treewidth of an undirected graph measures how close the graph is to being a tree. Several problems that are NP-hard on general graphs are solvable in polynomial time on graphs with bounded treewidth. Motivated by the success of treewidth, several directed analogues of treewidth have been introduced to measure the similarity of a directed graph to a directed acyclic graph (DAG). Directed treewidth, Dwidth, DAG-width, Kelly-width and directed pathwidth are some such parameters. In this paper, we present the first approximation algorithms for all these five directed width parameters. For directed treewidth and D-width we achieve an approximation factor of O( √ log n). For DAG-width, Kelly-width and directed pathwidth we achieve an O(log 3 2n) approximation factor. Our algorithms are constructive, i.e., they construct the decompositions associated with these parameters. The width of these decompositions are within the above mentioned factor of the corresponding optimal width.