A heuristic algorithm using tree decompositions for the maximum happy vertices problem

Louis Carpentier (), Jorik Jooken () and Jan Goedgebeur ()
Additional contact information
Louis Carpentier: KU Leuven Brugge
Jorik Jooken: KU Leuven KULAK
Jan Goedgebeur: KU Leuven KULAK

Journal of Heuristics, 2024, vol. 30, issue 1, No 3, 67-107

Abstract: Abstract We propose a new methodology to develop heuristic algorithms 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 introducing 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. In particular, we implement a heuristic algorithm for the Maximum Happy Vertices problem using this approach. Our algorithm more efficiently constructs optimal solutions compared to 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% of the vertices are initially coloured, at the cost of a larger running time.

Keywords: Tree decomposition; Combinatorial optimisation; Exactness runtime trade-off; Dynamic programming; Maximum happy vertices (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-023-09522-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:30:y:2024:i:1:d:10.1007_s10732-023-09522-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-023-09522-x

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().