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)?
10
-
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
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Sep 6, 2012 at 23:42
-
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