Optimal Cuts in Surface Imbedded Graphs

Speaker: Kyle Fox , ICERM

Date: Wednesday, April 02, 2014

Time: 4:30 PM to 5:30 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Ilya Razenshteyn

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/421

Speaker URL: None

Speaker Photo:

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Algorithms & Complexity Seminar: Kyle Fox

In this talk, I will describe some recent algorithmic results related to computing optimal flows and cuts in surface embedded graphs. These results are motivated by a desire to bring our understanding of efficient planar flow and cut algorithms to more general classes of graphs.

I will begin by sketching an algorithm to compute a global minimum cut in an embedded genus g undirected graph. The algorithm runs in time g^O(g) n log log n. For constant g, this running time is a polylogarithmic improvement over the best known running time for sparse graphs due to Karger. Unlike Karger’s algorithm, the one I will describe is deterministic

Second, I will describe an algorithm for counting minimum s,t-cuts in an embedded genus g directed graph. This problem has applications in image segmentation, and despite the problem being #P-complete in general, the algorithm I will describe runs in 2^O(g) n^2 time. The algorithm can also be used to aid in sampling minimum s,t-cuts uniformly at random.

When the genus is constant, both algorithms I will describe match the running time of the best known planar graph algorithms for their respective problems. I will conclude the talk by discussing some future work and open problems in this area of research.

This talk is based on work done with Erin W. Chambers, Jeff Erickson, and Amir Nayyeri.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Rebecca Yadegar Email at Tuesday, March 25, 2014 at 4:35 PM.