The Monotone Circuit Value Problem with Bounded Genus Is in NC

Faisal Abu Khzam, S LI, C Markarian, F.M. Auf Der Heide, P Podlipyan

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-review


    We present an efficient parallel algorithm for the general Monotone Circuit Value Problem (MCVP) with n gates and an underlying graph of bounded genus k. Our algorithm generalizes a recent result by Limaye et al. who showed that MCVP with toroidal embedding (genus 1) is in NC when the input contains a toroidal embedding of the circuit. In addition to extending this result from genus 1 to any bounded genus k, and unlike the work reported by Limaye et al., we do not require a precomputed embedding to be given. Most importantly, our results imply that given a P-complete problem, it is possible to find an algorithm that makes the problem fall into NC by fixing one or more parameters. Hence, we deduce the interesting analogy: Fixed Parameter Parallelizable (FPP) is with respect to P-complete what Fixed Parameter Tractable (FPT) is with respect to NP-complete. Similar work that uses treewidth as parameter was also presented by Elberfeld et al. in [6]. © Springer International Publishing Switzerland 2016.
    Original languageEnglish
    Title of host publicationComputing and Combinatorics
    EditorsThang N. Dinh, My T. Thai
    Place of PublicationSwitzerland
    Number of pages11
    ISBN (Print)978-3-319-42633-4
    Publication statusPublished - 2016
    EventInternational Conference on Computing and Combinatorics (COCOON 2016 22nd) - Ho Chi Minh City, Viet Nam
    Duration: 2 Aug 20164 Aug 2016
    Conference number: 2016 (22nd)

    Publication series

    NameLecture Notes in Computer Series


    ConferenceInternational Conference on Computing and Combinatorics (COCOON 2016 22nd)
    Abbreviated titleCOCOON
    CountryViet Nam
    CityHo Chi Minh City


    Dive into the research topics of 'The Monotone Circuit Value Problem with Bounded Genus Is in NC'. Together they form a unique fingerprint.

    Cite this