On Approximating Cutwidth and Pathwidth

2023/11/27 by Nikhil Bansal, Bansal, Nikhil, Dor Katzelnick +3 · 1 citation
Computer Science · Engineering · #Complexity and Algorithms in Graphs #VLSI and FPGA Design Techniques #Optimization and Packing Problems

paper · pdf · doi:10.48550/arxiv.2311.15639

Abstract

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.

Cited by

• Expander Decomposition with Almost Optimal Overhead

Related

• Cutwidth: obstructions and algorithmic aspects
• Path optimization and near-greedy analysis for graph partitioning: an empirical study
• Cutwidth and Crossings
• Min-Max Graph Partitioning and Small Set Expansion
• Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes