9
$\begingroup$

Let $G = ( V, E )$ be a graph. Let $k \leq |V|$ be an integer. Let $O_k$ be the number of edge induced subgraphs of $G$ having $k$ vertices and an odd number of edges. Let $E_k$ be the number of edge induced subgraphs of $G$ having $k$ vertices and an even number of edges. Let $\Delta_k = O_k - E_k$. The ODD EVEN DELTA problem consists in computing $\Delta_k$, given $G$ and $k$.

Questions

  1. Is it possible to compute $\Delta_k$ in polynomial time? Which is the best known algorithm to compute it?
  2. What if $G$ is 3-regular?
  3. What if $G$ is 3-regular bipartite?
  4. What if $G$ is 3-regular bipartite planar?
$\endgroup$
4
  • 4
    $\begingroup$ What is your motivation? $\endgroup$ Commented Sep 2, 2012 at 17:29
  • $\begingroup$ @TysonWilliams: My motivation is that, if the 1st part of the 1st question has an affirmative answer (even only for the bipartite 3-regular planar case), then there would be some interesting consequences deserving further exploration. If the algorithm is sub-exponential, it would still have some consequences (less interesting, but nonetheless deserving more exploration). $\endgroup$ Commented Sep 3, 2012 at 7:48
  • 2
    $\begingroup$ Can you be more specific? What do you mean by "some interesting consequences"? How did you encounter this problem in the first place? $\endgroup$ Commented Sep 3, 2012 at 12:34
  • $\begingroup$ @TysonWilliams: Could we continue this conversation privately, by e-mail? $\endgroup$ Commented Sep 3, 2012 at 13:47

2 Answers 2

9
$\begingroup$

The ODD EVEN DELTA problem is #P-hard, even on 3-regular bipartite planar graphs.

Let $\mathcal{C}$ be the set of vertex covers of a general graph $G$. Then, assuming $G$ has no isolated vertices, the following equation holds (refer to the above article for the proof):

$$|\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^{|V|} \Delta_k \cdot 2^{|V|-k}$$

Counting vertex covers is #P-complete even on 3-regular bipartite planar graphs, and it can be done with a linear number of calls to an ODD EVEN DELTA oracle.

$\endgroup$
7
$\begingroup$

UPDATE:

I should have pointed out that the answer below is about the special case of $k = |V|$. Since this case is hard, the problem for general $k$ is also hard.

The Holant framework is essentially an exponential sum over spanning subgraphs (i.e. all vertices are present in the subgraph, so the sum is over the subsets of edges). In contrast, the current version of the question is about edge induced subgraphs.

An earlier version of this question concerned counting certain subgraphs with no isolated vertices. The answer below correctly addresses this requirement. When considering both spanning subgraphs (i.e. the Holant framework) and no isolated vertices, this is the same as considering edge induced subgraphs with $|V|$ vertices. The OP basically pointed this out in this question.

3-Regular Planar Graphs

For the moment, I will ignore your requirement that the graph $G$ is bipartite.

Suppose that $G$ is a 3-regular planar graph. Your problem can be expressed as the bipartite planar Holant problem

$$\text{Pl-Holant}([1,0,-1]|[0,1,1,1]).$$

Let me explain how. For more detail than I provide below, see this paper.

The Holant is a sum over (Boolean) assignments to edges. On the vertices are constraints who's inputs are the assignments to their incident edges. For each assignment to the edges, we take the product of all the vertex constraints.

Your requirement that there be no isolated vertices is the constraint that is not satisfied at a particular vertex if none of its incident edges is selected and is satisfied if at least one edge is a selected. This symmetric constraint is denoted by [0,1,1,1], which outputs 0 (i.e. unsatisfied) when the number of input 1's is 0 (i.e. no incident edges in the subgraph) and outputs 1 (i.e. satisfied) when the number of input 1's is 1, 2, or 3 (i.e. 1, 2, or 3 incident edges in the subgraph).

Your other requirement is to compute the number of subgraphs with an even number of edges minus the subgraphs with an odd number of edges. For our graph $G$, we replace each edge by a path of length 2 (which is also called the 2-stretch of $G$). This gives a (2,3)-regular bipartite graph. To all of the original vertices, we assign the constraint [0,1,1,1] from above. To all of the new vertices, we assign the constraint [1,0,-1]. Since the middle entry of this constraint is 0, this forces the incident edges of these degree 2 vertices to either both be assigned 0 (i.e. not in the subgraph) or both be assigned 1 (i.e. in the subgraph). Now for a particular assignment to the edges, if the number $n$ of "original" edges is even, then the contribution from all the degree 2 vertices is $(-1)^n = 1$. Otherwise, $n$ is odd and the contribution is $(-1)^n = -1$. This is exactly what you want.

This bipartite Holant problem is #P-hard by Theorem 6.1 in this paper. However, that theorem is not the easiest to apply. Instead, consider the following.

We do a holographic transformation by $T = \begin{bmatrix} -1 & 1 \\ 0 & 1 \end{bmatrix},$ which does not change the value of the Holant. Thus, the above problem is exactly the same as

$$ \begin{align*} \text{Pl-Holant}([1,0,-1]|[0,1,1,1]) &= \text{Pl-Holant}([1,0,-1] T^{\otimes 2}|(T^{-1})^{\otimes 3}[0,1,1,1])\\ &= \text{Pl-Holant}([1,-1,0]|[1,0,0,1]). \end{align*} $$

Then it is easy to see that this problem is #P-hard by Theorem 1.1 in this paper.

Restricting to Bipartite Graphs

Just like your previous question, the same problem restricted to bipartite graphs is much harder to handle and I believe it is still an open problem. We have a conjecture as to the tractable cases (and I will check to see if your problem is one of them), but I think your problem is still #P-hard even when restricted to bipartite graphs.

$\endgroup$
1
  • $\begingroup$ Thanks for dedicating your time to this question and for having furnished such a detailed answer. Being not familiar with the Holant framework, I will need some time to parse it and to fully metabolize your reasoning (of course I've no doubt on its correctness, it is just that I want to understand every step, not only the conclusion). For what concerns the bipartiteness restriction, yes it would be really nice if you could check whether your tractable cases conjecture encompasses my problem. $\endgroup$ Commented Sep 3, 2012 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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