Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Almost Logarithmic Approximation for Cutwidth and Pathwidth
event speaker icon
Dor Katzelnick (Ph.D. Thesis Seminar)
event date icon
Wednesday, 31.01.2024, 12:30
event location icon
Taub 201
event speaker icon
Advisor: Prof. Roy Schwartz
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, and held together with the theory seminar.