期刊
THEORETICAL COMPUTER SCIENCE
卷 384, 期 1, 页码 111-125出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2007.05.023
关键词
#P-completeness; holographic reduction; vertex cover; matching
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据