A Faster Algorithm for Independent Cut
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918029006209024 |
|---|---|
| author | Chernyshev, Vsevolod Rauch, Johannes Rautenbach, Dieter Redina, Liliia |
| author_facet | Chernyshev, Vsevolod Rauch, Johannes Rautenbach, Dieter Redina, Liliia |
| contents | The previously fastest algorithm for deciding the existence of an independent cut had a runtime of $\mathcal{O}^*(1.4423^n)$, where $n$ is the order of the input graph. We improve this to $\mathcal{O}^*(1.4143^n)$. In fact, we prove a runtime of $\mathcal{O}^*\left( 2^{(\frac{1}{2}-α_Δ)n} \right)$ on graphs of order $n$ and maximum degree at most $Δ$, where $α_Δ=\frac{1}{2+4\lfloor \fracΔ{2} \rfloor}$. Furthermore, we show that the problem is fixed-parameter tractable on graphs of order $n$ and minimum degree at least $βn$ for some $β> \frac{1}{2}$, where $β$ is the parameter. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_15434 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Faster Algorithm for Independent Cut Chernyshev, Vsevolod Rauch, Johannes Rautenbach, Dieter Redina, Liliia Data Structures and Algorithms 68R10 G.2.2 The previously fastest algorithm for deciding the existence of an independent cut had a runtime of $\mathcal{O}^*(1.4423^n)$, where $n$ is the order of the input graph. We improve this to $\mathcal{O}^*(1.4143^n)$. In fact, we prove a runtime of $\mathcal{O}^*\left( 2^{(\frac{1}{2}-α_Δ)n} \right)$ on graphs of order $n$ and maximum degree at most $Δ$, where $α_Δ=\frac{1}{2+4\lfloor \fracΔ{2} \rfloor}$. Furthermore, we show that the problem is fixed-parameter tractable on graphs of order $n$ and minimum degree at least $βn$ for some $β> \frac{1}{2}$, where $β$ is the parameter. |
| title | A Faster Algorithm for Independent Cut |
| topic | Data Structures and Algorithms 68R10 G.2.2 |
| url | https://arxiv.org/abs/2505.15434 |