5
$\begingroup$

Given:

  • A bipartite graph G=(U,V,E)
  • Integers n and k.

Decision Problem:

  • Is there a subset of U of size k that has at most n neighbours?

I am trying to figure out whether this problem is NP-hard (I suspect so), but couldn't find any reduction so far. The only well-known NP-hard problems for bipartite graphs seem to be finding bipartite subgraphs in graphs [1], and railway schedule optimization. It seems somewhat like an inverse of set cover, but is also different from set packing (which appears called as inverse of set cover).

Does anyone have ideas which problems could be related?

[1]: Computers and Intractability: A Guide to the Theory of NP-Completeness

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Since you are also asking about related problems: Some time ago, we showed that the Hall Set problem is W[1]-hard parameterized by k: Given a bipartite graph G=(U,V,E) and an integer k, is there a subset S of U of size at most k such that |N(S)| < |S|? The reduction is similar to David's reduction below and also proves NP-hardness. We needed it as an intermediate problem to prove W[1]-hardness of a Local Search problem. See aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/4929 $\endgroup$
    – Serge Gaspers
    Commented Nov 24, 2015 at 22:27

1 Answer 1

Reset to default
10
$\begingroup$

It's NP-complete by a reduction from cliques in graphs. Given an arbitrary graph $G$, construct a bipartite graph from its incidence matrix, by making one side $U$ of the bipartition correspond to the edges of $G$ and the other side correspond to the vertices of $G$. Then $G$ has a clique of size $\omega$ if and only if the constructed bipartite graph has a set of $\binom{\omega}{2}$ vertices in $U$ that has at most $\omega$ neighbors on the other side of the bipartition.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot, that looks elegant! Will credit you should this go any further. $\endgroup$
    – Simon Razniewski
    Commented Nov 21, 2015 at 11: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.