Holant problems and holographic reduction: simple graphs or multigraphs?

Question

From what I can understand, Holographic reductions for Holant problems are used to show #P-hardness or polynomial time computability of certain counting problems on undirected graphs that have very restricted forms (for instance, 3-regular graphs, or 2-3-regular bipartite graphs).

My concern is about the confusion between the use of the word "graph" to mean either a) a simple graph, without self-loops and parallel edges or b) a multigraph, that can have self-loops and parallel edges (i.e., multiple edges between the same pair of vertices). I will first expose my problem by examples, then ask more precisely my questions.

Examples:

• In the paper Cai, Lu and Xia, Holographic Reduction, Interpolation and Hardness, 2012, the authors provide a dichotomy for all problems of the form $\mathrm{Holant}([x,y,z][t_1,t_2,t_3,t_4])$, so over 2-3-regular bipartite graphs. They do not specify if they talk about simple graphs or multigraphs. A search for "self loops" reveals that they might be using graphs with self loops, but this is not very explicit (and what about parallel edges?). However nowhere else in the paper this distinction is discussed, and all the gadgets they use seem to be simple graphs (in the Appendix).

• In Tyson Williams' thesis, by default the graphs considered are multigraphs (see page 4). He also says that Holant problems always consider multigraphs, suggesting that the first paper I cited considers multigraphs. In some of his results, he mentions the distinction between the two notions of graphs: for instance, Theorem 10.2.7 states that some problem is hard on 3-regular multigraphs, and he shows in Theorem 10.2.8 that the same problem is aslo hard on 3-regular simple graphs. By looking at the proof you see that the trick used is specific to this particular problem.

• In the paper Xia, Zhang and Zhao, Computational complexity of counting problems on 3-regular planar graphs, 2007, the abstract talks about 3-regular graphs. When I first read it I thought that they are considering simple graphs, but actually I did not find a place where they say this.

At this point, I want to say that this post is not a critic to the authors of all these papers (I know that this kind of details can be annoying to present rigorously), the goal is just to clarify what is happening here.

Questions:

1) Do all the PTIME results of, say, the first paper I cite, work for multigraphs?

2) Do all the hardness results of that paper work for 2-3-regular simple bipartite graphs?

3) If not, is there a simple general fix so that the hardness results work for simple graphs, or does one have to find an ad hoc patch for each one of these problems? (for example, as in Theorem 10.2.8 of Tyson Williams' thesis)

4) If yes, do they also work for 2-3-regular simple graph that also satisfy this special property: no two nodes of the partition of degree 2 have the same neighbors. This condition would insure that, when you take a 2-3-regular simple graph that satisfies this, then contracting the nodes in the partition of degree 2 would always give a 3-regular simple graph. (without this condition, we could end up with parallel edges.)

This post is also related to this post and this one, where the same kind of confusion arose (a positive answer to question 4) would solve these problems). I decided to create a new question because I realized that the problem is more general that the ones exposed in these posts.

Answer 1

My concern is about the confusion between the use of the word "graph" to mean either a) a simple graph, without self-loops and parallel edges or b) a multigraph, that can have self-loops and parallel edges (i.e., multiple edges between the same pair of vertices).

In the literature about Holant problems, the word "graph" should be read as "multigraph" unless otherwise stated. As you noticed, I tried to be more explicit about this in my thesis. In my experience, different areas of math use terms mostly consistently within their own area but in ways that would be contradictory when considering multiple areas and read strictly.

In your first example, the proper notation is $\mathrm{Holant}([x,y,z]|[t_1,t_2,t_3,t_4])$. This means that the input graphs are bipartite with one part having only vertices of degree 2 (and assigned the symmetric binary function $[x,y,z]$) and the other part having only vertices of degree 3 (and assigned the symmetric ternary function [t_1, t_2, t_3, t_4]).

Also (and I am sure you know this, but to be clear), a bipartite graph cannot have self loops. So if a bipartite graph is not a simple graph, then it is because it has parallel edges.

1) Yes

2) Not immediately. I think you have correctly observed that their reductions work for simple graphs. It remains to verify if the hard problems that they were reduced from are also hard when further restricted to simple graphs.

3) There is no general fix. In general, you have to reduce from problems that are hard for simple graphs.

4) Gadget 2 does not satisfy your condition. Consider $N_1$. The only two vertices of degree 2 without dangling edges have the same neighbor set.