Counting matrix partitions of graphs

详细信息    查看全文

• 作者：Martin Dyer^a ; Leslie Ann Goldberg^b ; David Richerby^b ; ^{david.richerby@cs.ox.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Matrix partitions of graphs ; Complexity of counting ; Complexity dichotomy ; #P-completeness
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 November 2016
• 年：2016
• 卷：213
• 期：Complete
• 页码：76-92
• 全文大小：505 K

文摘

Given a symmetric matrix class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si10.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=b5fc379955006cd5e41053b8bbf2e721">class="imgLazyJSB inlineImage" height="17" width="113" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16302189-si10.gif">class="mathContainer hidden">class="mathCode">$M\in {\{0,1,\ast \}}^{D\times D}$, an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si11.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=1750eeba9862b1fce9a11669839235ed" title="Click to view the MathML source">Mclass="mathContainer hidden">class="mathCode">$M$-partition of a graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si5.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=1247fab1fbc9a897ced99a57e517a0c5" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ is a function from class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si13.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=10c79920053c4a1d1dd04252449ce64f" title="Click to view the MathML source">V(G)class="mathContainer hidden">class="mathCode">$V\left(G\right)$ to class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si14.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=7029ed6b70f6acc735ffafecfc3d5222" title="Click to view the MathML source">Dclass="mathContainer hidden">class="mathCode">$D$ such that no edge of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si5.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=1247fab1fbc9a897ced99a57e517a0c5" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ is mapped to a class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si16.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=a78adec3682db8af4a9c58fe7d52eb66" title="Click to view the MathML source">0class="mathContainer hidden">class="mathCode">$0$ of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si11.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=1750eeba9862b1fce9a11669839235ed" title="Click to view the MathML source">Mclass="mathContainer hidden">class="mathCode">$M$ and no non-edge to a class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si18.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=2642f7229c42c6d068ac7984a08628bf" title="Click to view the MathML source">1class="mathContainer hidden">class="mathCode">$1$. We give a computer-assisted proof that, when class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si19.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=3e42b363a0e62647558ad7d16723b22f" title="Click to view the MathML source">|D|=4class="mathContainer hidden">class="mathCode">$\left|D\right|=4$, the problem of counting the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si11.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=1750eeba9862b1fce9a11669839235ed" title="Click to view the MathML source">Mclass="mathContainer hidden">class="mathCode">$M$-partitions of an input graph is either in class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si21.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=5e373751ee3978b0e0f1b9f2a919e8df">class="imgLazyJSB inlineImage" height="11" width="17" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16302189-si21.gif">class="mathContainer hidden">class="mathCode">$\mathrm{FP}$ or is class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si22.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=f364bcd929098ab75a9499d11566151e">class="imgLazyJSB inlineImage" height="11" width="20" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16302189-si22.gif">class="mathContainer hidden">class="mathCode">$\mathrm{\#P}$-complete. Tractability is proved by reduction to the related problem of counting list class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si11.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=1750eeba9862b1fce9a11669839235ed" title="Click to view the MathML source">Mclass="mathContainer hidden">class="mathCode">$M$-partitions; intractability is shown using a gadget construction and interpolation. We use a computer program to determine which of the two cases holds for all but a small number of matrices, which we resolve manually to establish the dichotomy. We conjecture that the dichotomy also holds for class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si24.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=1087eaaba3bd04294448660712d87fa9" title="Click to view the MathML source">|D|>4class="mathContainer hidden">class="mathCode">$\left|D\right|>4$. More specifically, we conjecture that, for any symmetric matrix class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si10.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=b5fc379955006cd5e41053b8bbf2e721">class="imgLazyJSB inlineImage" height="17" width="113" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16302189-si10.gif">class="mathContainer hidden">class="mathCode">$M\in {\{0,1,\ast \}}^{D\times D}$, the complexity of counting class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si11.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=1750eeba9862b1fce9a11669839235ed" title="Click to view the MathML source">Mclass="mathContainer hidden">class="mathCode">$M$-partitions is the same as the related problem of counting list class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302189&_mathId=si11.gif&_user=111111111&_pii=S0166218X16302189&_rdoc=1&_issn=0166218X&md5=1750eeba9862b1fce9a11669839235ed" title="Click to view the MathML source">Mclass="mathContainer hidden">class="mathCode">$M$-partitions.