Kolmogorov, Vladimir
Testing the Complexity of a Valued CSP Language
Abstract
A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set Gamma of cost functions, called a language.
Recent breakthrough results have established a complete complexity classification of such classes with respect to language Gamma: if all cost functions in Gamma satisfy a certain algebraic condition then all Gammainstances can be solved in polynomial time, otherwise the problem is NPhard. Unfortunately, testing this condition for a given language Gamma is known to be NPhard. We thus study exponential algorithms for this metaproblem. We show that the tractability condition of a finitevalued language Gamma can be tested in O(sqrt[3]{3}^{D}* poly(size(Gamma))) time, where D is the domain of Gamma and poly(*) is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant delta<1 there is no O(sqrt[3]{3}^{deltaD}) algorithm, assuming that SETH holds.
BibTeX  Entry
@InProceedings{kolmogorov:LIPIcs:2019:10653,
author = {Vladimir Kolmogorov},
title = {{Testing the Complexity of a Valued CSP Language}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {77:177:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10653},
URN = {urn:nbn:de:0030drops106531},
doi = {10.4230/LIPIcs.ICALP.2019.77},
annote = {Keywords: Valued Constraint Satisfaction Problems, Exponential time algorithms, Exponential Time Hypothesis}
}
2019
Keywords: 

Valued Constraint Satisfaction Problems, Exponential time algorithms, Exponential Time Hypothesis 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

2019 