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 Proceedings

    Abstract

    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
    PublisherSpringer
    Pages92-102
    Number of pages11
    Volume9797
    ISBN (Print)978-3-319-42633-4
    DOIs
    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
    PublisherSpringer
    Volume9797

    Conference

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

      Fingerprint

    Cite this

    Abu Khzam, F., LI, S., Markarian, C., Auf Der Heide, F. M., & Podlipyan, P. (2016). The Monotone Circuit Value Problem with Bounded Genus Is in NC. In T. N. Dinh, & M. T. Thai (Eds.), Computing and Combinatorics (Vol. 9797, pp. 92-102). (Lecture Notes in Computer Series; Vol. 9797). Springer. https://doi.org/10.1007/978-3-319-42634-1_8