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 Proceedingspeer-review


    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
    Number of pages12
    ISBN (Print)9783319487489
    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


    ConferenceConference on Combinatorial Optimization and Applications (COCOA 2016 10th)
    Abbreviated titleCOCOA
    CityHong Kong


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

    Cite this