Search code examples
algorithmgraphgraph-theorynetwork-flow

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

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
Solution

  • 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