4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 core.ac.uk/download/pdf/82063901.pdf $\endgroup$ – a3nm May 18 at 8:52
  • $\begingroup$ "$\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. $\endgroup$ – Tyson Williams May 24 at 10:59
  • $\begingroup$ 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$). $\endgroup$ – M.Monet May 24 at 13:37
  • $\begingroup$ Ah, yes. Very good. I now see that was part of a3nm's answer. $\endgroup$ – Tyson Williams May 24 at 14:51
  • $\begingroup$ 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? $\endgroup$ – Tyson Williams May 24 at 15:15
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – M.Monet May 15 at 18:49
  • 1
    $\begingroup$ 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? $\endgroup$ – a3nm May 15 at 20:30
  • $\begingroup$ 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). $\endgroup$ – M.Monet May 16 at 14:05
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.