Parameterized Algorithms for Modular-Width

D 2013

Parameterized Algorithms for Modular-Width

GAJARSKÝ, Jakub, Michael LAMPIS and Sebastian ORDYNIAK

Basic information

Original name

Parameterized Algorithms for Modular-Width

Authors

GAJARSKÝ, Jakub (703 Slovakia, guarantor, belonging to the institution), Michael LAMPIS (300 Greece) and Sebastian ORDYNIAK (276 Germany, belonging to the institution)

Edition

Berlin Heidelberg, Parameterized and Exact Computation, p. 163-176, 14 pp. 2013

Publisher

Springer International Publishing

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/13:00066750

Organization unit

Faculty of Informatics

ISBN

978-3-319-03897-1

ISSN

DOI

http://dx.doi.org/10.1007/978-3-319-03898-8_15

Keywords in English

parameterized complexity; modular width; shrub depth; chromatic number; hamiltonian path

Abstract

V originále

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 ILP 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.

Links

EE2.3.30.0009, research and development project

Name: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci

GAP202/11/0196, research and development project

Name: Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů

Investor: Czech Science Foundation, Well-structured combinatorial classes, width parameters, and design of efficient algorithms

MUNI/A/0739/2012, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Acronym: SKOMU)

Investor: Masaryk University, Category A

MUNI/A/0760/2012, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Acronym: FI MAV II.)

Investor: Masaryk University, Category A

Citovat

GAJARSKÝ, Jakub, Michael LAMPIS and Sebastian ORDYNIAK. Parameterized Algorithms for Modular-Width. In Gutin, Gregory and Szeider, Stefan. Parameterized and Exact Computation. Berlin Heidelberg: Springer International Publishing, 2013, p. 163-176. ISBN 978-3-319-03897-1. Available from: https://dx.doi.org/10.1007/978-3-319-03898-8_15.

@inproceedings{1159488,
   author = {Gajarský, Jakub and Lampis, Michael and Ordyniak, Sebastian},
   address = {Berlin Heidelberg},
   booktitle = {Parameterized and Exact Computation},
   doi = {http://dx.doi.org/10.1007/978-3-319-03898-8_15},
   editor = {Gutin, Gregory and Szeider, Stefan},
   keywords = {parameterized complexity; modular width; shrub depth; chromatic number; hamiltonian path},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Berlin Heidelberg},
   isbn = {978-3-319-03897-1},
   pages = {163-176},
   publisher = {Springer International Publishing},
   title = {Parameterized Algorithms for Modular-Width},
   year = {2013}
}

TY  - JOUR
ID  - 1159488
AU  - Gajarský, Jakub - Lampis, Michael - Ordyniak, Sebastian
PY  - 2013
TI  - Parameterized Algorithms for Modular-Width
PB  - Springer International Publishing
CY  - Berlin Heidelberg
SN  - 9783319038971
KW  - parameterized complexity
KW  - modular width
KW  - shrub depth
KW  - chromatic number
KW  - hamiltonian path
N2  - 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 ILP 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.
ER  -

GAJARSKÝ, Jakub, Michael LAMPIS and Sebastian ORDYNIAK. Parameterized Algorithms for Modular-Width. In Gutin, Gregory and Szeider, Stefan. \textit{Parameterized and Exact Computation}. Berlin Heidelberg: Springer International Publishing, 2013, p.~163-176. ISBN~978-3-319-03897-1. Available from: https://dx.doi.org/10.1007/978-3-319-03898-8\_{}15.

Detailed Information on Publication Record