Journal
THEORETICAL COMPUTER SCIENCE
Volume 384, Issue 1, Pages 111-125Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2007.05.023
Keywords
#P-completeness; holographic reduction; vertex cover; matching
Categories
Ask authors/readers for more resources
A variety of counting problems on 3-regular planar graphs are considered in this paper. We give a sufficient condition which guarantees that the coefficients of a homogeneous polynomial can be uniquely determined by its values on a recurrence sequence. This result enables us to use the polynomial interpolation technique in high dimension to prove the #P-completeness of problems on graphs with special requirements. Using this method, we show that #3-Regular Bipartite Planar Vertex Covers is #P-complete. Furthermore, we use Valiant's Holant Theorem to construct a holographic reduction from it to #2,3-Regular Bipartite Planar Matchings, establishing the #P-completeness of the latter. Finally, we completely classify the problems #Planar Read-twice 3SAT with different ternary symmetric relations according to their computational complexity, by giving several more applications of holographic reduction in proving the #P-completeness of the corresponding counting problems. (c) 2007 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available