Cutwidth Bounds via Vertex Partitions
By: Antoine Amarilli, Benoît Groz
Potential Business Impact:
Makes computer problems easier to solve.
We study the cutwidth measure on graphs and ways to bound the cutwidth of a graph by partitioning its vertices. We consider bounds expressed as a function of two quantities: on the one hand, the maximal cutwidth y of the subgraphs induced by the classes of the partition, and on the other hand, the cutwidth x of the quotient multigraph obtained by merging each class to a single vertex. We consider in particular the decomposition of directed graphs into strongly connected components (SCCs): in this case, y is the maximal cutwidth of an SCC, and x is the cutwidth of the directed acyclic condensation multigraph. We show that the cutwidth of a graph is always in O(x + y), specifically it can be upper bounded by 1.5x + y. We also show a lower bound justifying that the constant 1.5 cannot be improved in general
Similar Papers
Minimum Partition of Polygons under Width and Cut Constraints
Computational Geometry
Cuts shapes to fit into narrow spaces.
Solving Partial Dominating Set and Related Problems Using Twin-Width
Data Structures and Algorithms
Solves hard computer puzzles faster using graph structure.
Bounds and New Constructions for Girth-Constrained Regular Bipartite Graphs
Information Theory
Makes computer codes send more data reliably.