On the parameterized parallel complexity and the vertex cover problem

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

    Efficiently parallelizable parameterized problems have been classified as being either in the class FPP (fixed-parameter parallelizable) or the class PNC (parameterized analog of NC), which contains FPP as a subclass. In this paper, we propose a more restrictive class of parallelizable parameterized problems called fixed-parameter parallel-tractable (FPPT). For a problem to be in FPPT, it should possess an efficient parallel algorithm not only from a theoretical standpoint but in practice as well. The primary distinction between FPPT and FPP is the parallel processor utilization, which is bounded by a polynomial function in the case of FPPT. We initiate the study of FPPT with the well-known kvertex cover problem. In particular, we present a parallel algorithm that outperforms the best known parallel algorithm for this problem: using O(m) instead of O(n2) parallel processors, the running time improves from 4 log n+O(kk) to O(k · log3 n), where m is the number of edges, n is the number of vertices of the input graph, and k is an upper bound of the size of the sought vertex cover. We also note that a few P-complete problems fall into FPPT including the monotone circuit value problem (MCV) when the underlying graphs are bounded by a constant Euler genus.

    Original languageEnglish
    Title of host publicationProceeding of 10th International Conference on Combinatorial Optimization and Applications, COCOA 2016
    EditorsT.H Chan , M. Li , L. Wang
    Place of PublicationCham
    PublisherSpringer
    Pages477-488
    Number of pages12
    ISBN (Print)9783319487489
    DOIs
    Publication statusPublished - 2016
    EventConference on Combinatorial Optimization and Applications (COCOA 2016 10th) - Hong Kong, China
    Duration: 16 Dec 201618 Dec 2016
    Conference number: 2016 (10th)

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume10043 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    ConferenceConference on Combinatorial Optimization and Applications (COCOA 2016 10th)
    Abbreviated titleCOCOA
    CountryChina
    CityHong Kong
    Period16/12/1618/12/16

    Fingerprint Dive into the research topics of 'On the parameterized parallel complexity and the vertex cover problem'. Together they form a unique fingerprint.

  • Cite this

    Abu-Khzam, F. N., Li, S., Markarian, C., Meyer auf der Heide, F., & Podlipyan, P. (2016). On the parameterized parallel complexity and the vertex cover problem. In T. H. Chan , M. Li , & L. Wang (Eds.), Proceeding of 10th International Conference on Combinatorial Optimization and Applications, COCOA 2016 (pp. 477-488). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10043 LNCS). Springer. https://doi.org/10.1007/978-3-319-48749-6_35