A variant of #POSITIVE-2-DNF

Question

Let $G=(V,E)$ be an undirected graph. I call a valuation of $G$ a function $\nu: V \to E$ that maps every node $x \in V$ to an edge incident to $x$ (so that there are $\prod_{x \in V} d(x)$ valuations of $G$, where $d(x)$ is the degree of node $x$). I say that $\nu$ is satisfying if there exist an edge $e\in E$ such that both endpoints of $e$ are mapped to $e$ by $\nu$. I am interested in the following problem:

INPUT: An undirected graph $G$

OUTPUT: The number of satisfying valuations of $G$

My question: What is the complexity of this problem, and does it already have a name?

My guess is that it is #P-hard, even for bipartite graphs. A closely related #P-hard problem is #POSITIVE-2-DNF, or even #PARTITIONED-POSITIVE-2-DNF. Indeed, you can see an instance of #(PARTITIONED-)POSITIVE-2-DNF as a (bipartite) graph $G$, and you say that a valuation of $G$ either maps a node $x$ to all of its incident edges or to none of them. So my problem is somewhat a variant of #POSITIVE-2-DNF, but where valuations map variables to a single clause in which they occur, instead of mapping them to $0$ of $1$.

==== UPDATE ====

As a3nm showed in his answer, the problem is hard on 3-regular graphs with multi-edges. There are 2 questions left now (the first one I care about, the second one not so much but this would be nice to know):

1) Is the problem hard on bipartite graphs with multi-edges?

2) Can we get rid of the multi-edges?

Answer 1

Note: this reduction is written in the wrong direction, and when fixed it only works for multigraphs. See explanations in the edit to the original question.

I think the problem is #P-hard already on 3-regular graphs using the results of Cai, Lu and Xia, Holographic Reduction, Interpolation and Hardness, 2012. I will do this by showing the #P-hardness of counting the non-satisfying valuations of $G$, i.e., the valuations $\nu$ where for every edge $e$ at least one of the endpoints of $e$ is not mapped to $e$ by $\nu$. Indeed, counting this reduces in PTIME to counting the satisfying valuations of $G$ as you ask: this uses the fact that the total number of valuations (both satisfying and non-satisfying) can be computed in PTIME, using the closed-form formula in your question.

To show the hardness of counting non-satisfying valuations on 3-regular graphs, consider a 3-regular graph $G = (V, E)$, and construct the bipartite graph $G' = (V \cup E, W)$ between $V$ and $E$: it is a 2-3-regular graph in the sense that vertices in $V$ all have degree $3$ and vertices in $E$ all have degree $2$. Now, a non-satisfying valuation of $G$ in your sense amounts to picking one edge of $W$ incident to each vertex of $V$ in $G'$, so that we never pick the two edges of $W$ incident to a vertex of $E$. In other words, I'm claiming that counting the non-satisfying valuations of $G$ is exactly to counting the subsets $W'$ of $W$ such that each vertex of $V$ has exactly one incident edge in $W'$ (= we pick one edge for each vertex of $V$), and each vertex of $E$ has 0 or 1 incident edges in $W'$ (= no edge of $E$ has both its endpoints selected).

If I'm not mistaken, this is precisely the problem #[1,1,0][0,1,0,0] in the notation of Valiant used in the paper I quote: note that there's a hopefully legible explanation in Appendix D of this paper (which, incidentally, we co-authored ;-P). Now looking at the table on page 23 of Cai, Lu and Xia, we see that #[1,1,0][0,1,0,0] is #P-hard.

As for the problem having an established name more palatable than #[1,1,0][0,1,0,0], I don't know, but maybe this can be one direction in which to look.

Answer 2

Here is an attempt to prove that my problem is hard on $(2,3)-(2,3)$-regular bipartite multigraphs. These are bipartite multigraphs such that each node has either degree $2$ or $3$ (in both partitions, i.e., I do not impose that all the nodes of the first partition have degree $2$ and all the nodes of the second have degree $3$). I say attempt because I am not an expert in holographic reductions and interpolation at all, so I am not 100% sure that what I write makes sense. I will consider the following problems:

A) Counting matchings on $2-3$-regular bipartite multigraphs. Here $2-3$-regular means bipartite where first partition gets degree $2$ and second partition gets degree $3$. This is exactly the problem $\#[1,1,0]|[1,1,0,0]$ in the terminology of the paper of Cai, Lu and Xia, and it is #P-hard according to the table page 10.

B) The problem that I write $\#[1,0,1]|([1,1,0],[1,1,0,0])$-BipBip. What it means:

