Videos

Counting and sampling minimum cuts in weighted planar graphs

Presenter
January 13, 2012
Keywords:
  • lattice theory
  • lattice models in mechanics
  • min cut/max flow
  • planar graphs
  • colored graphs
  • weighted graphs
  • dynamic programming
  • antichains
MSC:
  • 60K35
  • 60J65
  • 60J67
  • 60Jxx
  • 60-xx
  • 82-xx
  • 06-xx
  • 05C20
  • 05C21
  • 05C15
  • 05C12
  • 05C10
  • 05Cxx
  • 05-xx
Abstract
We will discuss two minimum cut problems in weighted planar graphs: minimum source-sink cuts and contiguous minimum single-source-multi-sink cuts. A source-sink cut is a set of vertices containing the source vertex and not the sink vertex (or, in the case of multiple sinks, not containing any of the sink vertices). A cut is minimum if the sum of the weights of the cut edges, connecting a vertex in the cut set with a vertex outside the cut set, is the smallest possible. A cut is contiguous if the cut set can be separated from the remaining vertices by a simply connected planar region whose boundary intersects only the cut edges. We will present an O(n^2) algorithm counting all minimum source-sink cuts in weighted planar graphs, where n is the number of vertices. We will also sketch an O(n^3) algorithm counting all contiguous minimum single-source-multi-sink cuts. In both cases, having completed the counting part, subsequent sampling is very fast: a uniformly random cut can be produced in additional linear time. The counting algorithms share a common outline. First, we reduce the problem to the problem of counting a different type of cuts in an unweighted planar directed acyclic graph (these cuts can also be thought of as maximal antichains in the corresponding partially ordered set). These cuts correspond to certain cycles in the planar dual graph and we employ dynamic programming to count them. We will discuss the first algorithm in detail and briefly sketch the issues encountered by the contiguity requirement. Minimum source-sink and contiguous minimum single-source-multi-sinks cuts have applications in computer vision and medical imaging where the underlying graph often forms a 2D grid (lattice). Based on joint works with Adam Friedlander and Zach Langley.
Supplementary Materials