On Approximating Cutwidth and Pathwidth

We study graph ordering problems with a min-max objective. A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized. We give a $\log^{1+o(1)}(n)$ approximation for the problem, substantially improving upon the previous poly-logarithmic guarantees based on the standard recursive balanced partitioning approach of Leighton and Rao (FOCS'88). Our key idea is a new metric decomposition procedure that is suitable for handling min-max objectives, which could be of independent interest. We also use this to show other results, including an improved $\log^{1+o(1)}(n)$ approximation for computing the pathwidth of a graph.

Authors

• Nikhil Bansal 0001
• Dor Katzelnick
• Roy Schwartz 0002

Keywords

• Measurement
• Computer science
• Approximation algorithms
• Partitioning algorithms
• Standards
• Path Width
• Recursive Partitioning
• Decomposition Procedure
• Undirected
• Size Classes
• Directed Graph
• Topological States
• Directed Acyclic Graph
• Large Pieces
• Ball Of Radius
• Exact Algorithm
• Linear Arrangement
• Graph Layout
• Induced Subgraph
• Interesting Open Question
• Linear Programming Relaxation
• Minimum Bandwidth
• Ordering Of The Vertices
• Minimum Storage
• Radius Scaling
• Graph partitioning
• Min-max objectives