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

Improve this question
$\endgroup$
2
  • $\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
    Commented Oct 24, 2016 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
    Commented Oct 24, 2016 at 15:12

1 Answer 1

Reset to default
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.

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

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.