liu.seSearch for publications in DiVA
Change search
Refine search result
12 1 - 50 of 86
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • 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
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the 'Create feeds' function.
  • 1.
    Aghighi, Meysam
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Oversubscription planning: Complexity and compilability2014In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AI Access Foundation , 2014, Vol. 3, p. 2221-2227Conference paper (Refereed)
    Abstract [en]

    Many real-world planning problems are oversubscription problems where all goals are not simultaneously achievable and the planner needs to find a feasible subset. We present complexity results for the so-called partial satisfaction and net benefit problems under various restrictions; this extends previous work by van den Briel et al. Our results reveal strong connections between these problems and with classical planning. We also present a method for efficiently compiling oversubscription problems into the ordinary plan existence problem; this can be viewed as a continuation of earlier work by Keyder and Geffner.

  • 2.
    Aghighi, Meysam
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Ståhlberg, Simon
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs2015In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, 2015Conference 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.

  • 3.
    Angelsmark, Ola
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Dahllöf, Vilhelm
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Jonsson, Peter
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Finite Domain Constraint Satisfaction Using Quantum Computation2002In: Mathematical Foundations of Computer Science, 27th International Symposium MFCS-2002,2002, Heidelberg: Springer Verlag , 2002, p. 93-Conference paper (Refereed)
    Abstract [en]

    We present a quantum algorithm for finite domain constraint solving, where the constraints have arity 2. It is complete and runs in time, where d is size of the domain of the variables and n the number of variables. For the case of d=3 we provide a method to obtain an upper time bound of . Also for d=5 the upper bound has been improved. Using this method in a slightly different way we can decide 3-colourability in O(1.2185^n) time.

  • 4.
    Angelsmark, Ola
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Improved algorithms for counting solutions in constraint satisfaction problems2003In: Principles and Practice of Constraint Programming, 9th International Conference CP 2003,2003, Springer, 2003, Vol. 2833, p. 81-95Conference paper (Refereed)
    Abstract [en]

    Counting the number of solutions to CSP instances has vast applications in several areas ranging from statistical physics to artificial intelligence. We provide a new algorithm for counting the number of solutions to binary CSP s which has a time complexity ranging from O ((d/4 . alpha(4))(n)) to O((alpha + alpha(5) + [d/4 - 1] . alpha(4))(n)) (where alpha approximate to 1.2561) depending on the domain size d greater than or equal to 3. This is substantially faster than previous algorithms, especially for small d. We also provide an algorithm for counting k-colourings in graphs and its running time ranges from O ([log(2) k](n)) to O ([log(2) k + 1](n)) depending on k greater than or equal to 4. Previously, only an O(1.8171(n)) time algorithm for counting 3-colourings were known, and we improve this upper bound to O(1.7879(n)).

  • 5.
    Angelsmark, Ola
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Jonsson, Peter
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Linusson, Svante
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Applied Mathematics.
    Thapper, Johan
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Applied Mathematics.
    Determining the Number of Solutions to Binary CSP Instances2002In: Principles and Practice of Constraint Programming, 8th International Conference CP-2002,2002, Heidelberg: Springer Verlag , 2002, p. 327-Conference paper (Refereed)
    Abstract [en]

    Counting the number of solutions to CSP instances has applications in several areas, ranging from statistical physics to artificial intelligence. We give an algorithm for counting the number of solutions to binary CSPs, which works by transforming the problem into a number of 2-SAT instances, where the total number of solutions to these instances is the same as those of the original problem. The algorithm consists of two main cases, depending on whether the domain size d is even, in which case the algorithm runs in O(1.3247^n*(d/2)^n) time, or odd, in which case it runs in O(1.3247^n*((d^2+d+2)/4)^(n/2)) if d=4*k+1, and O(1.3247^n*((d^2+d)/4)^(n/2)) if d=4*k+3. We also give an algorithm for counting the number of possible 3-colourings of a given graph, which runs in O(1.8171^n), an improvement over our general algorithm gained by using problem specific knowledge. 

  • 6.
    Bjäreland, Marcus
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab.
    Jonsson, Peter
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Exploiting bipartiteness to identify yet another tractable subclass of CSP1999In: Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming (CP), Springer , 1999, Vol. 1713, p. 118-128Conference paper (Refereed)
    Abstract [en]

    The class of constraint satisfaction problems (CSPs) over finite domains has been shown to be NP-complete, but many tractable subclasses have been identified in the literature. In this paper we are interested in restrictions on the types of constraint relations in CSP instances. By a result of Jeavons et al. we know that a key to the complexity of classes arising from such restrictions is the closure properties of the sets of relations. It has been shown that sets of relations that are closed under constant, majority, affine, or associative, commutative, and idempotent (ACI) functions yield tractable subclasses of CSP. However, it has been unknown whether other closure properties may generate tractable subclasses. In this paper we introduce a class of tractable (in fact, SL-complete) CSPs based on bipartite graphs. We show that there are members of this class that are not closed under constant, majority, affine, or ACI functions, and that it, therefore, is incomparable with previously identified classes.

  • 7.
    Bodirsky, Manuel
    et al.
    Ecole Polytechnique, Palaiseau, France.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    von Oertzen, Timo
    Max-Planck-Institute for Human Development, Berlin, Germany and University of Virginia, Charlottesville, USA..
    Essential Convexity and Complexity of Semi-algebraic Constraints2012In: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 8, no 4Article in journal (Refereed)
    Abstract [en]

    Let \Gamma be a structure with a finite relational signature and a first-order definition in (R;*,+) with parameters from R, that is, a relational structure over the real numbers where all relations are semi-algebraic sets. In this article, we study the computational complexity of constraint satisfaction problem (CSP) for \Gamma: the problem to decide whether a given primitive positive sentence is true in \Gamma. We focus on those structures \Gamma that contain the relations \leq, {(x,y,z) | x+y=z} and {1}. Hence, all CSPs studied in this article are at least as expressive as the feasibility problem for linear programs. The central concept in our investigation is essential convexity: a relation S is essentially convex if for all a,b\inS, there are only finitely many points on the line segment between a and b that are not in S. If \Gamma contains a relation S that is not essentially convex and this is witnessed by rational points a,b, then we show that the CSP for \Gamma is NP-hard. Furthermore, we characterize essentially convex relations in logical terms. This different view may open up new ways for identifying tractable classes of semi-algebraic CSPs. For instance, we show that if \Gamma is a first-order expansion of (R;*,+), then the CSP for \Gamma can be solved in polynomial time if and only if all relations in \Gamma are essentially convex (unless P=NP).

  • 8.
    Bodirsky, Manuel
    et al.
    Ecole Polytechnique, Palaiseau, France.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    von Oertzen, Timo
    University of Virginia, USA.
    Horn versus Full First-order: Complexity Dichotomies in Algebraic Constraint Satisfaction2012In: Journal of logic and computation (Print), ISSN 0955-792X, E-ISSN 1465-363X, Vol. 22, no 3, p. 643-660Article in journal (Refereed)
    Abstract [en]

    We study techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems. For certain fundamental algebraic structures Delta, we prove definability dichotomy theorems of the following form: for every first-order expansion Gamma of Delta, either Gamma has a quantifier-free Horn definition in Delta, or there is an element d of Gamma such that all non-empty relations in Gamma contain a tuple of the form (d,...,d), or all relations with a first-order definition in Delta have a primitive positive definition in Gamma. The results imply that several families of constraint satisfaction problems exhibit a complexity dichotomy: the problems are in P or NP-hard, depending on the choice of the allowed relations. As concrete examples, we investigate fundamental algebraic constraint satisfaction problems. The first class consists of all first-order expansions of (Q;+). The second class is the affine variant of the first class. In both cases, we obtain full dichotomies by utilising our general methods.

  • 9.
    Bodirsky, Manuel
    et al.
    CNRS/LIX, École Polytechnique, 91128 Palaiseau, France.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    von Oertzen, Timo
    Max-Planck-Institute for Human Development, Königin-Luise-Strasse 5, 14195, Berlin.
    Semilinear Program Feasibility2009In: Automata, Languages and Programming, Berlin / Heidelberg: Springer , 2009, p. 79-90Conference paper (Refereed)
    Abstract [en]

    We study logical techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems (CSPs). For the fundamental algebraic structure where are the real numbers and L 1,L 2,... is an enumeration of all linear relations with rational coefficients, we prove that a semilinear relation R (i.e., a relation that is first-order definable with linear inequalities) either has a quantifier-free Horn definition in Γ or the CSP for is NP-hard. The result implies a complexity dichotomy for all constraint languages that are first-order expansions of Γ: the corresponding CSPs are either in P or are NP-complete depending on the choice of allowed relations. We apply this result to two concrete examples (generalised linear programming and metric temporal reasoning) and obtain full complexity dichotomies in both cases.

  • 10.
    Broxvall, Mathias
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Point Algebras for Temporal Reasoning: Algorithms and Complexity2003In: Artificial Intelligence, ISSN 0004-3702, Vol. 149, no 2, p. 179-220Article in journal (Refereed)
    Abstract [en]

    We investigate the computational complexity of temporal reasoning in different time models such as totally-ordered, partially-ordered and branching time. Our main result concerns the satisfiability problem for point algebras and point algebras extended with disjunctions—for these problems, we identify all tractable subclasses. We also provide a number of additional results; for instance, we present a new time model suitable for reasoning about systems with a bounded number of unsynchronized clocks, we investigate connections with spatial reasoning and we present improved algorithms for deciding satisfiability of the tractable point algebras.

  • 11.
    Broxvall, Mathias
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Towards a complete classification of tractability in point algebras for nonlinear time1999In: Principles and Practice of Constraint Programming – CP’99: 5th International Conference, CP’99, Alexandria, VA, USA, October 11-14, 1999. Proceedings / [ed] Joxan Jaffar, Berlin: Springer, 1999, Vol. 1713, p. 129-143Chapter in book (Refereed)
    Abstract [en]

    Efficient reasoning about temporal constraints over nonlinear time models is vital in numerous application areas, such as planning, distributed systems and cooperating agents. We identify all tractable subclasses of the point algebra for partially-ordered time and examine one large, nontrivial tractable subclass of the point algebra for branching time.

  • 12.
    Broxvall, Mathias
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Renz, Jochen
    Institut für Informationssysteme, Technische Universität Wien, Wien, Austria.
    Disjunctions, Independence, Refinements2002In: Artificial Intelligence, ISSN 0004-3702, Vol. 140, no 1-2, p. 153-173Article in journal (Refereed)
    Abstract [en]

    An important question in constraint satisfaction is how to restrict the problem to ensure tractability (since the general problem is NP-hard). The use of disjunctions has proven to be a useful method for constructing tractable constraint classes from existing classes; the well-known ‘max-closed’ and ‘ORD-Horn’ constraints are examples of tractable classes that can be constructed this way. Three sufficient conditions (the guaranteed satisfaction property, 1-independence and 2-independence) that each ensure the tractability of constraints combined by disjunctions have been proposed in the literature. We show that these conditions are both necessary and sufficient for tractability in three different natural classes of disjunctive constraints. This suggests that deciding this kind of property is a very important task when dealing with disjunctive constraints. We provide a simple, automatic method for checking the 1-independence property—this method is applicable whenever the consistency of the constraints under consideration can be decided by path-consistency. Our method builds on a connection between independence and refinements (which is a way of reducing one constraint satisfaction problem to another.)

  • 13.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Chen, Yue
    Vienna University of Technology, Austria.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Ordyniak, Sebastian
    Vienna University of Technology, Austria.
    Szeider, Stefan
    Vienna University of Technology, Austria.
    The Complexity of Planning Revisited - A Parameterized Analysis2012In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI Press, 2012, p. 1735-1741Conference paper (Refereed)
    Abstract [en]

    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.

  • 14.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Jonsson, Anders
    University of Pompeu Fabra, Spain.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Automaton Plans2014In: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 51, p. 255-291Article in journal (Refereed)
    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.

  • 15.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Jonsson, Anders
    Universitat Pompeu Fabra, Barcelona, Spain.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    From Macro Plans to Automata Plans2012In: ECAI 2012. 20th European Conference on Artificial Intelligence, 27-31 2012,  August, Montpellier, France, 2012, p. 91-96Conference paper (Refereed)
    Abstract [en]

    Macros have a long-standing role in planning as a tool for representing repeating subsequences of operators. Macros are useful both for guiding search towards a solution and for representing plans compactly. In this paper we introduce automata plans which consist of hierarchies of finite state automata. Automata plans can be viewed as an extension of macros that enables parametrization and branching. We provide several examples of the utility of automata plans, and prove that automata plans are strictly more expressive than macro plans. We also prove that automata plans admit polynomialtime sequential access of the operators in the underlying “flat” plan, and identify a subset of automata plans that admit polynomial-time random access. Finally, we compare automata plans with other representations allowing polynomial-time sequential access.

  • 16.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Jonsson, Anders
    Universitat Pompeu Fabra, Barcelona, Spain.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Macros, Reactive Plans and Compact Representations2012In: ECAI 2012. 20th European Conference on Artificial Intelligence 27-31 August 2+12, Montpellier, France / [ed] Luc De Raedt, Christian Bessiere, Didier Dubois, Patrick Doherty, Paolo Frasconi, Fredrik Heintz, Peter Lucas, 2012, p. 85-90Conference paper (Refereed)
    Abstract [en]

    The use and study of compact representations of objects is widespread in computer science. AI planning can be viewed as the problem of finding a path in a graph that is implicitly described by a compact representation in a planning language. However, compact representations of the path itself (the plan) have not received much attention in the literature. Although both macro plans and reactive plans can be considered as such compact representations, little emphasis has been placed on this aspect in earlier work. There are also compact plan representations that are defined by their access properties, for instance, that they have efficient random access or efficient sequential access. We formally compare two such concepts with macro plans and reactive plans, viewed as compact representations, and provide a complete map of the relationships between them.

  • 17.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond2013In: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 47, p. 575-611Article in journal (Refereed)
    Abstract [en]

    The causal graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal graphs have largely analysed the computational complexity of planning for instances where the causal graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Giménez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-closed. We then argue that most NP-hardness theorems for causal graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.

  • 18.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Abstracting Abstraction in Search II: Complexity Analysis2012In: Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012 / [ed] Daniel Borrajo, Ariel Felner, Richard Korf, Maxim Likhachev, Carlos Linares Lopez, Wheeler Ruml, and Nathan Sturtevant, AAAI Press, 2012, p. 10-17Conference paper (Refereed)
    Abstract [en]

    Modelling abstraction as a function from the original state space to an abstract state space is a common approach in combinatorial search. Sometimes this is too restricted, though, and we have previously proposed a framework using a more flexible concept of transformations between labelled graphs. We also proposed a number of properties to describe and classify such transformations. This framework enabled the modelling of a number of different abstraction methods in a way that facilitated comparative analyses. It is of particular interest that these properties can be used to capture the concept of refinement without backtracking between levels; how to do this has been an open question for at least twenty years. In this paper, we continue our previous research by analysing the complexity of testing the various transformation properties for both explicit and implicit graph representations.

  • 19.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Abstracting Abstraction in Search with Applications to Planning2012In: Proceedings, Thirteenth International Conference on Principles of Knowledge Representation and Reasoning, AAAI Press, 2012, p. 446-456Conference paper (Refereed)
    Abstract [en]

    Abstraction has been used in search and planning from the very beginning of AI. Many different methods and formalisms for abstraction have been proposed in the literature but they have been designed from various points of view and with varying purposes. Hence, these methods have been notoriously difficult to analyse and compare in a structured way. In order to improve upon this situation, we present a coherent and flexible framework for modelling abstraction (and abstraction-like) methods based on transformations on labelled graphs. Transformations can have certain method properties that are inherent in the abstraction methods and describe their fundamental modelling characteristics, and they can have certain instance properties that describe algorithmic and computational characteristics of problem instances. The usefulness of the framework is demonstrated by applying it to problems in both search and planning. First, we show that we can capture many search abstraction concepts (such as avoidance of backtracking between levels) and that we can put them into a broader context. We further model five different abstraction concepts from the planning literature. Analysing what method properties they have highlights their fundamental differences and similarities. Finally, we prove that method properties sometimes imply instance properties. Taking also those instance properties into account reveals important information about computational aspects of the five methods.

  • 20.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Algorithms and Limits for Compact Plan Representations2012In: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 44, p. 141-177Article in journal (Refereed)
    Abstract [en]

    Compact representations of objects is a common concept in computer science. Automated planning can be viewed as a case of this concept: a planning instance is a compact implicit representation of a graph and the problem is to find a path (a plan) in this graph. While the graphs themselves are represented compactly as planning instances, the paths are usually represented explicitly as sequences of actions. Some cases are known where the plans always have compact representations, for example, using macros. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. In addition to this, we show that our results have consequences for what can be gained from reformulating planning into some other problem. As a contrast to this we also prove a number of positive results, demonstrating restricted cases where plans do have useful compact representations, as well as proving that macro plans have favourable access properties. Our results are finally discussed in relation to other relevant contexts.

  • 21.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    All PSPACE-complete Planning Problems are Equal but some are more Equal than Others2011In: Proceedings, The Fourth International Symposium on Combinatorial Search (SoCS-2011) / [ed] Daniel Borrajo, Maxim Likhachev, Carlos Linares Lopez, AAAI Press, 2011, p. 10-17Conference paper (Refereed)
    Abstract [en]

    Complexity analysis of planning is problematic. Even very simple planning languages are PSPACE-complete, yet cannot model many simple problems naturally. Many languages with much more powerful features are also PSPACE-complete. It is thus difficult to separate planning languages in a useful way and to get complexity figures that better reflect reality.This paper introduces new methods for complexity analysis of planning and similar combinatorial search problems, in order to achieve more precision and complexity separations than standard methods allow. Padding instances with the solution size yields a complexity measure that is immune to this factor and reveals other causes of hardness, that are otherwise hidden. Further combining this method with limited nondeterminism improves the precision, making even finer separations possible. We demonstrate with examples how these methods can narrow the gap between theory and practice.

  • 22.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Bridging the Gap Between Refinement and Heuristics in Abstraction2013In: IJCAI'13 Proceedings of the Twenty-Third international joint conference on Artificial Intelligence, AAAI Press, 2013, p. 2261-2267Conference paper (Refereed)
    Abstract [en]

    There are two major uses of abstraction in planning and search: refinement (where abstract solutions are extended into concrete solutions) and heuristics (where abstract solutions are used to compute heuristics for the original search space). These two approaches are usually viewed as unrelated in the literature. It is reasonable to believe, though, that they are related, since they are both intrinsically based on the structure of abstract search spaces. We take the first steps towards formally investigating their relationships, employing our recently introduced framework for analysing and comparing abstraction methods. By adding some mechanisms for expressing metric properties, we can capture concepts like admissibility and consistency of heuristics. We present an extensive study of how such metric properties relate to the properties in the original framework, revealing a number of connections between the refinement and heuristic approaches. This also provides new insights into, for example, Valtorta's theorem and spurious states.

  • 23.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Limits for compact representations of plans2011In: ICAPS 2011 : proceedings of the twenty-first international conference on automated planning and scheduling : annual ICAPS conference : Jun 2011, Freiburg, Germany / [ed] Fahiem Bacchus, Carmel Domshlak, Stefan Edelkamp, Malte Helmert, AAAI Press, 2011, p. 18-25Conference paper (Refereed)
    Abstract [en]

    Most planning formalisms allow instances with shortest plans of exponential length. While such instances are problematic, they are usually unavoidable and can occur in practice. There are several known cases of restricted planning problems where plans can be exponential but always have a compact (ie. polynomial) representation, often using recursive macros. Such compact representations are important since exponential plans are difficult both to use and to understand. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. Further, we show that it is unlikely to get around this by reformulating planning into some other problem. The results are discussed in the context of abstraction, macros and plan explanation.

  • 24.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Ordyniak, Sebastian
    Masaryk University, Czech Republic.
    Szeider, Stefan
    Vienna University of Technology, Austria.
    A complete parameterized complexity analysis of bounded planning2015In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 81, no 7, p. 1311-1332Article in journal (Refereed)
    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.

  • 25.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Ordyniak, Sebastian
    Masaryk University, Brno, Czech Republic.
    Szeider, Stefan
    Vienna University of Technolgy, Austria.
    Parameterized Complexity and Kernel Bounds for Hard Planning Problems2013In: Algorithms and Complexity: 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings / [ed] Paul G. Spirakis & Maria Serna, Springer Berlin/Heidelberg, 2013, p. 13-24Conference paper (Refereed)
    Abstract [en]

    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.

  • 26.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Ståhlberg, Simon
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Fast Detection of Unsolvable Planning Instances Using Local Consistency2013In: Proceedings of the Sixth International Symposium on Combinatorial Search, AAAI Press, 2013, p. 29-37Conference paper (Refereed)
    Abstract [en]

    There has been a tremendous advance in domain-independent planning over the past decades, and planners have become increasingly efficient at finding plans. However, this has not been paired by any corresponding improvement in detecting unsolvable instances. Such instances are obviously important but largely neglected in planning. In other areas, such as constraint solving and model checking, much effort has been spent on devising methods for detecting unsolvability. We introduce a method for detecting unsolvable planning instances that is loosely based on consistency checking in constraint programming. Our method balances completeness against efficiency through a parameter k: the algorithm identifies more unsolvable instances but takes more time for increasing values of k. We present empirical data for our algorithm and some standard planners on a number of unsolvable instances, demonstrating that our method can be very efficient where the planners fail to detect unsolvability within reasonable resource bounds. We observe that planners based on the h^m heuristic or pattern databases are better than other planners for detecting unsolvability. This is not a coincidence since there are similarities (but also significant differences) between our algorithm and these two heuristic methods.

  • 27.
    Cohen, D
    et al.
    University of London.
    Jeavons, P
    University of Oxford.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Koubarakis, M
    Technical Unversity of Crete.
    Building tractable disjunctive constraints2000In: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 47, no 5, p. 826-853Article in journal (Refereed)
    Abstract [en]

    Many combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of problems is known to be NP-hard in general, but a number of restricted constraint classes have been identified which ensure tractability. This paper presents the first general results on combining tractable constraint classes to obtain larger, more general, tractable classes. We give examples to show that many known examples of tractable constraint classes, from a wide variety of different contexts, can be constructed from simpler tractable classes using a general method. We also construct several new tractable classes that have not previously been identified.

  • 28.
    Dahllöf, Vilhelm
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    An Algorithm for Counting Maximum Weighted Independent Sets and its Applications2002In: Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2002), ACM-SIAM , 2002Conference paper (Refereed)
  • 29.
    Dahllöf, Vilhelm
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Jonsson, Peter
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Beigel, R.
    Department of Computer Science, Temple University, 1805 N Broad St Fl 4, Philadelphia, PA 19122, United States.
    Algorithms for four variants of the exact satisfiability problem2004In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 320, no 2-3, p. 373-394Article in journal (Refereed)
    Abstract [en]

    We present four polynomial space and exponential time algorithms for variants of the EXACT SATISFIABILITY problem. First, an O(1.1120n) (where n is the number of variables) time algorithm for the NP-complete decision problem of EXACT 3-SATISFIABILITY, and then an O(1.1907n) time algorithm for the general decision problem of EXACT SATISFIABILITY. The best previous algorithms run in O(1.1193n) and O(1.2299n) time, respectively. For the #P-complete problem of counting the number of models for EXACT 3-SATISFIABILITY we present an O(1.1487n) time algorithm. We also present an O(1.2190n) time algorithm for the general problem of counting the number of models for EXACT SATISFIABILITY, presenting a simple reduction, we show how this algorithm can be used for computing the permanent of a 0/1 matrix. © 2004 Elsevier B.V. All rights reserved.

  • 30.
    Dahllöf, Vilhelm
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Wahlström, Magnus
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Counting Satisfying Assignments in 2-SAT and 3-SAT2003Conference paper (Other academic)
    Abstract [en]

    We present an O(1.3247n) algorithm for counting the number of satisfying assignments for instances of 2-SAT and an O(1.6894n) algorithm for instances of 3-SAT. This is an improvement compared to the previously best known algorithms running in O(1.381n) and O(1.739n) time, respectively.

  • 31.
    Dahllöf, Wilhelm
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB. Linköping University, The Institute of Technology.
    Wahlström, Magnus
    Linköping University, Department of Computer and Information Science, TCSLAB. Linköping University, The Institute of Technology.
    Counting models for 2sat and 3sat formulae2005In: Theoretical Computer Science, ISSN 0304-3975, Vol. 332, no 1-3, p. 265-291Article in journal (Refereed)
    Abstract [en]

    We here present algorithms for counting models and max-weight models for 2SAT and 3SAT formulae. They use polynomial space and run in O(1.2561n) and O(1.6737n) time, respectively, where n is the number of variables. This is faster than the previously best algorithms for counting non-weighted models for 2SAT and 3SAT, which run in O(1.3247n) and O(1.6894n) time, respectively. In order to prove these time bounds, we develop new measures of formula complexity, allowing us to conveniently analyze the effects of certain factors with a large impact on the total running time. We also provide an algorithm for the restricted case of separable 2SAT formulae, with fast running times for well-studied input classes. For all three algorithms we present interesting applications, such as computing the permanent of sparse 0/1 matrices.

  • 32.
    Dalmau, Victor
    et al.
    Departament de Tecnologia Universitat Pompeu Fabra.
    Jonsson, Peter
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    The Complexity of Counting Homomorphisms Seen from the Other Side2004In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 329, p. 315-323Article in journal (Refereed)
  • 33. Deineko, Vladimir
    et al.
    Jonsson, Peter
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Klasson, Mikael
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Krokhin, Andrei
    Supermodularity on chains and complexity of maximum constraint satisfaction problems2005In: Proceedings of the European Conference on Combinatorics, Graph Theory and Applications Eurocomb 05,2005, DMTCS , 2005, p. 51-Conference paper (Refereed)
  • 34.
    Deineko, Vladimir
    et al.
    University of Warwick.
    Jonsson, Peter
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Klasson, Mikael
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Krokhin, Andrei
    University of Durham.
    The approximability of Max CSP with fixed-value constraints2008In: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 55, no 4Article in journal (Refereed)
  • 35. Engstrom, Robert
    et al.
    Färnqvist, Tommy
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Thapper, Johan
    University of Paris Est Marne La Vallee, France.
    An Approximability-related Parameter on Graphs - Properties and Applications2015In: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, ISSN 1462-7264, Vol. 17, no 1, p. 33-66Article in journal (Refereed)
    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.

  • 36.
    Engström, Robert
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Färnqvist, Tommy
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Thapper, Johan
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Properties of an Approximability-related Parameter on Circular Complete Graphs2009In: Electronic Notes in Discrete Mathematics, ISSN 1571-0653, E-ISSN 1571-0653, Vol. 35, p. 115-120Article in journal (Refereed)
    Abstract [en]

    The instances of the Weighted Maximum H-Colourable Subgraph problem (Max H-Col) are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H; note that for H=Kk this problem is equivalent to Max k-cut. Färnqvist et al. have introduced a parameter on the space of graphs that allows close study of the approximability properties of Max H-Col. Here, we investigate the properties of this parameter on circular complete graphs Kp/q, where 2p/q3. The results are extended to K4-minor-free graphs. We also consider connections with Šámal's work on fractional covering by cuts: we address, and decide, two conjectures concerning cubical chromatic numbers.

  • 37.
    Feder, Tomas
    et al.
    Stanford University.
    Hell, Pavol
    Simon Fraser University.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Krokhin, Andrei
    University of Durham.
    Nordh, Gustav
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Retractions To Pseudoforests2010In: SIAM JOURNAL ON DISCRETE MATHEMATICS, ISSN 0895-4801, Vol. 24, no 1, p. 101-112Article in journal (Refereed)
    Abstract [en]

    For a fixed graph H, let RET(H) denote the problem of deciding whether a given input graph is retractable to H. We classify the complexity of RET(H) when H is a graph (with loops allowed) where each connected component has at most one cycle, i.e., a pseudoforest. In particular, this result extends the known complexity classifications of RET(H) for reflexive and irreflexive cycles to general cycles. Our approach is based mainly on algebraic techniques from universal algebra that previously have been used for analyzing the complexity of constraint satisfaction problems.

  • 38.
    Färnqvist, Tommy
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Bounded Tree-Width and CSP-Related Problems2007In: Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007. Proceedings / [ed] Takeshi Tokuyama, Springer Berlin/Heidelberg, 2007, p. 632-643Chapter in book (Refereed)
    Abstract [en]

    We study the complexity of structurally restricted homomorphism and constraint satisfaction problems. For every class of relational structures C , let LHom be the problem of deciding whether a structure A Î CA has a homomorphism to a given arbitrary structure B, when each element in A is only allowed a certain subset of elements of B as its image. We prove, under a certain complexity-theoretic assumption, that this list homomorphism problem is solvable in polynomial time if and only if all structures in C have bounded tree-width. The result is extended to the connected list homomorphism, edge list homomorphism, minimum cost homomorphism and maximum solution problems. We also show an inapproximability result for the minimum cost homomorphism problem.

  • 39.
    Färnqvist, Tommy
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Thapper, Johan
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Approximability Distance in the Space of H-Colourability Problems2009In: COMPUTER SCIENCE - THEORY AND APPLICATIONS, ISSN 0302-9743, Vol. 5675, p. 92-104Article in journal (Refereed)
    Abstract [en]

    A graph homomorphism is a vertex map which carries edges from a source graph to edges in a target graph. We Study the approximability properties of the Weigh feel Maximum H-Colourable Subgraph problem (MAX H-COL). The instances of this problem are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H note that for H = K-k this problem is equivalent to MAX k-CUT. To this end, we introduce a metric structure on the space of graphs which allows us to extend previously known approximability results to larger classes of graphs. Specifically, the approximation algorithms for MAX CUT by Goemans and Williamson and MAX k-CUT by Frieze and Jerrum can he used to yield non-trivial approximation results for MAX H-COL For a variety of graphs, we show near-optimality results under the Unique Games Conjecture. We also use our method for comparing the performance of Frieze andamp; Jerrums algorithm with Hastads approximation algorithm for general MAX 2-CSP. This comparison is, in most cases, favourable to Frieze andamp; Jerrum.

  • 40.
    Haslum, Patrik
    et al.
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Planning with Reduced Operator Sets2000In: Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS) / [ed] Steve Chien, Subbarao Kambhampati, Craig A. Knoblock, AAAI Press , 2000, p. 150-158Conference paper (Refereed)
    Abstract [en]

    Classical propositional STRIPS planning is nothing but the search for a path in the state transition graph induced by the operators in the planning problem. What makes the problem hard is the size and the sometimes adverse structure of this graph. We conjecture that the search for a plan would be more efficient if there were only a small number of paths from the initial state to the goal state. To verify this conjecture, we define the notion of reduced operator sets and describe ways of finding such reduced sets. We demonstrate that some state-of-the-art planners run faster using reduced operator sets.

  • 41.
    Haslum, Patrik
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab.
    Jonsson, Peter
    Some results on the complexity of planning with incomplete information1999In: Proceedings of the 5th European Conference on Planning (ECP), Springer , 1999, Vol. 1809, p. 308-318Conference paper (Refereed)
    Abstract [en]

    Planning with incomplete information may mean a number of different things, that certain facts of the initial state are not known, that operators can have random or nondeterministic effects, or that the plans created contain sensing operations and are branching. Study of the complexity of incomplete information planning has so far been concentrated on probabilistic domains, where a number of results have been found. We examine the complexity of planning in nondeterministic propositional domains. This differs from domains involving randomness, which has been well studied, in that for a nondeterministic choice, not even a probability distribution over the possible outcomes is known. The main result of this paper is that the non-branching plan existence problem in unobservable domains with an expressive operator formalism is EXPSPACE-complete. We also discuss several restrictions, which bring the complexity of the problem down to PSPACF-complete, and extensions to the fully and partially observable cases.

  • 42.
    Jonsson, Anders
    et al.
    University of Pompeu Fabra, Spain .
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Lööw, Tomas
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Limitations of acyclic causal graphs for planning2014In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 210, p. 36-55Article in journal (Refereed)
    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.

  • 43.
    Jonsson, Anders
    et al.
    Universitat Pompeu Fabra, Barcelona, Spain.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Lööw, Tomas
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    When Acyclicity is not Enough: Limitations of the Causal Graph2013In: Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling, AAAI Press, 2013, p. 117-125Conference paper (Refereed)
    Abstract [en]

    Causal graphs are widely used in planning to capture the internal  structure of planning instances. In the past, causal graphs have been exploited to generate hierarchical plans, to compute heuristics, and  to identify classes of planning instances that are easy to solve. It  is generally believed that planning is easier when the causal graph is acyclic. In this paper we show that this is not true in the worst  case, proving that 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 pre-conditions. Having  established that planning is hard for acyclic causal graphs, we study  a subclass of planning instances with acyclic causal graphs whose  variables have strongly connected domain transition graphs. For this  class, we show that plan existence is easy, but that bounded plan  existence is hard, implying that optimal planning is significantly  harder than satisficing planning for this class.

  • 44.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Adding Clauses to Poor Man's Logic (Without Increasing the Complexity)2005In: Journal of applied non-classical logics, ISSN 1166-3081, Vol. 15, no 3, p. 341-357Article in journal (Refereed)
    Abstract [en]

    Partly motivated by description logics, poor man's logics have been proposed as an interesting fragment of modal logics. A poor man's logic is a propositional modal logic where only literals and the connectives , , and are allowed. It is known that the complexity of the satisfiability problem may drop dramatically when going from a full modal logic to the corresponding poor man's logic, e.g., in the case of modal logic K one goes from PSPACEcomplete to coNP-complete. We prove that it is sometimes possible to extend poor man's logics with restricted disjunctions (i.e., clauses) without increasing the computational complexity. For Horn and Krom clauses, we provide necessary and sufficient conditions for when the resulting logic is polynomial-time. Such extensions correspond to allowing a restricted use of the union operator in description logics.

  • 45.
    Jonsson, Peter
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Boolean constraint satisfaction: complexity results for optimization problems with arbitrary weights2000In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 244, no 1-2, p. 189-203Article in journal (Refereed)
    Abstract [en]

    A boolean constraint satisfaction problem consists of some finite set of constraints (i.e., functions from 0/1-vectors to {0, 1}) and an instance of such a problem is a set of constraints applied to specified subsets of n boolean variables. The goal is to find an assignment to the variables which satisfy all constraint applications. The computational complexity of optimization problems in connection with such problems has been studied extensively but the results have relied on the assumption that the weights are non-negative. The goal of this article is to study variants of these optimization problems where arbitrary weights are allowed. For the four problems that we consider, we give necessary and sufficient conditions for when the problems can be solved in polynomial time. In addition, we show that the problems are NP-equivalent in all other cases. (C) 2000 Elsevier Science B.V. All rights reserved.

  • 46.
    Jonsson, Peter
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Some Observations on Durations, Scheduling and Allen's Algebra2000In: Principles and Practice of Constraint Programming, 6th International Conference CP-2000,2000, Heidelberg: Springer Berlin/Heidelberg, 2000, Vol. 1894, p. 484-489Conference paper (Refereed)
    Abstract [en]

    Representing and reasoning about time has for a long time been acknowledged as one of the core areas of artificial intelligence and a large number of formalisms for temporal constraint reasoning (TCR) have been proposed in the literature. Important examples are the time point algebra, Allen's algebra, simple temporal constraints, and the qualitative algebra. These formalisms are almost exclusively dealing with the relative positions of time points (qualitative information) and/or the absolute position of time points on the time line (quantitative or metric information).

  • 47.
    Jonsson, Peter
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Haslum, Patrik
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab.
    Bäckström, Christer
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Towards efficient universal planning: A randomized approach2000In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 117, no 1, p. 1-29Article in journal (Refereed)
    Abstract [en]

    One of the most widespread approaches to reactive planning is Schoppers' universal plans. We propose a stricter definition of universal plans which guarantees a weak notion of soundness, not present in the original definition, and isolate three different types of completeness that capture different behaviors exhibited by universal plans. We show that universal plans which run in polynomial time and are of polynomial size cannot satisfy even the weakest type of completeness unless the polynomial hierarchy collapses. By relaxing either the polynomial time or the polynomial space requirement, the construction of universal plans satisfying the strongest type of completeness becomes trivial. As an alternative approach, we study randomized universal planning. By considering a randomized version of completeness and a restricted (but nontrivial) class of problems, we show that there exists randomized universal plans running in polynomial time and using polynomial space which are sound and complete for the restricted class of problems. We also report experimental results on this approach to planning, showing that the performance of a randomized planner is not easily compared to that of a deterministic planner.

  • 48.
    Jonsson, Peter
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Krokhin, A.
    Department of Computer Science, University of Warwick, United Kingdom, Department of Computer Science, University of Durham, Durham DH1 3LE, United Kingdom.
    Complexity classification in qualitative temporal constraint reasoning2004In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 160, no 1-2, p. 35-51Article in journal (Refereed)
    Abstract [en]

    We study the computational complexity of the qualitative algebra which is a temporal constraint formalism that combines the point algebra, the point-interval algebra and Allen's interval algebra. We identify all tractable fragments and show that every other fragment is NP-complete. © 2004 Elsevier B.V. All rights reserved.

  • 49.
    Jonsson, Peter
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Krokhin, A.
    Department of Computer Science, University of Durham, Science Laboratories, South Road, Durham, DH1 3LE, United Kingdom.
    Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights2007In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 73, no 5, p. 691-702Article in journal (Refereed)
    Abstract [en]

    In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of positive-weight constraints on overlapping sets of variables, and the goal is to assign values from a given domain to the variables so that the total weight of satisfied constraints is maximized. We consider this problem and its variant Max AW CSP where the weights are allowed to be both positive and negative, and study how the complexity of the problems depends on the allowed constraint types. We prove that Max AW CSP over an arbitrary finite domain exhibits a dichotomy: it is either polynomial-time solvable or NP-hard. Our proof builds on two results that may be of independent interest: one is that the problem of finding a maximum H-colourable subdigraph in a given digraph is either NP-hard or trivial depending on H, and the other a dichotomy result for Max CSP with a single allowed constraint type. © 2007 Elsevier Inc. All rights reserved.

  • 50.
    Jonsson, Peter
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
    Krokhin, A.
    Departament of Computer Science, University of Durham, Durham, DH1 3LE, United Kingdom.
    Recognizing frozen variables in constraint satisfaction problems2004In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 329, no 1-3, p. 93-113Article in journal (Refereed)
    Abstract [en]

    In constraint satisfaction problems over finite domains, some variables can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the instances. We show that the complexity of such problems is determined by certain algebraic properties of these relations. Under the assumption that NP ? coNP (and consequently PTIME ? NP), we characterize all tractable problems, and describe large classes of NP-complete, coNP-complete, and DP-complete problems. As an application of these results, we completely classify the complexity of the problem in two cases: (1) with domain size 2, and (2) when all unary relations are present. We also give a rough classification for domain size 3.© 2004 Elsevier B.V. All rights reserved.

12 1 - 50 of 86
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • 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