×

On the algorithmic effectiveness of digraph decompositions and complexity measures. (English) Zbl 1183.68312

Hong, Seok-Hee (ed.) et al., Algorithms and computation. 19th international symposium, ISAAC 2008, Gold Coast, Australia, December 15–17, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-92181-3/pbk). Lecture Notes in Computer Science 5369, 220-231 (2008).
Summary: We place our focus on the gap between treewidth’s success in producing fixed-parameter polynomial algorithms for hard graph problems, and specifically Hamiltonian Circuit and Max Cut, and the failure of its directed variants (directed tree-width, DAG-width and Kelly-width) to replicate it in the realm of digraphs. We answer the question of why this gap exists by giving two hardness results: we show that Directed Hamiltonian Circuit is \(W\)[2]-hard when the parameter is the width of the input graph, for any of these widths, and that Max Di Cut remains NP-hard even when restricted to DAGs, which have the minimum possible width under all these definitions. Our results also apply to directed pathwidth.
For the entire collection see [Zbl 1154.68014].

MSC:

68Q25 Analysis of algorithms and problem complexity
05C20 Directed graphs (digraphs), tournaments
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI