2026-07-25T01:58:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23879 2025-11-12T13:10:51Z ddc:004 open_access

Greed Is Slow on Sparse Graphs of Oriented Valued Constraints Kaznatcheev, Artem Vazquez Alferez, Sofia valued constraint satisfaction problem local search algorithm analysis constraint graphs Greedy local search is especially popular for solving valued constraint satisfaction problems (VCSPs). Since any method will be slow for some VCSPs, we ask: what is the simplest VCSP on which greedy local search is slow? We construct a VCSP on 6n Boolean variables for which greedy local search takes 7(2ⁿ - 1) steps to find the unique peak. Our VCSP is simple in two ways. First, it is very sparse: its constraint graph has pathwidth 2 and maximum degree 3. This is the simplest VCSP on which some local search could be slow. Second, it is "oriented" – there is an ordering on the variables such that later variables are conditionally-independent of earlier ones. Being oriented allows many non-greedy local search methods to find the unique peak in a quadratic number of steps. Thus, we conclude that - among local search methods - greed is particularly slow. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Artem Kaznatcheev and Sofia Vazquez Alferez 2025 Is Part Of LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2025.18 urn:nbn:de:0030-drops-238793 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.18 eng https://creativecommons.org/licenses/by/4.0/legalcode