Bipartite graph minimal amount of vertices required
-
06-11-2019 - |
質問
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
.
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
正しい解決策はありません