24
$\begingroup$

I'm not a graph theorist or computational complexity specialist, so my apologies if this question is stupid or poorly posed!

Given a bipartite graph $G$ of $n$ vertices, how many induced subgraphs of $m\leq n$ vertices are there for which the total number of edges of the subgraph is odd? Or, what is the computational complexity of making such a determination?

One way to rephrase this is to take a bit string $y\in\{0,1\}^n$ so that each bit $y_k$ specifies whether or not to keep the $k^{th}$ vertex. Then the question amounts to counting the number of satisfying instances of $\bigoplus_{\{k,l\}\in E}y_ky_l=1$, where $E$ denotes the edges of $G$, and constrained by the requirement that the Hamming weight of $y$ is $m$.

While I'm interested in a result for all bipartite graphs, I'm also interested in the special case of the square lattice. I've not been able to find exactly this problem anywhere, but there are a couple of cases which I think have been answered:

  • If there is no restriction to the graph being bipartite, the problem is sharp-P complete [N. Creignou, H. Schnoor and I. Schnoor, Computer Science Logic 5213, 109 (2008), Springer Berlin.]
  • If, instead, we don't have the restriction to the $m$-vertex subgraphs, and just ask how many induced subgraphs there are with an odd number of edges, there is an efficient algorithm for counting them [A. Ehrenfeucht and M. Karpinski, The Computational Complexity of (XOR, AND)-Counting Problems, Technical Report 90-033 (1990).]
$\endgroup$
7
  • 2
    $\begingroup$ While probably not specialized enough to answer this particular question about bipartite graphs, there is a nice book which is "restricted" to the properties of bipartite graphs: Bipartite Graphs and Their Applications A. Asratian, T. Denley, R. Haggkvist, Cambridge U. Press., 1998. $\endgroup$ Jan 19, 2010 at 18:57
  • 1
    $\begingroup$ Similar problems are #P-complete, for example counting the number of induced subgraphs with m edges in a bipartite graph. (A reduction from 1-in-3 monotone 3-SAT springs to mind.) However, the result by Ehrenfeucht & Karpinksi suggests that there could be an efficient algorithm. $\endgroup$
    – Emil
    Jan 19, 2010 at 23:42
  • $\begingroup$ Question, are we picking m vertices and seeing if the set of induced edges that connect pairs of these vertices is of odd size, or are we picking an odd number of edges from the graph and checking if the set of vertices induced in this graph is of order m? as for your square lattice case, I want to guess than perhaps something involving the structure of the associated dual graphs would prove helpful (eg in the infinite case this lattice is selfdual). $\endgroup$ Mar 10, 2010 at 6:18
  • 1
    $\begingroup$ I cannot see how to apply the results by Creignou, Schnoor and Schnoor to prove the #P-completeness of the case of general graphs (not necessarily bipartite). Can you elaborate a little bit? $\endgroup$ Aug 3, 2010 at 12:00
  • $\begingroup$ Note that this is equivalent to computing the sum, over all order-m subsets of $V(G)$, of (-1) to the size of the induced subgraph on that subset. Believe it or not, similar sums have arisen in my research, which are related to counting graph homomorphisms. I'll have to think on whether it's possible to get a reduction to #3-COL in this way. $\endgroup$ Oct 4, 2010 at 4:41

2 Answers 2

1
$\begingroup$

I don't know the answer, just some thoughts.

Suppose you have $n$ vertices of the first type and $l$ of the second. Of course, you know the answer if there is no restriction on the number of edges (you want it to be odd). Therefore equivalently I can calculate cases, when it is odd with coefficient (-1) and cases, when it is even with coefficient 1 (I denote this amount by $N$). Let $y_1,\dots,y_n,z_1,\dots,z_l$ be elements of $\mathbb{Z}\_2=\mathbb{Z}/(2\mathbb{Z})$, corresponding to the vertices of the graph. Edges are given by $n\times l$ matrix $A$. Then $N$ is the coefficient of $h^m$ in $S(h,h)$, where $S$ is defined by $$S(h,g)=\sum_{y\in\mathbb{Z}\_2^n,\;z\in\mathbb{Z}\_2^l} h^{|y|} g^{|z|} (-1)^{\sum_{i,j}y_i A_{ij} z_j}.\tag{1}$$ Here $|y|$ is amount of components in $y\in \mathbb{Z}\_2^n$ which are equal to $1$. One can get rid of the sum over $y\in\mathbb{Z}\_2^n$ in the following way: $$S(h,g)=\sum_{z\in\mathbb{Z}\_2^l} g^{|z|}\prod_{i=1}^{n} (1+h(-1)^{\sum_j A_{ij} z_j}).\tag{2}$$ This for example solves the problem in two cases:
1. we fix the number of vertices only in one part of a bipartite graph and the map $\mathbb{Z}_2^l\to\mathbb{Z}_2^n\colon z\mapsto x$ with $x_i=\sum_j A_{ij} z_j$ is surjective (in this case we can omit $g^{|z|}$ in $(2)$, make described change of coordinates and apply again the trick we used to get (2) from (1));
2. amount of vertices in one part of a bipartite graph is small enough (in this case the sum (2) has small enough number of terms and each of them can be calculated in a polynomial time);

$\endgroup$
0
$\begingroup$

Unfortunately, I don't have an answer. The following observation lets me think that a clever brute force solution is near at hand, and may even find its way to an enumeration.

If m were n-1, the problem would be easy: determine the parity of the number of edges of the graph G, and determine the parity of the degree of each edge. Then the number of subgraphs on n-1 vertices with an odd number of edges is the same as the number of vertices whose degree has parity opposite that of parity of G.

Now if I were doing a brute force algorithm, and m satisfied 2*m > n, then I might use the above observation to look at the induced subgraphs on (m+1) vertices and then do the calculations over a covering set of the (m+1) subgraphs. Or there might be a 2-step version where I could use pairs of vertices in an (m+2) subgraph. It is tempting to think there is also an (n-m)-step version using generating functions or Polya enumeration, but I don't know enough to tell you about those.

When I am able to comment, then I might turn this musing from an answer into a comment.

Gerhard "Ask Me About System Design" Paseman, 2010.02.04

$\endgroup$
1
  • 2
    $\begingroup$ I do not expect that your method leads to a polynomial-time algorithm, because it seems that it would equally work in the case where G is not necessarily bipartite, where the problem is known to be #P-complete according to the references in the question. $\endgroup$ Aug 1, 2010 at 19:20

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.