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 proceedingConference Paper published in Proceedings

    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 languageEnglish
    Title of host publicationFrontiers in Algorithmics
    EditorsMingyu Xiao, Frances Rosamond
    PublisherSpringer, Cham
    Pages139-150
    Number of pages12
    ISBN (Electronic)9783319596051
    ISBN (Print)9783319596044
    DOIs
    Publication statusPublished - 2017
    Event11th International Frontiers of Algorithmics Workshop, FAW 2017 - Chengdu, China
    Duration: 23 Jun 201725 Jun 2017

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume10336
    ISSN (Print)0302-9743

    Conference

    Conference11th International Frontiers of Algorithmics Workshop, FAW 2017
    CountryChina
    CityChengdu
    Period23/06/1725/06/17

    Fingerprint Dive into the research topics of 'Modular-width: An auxiliary parameter for parameterized parallel complexity'. Together they form a unique fingerprint.

  • Cite this

    Abu-Khzam, F. N., 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 (pp. 139-150). (Lecture Notes in Computer Science; Vol. 10336). Springer, Cham. https://doi.org/10.1007/978-3-319-59605-1_13