Crab Graphs, Algorithms, Graph Theory, How is this network flow?

Question

Can somebody please help me out with this problem? The solution is apparently using network flow but I am not very familiar with network flow. How does network flow help you solve this?

A crab is an undirected graph which has two kinds of vertices: 1 head, and K feet , and exactly K edges which join the head to each of the legs.( 1 <= K <= T, where T is given)

Given an undirected graph, you have to find in it some vertex-disjoint subgraphs where each one is a crab . The goal is to select those crabs in such a way that the total number of vertices covered by them is maximized.

Note: two graphs are vertex-disjoint if they do not have any vertex in common.

ex . input

8 2 7
1 4
2 4
3 4
5 4
5 8
5 7
5 6

Answer 1

Think how can Network Flow can be applied to this problem. It should be something like that a flow passes from head of the crab to its feet. And flow coming to the head should be having a value equivalent to number of feet and each edge from head to feet of crab should have capacity one.

How can we achieve that? It is definitely tough to come to this by oneself but I hope after seeing the example multiple times you can get the hang of this.

We have to create a new graph where original vertices are duplicated. One set can give every vertex to have a chance of being head and other set can act as feet. Keeping this in mind, the precise algo can be written as following:-

1. We create a new graph where original vertices are duplicated (vertex i  becomes 2*i (head set) and 2*i+1  (feet set)    ).

2.For i and j vertices connected in original graph make sure that 2*i and 2*j+1 plus 2*j and 2*i+1 gets connected in new graph with capacity 1.

3.source vertex (S) is connected to each 2*i vertex(head set) with capacity min(T, degree).
4. Each 2*i+1(feet set) vertex is connected to target vertex (T) with capacity 1
5. Maxflow is the answer.

The image below can give a decent idea of how the graph forms. New Graph formation

Explanation of point 3:- every vertex in the headset should be connected with source with capacity min(t, degree) because if we would to like to have a max flow at this edge to be as large as T, not more than that because because crab cannot have more than t feet and value of capacity here is also limited by degree of vertex to which 0 is connected. A head cannot have more feet than its degree.

Explanation of point 4:- To ensure pairs are disjoint so that each vertex come only in one crab, every feet is connected with capacity 1 to the target 10 in figure.

I can post the code if it is required.

Answer 2

That is a vertex cover problem. With vertex cover of a graph, crab heads are vertices of a vertex cover, and feet are vertices connected to these heads. Duplicated feet should be removed, while taking a care not to remove all feet of one crab :-)

Update:

Minimal vertex cover is a NP-complete, what isn't nice :-) I think that crab cover is equivalent. At least having minimal crab covering we can get minimal vertex cover. So, if minimal crab isn't in NP-complete, than minimal vertex cover also shouldn't be NP-complete.

Lets prove that having minimal crab covering we can get minimal vertex cover. In standard way we get vertex cover with crab heads. Assume contrary, that there is a vertex cover of lower degree, with less vertices in cover than crab heads. For that vertex cover we can construct crab cover with same degree, except that we are not sure is there a crab without a foot because of removing duplicate feet. That can be case only if there is a head with feet that are shared with other heads where each other head doesn't have any other foot. In that case we can construct even smaller vertex cover by removing these 2 heads and setting head on that critical foot. With that we have a contradiction, so there is no vertex cover with less vertices. So minimal crab cover is also a minimal vertex cover.