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

Direct link
BETA
Alternative names
Publications (10 of 86) Show all publications
Jonsson, P. & Thapper, J. (2016). Constraint satisfaction and semilinear expansions of addition over the rationals and the reals. Journal of computer and system sciences (Print), 82(5), 912-928
Open this publication in new window or tab >>Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
2016 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 82, no 5, p. 912-928Article in journal (Refereed) Published
Abstract [en]

A semilinear relation is a finite union of finite intersections of open and closed half spaces over, for instance, the reals, the rationals, or the integers. Semilinear relations have been studied in connection with algebraic geometry, automata theory, and spatiotemporal reasoning. We consider semilinear relations over the rationals and the reals. Under this assumption, the computational complexity of the constraint satisfaction problem (CSP) is known for all finite sets containing R+ = {(x, y, z) vertical bar x y = z}, <=, and {1}. These problems correspond to expansions of the linear programming feasibility problem. We generalise this result and fully determine the complexity for all finite sets of semilinear relations containing R+. This is accomplished in part by introducing an algorithm, based on computing affine hulls, which solves a new class of semilinear CSPs in polynomial time. We further analyse the complexity of linear optimisation over the solution set and the existence of integer solutions. (C) 2016 Elsevier Inc. All rights reserved.

Place, publisher, year, edition, pages
ACADEMIC PRESS INC ELSEVIER SCIENCE, 2016
Keyword
Constraint satisfaction problems; Semilinear sets; Algorithms; Computational complexity
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-128917 (URN)10.1016/j.jcss.2016.03.002 (DOI)000374425900016 ()
Note

Funding Agencies|Swedish Research Council (VR) [621-2012-3239]

Available from: 2016-06-09 Created: 2016-06-07 Last updated: 2018-01-10
Bäckström, C., Jonsson, P., Ordyniak, S. & Szeider, S. (2015). A complete parameterized complexity analysis of bounded planning. Journal of computer and system sciences (Print), 81(7), 1311-1332
Open this publication in new window or tab >>A complete parameterized complexity analysis of bounded planning
2015 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 81, no 7, p. 1311-1332Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Elsevier, 2015
Keyword
Complexity of automated planning; Parameterized complexity; Kernelization
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-120202 (URN)10.1016/j.jcss.2015.04.002 (DOI)000356644600014 ()
Note

Funding Agencies|European Research Council [239962]; Employment of Newly Graduated Doctors of Science for Scientific Excellence [CZ.1.07/2.3.00/30.0009]; Austrian Science Fund [P 26200]

Available from: 2015-07-21 Created: 2015-07-20 Last updated: 2018-01-11
Engstrom, R., Färnqvist, T., Jonsson, P. & Thapper, J. (2015). An Approximability-related Parameter on Graphs - Properties and Applications. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 17(1), 33-66
Open this publication in new window or tab >>An Approximability-related Parameter on Graphs - Properties and Applications
2015 (English)In: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, ISSN 1462-7264, Vol. 17, no 1, p. 33-66Article in journal (Refereed) Published
Abstract [en]

We introduce a binary parameter on optimisation problems called separation. The parameter is used to relate the approximation ratios of different optimisation problems; in other words, we can convert approximability (and non-approximability) result for one problem into (non)-approximability results for other problems. Our main application is the problem (weighted) maximum H-colourable subgraph (MAX H-COL), which is a restriction of the general maximum constraint satisfaction problem (MAX CSP) to a single, binary, and symmetric relation. Using known approximation ratios for MAX k-CUT, we obtain general asymptotic approximability results for MAX H-COL for an arbitrary graph H. For several classes of graphs, we provide near-optimal results under the unique games conjecture. We also investigate separation as a graph parameter. In this vein, we study its properties on circular complete graphs. Furthermore, we establish a close connection to work by Samal on cubical colourings of graphs. This connection shows that our parameter is closely related to a special type of chromatic number. We believe that this insight may turn out to be crucial for understanding the behaviour of the parameter, and in the longer term, for understanding the approximability of optimisation problems such as MAX H-COL.

Place, publisher, year, edition, pages
DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE, 2015
Keyword
graph H-colouring; approximation; graph homomorphism; circular colouring; combinatorial optimisation; graph theory
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-117670 (URN)000352198400003 ()
Note

