liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Exploiting Structure in CSP-related Problems
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSlab)
2013 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In this thesis we investigate the computational complexity and approximability of computational problems from the constraint satisfaction framework. An instance of a constraint satisfaction problem (CSP) has three components; a set V of variables, a set D of domain values, and a set of constraints C. The constraints specify a set of variables and associated local conditions on the domain values allowed for each variable, and the objective of a CSP is to assign domain values to the variables, subject to these constraints.

The first main part of the thesis is concerned with studying restrictions on the structure induced by the constraints on the variables for different computational problems related to the CSP. In particular, we examine how to exploit various graph, and hypergraph, acyclicity measures from the literature to find classes of relational structures for which our computational problems become efficiently solvable. Among the problems studied are, such where, in addition to the constraints of a CSP, lists of allowed domain values for each variable are specified (LHom). We also study variants of the CSP where the objective is changed to: counting the number of possible assignments of domain values to the variables given the constraints of a CSP (#CSP), minimising or maximising the cost of an assignment satisfying all constraints given various different ways of assigning costs to assignments (MinHom, Max Sol, and CSP), or maximising the number of satisfied constraints (Max CSP). In several cases, our investigations uncover the largest known (or possible) classes of relational structures for which our problems are efficiently solvable. Moreover, we take a different view on our optimisation problems MinHom and VCSP; instead of considering fixed arbitrary values for some (hyper)graph acyclicity measure associated with the underlying CSP, we consider the problems parameterised by such measures in combination with other basic parameters such as domain size and maximum arity of constraints. In this way, we identify numerous combinations of the considered parameters which make these optimisation problems admit fixed-parameter algorithms.

In the second part of the thesis, we explore the approximability properties of the (weighted) Max CSP problem for graphs. This is a problem which is known to be approximable within some constant ratio, but not believed to be approximable within an arbitrarily small constant ratio. Thus it is of interest to determine the best ratio within which the problem can be approximated, or at least give some bound on this constant. We introduce a novel method for studying approximation ratios which, in the context of Max CSP for graphs, takes the form of a new binary parameter on the space of all graphs. This parameter may, informally, be thought of as a sort of distance between two graphs; knowing the distance between two graphs, we can bound the approximation ratio of one of them, given a bound for the other.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2013. , 165 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1496
National Category
Computer Science
URN: urn:nbn:se:liu:diva-85668ISBN: 978-91-7519-711-1 (print)OAI: diva2:576178
Public defence
2013-02-08, Visionen,Hus B, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Available from: 2012-12-17 Created: 2012-11-27 Last updated: 2012-12-20Bibliographically approved

Open Access in DiVA

Exploiting Structure in CSP-related Problems(1347 kB)674 downloads
File information
File name FULLTEXT01.pdfFile size 1347 kBChecksum SHA-512
Type fulltextMimetype application/pdf
omslag(42 kB)80 downloads
File information
File name COVER01.pdfFile size 42 kBChecksum SHA-512
Type coverMimetype application/pdf

Search in DiVA

By author/editor
Färnqvist, Tommy
By organisation
Software and SystemsThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 674 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 1530 hits
ReferencesLink to record
Permanent link

Direct link