Startseite > Publikationen > Publikationen


Abu-Khzam, Faisal N. ;Li, Shouwei;Markarian, Christine;Meyer auf der Heide, Friedhelm;Podlipyan, Pavel:

The Monotone Circuit Value Problem with Bounded Genus Is in NC.

In: Dinh, Thang N. ;Thai, My T. (Hrsg.): Computing and Combinatorics, The 22nd International Computing and Combinatorics Conference, Band 9797 , S. 92--102, Aug. 2016, Springer Verlag LNCS


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



author = {Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel},
title = {The Monotone Circuit Value Problem with Bounded Genus Is in NC},
editor = {Dinh, Thang N. and Thai, My T. },
booktitle = {Computing and Combinatorics},
volume = {9797},
series = {The 22nd International Computing and Combinatorics Conference},
pages = {92--102},
publisher = {Springer Verlag LNCS},
month = aug,
year = {2016},

BibTeX in die Zwischenablage kopieren