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? I guess this is a question for someone who understands well the paper by Cai, Lu and Xia.

2) Can we get rid of the multi-edges? Two choices here:

• understand the paper of Cai, Lu and Xia and show that #[1,1,0][0,1,0,0] is hard on 2-3-biregular graphs where no two nodes of the left partition (those with degree 2) have the same set of neighbors (so that when applying the reduction in a3nm's answer we don't end up with multi-edges). Unfortunately I don't understand well how their proofs work.

• find a graph gadget (without multi-edges) to replace two multi-edges, that always preserves the number of non-satisfying valuations, to a fixed multiplicative constant. More precisely, the gadget I am looking for is a graph $G_{\mathrm{gadget}}$ with two dandling edges $e$ and $e'$, $e$ being connected to the graph at nodes $a$ and $e'$ begin connected to the graph at node $a'$, with $a\neq a'$ (the other endpoints of $e$ and $e'$ are not in $G_{\mathrm{gadget}}$). This graph shall have the following property. Let:

  • $\alpha$ be the number of non-satisfying valuations of $G$ such that $a$ is mapped to $e$ and $a'$ is mapped to $e'$
  • $\beta$ be the number of non-satisfying valuations of $G$ such that $a$ is mapped to $e$ and $a'$ is not mapped to $e'$
  • $\gamma$ be the number of non-satisfying valuations of $G$ such that $a$ is not mapped to $e$ and $a'$ is mapped to $e'$
  • $\delta$ be the number of non-satisfying valuations of $G$ such that $a$ is not mapped to $e$ and $a'$ is not mapped to $e'$

  then $G_{\mathrm{gadget}}$ satisfies $\beta = \gamma = \delta = 2 \alpha$. If we had such a gadget, it would show that the problem is hard on graphs without multi-edges. Indeed, take a 3-regular graph $G$ with multi-edges, and let $e_2$ and $e_2$ be two edges connected to the same nodes $a$ and $a'$. Remove $e_1$ and $e_2$ and insert $G_{\mathrm{gadget}}$ between $a$ and $a'$. You can (painfully) check that, letting $G'$ be the graph with multi-edges obtained, we have that the number of non-satisfying valuations of $G'$ equals $\alpha$ times the number of non-satisfying valuations of $G$. Repeating this operation indeed shows that the problem is hard on graphs with no multi-edges. Now, it would be a bonus that this gadget also has the property that $G'$ is again a 3-regular graph (with multi-edges), since this would show that the problem is hard on 3-regular graphs (without multi-edges). Also, we could search for symmetric gadgets, so that we get $\beta = \gamma$ for free. This could simplify the search.

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.