SŽStanislav Živný

Stanislav Živný

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Stanislav Živný has a total of 65 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    A Dichotomy for Maximum PCSPs on Graphs

    by Tamio-Vesa Nakajima, Stanislav Živný

    Fix two non-empty loopless graphs \( G \) and \( H \) such that \( G \) maps homomorphically to \( H \) . The Maximum Promise Constraint Satisfaction Problem parameterised by \( G \) and \( H \) is the following computational problem, denoted by \(\text{MaxPCSP}(G,H)\) : Given an input (multi)graph \( X \) that admits a map to \( G \) preserving a \(\rho\) -fraction of the edges, find a map from \( X \) to \( H \) that preserves a \(\rho\) -fraction of the edges. As our main result, we give a complete classification of this problem under Khot’s Unique Games Conjecture: The only tractable cases are when \( G \) is bipartite and \( H \) contains a triangle. Along the way, we establish several results, including an efficient approximation algorithm for the following problem: Given a (multi)graph \( X \) which contains a bipartite subgraph with \(\rho\) edges, what is the largest triangle-free subgraph of \( X \) that can be found efficiently? We present an SDP-based algorithm that finds one with at least \(0.8823\rho\) edges, thus improving on the subgraph with \(0.878\rho\) edges obtained by the classic Max-Cut algorithm of Goemans and Williamson.

  • Open Access

    Real-weighted general factors on subcubic graphs

    by Shuai Shao, Stanislav Zivný

    General factors generalize the concept of graph matchings and have been extensively studied in combinatorial optimization. Given a graph G where each vertex v is assigned a set $$\pi (v)$$ π ( v ) of feasible degrees (called a degree constraint), the general factor problem seeks a (spanning) subgraph F of G such that $$\deg _F(v) \in \pi (v)$$ deg F ( v ) ∈ π ( v ) for all v of G . When all degree constraints are symmetric $$\Delta $$ Δ -matroids, the problem is solvable in polynomial-time. The weighted general factor problem further extends this by incorporating edge weights, and the goal is to find a general factor that maximizes the total weight in an edge-weighted graph. In this paper, we propose a strongly polynomial-time algorithm for the real-weighted general factor problem on subcubic graphs by establishing a refined structural result that ensures the optimality of weighted graph factors. As an application of our result, we obtain a strongly polynomial-time algorithm for the terminal backup problem, a variant of the Steiner tree problem. Furthermore, we provide a characterization theorem for matching-gadget realizable degree constraints.

  • Open Access

    Equations over Finite Monoids with Infinite Promises

    by Alberto Larrauri, Antoine Mottet, Stanislav Živný

    Larrauri and Živný [ICALP’24/ACM ToCL’24] recently established a complete complexity classification of the problem of solving a system of equations over a monoid \({N}\) assuming that a solution exists over a monoid \({M}\) , where both monoids are finite and \({M}\) admits a homomorphism to \({N}\) . Using the algebraic approach to promise constraint satisfaction problems, we extend their complexity classification in two directions: we obtain a complexity dichotomy in the case where arbitrary relations are added to the monoids, and we moreover allow the monoid \({M}\) to be finitely generated.

  • Open Access

    Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings

    by Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, Stanislav Zivny

    Using the algebraic approach to promise constraint satisfaction problems, we establish complexity classifications of three natural variants of hypergraph colourings: standard nonmonochromatic colourings, conflict-free colourings, and linearly-ordered colourings. Firstly, we show that finding an ℓ-colouring of a k -colourable r -uniform hypergraph is NP-hard for all constant 2 ≤ k ≤ ℓ and r ≥ 3. This provides a shorter proof of a celebrated result by Dinur, Regev, and Smyth [FOCS’02/Combinatorica’05]. Secondly, we show that finding an ℓ-conflict-free colouring of an r -uniform hypergraph that admits a k -conflict-free colouring is NP-hard for all constant 2 ≤ k ≤ ℓ and r ≥ 4, except for r = 4 and k = 2 (and any ℓ); this case is solvable in polynomial time. The case of r = 3 is the standard nonmonochromatic colouring, and the case of r = 2 is the notoriously difficult open problem of approximate graph colouring. Thirdly, we show that finding an ℓ-linearly-ordered colouring of an r -uniform hypergraph that admits a k -linearly-ordered colouring is NP-hard for all constant 3 ≤ k ≤ ℓ and r ≥ 4, thus improving on the results of Nakajima and Živný [ICALP’22/ACM ToCT’23].

  • Open Access

    Hierarchies of Minion Tests for PCSPs through Tensors

    by 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 hierarchy into an algebraic part, depending on a minion capturing the ‘base level’, and a geometric part—which we call tensorisation —inspired by multilinear algebra. We exploit the structure of the tensor spaces arising from our construction to prove general properties of hierarchies. We identify certain classes of minions, which we call linear and conic , whose corresponding hierarchies have particularly fine features. We establish that the (combinatorial) bounded-width, Sherali–Adams LP, affine IP, Sum-of-Squares SDP, and combined ‘LP + affine IP’ hierarchies are all captured by this framework. In particular, in order to analyse the Sum-of-Squares SDP hierarchy, we also characterise the solvability of the standard SDP relaxation through a new minion.

  • Open Access

    Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity

    by Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Živný

    We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class \( C \) of UCQs, the problem \(\#\text{UCQ} (C)\) provides as input a UCQ \(\Psi\in C\) and a database \(\mathcal{D}\) and the problem is to compute the number of answers of \(\Psi\) in \(\mathcal{D}\) . Chen and Mengel [PODS ’16] have shown that for any recursively enumerable class \( C \) , the problem \(\#\text{UCQ} (C)\) is either fixed-parameter tractable or hard for one of the parameterised complexity classes \(\mathrm{W}[1]\) or \(\#\mathrm{W}[1]\) . However, their tractability criterion is unwieldy in the sense that, given any concrete class \( C \) of UCQs, it is not easy to determine how hard it is to count answers to queries in \( C \) . Moreover, given a single specific UCQ \(\Psi\) , it is not easy to determine how hard it is to count answers to \(\Psi\) . In this work, we address the question of finding a natural tractability criterion: The combined conjunctive query of a UCQ \(\Psi=\varphi_{1}\vee\dots\vee\varphi_{\ell}\) is the conjunctive query \(\boldsymbol{\wedge}\left(\Psi\right)=\varphi_{1}\wedge\dots\wedge\varphi_{\ell}\) . We show that under natural closure properties of \( C \) , the problem \(\#\text{UCQ} (C)\) is FPT if and only if the combined conjunctive queries of UCQs in \( C \) , and their contracts, have bounded treewidth. A contract of a conjunctive query is an augmented structure, taking into account how the quantified variables are connected to the free variables—if all variables are free, then a conjunctive query is equal to its contract; in this special case the criterion for fixed-parameter tractability of \(\#\text{UCQ} (C)\) thus simplifies to the combined queries having bounded treewidth. Finally, we give evidence that a closure property on \( C \) is necessary for obtaining a natural tractability criterion: We show that even for a single UCQ \(\Psi\) , the meta problem of deciding whether \(\#\text{UCQ} (\{\Psi\})\) can be solved in time \(O(|\mathcal{D}|^{d})\) is \(\mathrm{NP}\) -hard for any fixed \(d\geq 1\) . Moreover, we prove that a known exponential-time algorithm for solving the meta problem is optimal under assumptions from fine-grained complexity theory. As a corollary of our reduction, we also establish that approximating the Weisfeiler-Leman-Dimension of a UCQ is \(\mathrm{NP}\) -hard.

  • Approximate Graph Coloring and the Crystal with a Hollow Shadow

    by Lorenzo Ciardo, Stanislav Živný

    We show that approximate graph coloring is not solved by the lift-and-project hierarchy for the combination of linear programming and linear Diophantine equations. The proof is based on combinatorial tensor theory.


  • Semidefinite Programming and Linear Equations vs. Homomorphism Problems

    by Lorenzo Ciardo, Stanislav Živný

    We introduce a relaxation for homomorphism problems that combines semidefinite programming with linear Diophantine equations and propose a framework for the analysis of its power based on the spectral theory of association schemes. We use this framework to establish an unconditional lower bound against the semidefinite programming + linear equations model by showing that the relaxation does not solve the approximate graph homomorphism problem and thus, in particular, the approximate graph coloring problem.


  • Open Access

    1 -in- 3 vs . N ot -A ll -E qual : Dichotomy of a Broken Promise

    by Lorenzo Ciardo, Marcin Kozik, Andrei Krokhin, Tamio-Vesa Nakajima, Stanislav Živný

    The 1 -in- 3 and N ot -A ll -E qual satisfiability problems for Boolean CNF formulas are two well-known NP -hard problems. In contrast, the promise 1 -in- 3 vs . N ot -A ll -E qual problem can be solved in polynomial time. In the present work, we investigate this constraint satisfaction problem in a regime where the promise is weakened from either side by a rainbow-free structure and establish a complexity dichotomy for the resulting class of computational problems.