The Taub Faculty of Computer Science Events and Talks

We study several graph layout problems with a min max objective. Here, given a graph we wish to find a linear ordering of the vertices that minimizes some worst case objective over the natural cuts in the ordering; which separate an initial segment of the vertices from the rest. A prototypical problem here is cutwidth, where we want to minimize the maximum number of edges crossing a cut. The only known algorithm here is by [Leighton-Rao J.ACM 99] based on recursively partitioning the graph using balanced cuts. This achieves an O(log^(3/2)n) approximation using the O(log^(1/2)n) approximation of [Arora-Rao-Vazirani J.ACM 09] for balanced cuts.

We depart from the above approach and give an improved O(log^(1+o(1))n) approximation for cutwidth. Our approach also gives a similarly improved O(log^(1+o(1))n) approximation for finding the pathwidth of a graph. Previously, the best known approximation for pathwidth was O(log^(3/2)n).

Talk is based on a joint work with Nikhil Bansal and Roy Schwartz.