Browsing by Author "Zivny, Stanislav"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Pliability and Approximating Max-CSPs
    (2023) Romero, Miguel; Wrochna, Marcin; Zivny, Stanislav
    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-2-CSPs parameterised by the class of allowed constraint graphs (with arbitrary constraints on an unbounded alphabet). Our result applies more generally to the maximum homomorphism problem between two rational-valued structures.