• the input is what I call a $2-(2,3)$-regular bipartite simple graph. These are bipartite simple graphs with partition $V_1,V_2$ such that all nodes in partition $V_1$ have degree $2$ and all nodes in partition $V_2$ have degree $2$ or $3$. Nodes in $V_1$ are assigned the signature $[1,0,1]$, while nodes in $V_2$ are assigned the signature $[1,1,0]$ or $[1,1,0,0]$, depending on their degree.
• the "BipBip" part means that I restrict to what I call BipBip $2-(2,3)$-regular bipartite simple graphs. This means that when you contract the nodes in the first partition (the one where all the nodes have degree $2$), then you end up with a $2-3$-regular bipartite multigraph.

C) The problem that I write $\#[1,1,0]|([0,1,0],[0,1,0,0])$-Bip. The meaning is similar, but here I impose that when you contract nodes of the first partition you only get a bipartite multigraph (which will then obviously be a $(2,3)-(2,3)$-regular bipartite multigraph).

Now, if problem C is #P-hard, then my problem is #P-hard as well on $(2,3)-(2,3)$-regular bipartite multigraphs. The reduction is exactly the one described in a3nm's answer, plus the observation that you end up with a $(2,3)-(2,3)$-regular bipartite multigraph, thanks to Bip. I will reduce problem C from problem B. But before that, let us observe that problem B is hard.

I reduce counting matchings in $2-3$-regular multigraphs to problem B. Let $G$ be an input of $\#[1,1,0]|[1,1,0,0]$, i.e., a $2-3$-regular bipartite multigraph. Replace each edge of $G$ by a path of length $2$ with a new node of degree $2$ in the middle, and call the resulting graph $G'$. Observe that $G'$ is a BipBip $2-(2,3)$-regular simple graph. The signatures of the nodes of $G$ do not change, and for the newly created degree-2 nodes assign them the equality signature, that is $[1,0,1]$. This shows that problem B is indeed hard.

Until here, nothing complicated. Now for the reduction from B to C. This is the tricky part, that I am unsure of. Start with a BipBip $2-(2,3)$-regular bipartite simple graph. I will apply a holographic reduction to $G$, with two different matrices for the nodes of the second partition, the matrix depending on the degree. For the nodes having degree $3$, take the matrix $T = \begin{bmatrix}1&-\frac{1}{3}\\0&1\end{bmatrix}$. Where does that come from? In the proof of Lemma 4.1, consider the second case and choose $A=1$ and $B=\alpha=0$. You can then check that indeed, the signature of nodes of degree $3$, which is $(1,1,1,0,1,0,0,0)^\top$ in full column form, gets transformed into $(0,1,1,0,1,0,0,0)^\top$ by $T^{\otimes 3}$. But $(0,1,1,0,1,0,0,0)^\top$ corresponds to the symmetric signature $[0,1,0,0]$. Now for the nodes (again of the second partition) of degree 2, use the matrix $T' = \begin{bmatrix}1&-\frac{1}{2}\\0&1\end{bmatrix}$. You can check that $T'^{\otimes 2} (1,1,1,0)^\top$ is $(0,1,1,0)^\top$, which corresponds to the symmetric signature $[0,1,0]$. The signature of the equality nodes (those of the first partition) gets transformed into some $[x_0,x_1,x_2]$, whose exact value I don't understand how to obtain but we don't care. This is the main part where I'm not sure, e.g., how do you obtain $x_0,x_1,x_2$ exactly, and why would it be symmetric. Also, here the BipBipness assumption is important I think, because otherwise it could introduce other signatures for the nodes of the first partition, like $[x'_0,x'_1,x'_2]$, and then it would not be clear (to me) that the rest of the proof works. But let's assume it works for now. So we have reduced problem B to the problem $\#[x_0,x_1,x_2]|([0,1,0],[0,1,0,0])$-BipBip.

To reduce problem $\#[x_0,x_1,x_2]|([0,1,0],[0,1,0,0])$-BipBip to problem C, I think it works as in the hardness proof of $\#[1,1,0]|[0,1,0,0]$ page 14. This is by interpolation. Namely, replace every node of degree 2 of the first partition by gadget 2 that they define page 13. You can do that polynomially many times and then solve the linear system. But observe that when you plug in these gadgets, no matter how long the gadget employed are, then the graph obtained is a Bip $2-(2,3)$-regular bipartite simple graph (I think you really have to draw to see it. Also, this gadget breaks the BipBipness of the graph). So this shows that problem B is hard.

I won't mark this as solved until someone confirms that it works.

(Also you cannot get rid of the parallel edges using these result because when you contract gadget 2 you necessarily obtain parallel edges. (But I don't care.))