Cutwidth Bounds via Vertex Partitions
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917975557144576 |
|---|---|
| author | Amarilli, Antoine Groz, Benoît |
| author_facet | Amarilli, Antoine Groz, Benoît |
| contents | 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 |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_01574 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cutwidth Bounds via Vertex Partitions Amarilli, Antoine Groz, Benoît Data Structures and Algorithms Discrete Mathematics 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 |
| title | Cutwidth Bounds via Vertex Partitions |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2504.01574 |