Modular-width: An auxiliary parameter for parameterized parallel complexity

Faisal N. Abu-Khzam; Shouwei Li; Christine Markarian; Friedhelm Meyer auf der Heide; Pavel Podlipyan

doi:10.1007/978-3-319-59605-1_13

Modular-width: An auxiliary parameter for parameterized parallel complexity

Faisal N. Abu-Khzam, Shouwei Li, Christine Markarian, Friedhelm Meyer auf der Heide, Pavel Podlipyan

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

7 Citations (Scopus)

Abstract

Many graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graphs, but become W-hard with respect to the clique-width parameter. Recently, Gajarský et al. proposed a new parameter called modular-width using the notion of modular decomposition of graphs. They showed that the chromatic number problem and the partitioning into paths problem, and hence hamiltonian path and hamiltonian cycle, are FPT when parameterized by this parameter. In this paper, we study modular-width in parameterized parallel complexity and show that the weighted maximum clique problem and the maximum matching problem are fixed-parameter parallel-tractable (FPPT) when parameterized by this parameter.

Original language	English
Title of host publication	Frontiers in Algorithmics
Editors	Mingyu Xiao, Frances Rosamond
Publisher	Springer, Cham
Pages	139-150
Number of pages	12
ISBN (Electronic)	9783319596051
ISBN (Print)	9783319596044
DOIs	https://doi.org/10.1007/978-3-319-59605-1_13
Publication status	Published - 2017
Event	11th International Frontiers of Algorithmics Workshop, FAW 2017 - Chengdu, China Duration: 23 Jun 2017 → 25 Jun 2017

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	10336
ISSN (Print)	0302-9743

Conference

Conference	11th International Frontiers of Algorithmics Workshop, FAW 2017
Country/Territory	China
City	Chengdu
Period	23/06/17 → 25/06/17

Access to Document

10.1007/978-3-319-59605-1_13

Cite this

@inproceedings{a2af653f52224db2ad80f3bc250634dd,

title = "Modular-width: An auxiliary parameter for parameterized parallel complexity",

abstract = "Many graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graphs, but become W-hard with respect to the clique-width parameter. Recently, Gajarsk{\'y} et al. proposed a new parameter called modular-width using the notion of modular decomposition of graphs. They showed that the chromatic number problem and the partitioning into paths problem, and hence hamiltonian path and hamiltonian cycle, are FPT when parameterized by this parameter. In this paper, we study modular-width in parameterized parallel complexity and show that the weighted maximum clique problem and the maximum matching problem are fixed-parameter parallel-tractable (FPPT) when parameterized by this parameter.",

author = "Abu-Khzam, {Faisal N.} and Shouwei Li and Christine Markarian and {Meyer auf der Heide}, Friedhelm and Pavel Podlipyan",

year = "2017",

doi = "10.1007/978-3-319-59605-1_13",

language = "English",

isbn = "9783319596044",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Cham",

pages = "139--150",

editor = "Mingyu Xiao and Frances Rosamond",

booktitle = "Frontiers in Algorithmics",

note = "11th International Frontiers of Algorithmics Workshop, FAW 2017 ; Conference date: 23-06-2017 Through 25-06-2017",

}

Abu-Khzam, FN, Li, S, Markarian, C, Meyer auf der Heide, F & Podlipyan, P 2017, Modular-width: An auxiliary parameter for parameterized parallel complexity. in M Xiao & F Rosamond (eds), Frontiers in Algorithmics. Lecture Notes in Computer Science, vol. 10336, Springer, Cham, pp. 139-150, 11th International Frontiers of Algorithmics Workshop, FAW 2017, Chengdu, China, 23/06/17. https://doi.org/10.1007/978-3-319-59605-1_13

Modular-width: An auxiliary parameter for parameterized parallel complexity. / Abu-Khzam, Faisal N.; Li, Shouwei; Markarian, Christine et al.
Frontiers in Algorithmics. ed. / Mingyu Xiao; Frances Rosamond. Springer, Cham, 2017. p. 139-150 (Lecture Notes in Computer Science; Vol. 10336).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

TY - GEN

T1 - Modular-width

T2 - 11th International Frontiers of Algorithmics Workshop, FAW 2017

AU - Abu-Khzam, Faisal N.

AU - Li, Shouwei

AU - Markarian, Christine

AU - Meyer auf der Heide, Friedhelm

AU - Podlipyan, Pavel

PY - 2017

Y1 - 2017

N2 - Many graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graphs, but become W-hard with respect to the clique-width parameter. Recently, Gajarský et al. proposed a new parameter called modular-width using the notion of modular decomposition of graphs. They showed that the chromatic number problem and the partitioning into paths problem, and hence hamiltonian path and hamiltonian cycle, are FPT when parameterized by this parameter. In this paper, we study modular-width in parameterized parallel complexity and show that the weighted maximum clique problem and the maximum matching problem are fixed-parameter parallel-tractable (FPPT) when parameterized by this parameter.

AB - Many graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graphs, but become W-hard with respect to the clique-width parameter. Recently, Gajarský et al. proposed a new parameter called modular-width using the notion of modular decomposition of graphs. They showed that the chromatic number problem and the partitioning into paths problem, and hence hamiltonian path and hamiltonian cycle, are FPT when parameterized by this parameter. In this paper, we study modular-width in parameterized parallel complexity and show that the weighted maximum clique problem and the maximum matching problem are fixed-parameter parallel-tractable (FPPT) when parameterized by this parameter.

UR - http://www.scopus.com/inward/record.url?scp=85021705618&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-59605-1_13

DO - 10.1007/978-3-319-59605-1_13

M3 - Conference Paper published in Proceedings

AN - SCOPUS:85021705618

SN - 9783319596044

T3 - Lecture Notes in Computer Science

SP - 139

EP - 150

BT - Frontiers in Algorithmics

A2 - Xiao, Mingyu

A2 - Rosamond, Frances

PB - Springer, Cham

Y2 - 23 June 2017 through 25 June 2017

ER -

Modular-width: An auxiliary parameter for parameterized parallel complexity

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this