Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909138416566272 |
|---|---|
| author | Chaplick, Steven Frohn, Martin Kelk, Steven Lottermoser, Johann Mihalak, Matus |
| author_facet | Chaplick, Steven Frohn, Martin Kelk, Steven Lottermoser, Johann Mihalak, Matus |
| contents | In this article we prove that the minimum-degree greedy algorithm, with adversarial tie-breaking, is a $(2/3)$-approximation for the Maximum Independent Set problem on interval graphs. We show that this is tight, even on unit interval graphs of maximum degree 3. We show that on chordal graphs, the greedy algorithm is a $(1/2)$-approximation and that this is again tight. These results contrast with the known (tight) approximation ratio of $\frac{3}{Δ+2}$ of the greedy algorithm for general graphs of maximum degree $Δ$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_10868 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs Chaplick, Steven Frohn, Martin Kelk, Steven Lottermoser, Johann Mihalak, Matus Data Structures and Algorithms In this article we prove that the minimum-degree greedy algorithm, with adversarial tie-breaking, is a $(2/3)$-approximation for the Maximum Independent Set problem on interval graphs. We show that this is tight, even on unit interval graphs of maximum degree 3. We show that on chordal graphs, the greedy algorithm is a $(1/2)$-approximation and that this is again tight. These results contrast with the known (tight) approximation ratio of $\frac{3}{Δ+2}$ of the greedy algorithm for general graphs of maximum degree $Δ$. |
| title | Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.10868 |