Suppose a bipartite graph $g$ consisting of $2n(n-1),n\in\Bbb N,n>1$ vertices, is divided equally into two colors: red and blue, and is constructed as follows:

enter image description here

For example, $g$ for $n=3$:

enter image description here

If I choose a set of vertices exclusively from one color, I could find the set of vertices from the other color that is a neighbour to at least one vertex in my set. For example, if I choose the following solid red vertices from the graph $n=3$, the set of unique neighbours to these vertices are highlighted in solid blue:

enter image description here

In this case, there are five unique blue neighbours. How could I go about finding the number of unique sets of red vertices such that the number of unique blue neighbours is exactly $k,2≤k≤n(n-1)$?

I know that finding the number of unique blue neighbours depends on the location of each red vertex (corner, edge or interior) and the location of each vertex with respect to the others (directly horizontally- and vertically- adjacent vertices will share two blue neighbours, while diagonally-adjacent vertices will share one), but I'm having a hard time conceptualizing a general approach much more sophisticated than brute force.

  • $\begingroup$ Is an $O(2^{2n}n^3)$-time, $O(2^nn^2)$-space DP algorithm interesting? Briefly the idea is to compute $f(p, k, m)$, the number of red vertex sets in a partial-height graph containing $m \le n$ full-width row pairs that (i) have $p$ as their topmost red row and (ii) contain exactly $k$ blue vertices below the topmost red row. This time complexity is pretty horrible, but at least better than the naive algorithm's $O(2^{n^2})$... $\endgroup$ Jun 26, 2015 at 20:41
  • $\begingroup$ Actually I think it's possible to drop the time complexity to $O(2^nn^4)$ by calculating $g(q, j, m)$, i.e., the number of red vertex sets in a height-$m$ graph that (i) have $q$ as their topmost blue row and (ii) have exactly $j$ blue vertices. For a fixed $m$ and for all $q$ and $j$, the contribution to $g(q, j, m)$ that is "forced" by the next red row can be found in $O(2^nn^2)$ time using a single pass through $f(p, k, m)$ for all $p$ and $k$; then we can "push" counts up by looping through $g()$ in order of increasing $|q|$ and inserting each absent (not-blue) vertex into $q$ in turn. $\endgroup$ Jun 27, 2015 at 0:06


You must log in to answer this question.

Browse other questions tagged .