1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ @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. $\endgroup$
    – QNA
    Commented Apr 7, 2023 at 15:57
  • $\begingroup$ 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'$)? $\endgroup$
    – D.W.
    Commented Apr 7, 2023 at 17:51
  • $\begingroup$ @D.W. I mean $G'=(V,E')$, i.e. the set of vertices remains the same regardless of what subset of edges we consider. $\endgroup$
    – QNA
    Commented Apr 8, 2023 at 0:44

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – QNA
    Commented Apr 8, 2023 at 0:53
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Commented Apr 8, 2023 at 3:10
  • $\begingroup$ 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. $\endgroup$
    – QNA
    Commented Apr 8, 2023 at 4:44
  • 1
    $\begingroup$ @DartLenin, OK. See edited answer for another attempt -- still unsatisfying. $\endgroup$
    – D.W.
    Commented Apr 8, 2023 at 5:07

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.