I would like to know whether counting number of induced (full) subgraphs (of an undirected graph) that have even number of edges is P or #P-complete. Additionally, is the problem easier if we assume that given undirected graph has constant degree (all vertices have up to k incident edges)?
-
2$\begingroup$ I'm not sure I understand. If you're just looking at subgraphs, then the number of subgraphs is exactly 2^m (m the number of edges) and the number of subgraphs with an even number of edges is merely the number of m-bit strings with an even number of ones, which has a closed form expression. $\endgroup$– Suresh VenkatSep 6, 2012 at 19:56
-
1$\begingroup$ @Suresh Right, my mistake. I meant induced (full) subgraphs. Thank you for pointing that out $\endgroup$– RobertSep 6, 2012 at 20:11
-
$\begingroup$ Are you looking for the number of subgraphs up to isomorphism? $\endgroup$– Tyson WilliamsSep 6, 2012 at 20:16
-
$\begingroup$ @Tyson No, I even want to treat all single node subgraphs as different. $\endgroup$– RobertSep 6, 2012 at 20:22
-
$\begingroup$ Then I agree with the comment by @SureshVenkat. The closed form is $2^{m-1}$ (see this wolfram alpha). $\endgroup$– Tyson WilliamsSep 6, 2012 at 20:26
1 Answer
This problem is tractable.
Let $G = (V,E)$ be the input graph with $|V| = n$ and let $e$ and $o$ be the number of vertex-induced subgraphs of $G$ with an even and odd number of edges respectively. Of course, $e + o = 2^n$. In polynomial time, we can compute $e - o$, which I explain below. With two equations and two unknowns, we can solve the linear system to determine the value of $e$.
From $G$, we create an instance of a counting constraint satisfaction problem (#CSP). Every vertex in $V$ is a Boolean variable and every edge in $E$ a constraint $f$ that depends on its incident vertices. The constraint $f$ evaluates to 1 unless the both vertices are assigned 1, in which case, $f$ evaluates to -1. The symmetric notation for this constraint is $[1,1,-1]$.
Now the answer to this #CSP instance is (by definition) $$\sum_{\sigma : V \to \{0,1\}} \prod_{e \in E} f(\sigma|_{I(e)}),$$ which is a sum over all vertex subsets, the product of the outputs of every constraint $f$, where $I(e)$ is the vertices incident to $e$ and $\sigma|_{I(e)}$ is the restriction of $\sigma$ to $I(e)$.
Fix a subset of $V$. Assigned 1 to the vertices in the subset and 0 to the vertices not in the subset. If either vertex incident to the same edge is assigned 0, then this edge is not in the vertex-induced subgraph and the constraint $f$ on this edge contributes a 1 to the product, which has no effect. If both vertices incident to the same edge are assigned 1, then this edge is in the vertex-induced subgraph and the constraint $f$ on this edge contributes a -1 to the product.
Vertex-induced subgraphs with an even number of edges contribute a 1 to the sum while vertex-induced subgraphs with an odd number of edges contribute a -1. Thus, the answer to this #CSP instance is exactly $e - o$.
Since the constraint $f$ is affine, this #CSP is tractable. The polynomial algorithm for any set of affine signatures is given in The Complexity of Complex Weighted Boolean #CSP by Jin-Yi Cai, Pinyan Lu, and Mingji Xia. There may be a simpler algorithm for this particular case. If such an algorithm is known, it is probably contained in one of the references cited in the above paper.
-
2$\begingroup$ Thank you very much. In the meantime I think I found another solution (which I was just starting to read). We can represent the given graph as multilinear polynomial f over GF[2], where there is an edge between x and y iff xy appears in f. Then, the number of induced subgraphs having even number of edges equals to number of solutions of f. And there is a polynomial algorithm to count that number of solutions, described in section 4 of the computational complexity of (xor and)-counting problems. $\endgroup$– RobertSep 7, 2012 at 0:18
-
2
-
2$\begingroup$ Actually, the #CSP in my solution only has a single binary constraint, which is the special case of counting weighted graph homomorphisms. Thus, the algorithm given in Graph Homomorphisms with Complex Values: A Dichotomy Theorem by Jin-Yi Cai, Xi Chen, and Pinyan Lu (or in one of the papers that it cites) might be simpler. $\endgroup$ Sep 7, 2012 at 1:30