# Given a bipartite graph G and an integer l, how many edge subsets of size l are there such that the degree of each vertex is odd?

Given a bipartite graph $$G=(V,E)$$ and an integer $$l$$, how many edge subsets ($$E'\subseteq E$$) of size $$l$$ are there such that the degree of each vertex in the resulting subgraph $$G'=(V,E')$$ is odd?

I have not been able to come up with anything smarter than explicitly enumerating all possible subsets and checking whether they satisfy the criteria, but the complexity of this approach is $$O(E^l)$$, which is exponential in $$l$$.

I encountered this problem when I was trying to simplify calculations of expectation values of certain operators relevant for Quantum Computing. These expectation values are exponentially hard to evaluate with my current algorithm, but I am not sure if it has to be that way, so I was trying to simplify it, and this is one of the key problems that I need to solve for that.

Does anyone know if there is a polynomial-time algorithm for this problem?

• @D.W. I have updated the question, I hope it is more clear now. I encountered this problem when I was trying to simplify calculations of expectation values of certain operators relevant for Quantum Computing. These expectation values are exponentially hard to evaluate with my current algorithm, but I am not sure if it has to be that way, so I was trying to simplify it, and this is one of the key problems that I need to solve for that. I understand it sounds like an XY problem, but the original problem seems too involved to explain here.
– QNA
Commented Apr 7, 2023 at 15:57
• Do you mean $G=(V,E')$, or do you mean $G=(V',E')$ where $V'$ are the edges that have at least one edge incident on them (i.e., the induced subgraph of $G$ that is induced by $E'$)?
– D.W.
Commented Apr 7, 2023 at 17:51
• @D.W. I mean $G'=(V,E')$, i.e. the set of vertices remains the same regardless of what subset of edges we consider.
– QNA
Commented Apr 8, 2023 at 0:44

I don't know whether this can be solved in polynomial time, and I don't know a faster way to get the exact count, but I can propose a way to approximate the number with close to $$O^*(E^{|l|/2})$$ time, which is a bit better than $$O(E^{|l|})$$. This is not very satisfying and not a very good answer, so I hope someone else will have a better solution.

Let $$GF(2)$$ denote the integers modulo 2 (i.e., the values 0 and 1, with an addition operator that adds modulo 2). Introduce variables $$x_e$$, one for each edge $$e$$, taking values in $$GF(2)$$, with the intended meaning that $$x_e=1$$ means that edge $$e$$ is included in the subset, and $$x_e=0$$ means that $$e$$ is not included.

Given a vertex $$v$$, note that the degree of $$v$$ is odd iff

$$\sum x_e = 1,$$

where the sum is taken over all edges $$e$$ that are incident on $$v$$. (Since we are working in $$GF(2)$$, the sum is implicitly modulo 2.) This is a linear equation on the variables $$x_e$$. Looking at all of the vertices, we obtain one linear equation per vertex in the graph.

Putting all of this together, we obtain $$|V|$$ linear equations over $$|E|$$ variables, with arithmetic done in $$GF(2)$$. So, introduce a $$|E|$$-vector $$x$$ that is the concatenation of all the $$x_e$$'s, and introduce a $$|V| \times |E|$$ matrix $$M$$ to represent all of the linear equations. Then we have the system of linear equations

$$Mx=1,$$

where here $$1$$ represents the $$|E|$$-vector containing all 1's.

Now your problem comes down to: how many choices of $$x$$ are there, such that $$Mx=1$$ and $$\text{wt}(x)=l$$?

The approach will be to let $$x=(y,z)$$, where each of $$y,v$$ are $$|E|/2$$-vectors, and let $$M=(M_1,M_2)$$, so that the problem becomes to count $$y,z$$ such that $$M_1y = 1 + M_2z$$ and such that $$\text{wt}(y) + \text{wt}(z) = l$$.

For each $$m$$ such that $$(1-\epsilon)l/2 \le m \le (1+\epsilon)l/2$$, we'll do the following. Enumerate all $$y$$ such that $$\text{wt}(y)=m$$, compute $$M_1y$$ for each such $$y$$, and store it in a hashtable keyed on the value $$t=M_1y$$ (and keeping a count of how many $$y$$'s yield the value $$t$$). Then, enumerate all $$z$$ such that $$\text{wt}(z)=l-m$$, compute $$u=1+M_2z$$, and look $$u$$ up in the hashtable. Sum up all the counts from matches in the hashtable. The total running time is $$O(|E|^{(1+\epsilon)l/2})$$.

This doesn't capture all matches, but I believe it'll give a reasonable approximation, as the overwhelming majority of $$x$$'s such that $$\text{wt}(x)=l$$ satisfy $$x=(y,z)$$ with $$\text{wt}(y) \le (1+\epsilon)l/2$$ and $$\text{wt}(z) \le (1+\epsilon)l/2$$.

This seems related to the problem of finding low-weight codewords for a linear code, except that here you want to count the number of codewords of weight $$l$$, rather than finding one codeword of weight $$\le l$$. I'm not sure whether any of the known algorithms for finding low-weight codewords can be adapted to your setting, but you could explore the literature on that problem and see if any of those techniques can be used for your goal.

• My case is the first one. This solutions helps to find the sum over all $l$, but I still need to know the answer for a given value of $l$, i.e. there is an additional condition $\sum x_e=l$. I don't see an easy way to incorporate this condition in your solution since this condition would not be in modulo 2 arithmetic. Do you know if this is still doable with this additional restriction?
– QNA
Commented Apr 8, 2023 at 0:53
• @DartLenin, oops, I apologize, I totally missed that constraint. This answer is not probably not helpful. I expect to delete it soon. I am sorry for missing that.
– D.W.
Commented Apr 8, 2023 at 3:10
• I think the answer is still helpful, since it provides some insight into the problem and solves it in a particular case when only a sum over all $l$ is of the interest, which is better than nothing.
– QNA
Commented Apr 8, 2023 at 4:44
• @DartLenin, OK. See edited answer for another attempt -- still unsatisfying.
– D.W.
Commented Apr 8, 2023 at 5:07