Blog

For a coloured graph G and 0 ≤ ρ ≤ 1, a vertex v is ρ-happy if at least ρ.deg(v) of its neighbours share its colour. The soft happy colouring problem seeks a complete colouring σ that extends a given precolouring and maximises the number of ρ-happy vertices [0]. This NP-hard problem is closely linked to community detection in graphs. For example, for a graph in the stochastic block model (SBM) and for suitable ρ, with high probability, complete soft happy colourings can be achieved by the planted community structure [1]. Moreover, for 0 ≤ ρ1 ≤ ρ2 ≤ 1, complete ρ2-happy colourings achieve higher detection
accuracy than complete ρ1-happy colourings, and when ρ surpasses a critical threshold, it is unlikely to find a complete ρ-happy colouring with near-equal class sizes [2]. Finally, we survey existing algorithms and propose novel heuristic, local search, evolutionary, metaheuristic, and matheuristic approaches that enhance solution quality for soft happy colouring [3].

[0] P. Zhang and A. Li. Algorithmic aspects of homophyly of networks. Theoretical Computer Science, 593:117–131, 2015.
[1] Shekarriz, M.H., Thiruvady, D., Nazari, A., & Lewis, R. (2025). Soft happy colourings and community structure of networks. Computers & Operations Research, 174, 106893.
[2] Shekarriz, M.H., Thiruvady, D., Nazari, A., & Imrich, W. (2025). Local Search Improvements for Soft Happy Colouring. arXiv preprint arXiv:2506.19284.
[3] Shekarriz, M.H., Thiruvady, D., & Nazari, A. (2025). Finding happiness by evolutionary algorithms. arXiv preprint arXiv:2508.20934.