Parameterized Algorithms for Modular-Width

DOI10.1007/978-3-319-03898-8_15MaRDI QIDQ2867081zbMATH OpenOpenAlexFDO

Authors Jakub Gajarský, Michael Lampis, Sebastian Ordyniak

Publication date 10 December 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

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

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: It is known that a number of natural graph problems which are FPT parameterized by treewidth become W-hard when parameterized by clique-width. It is therefore desirable to find a different structural graph parameter which is as general as possible, covers dense graphs but does not incur such a heavy algorithmic penalty. The main contribution of this paper is to consider a parameter called modular-width, defined using the well-known notion of modular decompositions. Using a combination of ILPs and dynamic programming we manage to design FPT algorithms for Coloring and Partitioning into paths (and hence Hamiltonian path and Hamiltonian cycle), which are W-hard for both clique-width and its recently introduced restriction, shrub-depth. We thus argue that modular-width occupies a sweet spot as a graph parameter, generalizing several simpler notions on dense graphs but still evading the "price of generality" paid by clique-width.

Recommendations

Cited in

(88)

This page was built for publication: Parameterized Algorithms for Modular-Width

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