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

Solving the above problem by vertex cover approach results in exponential tim algorithm but this can be solved by maximizing flows using Ford Fulkerson algorithm Above problem can be solved using Ford Fulkerson.

1. Create a path from source(0) to all nodes of the graph with capacity = t.
2. Create a path from from all nodes to target(1) with capacity = 1.
3. Find a max flow of the above modified graph using Ford Fulkerson.

Ford Fulkerson Algorithm to find max flow in the given Graph

1. Find a path from source to target in the graph.
2. Find the minimum flow along the path.
3. Increase the flow of all edges along the path by min flow calculated above
4. Store the min flow of the path.

Repeat the above 4 steps till no augmenting path possible.

Explanation for Ford Fulkerson Alogrithm

Chose one possible path and identify the edge with the smallest capacity. Record this number Substract this number from each number on that path. This is the new capacity for each arc long the path. Chose another route and repeat step 1 once again record the smallest capacity. Repeat untill all possible path are exhausted. Add the smallest capacities of all routes. This is the minimum carrying capacity of the network

Reference

http://anandtechblog.blogspot.in/search/label/Ford%20Fulkerson%20algorithm

Answer 2

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 3

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.