### Abstract

Original language | English |
---|---|

Title of host publication | Computing and Combinatorics |

Editors | Thang N. Dinh, My T. Thai |

Place of Publication | Switzerland |

Publisher | Springer |

Pages | 92-102 |

Number of pages | 11 |

Volume | 9797 |

ISBN (Print) | 978-3-319-42633-4 |

DOIs | |

Publication status | Published - 2016 |

Event | International Conference on Computing and Combinatorics (COCOON 2016 22nd) - Ho Chi Minh City, Viet Nam Duration: 2 Aug 2016 → 4 Aug 2016 Conference number: 2016 (22nd) |

### Publication series

Name | Lecture Notes in Computer Series |
---|---|

Publisher | Springer |

Volume | 9797 |

### Conference

Conference | International Conference on Computing and Combinatorics (COCOON 2016 22nd) |
---|---|

Abbreviated title | COCOON |

Country | Viet Nam |

City | Ho Chi Minh City |

Period | 2/08/16 → 4/08/16 |

### Fingerprint

### Cite this

*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

}

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

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › Research › peer-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 -