Lampis, Michael; Kaouri, Georgia; Mitsou, Valia 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]. Cited in 8 Documents 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 Keywords:treewidth; digraph decompositions; parameterized complexity PDFBibTeX XMLCite \textit{M. Lampis} et al., Lect. Notes Comput. Sci. 5369, 220--231 (2008; Zbl 1183.68312) Full Text: DOI