Constraint Satisfaction with Bounded Treewidth Revisited (bibtex)

by Marko Samer, Stefan Szeider

Abstract:

The constraint satisfaction problem can be solved in polynomial time for instances where certain parameters (e.g., the treewidth of primal graphs) are bounded. However, there is a trade-off between generality and performance: larger bounds on the parameters yield worse time complexities. It is desirable to pay for more generality only by a constant factor in the running time, not by a larger degree of the polynomial. Algorithms with such a uniform polynomial time complexity are known as fixed-parameter algorithms. In this paper we determine whether or not fixed-parameter algorithms for constraint satisfaction exist, considering all possible combinations of the following parameters: the treewidth of primal graphs, the treewidth of dual graphs, the treewidth of incidence graphs, the domain size, the maximum arity of constraints, and the maximum size of overlaps of constraint scopes. The negative cases are subject to the complexity theoretic assumption FPT ? W[1] which is the parameterized analog to P ? NP. For the positive cases we provide an effective fixed-parameter algorithm which is based on dynamic programming on “nice” tree decompositions.

Reference:

Constraint Satisfaction with Bounded Treewidth RevisitedMarko Samer, Stefan SzeiderJournal of Computer and System Sciences (JCSS), volume 76, number 2, pages 103-114, March 2010, Academic Press.

Bibtex Entry:

@article{SamSze09JCSS, author = {Marko Samer and Stefan Szeider}, title = {Constraint Satisfaction with Bounded Treewidth Revisited}, number = {2}, month = {March}, year = {2010}, journal = {Journal of Computer and System Sciences (JCSS)}, pages = {103-114}, publisher = {Academic Press}, volume = {76}, abstract = {The constraint satisfaction problem can be solved in polynomial time for instances where certain parameters (e.g., the treewidth of primal graphs) are bounded. However, there is a trade-off between generality and performance: larger bounds on the parameters yield worse time complexities. It is desirable to pay for more generality only by a constant factor in the running time, not by a larger degree of the polynomial. Algorithms with such a uniform polynomial time complexity are known as fixed-parameter algorithms. In this paper we determine whether or not fixed-parameter algorithms for constraint satisfaction exist, considering all possible combinations of the following parameters: the treewidth of primal graphs, the treewidth of dual graphs, the treewidth of incidence graphs, the domain size, the maximum arity of constraints, and the maximum size of overlaps of constraint scopes. The negative cases are subject to the complexity theoretic assumption FPT ? W[1] which is the parameterized analog to P ? NP. For the positive cases we provide an effective fixed-parameter algorithm which is based on dynamic programming on “nice” tree decompositions.}, issn = {0022-0000}, doi = {10.1016/j.jcss.2009.04.003} }

Powered by bibtexbrowser