2
$\begingroup$

I have a bipartite graph made of two sets (SET 1 and SET 2) and I want to determine how many vertices from the SET 1 I can remove while still having every vertex of the SET 2 connected to at least one vertex of the SET 1. example graph In this example, E and F can obviously be removed as D and C are connected 5 and 6.
But we could also remove B as A and C together cover more points. But so far I only have a very slow implementation of this which is to compare every vertex of SET 1 to every combination of vertices of SET1.
Is there any smart way to do this? I've been thinking about Kőnig's theorem but I didn't find a way to use it in this context as it seems to be made for undirected bipartite graphs.

Also, there are some constraints the input follows:
-Every element of SET 2 is connected to SET 1
-Every node of SET 2 is connected exactly to two vertices of SET 1

$\endgroup$
  • $\begingroup$ Does any one know if this problem has a formal name? I think I might have come across it once before but I can't recall its name. $\endgroup$ – narek Bojikian Oct 23 at 22:22
  • 1
    $\begingroup$ @narek Bojikian Yeah, this looks like a very basic problem in bipartite graphs, but I couldn't find any ressources about that; tryalgo.org/en/matching/2016/08/05/konig is the closest I found. $\endgroup$ – Neirpyc Oct 24 at 9:46
1
$\begingroup$

Let's define a graph $G=(V,E)$, for which:

  • Set of vertices $V$ is identical to your SET1.
  • Two vertices $v_1,v_2 \in V$ are connected by an edge, if and only if there exists a vertex from the SET2, incident to both $v_1$ and $v_2$ in your bipartite graph.

For instance, the graph below corresponds to the bipartite graph from the example in your question:

ABCDEF

Now, your problem is reduced to the Minimum Vertex Cover problem on the graph $G$, defined above, so you'll be able to use known algorithms to find minimum vertex cover in your SET1 only.

This graph $G$ doesn't have any special structure, which could be used to find its minimum vertex cover more effectively than in general case. Also, any graph can be transformed to your bipartite graph form by splitting each edge by a new vertex. So, it means that your problem is equivalent to the minimum vertex cover problem, which is NP-complete - thanks to @narekBojikian for mentioning that in his answer.

$\endgroup$
  • $\begingroup$ But minimum vertex cover is np-hard, do you think the proposed problem is also np-hard? If not this is not very useful approach since we will be interested in a polynomial solution $\endgroup$ – narek Bojikian Oct 23 at 22:03
  • 1
    $\begingroup$ @narekBojikian - I don't see any way to solve it in polynomial time. $\endgroup$ – HEKTO Oct 23 at 22:19
  • $\begingroup$ You are right, I just proposed a reduction from vertex-cover, I hope I did not mess up any thing among my calculation since @D.W. is suggesting it is solvable through max-flow $\endgroup$ – narek Bojikian Oct 23 at 22:20
  • $\begingroup$ Isn't the graph G bipartite? $\endgroup$ – Neirpyc Oct 24 at 12:13
  • $\begingroup$ Not necessarily - consider a $K_3$ (triangle) $\endgroup$ – HEKTO Oct 24 at 13:37
1
$\begingroup$

This problem is NP-Hard. I will present a simple reduction from the vertex-cover problem to this problem. This reduction shows that there is probably no polynomial time algorithm for this problem, since such an algorithm will implies a polynomial time algorithm for the vertex cover problem which will implies that P=NP, since the vertex cover problem is NP-complete.

So given a graph $G(V, E)$ as an instance of the vertex cover problem, Let us build the bipartite graph $G'(V_1, V_2, E')$, where $V_1$ is a copy of $V$, $V_2$ is a copy of $E$ and $E'$ represent the incident relation in the graph, meaning that a vertex $v_1 \in V_1$ is adjacent to a vertex $v_2 \in V_2$ in $G'$, if the the edge corresponding to $v_2$ in $E$ is incident to the vertex corresponding to $v_1$ in $V$. Let $n$ be the number of vertices and $m$ the number of edges in the given graph.

Let us call your problem $P$. We claim that $G$ admits a vertex cover of size $k$, if and only if the problem $P$ on the graph $G'$ admits a solution of size $n - k$.

Proof. Note that $P$ admits a solution of size $n-k$, meaning that there are $k$ vertices adjacent to all vertices in $V_2$, meaning that there are $k$ vertices in $V$ incident to all edges in $E$, meaning that $G$ has a vertex cover of size $k$.

This proof shows the correctness of the reduction in both directions. (If $G$ admits a vertex cover of size $k$ then $G'$ admits a solution of $P$ of size $n-k$ and if $G'$ admits a solution of size $n-k$ then $G$ admits a vertex cover of size $k$).

This completes the proof that $P$ is NP-hard. @HEKTO showed a reduction in the other direction, proving that $P$ is NP-complete as well.

$\endgroup$

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.