<p>This problem is tractable.</p>

<p>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$.</p>

<p>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]$.</p>

<p>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)$.</p>

<p>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.</p>

<p>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$.</p>

<p>Since the constraint $f$ is affine, this #CSP is tractable. The polynomial algorithm for any set of affine signatures is given in <a href="http://pages.cs.wisc.edu/~jyc/papers/cw-csp.pdf">The Complexity of Complex Weighted Boolean #CSP</a> 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.</p>

CC BY-SA 3.0
2012-09-07T00:18:22.640Z
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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.9881&rep=rep1&type=pdf).
Robert
CC BY-SA 3.0
2012-09-07T01:21:37.387Z
[Here is a link](http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/1990/8543-CS.pdf) to a better version of that paper.
Tyson Williams
CC BY-SA 3.0
2012-09-07T01:30:39.403Z
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](http://arxiv.org/abs/0903.4728) by Jin-Yi Cai, Xi Chen, and Pinyan Lu (or in one of the papers that it cites) might be simpler.
Tyson Williams
CC BY-SA 3.0
2012-09-06T23:42:48.643Z
2012-09-06T23:49:06.883Z
2012-09-06T23:49:06.883Z
Tyson Williams
<p>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)?</p>

CC BY-SA 3.0
2012-09-06T19:56:30.023Z
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.
Suresh Venkat
CC BY-SA 3.0
2012-09-06T20:11:51.310Z
@Suresh Right, my mistake. I meant induced (full) subgraphs. Thank you for pointing that out
Robert
CC BY-SA 3.0
2012-09-06T20:16:44.133Z
Are you looking for the number of subgraphs up to isomorphism?
Tyson Williams
CC BY-SA 3.0
2012-09-06T20:22:32.370Z
@Tyson No, I even want to treat all single node subgraphs as different.
Robert
CC BY-SA 3.0
2012-09-06T20:26:59.997Z
Then I agree with the comment by @SureshVenkat. The closed form is $2^{m-1}$ (see [this wolfram alpha](http://www.wolframalpha.com/input/?i=sum+m+choose+2k%2C+k%3D0+to+m%2F2)).
Tyson Williams
CC BY-SA 3.0
2012-09-06T20:29:45.463Z
@TysonWilliams but my comment was not about induced subgraphs, only "regular" subgraphs.
Suresh Venkat
CC BY-SA 3.0
2012-09-06T20:30:46.107Z
@SureshVenkat If we are not counting up to isomorphism, what difference does it make?
Tyson Williams
CC BY-SA 3.0
2012-09-06T20:33:24.507Z
@TysonWilliams Unfortunately, I am interested in induced subgraphs, I agree that for any subgraphs the problem is easy.
Robert
CC BY-SA 3.0
2012-09-06T20:46:29.093Z
Robert, so you are saying that a set of vertices defines an induced subgraph and you want to know how many of these induced subgraphs have an even number of edges?
Tyson Williams
CC BY-SA 3.0
2012-09-06T20:52:41.040Z
@TysonWilliams Exactly. In other words "in how many ways I can choose vertices from the grapg, so that number of edges between any pairs of those vertices will be even". I think you had a comment posted for a moment that meant precisely this.
Robert
<ds.algorithms><graph-theory><graph-algorithms><counting-complexity>
Number of subgraphs with given edge parity
Robert
# Number of subgraphs with given edge parity

(Asked by: username_0 on 2012-09-06)

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

**Tags:** ds.algorithms, graph-theory, graph-algorithms, counting-complexity

> **Comments:**
> **username_1**: 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.  
> **username_0**: @Suresh Right, my mistake. I meant induced (full) subgraphs. Thank you for pointing that out  
> **username_2**: Are you looking for the number of subgraphs up to isomorphism?  
> **username_0**: @Tyson No, I even want to treat all single node subgraphs as different.  
> **username_2**: Then I agree with the comment by @SureshVenkat. The closed form is $2^{m-1}$ (see [this wolfram alpha](http://www.wolframalpha.com/input/?i=sum+m+choose+2k%2C+k%3D0+to+m%2F2)).  
> **username_1**: @TysonWilliams but my comment was not about induced subgraphs, only "regular" subgraphs.  
> **username_2**: @SureshVenkat If we are not counting up to isomorphism, what difference does it make?  
> **username_0**: @TysonWilliams Unfortunately, I am interested in induced subgraphs, I agree that for any subgraphs the problem is easy.  
> **username_2**: username_0, so you are saying that a set of vertices defines an induced subgraph and you want to know how many of these induced subgraphs have an even number of edges?  
> **username_0**: @TysonWilliams Exactly. In other words "in how many ways I can choose vertices from the grapg, so that number of edges between any pairs of those vertices will be even". I think you had a comment posted for a moment that meant precisely this.  

---

## 1 answers

### Answer by username_2 on 2012-09-06. Score: 7 | Accepted 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](http://pages.cs.wisc.edu/~jyc/papers/cw-csp.pdf) 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.

> **Comments:**
> **username_0**: 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.9881&rep=rep1&type=pdf).  
> **username_2**: [Here is a link](http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/1990/8543-CS.pdf) to a better version of that paper.  
> **username_2**: 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](http://arxiv.org/abs/0903.4728) by Jin-Yi Cai, Xi Chen, and Pinyan Lu (or in one of the papers that it cites) might be simpler.  

---

