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

    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

    Networks (circuits)
    Parallel algorithms

    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). Switzerland: Springer. https://doi.org/10.1007/978-3-319-42634-1_8
    Abu Khzam, Faisal ; LI, S ; Markarian, C ; Auf Der Heide, F.M. ; Podlipyan, P. / The Monotone Circuit Value Problem with Bounded Genus Is in NC. Computing and Combinatorics. editor / Thang N. Dinh ; My T. Thai. Vol. 9797 Switzerland : Springer, 2016. pp. 92-102 (Lecture Notes in Computer Series).
    @inproceedings{a394d7063c1b4419901134ce205049fb,
    title = "The Monotone Circuit Value Problem with Bounded Genus Is in NC",
    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]. {\circledC} Springer International Publishing Switzerland 2016.",
    author = "{Abu Khzam}, Faisal and S LI and C Markarian and {Auf Der Heide}, F.M. and P Podlipyan",
    year = "2016",
    doi = "10.1007/978-3-319-42634-1_8",
    language = "English",
    isbn = "978-3-319-42633-4",
    volume = "9797",
    series = "Lecture Notes in Computer Series",
    publisher = "Springer",
    pages = "92--102",
    editor = "Dinh, {Thang N.} and Thai, {My T.}",
    booktitle = "Computing and Combinatorics",
    address = "Switzerland",

    }

    Abu Khzam, F, LI, S, Markarian, C, Auf Der Heide, FM & Podlipyan, P 2016, The Monotone Circuit Value Problem with Bounded Genus Is in NC. in TN Dinh & MT Thai (eds), Computing and Combinatorics. vol. 9797, Lecture Notes in Computer Series, vol. 9797, Springer, Switzerland, pp. 92-102, International Conference on Computing and Combinatorics (COCOON 2016 22nd), Ho Chi Minh City, Viet Nam, 2/08/16. https://doi.org/10.1007/978-3-319-42634-1_8

    The Monotone Circuit Value Problem with Bounded Genus Is in NC. / Abu Khzam, Faisal; LI, S; Markarian, C; Auf Der Heide, F.M.; Podlipyan, P.

    Computing and Combinatorics. ed. / Thang N. Dinh; My T. Thai. Vol. 9797 Switzerland : Springer, 2016. p. 92-102 (Lecture Notes in Computer Series; Vol. 9797).

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

    TY - GEN

    T1 - The Monotone Circuit Value Problem with Bounded Genus Is in NC

    AU - Abu Khzam, Faisal

    AU - LI, S

    AU - Markarian, C

    AU - Auf Der Heide, F.M.

    AU - Podlipyan, P

    PY - 2016

    Y1 - 2016

    N2 - 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.

    AB - 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.

    UR - http://www.scopus.com/inward/record.url?scp=84979205111&partnerID=8YFLogxK

    U2 - 10.1007/978-3-319-42634-1_8

    DO - 10.1007/978-3-319-42634-1_8

    M3 - Conference Paper published in Proceedings

    SN - 978-3-319-42633-4

    VL - 9797

    T3 - Lecture Notes in Computer Series

    SP - 92

    EP - 102

    BT - Computing and Combinatorics

    A2 - Dinh, Thang N.

    A2 - Thai, My T.

    PB - Springer

    CY - Switzerland

    ER -

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