Local Search Improvements for Soft Happy Colouring
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916810557751296 |
|---|---|
| author | Shekarriz, Mohammad Hadi Thiruvady, Dhananjay Nazari, Asef Imrich, Wilfried |
| author_facet | Shekarriz, Mohammad Hadi Thiruvady, Dhananjay Nazari, Asef Imrich, Wilfried |
| contents | For $0\leq ρ\leq 1$ and a coloured graph $G$, a vertex $v$ is $ρ$-happy if at least $ρ\mathrm{deg}(v)$ of its neighbours have the same colour as $v$. Soft happy colouring of a partially coloured graph $G$ is the problem of finding a vertex colouring $σ$ that preserves the precolouring and has the maximum number of $ρ$-happy vertices. It is already known that this problem is NP-hard and directly relates to the community structure of the graphs; under a certain condition on the proportion of happiness $ρ$ and for graphs with community structures, the induced colouring by communities can make all the vertices $ρ$-happy. We show that when $0\leq ρ_1<ρ_2\leq 1$, a complete $ρ_2$-happy colouring has a higher accuracy of community detection than a complete $ρ_1$-happy colouring. Moreover, when $ρ$ is greater than a threshold, it is unlikely for an algorithm to find a complete $ρ$-happy colouring with colour classes of almost equal sizes. Three local search algorithms for soft happy colouring are proposed, and their performances are compared with one another and other known algorithms. Among them, the linear-time local search is shown to be not only very fast, but also a reliable algorithm that can dramatically improve the number of $ρ$-happy vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19284 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Local Search Improvements for Soft Happy Colouring Shekarriz, Mohammad Hadi Thiruvady, Dhananjay Nazari, Asef Imrich, Wilfried Discrete Mathematics Combinatorics 05C15, 05C80, 05C85 For $0\leq ρ\leq 1$ and a coloured graph $G$, a vertex $v$ is $ρ$-happy if at least $ρ\mathrm{deg}(v)$ of its neighbours have the same colour as $v$. Soft happy colouring of a partially coloured graph $G$ is the problem of finding a vertex colouring $σ$ that preserves the precolouring and has the maximum number of $ρ$-happy vertices. It is already known that this problem is NP-hard and directly relates to the community structure of the graphs; under a certain condition on the proportion of happiness $ρ$ and for graphs with community structures, the induced colouring by communities can make all the vertices $ρ$-happy. We show that when $0\leq ρ_1<ρ_2\leq 1$, a complete $ρ_2$-happy colouring has a higher accuracy of community detection than a complete $ρ_1$-happy colouring. Moreover, when $ρ$ is greater than a threshold, it is unlikely for an algorithm to find a complete $ρ$-happy colouring with colour classes of almost equal sizes. Three local search algorithms for soft happy colouring are proposed, and their performances are compared with one another and other known algorithms. Among them, the linear-time local search is shown to be not only very fast, but also a reliable algorithm that can dramatically improve the number of $ρ$-happy vertices. |
| title | Local Search Improvements for Soft Happy Colouring |
| topic | Discrete Mathematics Combinatorics 05C15, 05C80, 05C85 |
| url | https://arxiv.org/abs/2506.19284 |