Funding Agencies|National Graduate School in Computer Science (CUGS), Sweden; Center for Industrial Information Technology (CENIIT) [04.01]; Swedish Research Council (VR) [2006-4532, 621-2009-4431]; European Communitys Seventh Framework Programme (FP7) [257039]; LIX-Qualcomm Postdoctoral Fellowship

Available from: 2015-05-11 Created: 2015-05-06 Last updated: 2018-01-11
Jonsson, P., Lagerkvist, V. & Nordh, G. (2015). Constructing NP-intermediate problems by blowing holes with parameters of various properties. Theoretical Computer Science, 581, 67-82
Open this publication in new window or tab >>Constructing NP-intermediate problems by blowing holes with parameters of various properties
2015 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 581, p. 67-82Article in journal (Refereed) Published
Abstract [en]

The search for natural NP-intermediate problems is one of the holy grails within computational complexity. Ladners original diagonalization technique for generating NP-intermediate problems, blowing holes, has a serious shortcoming: it creates problems with a highly artificial structure by arbitrarily removing certain problem instances. In this article we limit this problem by generalizing Ladners method to use parameters with various characteristics. This allows one to define more fine-grained parameters, resulting in NP-intermediate problems where we only blow holes in a controlled subset of the problem. We begin by fully characterizing the problems that admit NP-intermediate subproblems for a broad and natural class of parameterizations, and extend the result further such that structural CSP restrictions based on parameters that are hard to compute (such as tree-width) are covered, thereby generalizing a result by Grohe. For studying certain classes of problems, including CSPs parameterized by constraint languages, we consider more powerful parameterizations. First, we identify a new method for obtaining constraint languages Gamma such that CSP(Gamma) are NP-intermediate. The sets Gamma can have very different properties compared to previous constructions (by, for instance, Bodirsky and Grohe) and provides insights into the algebraic approach for studying the complexity of infinite-domain CSPs. Second, we prove that the propositional abduction problem parameterized by constraint languages admits NP-intermediate problems. This settles an open question posed by Nordh and Zanuttini. (C) 2015 Elsevier B.V. All rights reserved.

Place, publisher, year, edition, pages
Elsevier, 2015
Keyword
Computational complexity; NP-intermediate problems; Constraint satisfaction problems; Abduction problems
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-118236 (URN)10.1016/j.tcs.2015.03.009 (DOI)000353608700005 ()
Note

Funding Agencies|Swedish Research Council (VR) [621-2012-3239]; National Graduate School in Computer Science (CUGS) [12.02]

Available from: 2015-05-22 Created: 2015-05-22 Last updated: 2018-01-11
Kuhlmann, M. & Jonsson, P. (2015). Parsing to Noncrossing Dependency Graphs. Transactions of the Association for Computational Linguistics, 3, 559-570
Open this publication in new window or tab >>Parsing to Noncrossing Dependency Graphs
2015 (English)In: Transactions of the Association for Computational Linguistics, ISSN 2307-387X, Vol. 3, p. 559-570Article in journal (Refereed) Published
Abstract [en]

We study the generalization of maximum spanning tree dependency parsing to maximum acyclic subgraphs. Because the underlying optimization problem is intractable even under an arc-factored model, we consider the restriction to noncrossing dependency graphs. Our main contribution is a cubic-time exact inference algorithm for this class. We extend this algorithm into a practical parser and evaluate its performance on four linguistic data sets used in semantic dependency parsing. We also explore a generalization of our parsing framework to dependency graphs with pagenumber at most $k$ and show that the resulting optimization problem is NP-hard for k ≥ 2.

Place, publisher, year, edition, pages
Association for Computational Linguistics, 2015
Keyword
natural language processing, algorithms, complexity theory
National Category
Language Technology (Computational Linguistics)
Identifiers
urn:nbn:se:liu:diva-124718 (URN)
Available from: 2016-02-11 Created: 2016-02-11 Last updated: 2018-01-10
Aghighi, M., Jonsson, P. & Ståhlberg, S. (2015). Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence: . Paper presented at 29th AAAI Conference on Artificial Intelligence (AAAI-15), January 25–30, Austin, TX, USA. AAAI Press
Open this publication in new window or tab >>Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs
2015 (English)In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, 2015Conference paper, Published paper (Refereed)
Abstract [en]

