Minimum K-Cut

Problem definition.

In minimum k-cut we have graph G and number k. The goal is to find minimum cost set of edges whose removal leaves k components.

Solution

Minimum K-Cut problem is solved by greedy algorithm. We start from graph G. and in each step we remove lightest cut to increase number components by 1

Example

#include "paal/greedy/k_cut/k_cut.hpp"

#include <boost/graph/adjacency_list.hpp>

#include <iostream>

int main() {
    // sample data
    std::vector<std::pair<int,int>> edges_p {{1,2},{1,5},{2,3},{2,5},{2,6},
        {3,4},{3,7},{4,7},{4,0},{5,6},{6,7},{7,0}};
    std::vector<int> costs{2,3,3,2,2,4,2,2,2,3,1,3};
    boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
                    boost::no_property,
                    boost::property<boost::edge_index_t, std::size_t>
                    > graph(8);
    for (std::size_t i = 0; i < edges_p.size(); ++i) {
        add_edge(edges_p[i].first, edges_p[i].second, i, graph);
    }
    const int parts = 3;

    auto edge_id = get(boost::edge_index, graph);
    auto weight = make_iterator_property_map(costs.begin(), edge_id);

    // solve
    int cost_cut;
    std::vector<std::pair<int,int>> vertices_parts;
    cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts),
            boost::weight_map(weight));

    // alternative form
    // cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts));
    // this works if the graph has and internal edge weight property map

    // print result
    std::cout << "cost cut:" << cost_cut << std::endl;
    std::vector<int> vertices_to_parts;
    for (auto i: vertices_parts) {
        std::cout << i.first << "(" << i.second << "), ";
    }
    std::cout << std::endl;
}

example file is k_cut_example.cpp

Parameters

IN: const Graph& g

IN: unsigned int number_of_parts

OUT: OutputIterator result The pair of vertex descriptor and id of part will be output to the result output iterator The iterator type must be a model of Output Iterator

Named Parameters

IN: vertex_index_map(VertexIndexMap index_map)

IN: weight_map(EdgeWeightMap weight_map) map contains weights of edges

Approximation Ratio equals 2-2/k.

Complexity

Complexity of the algorithm is \(O(|K|*|V|*|E|*log(|E|)|)\) where K is number from the input, V is number of vertices and E is number of edges

Memory complexity of the algorithm is \(O(|K|*(|V|+|E|)|)\) where K is number from the input, V is number of vertices and E is number of edges

References

The algorithm analysis is described in [22]