[Lowerbounds, Upperbounds]

Graph Partitioning using Single Commodity Flows

Rohit Khandekar
University of Waterloo

Feb 3, 15:30-16:30
Wean 7220

Graph partitioning is one of the fundamental optimization problems that has been extensively studied both in theory and practice. In this talk, we shall consider the problem of approximating the sparsest cuts in graphs. Almost all the previous algorithms for this problem use either eigenvector computations, multi-commodity flows, or solving semi-definite programs as sub-routines. While eigenvector based approaches yield poor approximation guarantees, the multi-commodity flows or SDP based algorithms are slow.

We show that the sparsest cuts can be approximated well using single commodity max-flow computations which are fast both in theory and perhaps more so in practice. Our algorithm iteratively computes max-flows to embed a complete graph and yields a certificate of expansion. Our technique can also be extended to obtain fast approximations for the balanced separator problem.

This is a joint work with Satish Rao and Umesh Vazirani (UC Berkeley).

TITLE: Hamilton cycles in random graphs (Dissertation Proposal)
SPEAKER: Kelley Burgin
WHEN: January 30, 1:30pm
WHERE: Porter Hall A19

ABSTRACT: We discuss the existence of Hamilton cycles in three different models of random graphs. In doing so, we present general proof techniques which include the differential equation method.

The first model is the random lift model introduced by Linial and Amit. For a fixed base graph K=(V,E), a random lift has vertex set V x [n] and for each edge (i,j) in E, there is a random perfect matching between {i} x [n] and {j} x [n]. We show that random lifts of the complete graph and complete bipartite graph contain a Hamilton cycle whp.

The second model is a random graph on n vertices in which (1-b)n vertices have degree 4 and the other bn vertices have degree 5. We show that for certain values of b, the graph is Hamiltonian whp.

The last model is a sparse random graph on n vertices with cn/2 random edges and minimum degree 3. We show that this random graph is Hamiltonian for c at least 3.01.