Causal graphs are widely used to analyze the complexity of planning problems. Many tractable classes have been identified with their aid and state-of-the-art heuristics have been derived by exploiting such classes. In particular, Katz and Keyder have studied causal graphs that are hourglasses (which is a generalization of forks and inverted-forks) and shown that the corresponding cost-optimal planning problem is tractable under certain restrictions. We continue this work by studying polytrees (which is a generalization of hourglasses) under similar restrictions. We prove tractability of cost-optimal planning by providing an algorithm based on a novel notion of variable isomorphism. Our algorithm also sheds light on the k-consistency procedure for identifying unsolvable planning instances. We speculate that this may, at least partially, explain why merge-and-shrink heuristics have been successful for recognizing unsolvable instances.

Place, publisher, year, edition, pages
AAAI Press, 2015
Series
Proceedings of the AAAI Conference on Artificial Intelligence, ISSN 2159-5399, E-ISSN 2374-3468
Keyword
automated planning, causal graph, polynomial-time algorithm, cost-optimal planning, polytree
National Category
Computer Systems
Identifiers
urn:nbn:se:liu:diva-118729 (URN)978-1-57735-703-2 (ISBN)
Conference
29th AAAI Conference on Artificial Intelligence (AAAI-15), January 25–30, Austin, TX, USA
Funder
CUGS (National Graduate School in Computer Science)
Available from: 2015-06-03 Created: 2015-06-03 Last updated: 2017-05-17
Jonsson, P. & Lagerkvist, V. (2015). Upper and Lower Bounds on the Time Complexity of Infinite-domain CSPs. In: Pesant, Gilles (Ed.), Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015, Proceedings: . Paper presented at 21st International Conference on Principles and Practice of Constraint Programming (CP-2015) (pp. 183-199). Springer Berlin/Heidelberg, 9255
Open this publication in new window or tab >>Upper and Lower Bounds on the Time Complexity of Infinite-domain CSPs
2015 (English)In: Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015, Proceedings / [ed] Pesant, Gilles, Springer Berlin/Heidelberg, 2015, Vol. 9255, p. 183-199Conference paper, Published paper (Refereed)
Abstract [en]

The constraint satisfaction problem (CSP) is a widely studied problem with numerous applications in computer science. For infinite-domain CSPs, there are many results separating tractable and NP-hard cases while upper bounds on the time complexity of hard cases are virtually unexplored. Hence, we initiate a study of the worst-case time cmplexity of such CSPs. We analyse backtracking algorithms and show that they can be improved by exploiting sparsification. We present even faster algorithms based on enumerating finite structures. Last, we prove non-trivial lower bounds applicable to many interesting CSPs, under the assumption that the strong exponential-time hypothesis is true.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2015
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 9255
National Category
Computer and Information Sciences Computer Sciences
Identifiers
urn:nbn:se:liu:diva-123120 (URN)10.1007/978-3-319-23219-5_14 (DOI)000364707100014 ()978-3-319-23218-8 (ISBN)
Conference
21st International Conference on Principles and Practice of Constraint Programming (CP-2015)
Available from: 2015-12-04 Created: 2015-12-04 Last updated: 2018-02-20
Jonsson, P. & Thapper, J. (2014). Affine Consistency and the Complexity of Semilinear Constraints. In: Ersébet Csuhaj-Varjú,Martin Dietzfelbinger,Zoltán Ésik (Ed.), Mathematical Foundations of Computer Science 2014: . Paper presented at 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014) (pp. 420-431). Berlin/Heidelberg
Open this publication in new window or tab >>Affine Consistency and the Complexity of Semilinear Constraints
2014 (English)In: Mathematical Foundations of Computer Science 2014 / [ed] Ersébet Csuhaj-Varjú,Martin Dietzfelbinger,Zoltán Ésik, Berlin/Heidelberg, 2014, p. 420-431Conference paper, Published paper (Refereed)
Abstract [en]

