The Maximum Induced Happy Subgraph Problem: A Path-based Branch-and-Cut Approach

This work addresses the Maximum Happy Induced Subgraph Problem (MHIS), a vertex-
coloring variant that seeks to color connected components with a single color. In this problem, a
vertex is considered happy if it is colored and all of its neighbors are also colored with the same
color. We propose a new mathematical formulation based on paths between pre-colored vertices
with distinct colors and develop a Branch-and-Cut algorithm that dynamically inserts cuts based
on the detection of violated paths. Computational experiments show that the proposed approach is
effective on small instances and significantly outperforms the original model on larger and more
complex graphs, reinforcing the efficacy of the formulation and method developed in the context of
combinatorial optimization.