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][1]. 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. My answer shows that the problem is also hard on $2$-$3$ regular simple graphs. There is the minor question of knowing if it is hard one $3-regular simple graphs. I don't really care about it, but I still leave it here for completeness.

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

a3nm's answer shows that the problem is hard on 3-regular multigraphs. In this post I show that it is also hard on bipartite graphs (in fact, $2$-$3$--regular bipartite simple graphs), which is what I needed.

I reduce from the problem on $3$-regular multigraphs. Let $G=(V,E)$ be a $3$-regular multigraph. Construct $G'$ by adding a node in the middle of every edge of $G$. Formally, the vertices of $G'$ are $V \sqcup \{n_e \mid e \in E\}$ and its edges are $\bigcup_{e \in E \text{ with endpoints }u \text{ and }v} \{\{u,n_e\},\{n_e,v\}\}$.It is clear that $G'$ is a $2$-$3$-regular bipartite simple graph. I claim that the number of nonsatisfying valuations of $G'$ is $2^{|E|-|V|}$ times that of $G$, which would complete the reduction. To prove this, I will use the following definition: letting $\mu$ be a valuation of $G$ and $\mu'$ be a valuation of $G'$, I say that $\mu$ and $\mu'$ agree if $\mu'_{|V} = \mu$. I then show the following, which directly implies the claim and concludes the proof:

• For every nonsatisfying valuation $\mu$ of $G$, there are exactly $2^{|E]-|V|}$ nonsatisfying valuations $\mu'$ of $G'$ that agree with $\mu$;

• If $\mu'$ is a nonsatisfying valuation of $G'$, then $\mu'_{|V}$ is a nonsatisfying valuation of $G$.

I first prove item 1). I say that an edge $e$ of $G$ is chosen if for one of its endpoints $u\in V$ we have $\mu(u)=e$. Observe that, because $\mu$ is nonsatisfying, there are exactly $|V|$ edges of $G$ that are chosen. Let us now look at the number of ways to extend $\mu$ into a nonsatisfying valuation $\mu'$ of $G'$. It is easy to see that for every edge $e$ of $G$ that is chosen, the value of $\mu'(n_e)$ is forced: we have to set $\mu'(n_e)$ to be the (unique) edge $\{n_e,v\}$ such that $\mu(v) \neq e$. Moreover when $e$ is not chosen, both values for $n_e$ are possible. But then this indeed implies that there are $2^{|E]-|V|}$ nonsatisfying valuation $\mu'$ of $G'$ that agree with $\mu$. To show item 2), assume by contradiction that $\mu'_{|V}$ is satisfying. This means that there is an edge $e\in E$ with endpoints $u,v$ such that we have $\mu'_{|V}(u) = \mu'_{|V}(u) = e$. But then, looking at the possible value for $\mu'(n_e)$, we see that $\mu'$ must also be satisfying, a contradiction.