Parameterized algorithms for directed modular width

DOI10.1007/978-3-030-39219-2_33zbMATH Open1453.68097arXiv1905.13203OpenAlexW3004208184MaRDI QIDQ779243FDOQ779243

Authors: Raphael Steiner, Sebastian Wiederrecht 

Publication date: 21 July 2020

Abstract: Many well-known NP-hard algorithmic problems on directed graphs resist efficient parametrisations with most known width measures for directed graphs, such as directed treewidth, DAG-width, Kelly-width and many others. While these focus on measuring how close a digraph is to an oriented tree resp. a directed acyclic graph, in this paper, we investigate directed modular width as a parameter, which is closer to the concept of clique-width. We investigate applications of modular decompositions of directed graphs to a wide range of algorithmic problems and derive FPT-algorithms for several well-known digraph-specific NP-hard problems, namely minimum (weight) directed feedback vertex set, minimum (weight) directed dominating set, digraph colouring, directed Hamiltonian path/cycle, partitioning into paths, (capacitated) vertex-disjoint directed paths, and the directed subgraph homeomorphism problem. The latter yields a polynomial-time algorithm for detecting topological minors in digraphs of bounded directed modular width. Finally we illustrate that also other structural digraph parameters, such as the directed pathwidth and the cycle-rank can be computed efficiently using directed modular width as a parameter.

Full work available at URL: https://arxiv.org/abs/1905.13203

Recommendations

• Digraph width measures in parameterized algorithmics
• Parameterized Algorithms for Modular-Width
• On digraph width measures in parameterized algorithmics
• On the algorithmic effectiveness of digraph decompositions and complexity measures
• On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures

zbMATH Keywords

integer linear programmingmodular decompositionfixed-parameter tractabilityparameterized complexitywidth measures

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Cited In (8)

• Acyclic coloring parameterized by directed clique-width
• Efficient computation of the oriented chromatic number of recursively defined digraphs
• Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs
• Dominance drawings for DAGs with bounded modular width
• Digraph coloring and distance to acyclicity
• A linear-time parameterized algorithm for computing the width of a DAG
• How to compute digraph width measures on directed co-graphs
• A slice theoretic approach for embedding problems on digraphs

This page was built for publication: Parameterized algorithms for directed modular width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q779243)