id: 06094038
dt: j
an: 06094038
au: Lampis, Michael; Kaouri, Georgia; Mitsou, Valia
ti: On the algorithmic effectiveness of digraph decompositions and complexity
    measures.
so: Discrete Optim. 8, No. 1, 129-138 (2011).
py: 2011
pu: Elsevier B. V., Amsterdam
la: EN
cc: 
ut: treewidth; digraph decompositions; parameterized complexity
ci: 
li: doi:10.1016/j.disopt.2010.03.010
ab: Summary: We place our focus on the gap between treewidth’s success in
    producing fixed-parameter polynomial algorithms for hard graph
    problems, and specifically {\sc Hamiltonian Circuit} and {\sc Max Cut},
    and the failure of its directed variants (directed treewidth, 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 {\sc Directed Hamiltonian Circuit} is $W[2]$-hard when the
    parameter is the width of the input graph, for any of these widths, and
    that {\sc 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 {\sc Directed Hamiltonian
    Circuit} to show that the related {\sc 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.
rv: