77 citations · 733 across the 54 of their papers we have counts for
36 papers · 1 filter
Approximate Graph Colouring and Crystals
Lorenzo Ciardo, Stanislav Živný
We show that approximate graph colouring is not solved by any level of the affine integer programming (AIP) hierarchy. To establish the result, we translate the problem of exhibiti…
Hierarchies of Minion Tests for PCSPs through Tensors
Lorenzo Ciardo, Stanislav Živný
We provide a unified framework to study hierarchies of relaxations for Constraint Satisfaction Problems and their Promise variant. The idea is to split the description of a hierarc…
Linearly ordered colourings of hypergraphs
Tamio-Vesa Nakajima, Stanislav Živný
A linearly ordered (LO) -colouring of an -uniform hypergraph assigns an integer from to every vertex so that, in every edge, the (multi)set of colours has…
The Sherali-Adams Hierarchy for Promise CSPs through Tensors
Lorenzo Ciardo, Stanislav Živný
We study the Sherali-Adams linear programming hierarchy in the context of promise constraint satisfaction problems (PCSPs). We characterise when a level of the hierarchy accepts an…
CLAP: A New Algorithm for Promise CSPs
Lorenzo Ciardo, Stanislav Živný
We propose a new algorithm for Promise Constraint Satisfaction Problems PCSPs). It is a combination of the onstraint Basic P relaxation and the …
Beyond PCSP (1-in-3,NAE)
Alex Brandts, Stanislav Živný
The promise constraint satisfaction problem (PCSP) is a recently introduced vast generalisation of the constraint satisfaction problem (CSP) that captures approximability of satisf…
QCSP on Reflexive Tournaments
Benoit Larose, Petar Markovic, Barnaby Martin +3
We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split…
The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
Caterina Viola, Stanislav Zivny
Convex relaxations have been instrumental in solvability of constraint satisfaction problems (CSPs), as well as in the three different generalisations of CSPs: valued CSPs, infinit…
Counting Homomorphisms to -minor-free Graphs, modulo 2
Jacob Focke, Leslie Ann Goldberg, Marc Roth +1
We study the problem of computing the parity of the number of homomorphisms from an input graph to a fixed graph . Faben and Jerrum [ToC'15] introduced an explicit criterion…
Topology and adjunction in promise constraint satisfaction
Andrei Krokhin, Jakub Opršal, Marcin Wrochna +1
The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a -colouring of a graph that is promised to be -colourable, where $c\g…
Approximate counting CSP seen from the other side
Andrei A. Bulatov, Stanislav Zivny
In this paper we study the complexity of counting Constraint Satisfaction Problems (CSPs) of the form #CSP(,-), in which the goal is, given a relational structure $\ma…
The Complexity of Approximately Counting Retractions to Square-Free Graphs
Jacob Focke, Leslie Ann Goldberg, Stanislav Živný
A retraction is a homomorphism from a graph to an induced subgraph of that is the identity on . In a long line of research, retractions have been studied under vario…
Improved hardness for H-colourings of G-colourable graphs
Marcin Wrochna, Stanislav Živný
We present new results on approximate colourings of graphs and, more generally, approximate H-colourings and promise constraint satisfaction problems. First, we show NP-hardness of…
The Complexity of Approximately Counting Retractions
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny
Let be a graph that contains an induced subgraph . A retraction from to is a homomorphism from to that is the identity function on . Retractions are very…
Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg +2
We analyse the complexity of approximate counting constraint satisfactions problems , where is a set of nonnegative rational-valued funct…
The complexity of general-valued CSPs seen from the other side
Clement Carbonnel, Miguel Romero, Stanislav Zivny
The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand side structures, the results of Dalmau, Kolaiti…
The Complexity of Counting Surjective Homomorphisms and Compactions
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny
A homomorphism from a graph G to a graph H is a function from the vertices of G to the vertices of H that preserves edges. A homomorphism is surjective if it uses all of the vertic…
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
Clement Carbonnel, David A. Cohen, Martin C. Cooper +1
Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of…
The complexity of Boolean surjective general-valued CSPs
Peter Fulla, Hannes Uppman, Stanislav Zivny
Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a -valued objective function given as a sum of fixed-arity funct…
The limits of SDP relaxations for general-valued CSPs
Johan Thapper, Stanislav Zivny
It has been shown that for a general-valued constraint language the following statements are equivalent: (1) any instance of can be solved to optimalit…
Binary Constraint Satisfaction Problems Defined by Excluded Topological Minors
David A. Cohen, Martin C. Cooper, Peter G. Jeavons +1
The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variab…
The power of Sherali-Adams relaxations for general-valued CSPs
Johan Thapper, Stanislav Zivny
We give a precise algebraic characterisation of the power of Sherali-Adams relaxations for solvability of valued constraint satisfaction problems to optimality. The condition is th…
The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
Martin C. Cooper, Stanislav Živný
Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and artificial intelligence. Forbidding pa…
On Planar Valued CSPs
Peter Fulla, Stanislav Zivny
We study the computational complexity of planar valued constraint satisfaction problems (VCSPs), which require the incidence graph of the instance be planar. First, we show that in…