The Monotone Circuit Value Problem with Bounded Genus Is in NC
Abu-Khzam, Faisal N.
Li, Shouwei
Markarian, Christine
Meyer auf der Heide, Friedhelm
Podlipyan, Pavel
ddc:000
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].
2016
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://ris.uni-paderborn.de/record/143
Abu-Khzam FN, Li S, Markarian C, Meyer auf der Heide F, Podlipyan P. The Monotone Circuit Value Problem with Bounded Genus Is in NC. In: <i>Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON)</i>. LNCS. ; 2016:92-102. doi:<a href="https://doi.org/10.1007/978-3-319-42634-1_8">10.1007/978-3-319-42634-1_8</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-42634-1_8
info:eu-repo/semantics/closedAccess