<p><em>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.</em></p>

<p>I think the problem is #P-hard already on 3-regular graphs using the results of <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.145.8882&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Cai, Lu and Xia, <em>Holographic Reduction, Interpolation and Hardness</em>, 2012</a>. I will do this by showing the #P-hardness of counting the <em>non-satisfying</em> valuations of <span class="math-container">$G$</span>, i.e., the valuations <span class="math-container">$\nu$</span> where for every edge <span class="math-container">$e$</span> at least one of the endpoints of <span class="math-container">$e$</span> is not mapped to <span class="math-container">$e$</span> by <span class="math-container">$\nu$</span>. Indeed, counting this reduces in PTIME to counting the satisfying valuations of <span class="math-container">$G$</span> 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.</p>

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

<p>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 <a href="https://arxiv.org/pdf/1703.03201" rel="nofollow noreferrer">this paper</a> (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.</p>

<p>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.</p>

CC BY-SA 4.0
2019-05-15T18:49:20.327Z
Ahah indeed, thanks :). (The reduction is in the wrong direction, but it works since any 2-3-regular graph can be obtained as you describe from a 3 regular graph)
M.Monet
CC BY-SA 4.0
2019-05-15T20:30:36.737Z
Argh you are right, sorry about reducing in the wrong direction. :-P Anyway there is a slight hitch though: a 2-3-regular graph when coded as a 3-regular graph could lead to multi-edges, i.e., multiple edges between the same vertex pair, right? You can't just eliminate them because these additional edges mess up the counts... I'm not sure of what happens then, but maybe for your purposes it somehow doesn't matter?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-05-16T14:05:31.610Z
Hmmm yes this is frustrating... Actually I realized that I need this problem to be hard on bipartite graphs, possibly with multi-edges. I'll update my question and un-mark it as solved (but once it's solved I'll accept your answer).
M.Monet
CC BY-SA 4.0
2019-05-15T15:59:14.357Z
2019-05-18T08:43:56.190Z
2019-05-18T08:43:56.190Z
Antoine Amarilli 'a3nm'
<p>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, <span class="math-container">$2$</span>-<span class="math-container">$3$</span>--regular bipartite simple graphs), which is what I needed.</p>

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

<ul>
<li><p>For every nonsatisfying valuation <span class="math-container">$\mu$</span> of <span class="math-container">$G$</span>, there are exactly <span class="math-container">$2^{|E]-|V|}$</span> nonsatisfying valuations <span class="math-container">$\mu'$</span> of <span class="math-container">$G'$</span> that agree with <span class="math-container">$\mu$</span>;</p></li>
<li><p>If <span class="math-container">$\mu'$</span> is a nonsatisfying valuation of <span class="math-container">$G'$</span>, then <span class="math-container">$\mu'_{|V}$</span> is a nonsatisfying valuation of <span class="math-container">$G$</span>.</p></li>
</ul>

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

CC BY-SA 4.0
2019-08-09T19:00:14.650Z
2019-08-09T19:00:14.650Z
M.Monet
<p>Let <span class="math-container">$G=(V,E)$</span> be an undirected graph. I call a <em>valuation of <span class="math-container">$G$</span></em> a function <span class="math-container">$\nu: V \to E$</span> that maps every node <span class="math-container">$x \in V$</span> to an edge incident to <span class="math-container">$x$</span> (so that there are <span class="math-container">$\prod_{x \in V} d(x)$</span> valuations of <span class="math-container">$G$</span>, where <span class="math-container">$d(x)$</span> is the degree of node <span class="math-container">$x$</span>). I say that <span class="math-container">$\nu$</span> is <em>satisfying</em> if there exist an edge <span class="math-container">$e\in E$</span> such that both endpoints of <span class="math-container">$e$</span> are mapped to <span class="math-container">$e$</span> by <span class="math-container">$\nu$</span>. I am interested in the following problem:</p>

<p><strong>INPUT:</strong> An undirected graph <span class="math-container">$G$</span></p>

<p><strong>OUTPUT:</strong> The number of satisfying valuations of <span class="math-container">$G$</span></p>

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

<p>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 <span class="math-container">$G$</span>, and you say that a valuation of <span class="math-container">$G$</span> either maps a node <span class="math-container">$x$</span> to <em>all</em> of its incident edges or to <em>none</em> 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 <span class="math-container">$0$</span> of <span class="math-container">$1$</span>.</p>

<p>==== UPDATE ====</p>

