Change search
ReferencesLink to record
Permanent link

Direct link
On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
University of New York.
2011 (English)In: Discrete Optimization, ISSN 1572-5286, Vol. 8, no 1, 129-138 p.Article in journal (Refereed) Published
Abstract [en]

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 treewidth (Johnson et al., 2001 [13]), DAG-width (Obdrzalek, 20061141) and Kelly-width (Hunter and Kreutzer, 2007[15]) 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. Along the way, we extend our reduction for DIRECTED HAMILTONIAN CIRCUIT to show that the related MINIMUM LEAF OUTBRANCHING problem is also W[2]-hard when naturally parameterized by the number of leaves of the solution, even if the input graph has constant width. All our results also apply to directed pathwidth and cycle rank.

Place, publisher, year, edition, pages
2011. Vol. 8, no 1, 129-138 p.
Keyword [en]
Treewidth, Digraph decompositions, Parameterized complexity
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-58604DOI: 10.1016/j.disopt.2010.03.010ISI: 000289018300012OAI: diva2:473413
QC 20120109Available from: 2012-01-05 Created: 2012-01-05 Last updated: 2012-01-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Lampis, Michael
In the same journal
Discrete Optimization
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 17 hits
ReferencesLink to record
Permanent link

Direct link