The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
2013 (English)In: Automata, Languages, and Programming 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I / [ed] Fedor V. Fomin, Rūsiņš Freivalds, Marta Kwiatkowska, David Peleg, Springer Berlin/Heidelberg, 2013, 804-815 p.Chapter in book (Refereed)
Thapper and Živný [STOC’13] recently classified the complexity of VCSP for all finite-valued constraint languages. However, the complexity of VCSPs for constraint languages that are not finite-valued remains poorly understood. In this paper we study the complexity of two such VCSPs, namely Min-Cost-Hom and Min-Sol. We obtain a full classification for the complexity of Min-Sol on domains that contain at most three elements and for the complexity of conservative Min-Cost-Hom on arbitrary finite domains. Our results answer a question raised by Takhanov [STACS’10, COCOON’10].
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013. 804-815 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 7965
IdentifiersURN: urn:nbn:se:liu:diva-102664DOI: 10.1007/978-3-642-39206-1_68ISI: 000342686600068ISBN: 978-3-642-39205-4 (print)ISBN: 978-3-642-39206-1 (online)OAI: oai:DiVA.org:liu-102664DiVA: diva2:680731
40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013