A heuristic algorithm for the maximum happy vertices problem using tree decompositions
share
We propose a new heuristic algorithm for the Maximum Happy Vertices problem, using tree decompositions. Traditionally, such algorithms construct an optimal solution of the given problem instance through a dynamic programming approach. We modify this procedure by integrating a parameter W that dictates the number of dynamic programming states to consider. We drop the exactness guarantee in favour of a shorter running time. However, if W is large enough such that all valid states are considered, our heuristic algorithm proves optimality of the constructed solution. Our algorithm more efficiently constructs an optimal solution for the Maximum Happy Vertices problem than the exact algorithm for graphs of bounded treewidth. Furthermore, our algorithm constructs higher quality solutions than state-of-the-art heuristic algorithms Greedy-MHV and Growth-MHV for instances of which at least 40 are initially coloured, at the cost of a larger running time.
READ FULL TEXT