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. 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?

$\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
  • 1
    $\begingroup$ Thanks! With this observation and some serious digging into the paper of Cai, Lu and Xia (2012), I can show that if counting the matchings in 3-regular bipartite multigraphs is #P-hard, then my problem is #P-hard on bipartite multigraphs. Now, in Xia, Zhang and Zhao, Computational complexity of counting problems on 3-regular planar graphs, 2007, it is shown that counting matchings on 2-3-regular bipartite multigraphs is #P hard, but this is not what I want, I want every node to have degree 3. By chance, would this be already known? If yes, I'll explain the full reduction in an answer. $\endgroup$ – M.Monet May 21 at 17:23
  • $\begingroup$ Ah I think hardness of counting matchings on 2-3-regular bipartite graphs will do. I'll sketch the reduction tomorrow. $\endgroup$ – M.Monet May 21 at 22:17
  • $\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
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
0
$\begingroup$

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.))

$\endgroup$
  • $\begingroup$ I think your bold part is indeed a gap. I think we only ever consider homogenous holographic transformations because of the issue you are facing there. If you really did want to consider a heterogeneous holographic transformation, then I suggest simplifying things by first considering an orthogonal transformation applied to the binary equality since such a transformation leaves it unchanged. Then try to use that freedom to make your current heterogeneous transformation into a homogenous one. $\endgroup$ – Tyson Williams May 24 at 11:25
  • $\begingroup$ What is it exactly that does not work? Since the graph is BipBip, it seems that the equality nodes are all mapped to $(1,0,0,1) T^{-1} \otimes T'^{-1}$, or something like that no? (I don't actually understand how these tensors work) $\endgroup$ – M.Monet May 24 at 14:20
  • $\begingroup$ Also, if it were known that counting matchings on 3-regular bipartite multigraphs is hard, then this proof would work directly, since we would only need the matrix $T$ and then this is a "usual" holographic reduction. $\endgroup$ – M.Monet May 24 at 15:56
  • $\begingroup$ Ok, I am now onboard with that tensor expression. One thing that confused me is why it seemed that you have the freedom to pick the order of $T$ and $T'$. Directly, it because (each instance of) $[1,0,1]$ is symmetric. As a sanity check though, it was helpful for me to see that this equivalence also follows from reversing the interpretation of the edge assignments. $\endgroup$ – Tyson Williams May 26 at 11:28
  • 1
    $\begingroup$ Damn, it is not symmetric (checked with sympy)... I will try to insert an orthogonal matrix in between to see if that can be fixed. If it cannot, then I guess that I really need hardness of counting matchings on 3-regular bipartite graphs, or to do the reduction myself, but this will require more sweat... $\endgroup$ – M.Monet May 26 at 22:59

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.