<p>As a3nm showed in his answer, the problem is hard on 3-regular graphs <em>with multi-edges</em>. My answer shows that the problem is also hard on <span class="math-container">$2$</span>-<span class="math-container">$3$</span> regular simple graphs. There is the minor question of knowing if it is hard one $3-regular <strong>simple</strong> graphs. I don't really care about it, but I still leave it here for completeness. </p>

CC BY-SA 4.0
2019-05-18T08:52:56.147Z
Side comment about bipartite graphs: it seems like at least some papers on Holant are showing hardness results that could apply to bipartite graphs. Namely, they work with 2-3-regular bipartite graphs such that the 3-regular (multi-)graph that it codes is also bipartite. Search for "is still bipartite" in https://core.ac.uk/download/pdf/82063901.pdf
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-05-24T10:59:10.343Z
"$\nu$ is *satisfying* if there exist an edge $e\in E$ such that both endpoints of $e$ are mapped to $e$ by $\nu$." I don't see how you are relating this to a Holant problem. Your constraint is a global one, but Holant can only express local ones.
Tyson Williams
CC BY-SA 4.0
2019-05-24T13:37:51.217Z
Yes, but the negation of the problem, counting non-satisfying valuations, is local and can be expressed as a Holant problem (on the stretch of $G$).
M.Monet
CC BY-SA 4.0
2019-05-24T14:51:15.377Z
Ah, yes.  Very good.  I now see that was part of a3nm's answer.
Tyson Williams
CC BY-SA 4.0
2019-05-24T15:15:41.470Z
Let $f(G)$ be the number of non-satisfying valuations of $G$.  Let $e$ be a self loop edge in $G$.  Then $f(G) = 3 f(G - e)$, right?
Tyson Williams
CC BY-SA 4.0
2019-05-24T15:52:43.430Z
I think it depends how we define the problem on graphs with self loops, but let's say we only define it for multigraphs without self loops.
M.Monet
<reference-request><counting-complexity>
A variant of #POSITIVE-2-DNF
M.Monet
# A variant of #POSITIVE-2-DNF

(Asked by: username_0 on 2019-05-14)

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.

**Tags:** reference-request, counting-complexity

> **Comments:**
> **username_1**: Side comment about bipartite graphs: it seems like at least some papers on Holant are showing hardness results that could apply to bipartite graphs. Namely, they work with 2-3-regular bipartite graphs such that the 3-regular (multi-)graph that it codes is also bipartite. Search for "is still bipartite" in https://core.ac.uk/download/pdf/82063901.pdf  
> **username_2**: "$\nu$ is *satisfying* if there exist an edge $e\in E$ such that both endpoints of $e$ are mapped to $e$ by $\nu$." I don't see how you are relating this to a Holant problem. Your constraint is a global one, but Holant can only express local ones.  
> **username_0**: Yes, but the negation of the problem, counting non-satisfying valuations, is local and can be expressed as a Holant problem (on the stretch of $G$).  
> **username_2**: Ah, yes.  Very good.  I now see that was part of a3nm's answer.  
> **username_2**: Let $f(G)$ be the number of non-satisfying valuations of $G$.  Let $e$ be a self loop edge in $G$.  Then $f(G) = 3 f(G - e)$, right?  
> **username_0**: I think it depends how we define the problem on graphs with self loops, but let's say we only define it for multigraphs without self loops.  

---

## 2 answers

### Answer by username_1 on 2019-05-15. Score: 3 | Accepted answer

*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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.145.8882&rep=rep1&type=pdf). 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](https://arxiv.org/pdf/1703.03201) (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.

> **Comments:**
> **username_0**: Ahah indeed, thanks :). (The reduction is in the wrong direction, but it works since any 2-3-regular graph can be obtained as you describe from a 3 regular graph)  
> **username_1**: Argh you are right, sorry about reducing in the wrong direction. :-P Anyway there is a slight hitch though: a 2-3-regular graph when coded as a 3-regular graph could lead to multi-edges, i.e., multiple edges between the same vertex pair, right? You can't just eliminate them because these additional edges mess up the counts... I'm not sure of what happens then, but maybe for your purposes it somehow doesn't matter?  
> **username_0**: Hmmm yes this is frustrating... Actually I realized that I need this problem to be hard on bipartite graphs, possibly with multi-edges. I'll update my question and un-mark it as solved (but once it's solved I'll accept your answer).  

---

### Answer by username_0 on 2019-08-09. Score: 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.


---

