<p>Holant problems are an important framework to study counting problems. In the present paper, we give a complexity dichotomy theorem for Holant problems on 3-regular bipartite graphs. Specifically, given a non-negative ternary signature <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10206_Article_IEq1.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{f}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">f</mi> </mrow> </math></EquationSource> </InlineEquation> (not necessarily symmetric), we prove that the bipartite Holant problem Holant(<InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10206_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{f}\varvec{|}\varvec{=}_{\varvec{3}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">f</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">|</mo> </mrow> <msub> <mrow> <mo mathvariant="bold">=</mo> </mrow> <mrow> <mn mathvariant="bold">3</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation>) is <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10206_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\#$</EquationSource> <EquationSource Format="MATHML"><math> <mo>#</mo> </math></EquationSource> </InlineEquation>P-hard except for <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10206_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="53" /> </InlineMediaObject> <EquationSource Format="TEX">$(\varvec{f}\varvec{|}\varvec{=}_{\varvec{3}})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mrow> <mi mathvariant="bold-italic">f</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">|</mo> </mrow> <msub> <mrow> <mo mathvariant="bold">=</mo> </mrow> <mrow> <mn mathvariant="bold">3</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10206_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{\mathcal {A}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-script">A</mi> </mrow> </math></EquationSource> </InlineEquation>-transformable or <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10206_Article_IEq6.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{\mathcal {P}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-script">P</mi> </mrow> </math></EquationSource> </InlineEquation>-transformable, in which cases the problem is tractable.</p>

Dichotomy for Non-negative Valued Holant Problems on 3-Regular Bipartite Graphs

期刊论文
发表日期：

2025年1月15日

查看全文

Junda Li,
Yuan Huang,
Yanlin Zheng

摘要

Holant problems are an important framework to study counting problems. In the present paper, we give a complexity dichotomy theorem for Holant problems on 3-regular bipartite graphs. Specifically, given a non-negative ternary signature $\varvec{f}$ $f$ (not necessarily symmetric), we prove that the bipartite Holant problem Holant( $\varvec{f}\varvec{|}\varvec{=}_{\varvec{3}}$ $f | =_{3}$ ) is $\#$ $#$ P-hard except for $(\varvec{f}\varvec{|}\varvec{=}_{\varvec{3}})$ $(f | =_{3})$ is $\varvec{\mathcal {A}}$ $A$ -transformable or $\varvec{\mathcal {P}}$ $P$ -transformable, in which cases the problem is tractable.