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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Parameterized Complexity Classification for Interval Constraints
School of Computing, Newcastle University, UK.ORCID iD: 0000-0001-9515-6945
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-5288-3330
School of Computing, University of Leeds, UK.ORCID iD: 0000-0003-1935-651X
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-2884-9837
Show others and affiliations
2023 (English)In: 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) / [ed] Neeldhara Misra, Magnus Wahlström, Saarbrücken/Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik , 2023, Vol. 285, p. 11:1-11:19Conference paper, Published paper (Refereed)
Abstract [en]

Constraint satisfaction problems form a nicely behaved class of problems that lends itself to complexity classification results. From the point of view of parameterized complexity, a natural task is to classify the parameterized complexity of MinCSP problems parameterized by the number of unsatisfied constraints. In other words, we ask whether we can delete at most k constraints, where k is the parameter, to get a satisfiable instance. In this work, we take a step towards classifying the parameterized complexity for an important infinite-domain CSP: Allen’s interval algebra (IA). This CSP has closed intervals with rational endpoints as domain values and employs a set A of 13 basic comparison relations such as "precedes" or "during" for relating intervals. IA is a highly influential and well-studied formalism within AI and qualitative reasoning that has numerous applications in, for instance, planning, natural language processing and molecular biology. We provide an FPT vs. W[1]-hard dichotomy for MinCSP(Γ) for all Γ ⊆ A. IA is sometimes extended with unions of the relations in A or first-order definable relations over A, but extending our results to these cases would require first solving the parameterized complexity of Directed Symmetric Multicut, which is a notorious open problem. Already in this limited setting, we uncover connections to new variants of graph cut and separation problems. This includes hardness proofs for simultaneous cuts or feedback arc set problems in directed graphs, as well as new tractable cases with algorithms based on the recently introduced flow augmentation technique. Given the intractability of MinCSP(A) in general, we then consider (parameterized) approximation algorithms. We first show that MinCSP(A) cannot be polynomial-time approximated within any constant factor and continue by presenting a factor-2 fpt-approximation algorithm. Once again, this algorithm has its roots in flow augmentation. 

Place, publisher, year, edition, pages
Saarbrücken/Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik , 2023. Vol. 285, p. 11:1-11:19
Series
Leibniz International Proceedings in Informatics (LIPIcs) ; 285
Keywords [en]
(Minimum) constraint satisfaction problem, Allen's interval algebra, Parameterized complexity, Cut problems
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-203025DOI: 10.4230/LIPIcs.IPEC.2023.11ISBN: 9783959773058 (electronic)OAI: oai:DiVA.org:liu-203025DiVA, id: diva2:1854183
Conference
International Symposium on Parameterized and Exact Computation (IPEC), Amsterdam, September 6-8, 2023
Note

Funding agency: Partially supported by the Swedish Research Council (VR) under grant 2021-0437 and the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.

Available from: 2024-04-24 Created: 2024-04-24 Last updated: 2024-04-24Bibliographically approved
In thesis
1. On Infinite-Domain CSPs Parameterized by Solution Cost
Open this publication in new window or tab >>On Infinite-Domain CSPs Parameterized by Solution Cost
2024 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In this thesis we study the computational complexity of MinCSP - an optimization version of the Constraint Satisfaction Problem (CSP). The input to a MinCSP is a set of variables and constraints applied to these variables, and the goal is to assign values (from a fixed domain) to the variables while minimizing the solution cost, i.e. the number of unsatisfied constraints. We are specifically interested in MinCSP with infinite domains of values. Infinite-domain MinCSPs model fundamental optimization problems in computer science and are of particular relevance to artificial intelligence, especially temporal and spatial reasoning. The usual way to study computational complexity of CSPs is to restrict the types of constraints that can be used in the inputs, and either construct fast algorithms or prove lower bounds on the complexity of the resulting problems.

The vast majority of interesting MinCSPs are NP-hard, so standard complexity-theoretic assumptions imply that we cannot find exact solutions to all inputs of these problems in polynomial time with respect to the input size. Hence, we need to relax at least one of the three requirements above, opting for either approximate solutions, solving some inputs, or using super-polynomial time. Parameterized algorithms exploits the latter two relaxations by identifying some common structure of the interesting inputs described by some parameter, and then allowing super-polynomial running times with respect to that parameter. Such algorithms are feasible for inputs of any size whenever the parameter value is small. For MinCSP, a natural parameter is optimal solution cost. We also study parameterized approximation algorithms, where the requirement for exact solutions is also relaxed.

We present complete complexity classifications for several important classes of infinite-domain constraints. These are simple temporal constraints and interval constraints, which have notable applications in temporal reasoning in AI, linear equations over finite and infinite fields as well as some commutative rings (e.g., the rationals and the integers), which are of fundamental theoretical importance, and equality constraints, which are closely related to connectivity problems in undirected graphs and form the basis of studying first-order definable constraints over infinite domains. In all cases, we prove results as follows: we fix a (possibly infinite) set of allowed constraint types C, and for every finite subset of C, determine whether MinCSP(), i.e., MinCSP restricted to the constraint types in , is fixed-parameter tractable, i.e. solvable in f(k) · poly(n) time, where k is the parameter, n is the input size, and f is any function that depends solely on k. To rule out such algorithms, we prove lower bounds under standard assumptions of parameterized complexity. In all cases except simple temporal constraints, we also provide complete classifications for fixed-parameter time constant-factor approximation.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2024. p. 37
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 2368
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-203026 (URN)10.3384/9789180754972 (DOI)9789180754965 (ISBN)9789180754972 (ISBN)
Public defence
2024-06-03, Nobel, B Building, Campus Valla, Linköping, 14:00 (English)
Opponent
Supervisors
Note

Funding Agency: Wallenberg AI, Autonomous Systems and Software Program (WASP), funded by the Knut and Alice Wallenberg Foundation

Available from: 2024-04-24 Created: 2024-04-24 Last updated: 2024-04-26Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Jonsson, PeterOsipov, George

Search in DiVA

By author/editor
Dabrowski, Konrad K.Jonsson, PeterOrdyniak, SebastianOsipov, GeorgePilipczuk, MarcinSharma, Roohani
By organisation
Artificial Intelligence and Integrated Computer SystemsFaculty of Science & Engineering
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 87 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf