# Partitioning a bipartite graph to get disjoint components of same size

I have a bipartite graph $G = (V, E)$ where $V = S \cup T$ is the division into the two halves. I want to select $n$ elements from $S$ and $nk$ elements from $T$ such that the graph they generate has $n$ connected components, each of size $k+1$ and containing one element of $S$. To be clear, $n$ and $k$ are inputs to the problem: it's not a maximisation problem.

The naïve brute force algorithm would consider $\binom{S}{n}$ candidate subsets of $S$, and would do $O(E)$ work for each to identify vertices in $T$ which have an edge to exactly one element of the candidate subset of $S$. For fixed $n$ that's $O(S^n E)$.

I'm not optimistic, because it's an independence problem, but is there an algorithm for fixed $n$ and $k$ whose running time is polynomial in $E$ with exponent independent of $n$ and $k$?

• Do you mean "with neither $n$ nor $k$ appearing in any exponent"? Because if so, and if you further require polynomiality in $E$, then I don't see what's left that the algorithm is permitted to be "exponential in" -- IOW, it would seem you're looking for an algorithm that is poly-time in all parameters, which is ruled out by aelguindy's reduction. (If OTOH you meant "with the exponent of $E$ independent of $n$ and $k$", then isn't this already achieved by your $O(S^nE)$ algorithm?) – j_random_hacker Oct 24 '16 at 14:55
• $O(S^n E)$ is not polynomial in $E$, unless you use the fact that $S \in O(E)$ to simplify it to $O(E^{n+1})$, in which case the exponent is not independent of $n$. As aelguindy comments in response to a deleted comment on his answer, an algorithm in $O(f(n, k) \,E^a)$ would do. – Peter Taylor Oct 24 '16 at 15:12

Your problem is NP-hard, even for any fixed $k \geq 3$ by a straight-forward reduction from 3-SET-COVER. Quick explanation: nodes of $S$ are triplets, nodes of $T$ are set elements and each triplet connected to all elements it contains.
I am still thinking about the case when $n$ is fixed.
• @D.W. OP asks for an algorithm that runs in poly(E) with an exponent that is NOT a function of n. Something like $O(2^{f(n)} poly(E))$. I am guessing that this is hard, I just cannot prove it yet. – aelguindy Oct 21 '16 at 17:19