3
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ 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?) $\endgroup$ – j_random_hacker Oct 24 '16 at 14:55
  • $\begingroup$ $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. $\endgroup$ – Peter Taylor Oct 24 '16 at 15:12
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – aelguindy Oct 21 '16 at 17:19
  • $\begingroup$ Oops, my mistake! Thanks for explaining. $\endgroup$ – D.W. Oct 21 '16 at 17:21
  • $\begingroup$ @D.W. Np, if you look at my edit history, I got that same misunderstanding twice ;). $\endgroup$ – aelguindy Oct 21 '16 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.