| 1. |
- Bäckström, Christer, et al.
(author)
-
A complete parameterized complexity analysis of bounded planning
- 2015
-
In: Journal of computer and system sciences (Print). - : Elsevier. - 0022-0000 .- 1090-2724. ; 81:7, s. 1311-1332
-
Journal article (peer-reviewed)abstract
- The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this paper we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter "length of the solution plan." We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by Backstrom and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which do not. (C) 2015 Elsevier Inc. All rights reserved.
|
|
| 2. |
- Bäckström, Christer, 1962-, et al.
(author)
-
A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs
- 2018
-
In: 11th Annual Symposium on Combinatorial Search. - : AAAI Press. - 9781577358022 ; , s. 19-27
-
Conference paper (peer-reviewed)abstract
- Complexity analysis based on the causal graphs of planning instances has emerged as a highly important area of research. In particular, tractability results have led to new methods for the identification of domain-independent heuristics. Important early examples of such tractability results have been presented by, for instance, Brafman & Domshlak and Katz & Keyder. More general results based on polytrees and bounding certain parameters were subsequently derived by Aghighi et al. and Ståhlberg. We continue this line of research by analyzing cost-optimal planning restricted to instances with a polytree causal graph, bounded domain size and bounded depth (i.e. the length of the longest directed path in the causal graph). We show that no further restrictions are necessary for tractability, thus generalizing the previous results. Our approach is based on a novel method of closely analysing optimal plans: we recursively decompose the causal graph in a way that allows for bounding the number of variable changes as a function of the depth, using a reording argument and a comparison with prefix trees of known size. We can then transform the planning instances into constraint satisfaction instances; an idea that has previously been exploited by, for example, Brafman & Domshlak and Bäckström. This allows us to utilise efficient algorithms for constraint optimisation over tree-structured instances.
|
|
| 3. |
- Bäckström, Christer, et al.
(author)
-
Cost-Optimal Planning, Delete Relaxation, Approximability, and Heuristics
- 2021
-
In: The journal of artificial intelligence research. - : AI ACCESS FOUNDATION. - 1076-9757 .- 1943-5037. ; 70, s. 169-204
-
Journal article (peer-reviewed)abstract
- Cost-optimal planning is a very well-studied topic within planning, and it has proven to be computationally hard both in theory and in practice. Since cost-optimal planning is an optimisation problem, it is natural to analyse it through the lens of approximation. An important reason for studying cost-optimal planning is heuristic search; heuristic functions that guide the search in planning can often be viewed as algorithms solving or approximating certain optimisation problems. Many heuristic functions (such as the ubiquitious h(+) heuristic) are based on delete relaxation, which ignores negative effects of actions. Planning for instances where the actions have no negative effects is often referred to as monotone planning. The aim of this article is to analyse the approximability of cost-optimal monotone planning, and thus the performance of relevant heuristic functions. Our findings imply that it may be beneficial to study these kind of problems within the framework of parameterised complexity and we initiate work in this direction.
|
|
| 4. |
- Bäckström, Christer, 1962-, et al.
(author)
-
Novel Structural Parameters for Acyclic Planning Using Tree Embeddings
- 2018
-
In: 27th International Joint Conference on Artificial Intelligence. - California : International Joint Conferences on Artificial Intelligence Organization. - 9780999241127 ; , s. 4653-4659
-
Conference paper (peer-reviewed)abstract
- We introduce two novel structural parameters for acyclic planning (planning restricted to instances with acyclic causal graphs): up-depth and down-depth. We show that cost-optimal acyclic planning restricted to instances with bounded domain size and bounded up- or down-depth can be solved in polynomial time. For example, many of the tractable subclasses based on polytrees are covered by our result. We analyze the parameterized complexity of planning with bounded up- and down-depth: in a certain sense, down-depth has better computational properties than up-depth. Finally, we show that computing up- and down-depth are fixed-parameter tractable problems, just as many other structural parameters that are used in computer science. We view our results as a natural step towards understanding the complexity of acyclic planning with bounded treewidth and other parameters.
|
|
| 5. |
- Bäckström, Christer, et al.
(author)
-
Parameterized Complexity and Kernel Bounds for Hard Planning Problems
- 2013
-
In: Algorithms and Complexity. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783642382321 - 9783642382338 ; , s. 13-24
-
Conference paper (peer-reviewed)abstract
- The propositional planning problem is a notoriously difficult computational problem. Downey et al. (1999) initiated the parameterized analysis of planning (with plan length as the parameter) and Bäckström et al. (2012) picked up this line of research and provided an extensive parameterized analysis under various restrictions, leaving open only one stubborn case. We continue this work and provide a full classification. In particular, we show that the case when actions have no preconditions and at most e postconditions is fixed-parameter tractable if e ≤ 2 and W[1]-complete otherwise. We show fixed-parameter tractability by a reduction to a variant of the Steiner Tree problem; this problem has been shown fixed-parameter tractable by Guo et al. (2007). If a problem is fixed-parameter tractable, then it admits a polynomial-time self-reduction to instances whose input size is bounded by a function of the parameter, called the kernel. For some problems, this function is even polynomial which has desirable computational implications. Recent research in parameterized complexity has focused on classifying fixed-parameter tractable problems on whether they admit polynomial kernels or not. We revisit all the previously obtained restrictions of planning that are fixed-parameter tractable and show that none of them admits a polynomial kernel unless the polynomial hierarchy collapses to its third level.
|
|
| 6. |
- Bäckström, Christer, et al.
(author)
-
The Complexity of Planning Revisited - A Parameterized Analysis
- 2012
-
In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. - : AAAI Press. - 9781577355687 - 9781577355694 ; , s. 1735-1741
-
Conference paper (peer-reviewed)abstract
- The early classifications of the computational complexity of planning under various restrictions in STRIPS (Bylander) and SAS+ (B¨ackstr¨om and Nebel) have influenced following research in planning in many ways. We go back and reanalyse their subclasses, but this time using the more modern tool of parameterized complexity analysis. This provides new results that together with the old results give a more detailed picture of the complexity landscape. We demonstrate separation results not possible with standard complexity theory, which contributes to explaining why certain cases of planning haveseemed simpler in practice than theory has predicted. In particular, we show that certain restrictions of practical interest are tractable in the parameterized sense of the term, and that a simple heuristic is sufficient to make a well-known partialorder planner exploit this fact.
|
|
| 7. |
- Dabrowski, Konrad K., et al.
(author)
-
Almost Consistent Systems of Linear Equations
- 2023
-
In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). - Philadelphia, PA : Society for Industrial and Applied Mathematics. - 9781611977554 ; , s. 3179-3217
-
Conference paper (peer-reviewed)abstract
- Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimizes the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over Euclidean domains—a family of commutative rings that generalize finite and infinite fields including the rationals, the ring of integers and many other structures. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalizes many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not Euclidean domains. On the technical side, we introduce the notion of important balanced subgraphs, generalizing important separators of Marx [Theor. Comput. Sci. 2006] to the setting of biased graphs. Furthermore, we use recent results on parameterized MinCSP [Kim et al., SODA 2021] to efficiently solve a generalization of Multicut with disjunctive cut requests.
|
|
| 8. |
- Dabrowski, Konrad K., et al.
(author)
-
Disjunctive Temporal Problems under Structural Restrictions
- 2021
-
In: THIRTY-FIFTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THIRTY-THIRD CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE AND THE ELEVENTH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE. - : ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE. - 9781577358664 ; , s. 3724-3732
-
Conference paper (peer-reviewed)abstract
- The disjunctive temporal problem (DTP) is an expressive temporal formalism that extends Dechter et al.s simple temporal problem. The DTP is well studied in the literature and has many important applications. It is known that deciding satisfiability of DTPs is NP-hard and that, in many cases, single-exponential algorithms (running in O(c(n)) time) do not exist under the Exponential-Time Hypothesis. The computational hardness makes it worthwhile to identify restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints. We show that instances of DTP of any arity with integers bounded by poly(n) can be solved in n(f(w)) time, where n denotes the problem size, w is the treewidth of the incidence graph and f is a computable function; in other words, this problem is in the complexity class XP and it can be solved in polynomial time whenever w is fixed. We complement this result by showing that binary DTPs that only involve the integers 0 and 1 are not fixed-parameter tractable with respect to treewidth, i.e. they do not admit a f (w) . poly(n) time algorithm for any computable function f , under standard complexity assumptions. For instances with unbounded integers, we show that even binary DTPs parameterized by treewidth cannot be in XP, unless P = N P.
|
|
| 9. |
- Dabrowski, Konrad K., et al.
(author)
-
Fine-Grained Complexity of Temporal Problems
- 2020
-
In: KR2020: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning. - California : IJCAI-INT JOINT CONF ARTIF INTELL. - 9780999241172 ; , s. 284-293
-
Conference paper (peer-reviewed)abstract
- Expressive temporal reasoning formalisms are essential for AI. One family of such formalisms consists of disjunctive extensions of the simple temporal problem (STP). Such extensions are well studied in the literature and they have many important applications. It is known that deciding satisfiability of disjunctive STPs is NP-hard, while the fine-grained complexity of such problems is virtually unexplored. We present novel algorithms that exploit structural properties of the solution space and prove, assuming the Exponential-Time Hypothesis, that their worst-case time complexity is close to optimal. Among other things, we make progress towards resolving a long-open question concerning whether Allens interval algebra can be solved in single-exponential time, by giving a 2(O(n log log n)) algorithm for the special case of unit-length intervals.
|
|
| 10. |
- Dabrowski, Konrad K., et al.
(author)
-
Parameterized Complexity Classification for Interval Constraints
- 2023
-
In: 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). - Saarbrücken/Wadern : Schloss Dagstuhl – Leibniz-Zentrum für Informatik. - 9783959773058 ; , s. 11:1-11:19
-
Conference paper (peer-reviewed)abstract
- 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.
|
|
| 11. |
- Dabrowski, Konrad K., et al.
(author)
-
Resolving Inconsistencies in Simple Temporal Problems: A Parameterized Approach
- 2022
-
In: THIRTY-SIXTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FOURTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE / THE TWELVETH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE. - : ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE. - 9781577358763 ; , s. 3724-3732
-
Conference paper (peer-reviewed)abstract
- The simple temporal problem (STP) is one of the most influential reasoning formalisms for representing temporal information in AL We study the problem of resolving inconsistency of data encoded in the STP. We prove that the problem of identifying a maximally large consistent subset of data is NP-hard. In practical instances, it is reasonable to assume that the amount of erroneous data is small. We therefore parameterize by the number of constraints that need to be removed to achieve consistency. Using tools from parameterized complexity we design fixed-parameter tractable algorithms for two large fragments of the STP. Our main algorithmic results employ reductions to the Directed Subset Feedback Arc Set problem and iterative compression combined with an efficient algorithm for the Edge Multicut problem. We complement our algorithmic results with hardness results that rule out fixed-parameter tractable algorithms for all remaining non-trivial fragments of the STP (under standard complexity-theoretic assumptions). Together, our results give a full classification of the classical and parameterized complexity of the problem.
|
|
| 12. |
- Dabrowski, Konrad K., et al.
(author)
-
Solving Infinite-Domain CSPs Using the Patchwork Property
- 2021
-
In: THIRTY-FIFTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THIRTY-THIRD CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE AND THE ELEVENTH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE. - : ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE. - 9781577358664 ; , s. 3715-3723
-
Conference paper (peer-reviewed)abstract
- The constraint satisfaction problem (CSP) has important applications in computer science and AL In particular, infinite-domain CSPs have been intensively used in subareas of AI such as spatio-temporal reasoning. Since constraint satisfaction is a computationally hard problem, much work has been devoted to identifying restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints, and a highly successful approach is to bound the treewidth of the underlying primal graph. Bodirsky & Dalmau [J. Comput. System. Sci. 79(1), 2013] and Huang et al. [Artif. Intell. 195, 2013] proved that CSP(Gamma) can be solved in n(f(w)) time (where n is the size of the instance, w is the treewidth of the primal graph and f is a computable function) for certain classes of constraint languages Gamma. We improve this bound to n(f(w)) . n(O(1)), where the function f only depends on the language Gamma, for CSPs whose basic relations have the patchwork property. Hence, such problems are fixed-parameter tractable and our algorithm is asymptotically faster than the previous ones. Additionally, our approach is not restricted to binary constraints, so it is applicable to a strictly larger class of problems than that of Huang et al. However, there exist natural problems that are covered by Bodirsky & Dalmaus algorithm but not by ours.
|
|
| 13. |
- Dabrowski, Konrad K., et al.
(author)
-
Solving infinite-domain CSPs using the patchwork property
- 2023
-
In: Artificial Intelligence. - : ELSEVIER. - 0004-3702 .- 1872-7921. ; 317
-
Journal article (peer-reviewed)abstract
- The constraint satisfaction problem (CSP) has important applications in computer science and AI. In particular, infinite-domain CSPs have been intensively used in subareas of AI such as spatio-temporal reasoning. Since constraint satisfaction is a computationally hard problem, much work has been devoted to identifying restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints, and a highly successful approach is to bound the treewidth of the underlying primal graph. Bodirsky & Dalmau (2013) [14] and Huang et al. (2013) [47] proved that CSP(Gamma) can be solved in nf (w) time (where n is the size of the instance, w is the treewidth of the primal graph and f is a computable function) for certain classes of constraint languages Gamma. We improve this bound to f (w) middot nO (1) , where the function f only depends on the language r, for CSPs whose basic relations have the patchwork property. Hence, such problems are fixed-parameter tractable and our algorithm is asymptotically faster than the previous ones. Additionally, our approach is not restricted to binary constraints, so it is applicable to a strictly larger class of problems than that of Huang et al. However, there exist natural problems that are covered by Bodirsky & Dalmaus algorithm but not by ours, and we begin investigating ways of generalising our results to larger families of languages. We also analyse our algorithm with respect to its running time and show that it is optimal (under the Exponential Time Hypothesis) for certain languages such as Allens Interval Algebra.
|
|
| 14. |
- Fichte, Johannes K., et al.
(author)
-
Structure-Aware Lower Bounds and Broadening the Horizon of Tractability for QBF
- 2023
-
In: 2023 38TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS. - : IEEE. - 9798350335873 - 9798350335880
-
Conference paper (peer-reviewed)abstract
- The QSAT problem, which asks to evaluate a quantified Boolean formula (QBF), is of fundamental interest in approximation, counting, decision, and probabilistic complexity and is also considered the prototypical PSPACE-complete problem. As such, it has previously been studied under various structural restrictions (parameters), most notably parameterizations of the primal graph representation of instances. Indeed, it is known that QSAT remains PSPACE-complete even when restricted to instances with constant treewidth of the primal graph, but the problem admits a double-exponential fixed-parameter algorithm parameterized by the vertex cover number (primal graph). However, prior works have left a gap in our understanding of the complexity of QSAT when viewed from the perspective of other natural representations of instances, most notably via incidence graphs. In this paper, we develop structure-aware reductions which allow us to obtain essentially tight lower bounds for highly restricted instances of QSAT, including instances whose incidence graphs have bounded treedepth or feedback vertex number. We complement these lower bounds with novel algorithms for QSAT which establish a nearly-complete picture of the problems complexity under standard graph-theoretic parameterizations. We also show implications for other natural graph representations, and obtain novel upper as well as lower bounds for QSAT under more fine-grained parameterizations of the primal graph.
|
|
| 15. |
- Jonsson, Peter, et al.
(author)
-
Computational Short Cuts in Infinite Domain Constraint Satisfaction
- 2022
-
In: The journal of artificial intelligence research. - : AI ACCESS FOUNDATION. - 1076-9757 .- 1943-5037. ; 75, s. 793-831
-
Journal article (peer-reviewed)abstract
- A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a polynomial-time solvable class. Backdoors have found many applications in artificial intelligence and elsewhere, and the algorithmic problem of finding such backdoors has consequently been intensively studied. Sioutis and Janhunen have proposed a generalised backdoor concept suitable for infinite-domain CSP instances over binary constraints. We generalise their concept into a large class of CSPs that allow for higher-arity constraints. We show that this kind of infinite-domain backdoors have many of the positive computational properties that finite-domain backdoors have: the associated computational problems are fixed-parameter tractable whenever the underlying constraint language is finite. On the other hand, we show that infinite languages make the problems considerably harder: the general backdoor detection problem is W[2]-hard and fixed-parameter tractability is ruled out under standard complexity-theoretic assumptions. We demonstrate that backdoors may have suboptimal behaviour on binary constraints| this is detrimental from an AI perspective where binary constraints are predominant in, for instance, spatiotemporal applications. In response to this, we introduce sidedoors as an alternative to backdoors. The fundamental computational problems for sidedoors remain fixed-parameter tractable for finite constraint language (possibly also containing non-binary relations). Moreover, the sidedoor approach has appealing computational properties that sometimes leads to faster algorithms than the backdoor approach.
|
|
| 16. |
- Jonsson, Peter, 1969-, et al.
(author)
-
Reasoning Short Cuts in Infinite Domain Constraint Satisfaction : Algorithms and Lower Bounds for Backdoors
- 2021
-
In: Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming. - Dagstuhl, Germany : Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. - 9783959772112 ; , s. 32:1-32:20
-
Conference paper (peer-reviewed)abstract
- A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a polynomial-time solvable class. Backdoors have found many applications in artificial intelligence and elsewhere, and the algorithmic problem of finding such backdoors has consequently been intensively studied. Sioutis and Janhunen (KI, 2019) have proposed a generalised backdoor concept suitable for infinite-domain CSP instances over binary constraints. We generalise their concept into a large class of CSPs that allow for higher-arity constraints. We show that this kind of infinite-domain backdoors have many of the positive computational properties that finite-domain backdoors have: the associated computational problems are fixed-parameter tractable whenever the underlying constraint language is finite. On the other hand, we show that infinite languages make the problems considerably harder.
|
|
