質問

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

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top