10.1007/978-3-319-42634-1_8
Abu-Khzam, Faisal N.
Faisal N.
Abu-Khzam
Li, Shouwei
Shouwei
Li
Markarian, Christine
Christine
Markarian
Meyer auf der Heide, Friedhelm
Friedhelm
Meyer auf der Heide
Podlipyan, Pavel
Pavel
Podlipyan
The Monotone Circuit Value Problem with Bounded Genus Is in NC
2016
2017-10-17T12:41:19Z
2019-01-03T13:11:51Z
conference
https://ris.uni-paderborn.de/record/143
https://ris.uni-paderborn.de/record/143.json
234587 bytes
application/pdf
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].