A semilinear relation is a finite union of finite intersections of open and closed half-spaces over, for instance, the reals, the rationals or the integers. Semilinear relations have been studied in connection with algebraic geometry, automata theory, and spatiotemporal reasoning, just to mention a few examples. We concentrate on relations over the reals and rational numbers. Under this assumption, the computational complexity of the constraint satisfaction problem (CSP) is known for all finite sets Γ of semilinear relations containing the relations R +={(x,y,z) | x+y=z}, ≤ and {1}. These problems correspond to extensions of LP feasibility. We generalise this result as follows. We introduce an algorithm, based on computing affine hulls, which solves a new class of semilinear CSPs in polynomial time. This allows us to fully determine the complexity of CSP(Γ) for semilinear Γ containing R+ and satisfying two auxiliary conditions. Our result covers all semilinear Γ such that {R+,{1}}⊆Γ. We continue by studying the more general case when Γ contains R+ but violates either of the two auxiliary conditions. We show that each such problem is equivalent to a problem in which the relations are finite unions of homogeneous linear sets and we present evidence that determining the complexity of these problems may be highly non-trivial.

Place, publisher, year, edition, pages
Berlin/Heidelberg: , 2014
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-112904 (URN)10.1007/978-3-662-44465-8_36 (DOI)000358254600036 ()2-s2.0-84906239762 (Scopus ID)978-3-662-44464-1 (ISBN)
Conference
39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014)
Available from: 2014-12-19 Created: 2014-12-19 Last updated: 2018-02-06
Bäckström, C., Jonsson, A. & Jonsson, P. (2014). Automaton Plans. The journal of artificial intelligence research, 51, 255-291
Open this publication in new window or tab >>Automaton Plans
2014 (English)In: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 51, p. 255-291Article in journal (Refereed) Published
Abstract [en]

Macros have long been used in planning to represent subsequences of operators. Macros can be used in place of individual operators during search, sometimes reducing the effort required to find a plan to the goal. Another use of macros is to compactly represent long plans. In this paper we introduce a novel solution concept called automaton plans in which plans are represented using hierarchies of automata. Automaton plans can be viewed as an extension of macros that enables parameterization and branching. We provide several examples that illustrate how automaton plans can be useful, both as a compact representation of exponentially long plans and as an alternative to sequential solutions in benchmark domains such as LOGISTICS and GRID. We also compare automaton plans to other compact plan representations from the literature, and find that automaton plans are strictly more expressive than macros, but strictly less expressive than HTNs and certain representations allowing efficient sequential access to the operators of the plan.

Place, publisher, year, edition, pages
AI ACCESS FOUNDATION, 2014
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-112193 (URN)10.1613/jair.4391 (DOI)000343090300001 ()
Available from: 2014-11-18 Created: 2014-11-18 Last updated: 2018-01-11
Jonsson, A., Jonsson, P. & Lööw, T. (2014). Limitations of acyclic causal graphs for planning. Artificial Intelligence, 210, 36-55
Open this publication in new window or tab >>Limitations of acyclic causal graphs for planning
2014 (English)In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 210, p. 36-55Article in journal (Refereed) Published
Abstract [en]

Causal graphs are widely used in planning to capture the internal structure of planning instances. Researchers have paid special attention to the subclass of planning instances with acyclic causal graphs, which in the past have been exploited to generate hierarchical plans, to compute heuristics, and to identify classes of planning instances that are easy to solve. This naturally raises the question of whether planning is easier when the causal graph is acyclic. In this article we show that the answer to this question is no, proving that in the worst case, the problem of plan existence is PSPACE-complete even when the causal graph is acyclic. Since the variables of the planning instances in our reduction are propositional, this result applies to STRIPS planning with negative preconditions. We show that the reduction still holds if we restrict actions to have at most two preconditions. Having established that planning is hard for acyclic causal graphs, we study two subclasses of planning instances with acyclic causal graphs. One such subclass is described by propositional variables that are either irreversible or symmetrically reversible. Another subclass is described by variables with strongly connected domain transition graphs. In both cases, plan existence is bounded away from PSPACE, but in the latter case, the problem of bounded plan existence is hard, implying that optimal planning is significantly harder than satisficing planning for this class.

Place, publisher, year, edition, pages
Elsevier, 2014
Keyword
Planning; Computational complexity
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-106831 (URN)10.1016/j.artint.2014.02.002 (DOI)000334974800002 ()
Available from: 2014-05-28 Created: 2014-05-23 Last updated: 2017-12-05
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-5288-3330

Search in DiVA

Show all publications