77 citations · 733 across the 54 of their papers we have counts for
55 papers
Sparsification of Monotone -Submodular Functions of Low Curvature
Jannik Kudla, Stanislav Živný
Pioneered by Benczur and Karger for cuts in graphs [STOC'96], sparsification is a fundamental topic with wide-ranging applications that has been studied, e.g., for graphs and hyper…
A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
Shuai Shao, Stanislav Živný
General factors are a generalization of matchings. Given a graph with a set of feasible degrees, called a degree constraint, for each vertex of , the general fact…
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 …
On rainbow-free colourings of uniform hypergraphs
Ragnar Groot Koerkamp, Stanislav Živný
We study rainbow-free colourings of -uniform hypergraphs; that is, colourings that use colours but with the property that no hyperedge attains all colours. We show that $p^*…
Additive Sparsification of CSPs
Eden Pelleg, Stanislav Živný
Multiplicative cut sparsifiers, introduced by Benczúr and Karger [STOC'96], have proved extremely influential and found various applications. Precise characterisations were establi…
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…
PTAS for Sparse General-Valued CSPs
Balázs F. Mezei, Marcin Wrochna, Stanislav Živný
We study polynomial-time approximation schemes (PTASes) for constraint satisfaction problems (CSPs) such as Maximum Independent Set or Minimum Vertex Cover on sparse graph classes.…
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…
The complexity of promise SAT on non-Boolean domains
Alex Brandts, Marcin Wrochna, Stanislav Živný
While 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin, Guruswami, and Håstad roved a result known as "-SAT is NP-hard" [FOCS'14/SICOMP'17]. They sh…
Pliability and Approximating Max-CSPs
Miguel Romero, Marcin Wrochna, Stanislav Živný
We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time algorithm for an arbitrarily good approximation of the optimal value in a large class of Max-…
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…
Point-width and Max-CSPs
Clement Carbonnel, Miguel Romero, Stanislav Zivny
The complexity of (unbounded-arity) Max-CSPs under structural restrictions is poorly understood. The two most general hypergraph properties known to ensure tractability of Max-CSPs…
Using a min-cut generalisation to go beyond Boolean surjective VCSPs
Gregor Matl, Stanislav Zivny
In this work, we first study a natural generalisation of the Min-Cut problem, where a graph is augmented by a superadditive set function defined on its vertex subsets. The goal is…
Sparsification of Binary CSPs
Silvia Butti, Stanislav Zivny
A cut -sparsifier of a weighted graph is a re-weighted subgraph of of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor 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…