7
$\begingroup$

Let $G$ be a graph. Let $O$ be the number of edge induced subgraphs of $G$ having an odd number of vertices.

Questions

  1. How hard is to compute $O$?
  2. How hard is to compute the parity of $O$?

Related questions:


Update 11/05/2013 18:00

By a reasoning similar to the one in the answer to the first question referenced above, we can create a Holant by placing on each vertex $v$ a constraint $f_v$ which returns $1$ when all the edges incident to $v$ have been assigned $0$, and $-1$ otherwise. For a specific assignment to the edges ($0$ means not selected, $1$ means selected) we get an edge induced subgraph such that the number of its vertices is odd if and only if the product of the Holant returned $-1$. The summation of the Holant is thus equal to the difference $E - O$ between the number of edge induced subgraphs having an even number of vertices and the number of edge induced subgraphs having an odd number of vertices: as $E + O$ is known, we can determine $E$ and $O$.

Now, if I correctly understand the paper A Dichotomy for Real Weighted Holant Problems, the constraint $f_v$ is symmetric (obviously) and affine: by Theorem 3.2 this means that we can compute $E-O$ in polynomial time.

Am I right?

$\endgroup$
4
$\begingroup$

For simplicity, let's restrict ourselves to $k$-regular graphs.

The first part of your update is correct. Changing notation slightly from what you have introduced, let me define $n_e$ (resp. $n_o$) to be the number even (resp. odd) edge-induced subgraphs of a given graph $G$. For the (arity $k$) signature $f = [1, -1, -1, \dotsc, -1]$, the Holant problem Holant($f$) does indeed correspond to the problem "Given a graph, compute $n_e - n_o$." To see this, fix a subset of edges $E'$ (i.e. the subset of edges assigned 1) and consider a vertex $v$. If none of the incident edges of $v$ are in $E'$, then $v$ is not in the edge-induced subgraph defined by $E'$ and the constraint at $v$ contributes a factor of 1 to the weight of $E'$. Otherwise, some incident edge of $v$ is in $E'$, then $v$ is in the edge-induced subgraph defined by $E'$ and the constraint at $v$ contributes a $-1$ to the weight of $E'$. Summing over the weights of all subsets of the edges gives $n_e - n_o$. Since $n_e + n_o = 2^{|E(G)|}$, we could solve for $n_e$ and $n_o$ if we could knew $n_e - n_o$.

The second part of your update is incorrect. The $k$-ary signature $f = [1, -1, -1, \dotsc, -1]$ is not affine for $k \ge 3$. For a (rather explicit) list of the affine signatures, see page 7 of this paper. For $k \ge 3$, this signature defines a #P-hard Holant problem. To determine the complexity of this problem, notice that $f$ has the tensor rank 2 decomposition $f = 2 [1, 0]^{\otimes k} - [1,1]^{\otimes k}$. Let $\omega_{2k}$ be a $2k$th primitive root of unity. Then $f = [\sqrt[k]{2}, 0]^{\otimes k} + [\omega_{2k},\omega_{2k}]^{\otimes k}$. Under a holographic transformation by the inverse of $M = \begin{bmatrix} \sqrt[k]{2} & \omega_{2k} \\ 0 & \omega_{2k} \end{bmatrix}$, we have the bipartite Holant problem $\operatorname{Holant}([\sqrt[k]{4}, \omega_{2k} \sqrt[k]{2}, 2 \omega_{2k}^2] | =_k)$. This problem is #P-hard by Theorem 22 in this paper, even when also restricting to planar graphs.

For $k \le 2$, $f$ is actually affine, so the problem is tractable, but it is also tractable for a much simpler reason as well. Any Holant problem using only constraints of arity at most 2 is tractable using matrix product and trace.

$\endgroup$
  • $\begingroup$ Tyson, you said "...fix $k=4$" which lead us to a #P-hard problem by Theorem 22 in Kowalczyk's paper. What about $k = 3$? I'm wondering if the signature $[1, -1, -1, -1]$ is affine-transformable (in the sense of Definition 3.1 in Huang and Lu paper). Finally, what is known about the complexity of computing the parity of $n_o$ in $3$-regular graphs or even in $2/3$-regular bipartite planar graphs? Thanks as usual for your very good answers. $\endgroup$ – Giorgio Camerani May 12 '13 at 8:57
  • $\begingroup$ @GiorgioCamerani I have updated my answer to consider $k >= 3$. Not sure about parity. Look in "The Complexity of Symmetric Boolean Parity Holant Problems" by Heng Guo, Pinyan Lu, and Leslie G. Valiant for relevant papers. $\endgroup$ – Tyson Williams May 21 '13 at 20:12

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.