Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917924581670912 |
|---|---|
| author | Bentert, Matthias Fomin, Fedor V. Inamdar, Tanmay Saurabh, Saket |
| author_facet | Bentert, Matthias Fomin, Fedor V. Inamdar, Tanmay Saurabh, Saket |
| contents | In this paper, we begin the exploration of vertex-ordering problems through the lens of exponential-time approximation algorithms. In particular, we ask the following question: Can we simultaneously beat the running times of the fastest known (exponential-time) exact algorithms and the best known approximation factors that can be achieved in polynomial time? Following the recent research initiated by Esmer et al. (ESA 2022, IPEC 2023, SODA 2024) on vertex-subset problems, and by Inamdar et al. (ITCS 2024) on graph-partitioning problems, we focus on vertex-ordering problems. In particular, we give positive results for Feedback Arc Set, Optimal Linear Arrangement, Cutwidth, and Pathwidth. Most of our algorithms build upon a novel ``balanced-cut'' approach, which is our main conceptual contribution. This allows us to solve various problems in very general settings allowing for directed and arc-weighted input graphs. Our main technical contribution is a (1+ε)-approximation for any ε > 0 for (weighted) Feedback Arc Set in O*((2-δ)^n) time, where δ > 0 is a constant only depending on ε. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_10909 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems Bentert, Matthias Fomin, Fedor V. Inamdar, Tanmay Saurabh, Saket Data Structures and Algorithms In this paper, we begin the exploration of vertex-ordering problems through the lens of exponential-time approximation algorithms. In particular, we ask the following question: Can we simultaneously beat the running times of the fastest known (exponential-time) exact algorithms and the best known approximation factors that can be achieved in polynomial time? Following the recent research initiated by Esmer et al. (ESA 2022, IPEC 2023, SODA 2024) on vertex-subset problems, and by Inamdar et al. (ITCS 2024) on graph-partitioning problems, we focus on vertex-ordering problems. In particular, we give positive results for Feedback Arc Set, Optimal Linear Arrangement, Cutwidth, and Pathwidth. Most of our algorithms build upon a novel ``balanced-cut'' approach, which is our main conceptual contribution. This allows us to solve various problems in very general settings allowing for directed and arc-weighted input graphs. Our main technical contribution is a (1+ε)-approximation for any ε > 0 for (weighted) Feedback Arc Set in O*((2-δ)^n) time, where δ > 0 is a constant only depending on ε. |
| title | Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.10909 |