Fast FPT Algorithms for Grundy Number on Dense Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912154777550848 |
|---|---|
| author | Nezhad, Sina Ghasemi Moghaddas, Maryam Panolan, Fahad |
| author_facet | Nezhad, Sina Ghasemi Moghaddas, Maryam Panolan, Fahad |
| contents | In this paper, we investigate the \textsc{Grundy Coloring} problem for graphs with a cluster modulator, a structure commonly found in dense graphs. The Grundy chromatic number, representing the maximum number of colors needed for the first-fit coloring of a graph in the worst-case vertex ordering, is known to be $W[1]$-hard when parameterized by the number of colors required by the most adversarial ordering. We focus on fixed-parameter tractable (FPT) algorithms for solving this problem on graph classes characterized by dense substructures, specifically those with a cluster modulator. A cluster modulator is a vertex subset whose removal results in a cluster graph (a disjoint union of cliques). We present FPT algorithms for graphs where the cluster graph consists of one, two, or $k$ cliques, leveraging the cluster modulator's properties to achieve the best-known FPT runtimes, parameterized by both the modulator's size and the number of cliques. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_10082 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast FPT Algorithms for Grundy Number on Dense Graphs Nezhad, Sina Ghasemi Moghaddas, Maryam Panolan, Fahad Data Structures and Algorithms 68W05 F.2.2 In this paper, we investigate the \textsc{Grundy Coloring} problem for graphs with a cluster modulator, a structure commonly found in dense graphs. The Grundy chromatic number, representing the maximum number of colors needed for the first-fit coloring of a graph in the worst-case vertex ordering, is known to be $W[1]$-hard when parameterized by the number of colors required by the most adversarial ordering. We focus on fixed-parameter tractable (FPT) algorithms for solving this problem on graph classes characterized by dense substructures, specifically those with a cluster modulator. A cluster modulator is a vertex subset whose removal results in a cluster graph (a disjoint union of cliques). We present FPT algorithms for graphs where the cluster graph consists of one, two, or $k$ cliques, leveraging the cluster modulator's properties to achieve the best-known FPT runtimes, parameterized by both the modulator's size and the number of cliques. |
| title | Fast FPT Algorithms for Grundy Number on Dense Graphs |
| topic | Data Structures and Algorithms 68W05 F.2.2 |
| url | https://arxiv.org/abs/2412.10082 |