Karger_Stein.H File Reference

Karger-Stein randomized min-cut algorithm (alias for Karger.H fast method). More...

#include <Karger.H>

Include dependency graph for Karger_Stein.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Typedefs
template<class GT , class SA = Dft_Show_Arc<GT>>
using	Aleph::Karger_Stein_Min_Cut = Karger_Min_Cut< GT, SA >
	Alias for Karger_Min_Cut (use fast() method for Karger-Stein)

Detailed Description

Karger-Stein randomized min-cut algorithm (alias for Karger.H fast method).

This header provides the Karger-Stein algorithm as an alias to the fast() method in Karger_Min_Cut. The implementation is in Karger.H.

Algorithm Description

The Karger-Stein algorithm improves upon the basic Karger algorithm by observing that most of the randomness is "wasted" when the graph is large. The probability of contracting a min-cut edge increases as the graph shrinks, so the algorithm:

1. Contract to √(2n) vertices: Randomly contract edges until only ⌈n/√2⌉ + 1 vertices remain. This phase has high probability of preserving the min-cut.
2. Recurse twice: Make two independent recursive calls on the contracted graph. This branching compensates for the increasing probability of error as the graph shrinks.
3. Return minimum: Return the smaller of the two cuts found.

Time Complexity

• Karger basic: O(n² m) per iteration × O(n²) iterations = O(n⁴ m)
• Karger-Stein: O(n² log³ n) total

Usage

Use Karger_Min_Cut<GT>::fast() method from Karger.H:

#include <Karger.H>
 
Karger_Min_Cut<GT> karger;
DynList<GT::Node*> S, T;
DynList<GT::Arc*> cut_arcs;
 
// Fast Karger-Stein: O(n² log³ n)
size_t cut_size = karger.fast(g, S, T, cut_arcs);

See also

Karger_Min_Cut The main class with both standard and fast methods

Stoer_Wagner_Min_Cut Deterministic O(nm + n² log n) algorithm

Author

Leandro Rabindranath León

Definition in file Karger_Stein.H.