77 citations · 733 across the 54 of their papers we have counts for
9 papers · 1 filter
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…
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 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-…
A tractable class of binary VCSPs via M-convex intersection
Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota +1
A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions. An important line of VCSP research is to…
Discrete Convexity in Joint Winner Property
Yuni Iwamasa, Kazuo Murota, Stanislav Zivny
In this paper, we reveal a relation between joint winner property (JWP) in the field of valued constraint satisfaction problems (VCSPs) and M-convexity in the field of…
Functional Clones and Expressibility of Partition Functions
Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum +2
We study functional clones, which are sets of non-negative pseudo-Boolean functions (functions ) closed under (essentially) multiplication, summati…
Binarisation for Valued Constraint Satisfaction Problems
David A. Cohen, Martin C. Cooper, Peter G. Jeavons +3
We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the alge…
The Expressive Power of Binary Submodular Functions
Stanislav Zivny, David A. Cohen, Peter G. Jeavons
It has previously been an open problem whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables.…