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

doi:10.1007/978-3-319-42634-1_8

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 proceeding › Conference Paper published in Proceedings › peer-review

2 Citations (Scopus)

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 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	https://doi.org/10.1007/978-3-319-42634-1_8
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/Territory	Viet Nam
City	Ho Chi Minh City
Period	2/08/16 → 4/08/16

Access to Document

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

Cite this

@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]. {\textcopyright} 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",

note = "International Conference on Computing and Combinatorics (COCOON 2016 22nd), COCOON ; Conference date: 02-08-2016 Through 04-08-2016",

}

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 et al.
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 proceeding › Conference Paper published in Proceedings › 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

N1 - Conference code: 2016 (22nd)

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

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

Y2 - 2 August 2016 through 4 August 2016

ER -

The Monotone Circuit Value Problem with Bounded Genus Is in NC

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this