# PTAS for Sparse General-Valued CSPs††thanks:  Stanislav Živný was supported
by a Royal Society University Research Fellowship. This project has received
funding from the European Research Council (ERC) under the European Union’s
Horizon 2020 research and innovation programme (grant agreement No 714532).
The paper reflects only the authors’ views and not the views of the ERC or the
European Commission. The European Union is not liable for any use that may be
made of the information contained therein.

Balázs F. Mezei
University of Oxford
<EMAIL_ADDRESS>Marcin Wrochna
University of Oxford
<EMAIL_ADDRESS>Stanislav Živný
University of Oxford
<EMAIL_ADDRESS>
###### Abstract

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.

Baker’s approach gives a PTAS on planar graphs, excluded-minor classes, and
beyond. For Max-CSPs, and even more generally, maximisation finite-valued CSPs
(where constraints are arbitrary non-negative functions), Romero, Wrochna, and
Živný [SODA’21] showed that the Sherali-Adams LP relaxation gives a simple
PTAS for all fractionally-treewidth-fragile classes, which is the most general
“sparsity” condition for which a PTAS is known. We extend these results to
general-valued CSPs, which include “crisp” (or “strict”) constraints that have
to be satisfied by every feasible assignment. The only condition on the crisp
constraints is that their domain contains an element which is at least as
feasible as all the others (but possibly less valuable).

For minimisation general-valued CSPs with crisp constraints, we present a PTAS
for all _Baker_ graph classes — a definition by Dvořák [SODA’20] which
encompasses all classes where Baker’s technique is known to work, except
possibly for fractionally-treewidth-fragile classes. While this is standard
for problems satisfying a certain monotonicity condition on crisp constraints,
we show this can be relaxed to _diagonalisability_ — a property of relational
structures connected to logics, statistical physics, and random CSPs.

##  1 Introduction

Min-Ones and Max-Ones, studied by Khanna and Motwani (under the names of TMIN
and TMAX, respectively) [KM96] and by Khanna, Sudan, Trevisan, and Williamson
[Kha+01], are Boolean CSPs in which one seeks a feasible solution (a 0–1
assignment satisfying all constraints) minimising/maximising the number of
variables assigned the label $1$. Classical examples are the Minimum Vertex
Cover and the Maximum Independent Set problem, respectively. A natural
generalisation to larger alphabets is the problem in which one seeks a
solution to a CSP instance while minimising/maximising a sum of unary
functions. With injective unary functions, such problems have been studied
under the name of Strict-CSP by Kumar, Manokaran, Tulsiani, and Vishnoi
[Kum+11], and Min/Max-Solution by Jonsson, Kuivinen, and Nordh [JKN08]. With
arbitrary unary functions, such problems have been studied under the name of
Min-Cost-Hom by Gutin, Hell, Rafiey, and Yeo [Gut+08], Takhanov [Tak10], and
others [HR12, Hel+12, RRS19]. In this paper we consider the still more general
setting of _general-valued_ CSPs, where constraints are functions which give
values to every possible assignment on a tuple of variables; we allow $\infty$
or $-\infty$ values to express _crisp_ (also known as _strict_) constraints,
which have to be satisfied by every feasible (finite-valued) assignment. While
a lot of research is devoted to exact algorithms or optimal approximation
ratios in APX-hard cases (see [JN08, JKŽ14, MM17] for surveys), we seek the
most general conditions that allow to obtain a polynomial-time approximation
scheme (PTAS).

Baker [Bak94] gave an elegant method (sometimes known as the _shifting_ or
_layering technique_) for constructing polynomial-time approximation schemes
(PTASes) which applies to many such problems, with the condition that the
input instance’s graph (the Gaifman graph) is “sparse”. This was initially
presented for planar graphs, but it is known that similar structural
properties are exhibited by all proper minor-closed graph classes [Gro03,
DeV+04, DHK05] and beyond: e.g. graphs embeddable in a fixed surface with few
intersections per edge [MHS97, GB07], or sparse unit ball intersection graphs
in few dimensions [Hun+98] (but not e.g. 3-regular expanders: bounded degree
is not sufficient to get a PTAS even for Independent Set [BK99]). Dvořák
[Dvo16] defined _fractionally-treewidth-fragile_ classes — a natural
generalisation of earlier sparsity conditions — which encompasses all these
examples. A class of graphs is fractionally-treewidth-fragile if one can
remove vertices in a randomised way so that each vertex is removed with
arbitrarily small probability $\varepsilon$, but the treewidth after removal
is always bounded, the bound depending on $\varepsilon$ only. He showed that
if this notion of sparsity can be efficiently certified in a class of graphs,
then this suffices to guarantee a PTAS, at least for a few problems such as
Weighted Maximum Independent Set. On the other hand it is not known whether
this suffices for Minimum Vertex Cover, for example.

To remedy this, Dvořák [Dvo20] later defined _Baker classes_ and proved that
(an effective version of) this condition suffices to provide a PTAS to all
monotone optimisation problems expressible in first-order logic (including of
course Vertex Cover). Very roughly, a class of graphs is _Baker_ if one can
reduce each graph in it to the empty graph by a bounded number of the
following steps: either remove a single vertex, or select a breadth-first-
search layering and recurse into all subgraphs that can be induced by a few
consecutive layers. Dvořák proved that the family of Baker classes still
includes all the examples discussed above; on the other hand, it is included
in the family of fractionally-treewidth-fragile classes (and hence less
general, though the inclusion is not known to be strict). It is worth
mentioning that proper minor-closed graph classes can be shown to be Baker
(and fractionally-treewidth-fragile) relatively easily, without using the
Graph Minor Structure theorem, in contrast to the earlier, less general
definitions (see [Dvo20] for details).

In order to provide a PTAS for a class of general-valued CSPs, _a sparsity
condition is not enough_ : we also need to restrict what types of constraints
can be used in an instance. Otherwise, even if the values to be optimised are
trivial, either 0 or infinity, one could use the crisp constraints to express
3-Colouring, which is NP-hard even on planar graphs of bounded degree [Dai80].
In fact, as long as all crisp constraints are available, for any possible
restriction on Gaifman graphs, either the restriction implies bounded
treewidth, making the problem exactly solvable, or it is hard to decide
whether the optimum is zero or infinite, by a result of Grohe, Schwentick, and
Segoufin [GSS01]. We will hence require a condition which ensures that one can
easily decide whether a feasible solution (of finite value) exists. This
usually takes the form of a monotonicity condition.

On the other hand, _some sparsity condition is also necessary_ : on general
Gaifman graphs, there is no restriction of constraint types that would result
in a general-valued CSP that admits a PTAS but is not solvable exactly in
polynomial time.111This follows from the NP-hardness result of Kozik and
Ochremiak [KO15], which actually shows APX-hardness; for earlier, explicit
APX-hardness results for CSPs see, e.g., [JKN08, JKK09]. However, we remark
non-trivial PTAS examples are known for “surjective” maximisation finite-
valued CSPs [FUŽ19]. In this sense our work follows the line of “uniform” or
“hybrid” CSPs, which include restrictions on both the input’s Gaifman graph
(_left-hand side_ restrictions) and on the types of constraints (_right-hand
side_ restrictions); see [CŽ17] for a survey. However, unlike that line of
work, we look for PTASes instead of exact solvability, which also lets us go
well beyond planar graphs and beyond very specialised algebraic algorithms.

#### Related work

The exact solvability of general-valued CSPs has been characterised for left-
hand side restrictions [CRŽ18] (tractable cases are precisely classes that
have bounded treewidth, up to a certain notion of homomorphic equivalence) and
right-hand side restrictions [KKR17] (tractable cases are precisely delineated
by certain algebraic properties); both results include the case where infinite
values are allowed.

As discussed above, there are no PTASes for general-valued CSPs with only
left-hand side or only right-hand side restrictions, beyond exactly solvable
cases. In fact Khanna et al. [Kha+01], in their work on Min-Ones and Max-Ones
with right-hand side restriction, remark that “Our framework lacks such
phenomena as PTAS” and discuss left-hand side restrictions as an interesting
avenue for future work for that reason. Similarly [JKN08] and [JN08] ask in
the context of right-hand side restricted Min-Solution and Max-Solution
problems: “Under which restrictions on variable scopes does Max Sol admit a
PTAS?”.

Very recently, PTASes for left-hand side restricted Max-CSP without crisp
constraints, such as Max-Cut, have been studied by Romero, Wrochna, and Živný
[RWŽ21]. More generally, they consider so-called finite-valued CSPs, where the
only right-hand side restriction is having finite, non-negative values. They
showed a PTAS is possible for every fractionally-treewidth-fragile class of
Gaifman graphs. In fact the algorithm is simply the Sherali-Adams linear
programming relaxation (with a growing number of levels giving a better and
better approximation), which is oblivious to the graph structure and does not
require it to be efficiently certified in any way.

As for constant-factor approximations, Raghavendra’s celebrated result gave
the best approximation ratio, assuming the Unique Games Conjecture of Khot
[Kho02], for all right-hand side restricted Max-CSPs (and also finite-valued
CSPs) [Rag08]. Analogous results for monotone Strict-CSPs were obtained by
Kumar et al. [Kum+11]. Constant-factor approximation algorithms have been
established for right-hand side restricted Min-Cost-Hom on special graphs by
Hell, Mastrolilli, Nevisi, and Rafiey [Hel+12], and for all graphs and some
digraphs by Rafiey, Rafiey, and Santos [RRS19].

#### Our results

To clearly separate left-hand side and right-hand side restriction, it is
convenient to phrase a general-valued CSP as the problem of optimizing the
value of a function between two valued structures. Precise definitions are
given in Section 2. Briefly, a _valued structure_ $\mathbb{A}$ consists of a
domain $A$ and a collection of functions $f^{\mathbb{A}}\colon
A^{n}\to\mathbb{Q}\cup\\{\pm\infty\\}$, indexed by symbols $f$ belonging to a
set of symbols $\sigma$ called a signature. For two structures
$\mathbb{A},\mathbb{C}$, the _value_ of an assignment $h\colon A\to C$ is an
expression of the form $\sum
f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(h(\mathbf{x}))$. _Feasible_
assignments are those of finite value. The reader should think of the left-
hand side structure $\mathbb{A}$ as of a set of variables $A$ together with
weighted constraint scopes: for $\mathbf{x}\in A^{n}$,
$f^{\mathbb{A}}(\mathbf{x})=w\neq 0$ means that the instance applies the
constraint “$f$” to variables in $\mathbf{x}$ with weight $w$. The right-hand
side structure $\mathbb{C}$ encodes the alphabet $C$ (to which an assignment
$h$ maps each variable) and the collection of available constraints, which
could be arbitrary $\mathbb{Q}\cup\\{\pm\infty\\}$-valued cost functions in
general. An instance of the problem VCSP is a pair $(\mathbb{A},\mathbb{C})$;
its Gaifman graph, denoted by $\operatorname{G}(\mathbb{A})$, is a graph whose
vertex set is the domain $A$ with edges between two vertices that occur
together in a constraint of non-zero weight.

##### Minimum Solution

For minimisation, we first consider $(\mathbb{Q}_{\geq
0}\cup\\{\infty\\})$-valued right-hand side structures $\mathbb{C}$, in which
the sets of zero-valued tuples and finite-valued tuples are anti-monotone, in
the following sense. There is a total order $\leq_{\top}$ on $C$, and for all
tuples $\mathbf{x},\mathbf{y}\in C^{n}$ with $\mathbf{x}\leq_{\top}\mathbf{y}$
(coordinate-wise) we have that for all non-unary function symbols $f$ of
$\mathbb{C}$:

  * •

$f^{\mathbb{C}}(\mathbf{x})<\infty$ implies
$f^{\mathbb{C}}(\mathbf{y})<\infty$, and

  * •

$f^{\mathbb{C}}(\mathbf{x})=0$ implies $f^{\mathbb{C}}(\mathbf{y})=0$.

Intuitively, larger tuples are more feasible. We call valued structures
$\mathbb{C}$ satisfying this condition Min-Sol structures. We define
$\mbox{Min-Sol}_{\mathcal{G}}$ to be the general-valued CSP restricted to
instances $(\mathbb{A},\mathbb{C})$ where $\mathbb{A}$ is a $\mathbb{Q}_{\geq
0}$-valued structured with $\operatorname{G}(\mathbb{A})\in\mathcal{G}$ and
$\mathbb{C}$ is a Min-Sol structure.

For example, Weighted Minimum Vertex Cover is equivalent to the Min-Sol case
where $\mathbb{C}$ is the structure with domain $\\{0,1\\}$ with a 2-ary cost
function $f^{\mathbb{C}}(0,0)=\infty$,
$f^{\mathbb{C}}(1,0)=f^{\mathbb{C}}(0,1)=f^{\mathbb{C}}(1,1)=0$, and a unary
cost function $u^{\mathbb{C}}(0)=0$, $u^{\mathbb{C}}(1)=1$.

We show that $\mbox{Min-Sol}_{\mathcal{G}}$ admits a PTAS for all graph
classes $\mathcal{G}$ that are efficiently Baker. (Dvořák’s definition is
somewhat involved but we give an exposition in Section 4). As discussed above,
this captures essentially all graph classes where a version of Baker’s
technique is known to apply (including excluded-minor classes and more),
except possibly for fractionally-treewidth-fragile classes. We remark that
already the very special case of Minimum Vertex Cover is not known to admit a
PTAS on fractionally-treewidth-fragile classes.

Simultaneously, our results are less restrictive on the right-hand side, as
unlike in earlier work such as the framework of Strict-CSP of [Kum+11], we
allow arbitrary values strictly between $0$ and $\infty$ (not only on unary
constraints). Once we realise this is possible, however, the algorithm turns
out to be a rather standard application of Baker’s technique: the only
difference is that we increase the number of layers to account for the maximum
ratio between finite, positive values (which is a constant depending on values
of $\mathbb{C}$ only).

The main novelty in this work is that we extend this further by relaxing the
right-hand side restriction that $\mathbb{C}$ is a Min-Sol structure to the
even more general assumption that $\mathbb{C}$ is a diagonalisable structure.
Diagonalisability is a notion derived from the work of Brightwell and Winkler
[BW00] in the case of graphs and Briceño, Bulatov, Dalmua, and Larose [Bri+19]
in more general relational structures. It has many equivalent definitions (see
[Bri+19]: Corollary 6.3 and Theorem 3.6 in the case $J=V(H)$). One definition
is dismantlability of the square of the structure to its diagonal (see details
in Section 3.1). Another is connectivity of spaces of homomorphisms into the
structure (where two homomorphisms are connected if they differ at only one
vertex). A few other characterisations connect it to statistical physics via
“mixing” properties. Diagonalisability is also equivalent to finite duality
(the existence of finitely many obstructions to having a homomorphism into the
structure), a notion important to the study of CSPs via logic [BKL08].

Our main result for minimisation (proved in Section 4) shows that
diagonalisability connects naturally with Baker’s technique.

######  Theorem 1.1.

Let $\mathcal{G}$ be an $(f_{1},f_{2})$-efficiently Baker class. Then, for any
$\varepsilon>0$ and any instance $(\mathbb{A},\mathbb{C})$ of general-valued
CSP where $\mathbb{A}$ is a $\mathbb{Q}_{\geq 0}$-valued structured with
$\operatorname{G}(\mathbb{A})\in\mathcal{G}$ and $\mathbb{C}$ is
diagonalisable, we can find a solution of value at most
$(1+\varepsilon)\operatorname{minval}(\mathbb{A},\mathbb{C})$ in time
$f_{1}(\lvert\mathbb{A}\rvert)+f_{2}(c\lvert\mathbb{A}\rvert)\cdot
c^{1/\varepsilon}$ where $c$ depends on $\mathbb{C}$ and $\mathcal{G}$ only.

Here the constant $c$ depends polynomially on $\lvert\mathbb{C}\rvert$ and
exponentially on the maximum ratio between certain finite positive values of
$\mathbb{C}$. Since every class of graphs that excludes a minor is
$(\mathcal{O}\left\lparen n^{2}\right\rparen,\mathcal{O}\left\lparen
n\right\rparen)$-efficiently Baker [Dvo20, Theorem 2.1], Theorem 1.1 in fact
gives an EPTAS on such classes for any fixed diagonalisable structure
$\mathbb{C}$.

##### Maximum Solution

For maximisation, we extend the results of [RWŽ21], which restricted the
right-hand side $\mathbb{C}$ to be $\mathbb{Q}_{\geq 0}$-valued. We
additionally allow $-\infty$ values, but the set of tuples $\mathbf{y}\in
C^{n}$ with $f^{\mathbb{C}}(\mathbf{y})=-\infty$ is restricted to be monotone
in the following very weak sense. There is an element $c_{\bot}\in C$ such
that whenever $\mathbf{y}$ is feasible
($f^{\mathbb{C}}(\mathbf{y})\neq-\infty$) and $\mathbf{y}^{\prime}$ is a tuple
obtained from $\mathbf{y}$ by replacing some of its elements with $c_{\bot}$,
then $\mathbf{y}^{\prime}$ is still feasible
($f^{\mathbb{C}}(\mathbf{y}^{\prime})\neq-\infty$).

We call structures $\mathbb{C}$ satisfying this condition Max-Sol structures
and we define $\mbox{Max-Sol}_{\mathcal{G}}$ to be the general-valued CSP
restricted to instances $(\mathbb{A},\mathbb{C})$ where $\mathbb{A}$ is a
$\mathbb{Q}_{\geq 0}$-valued structured with
$\operatorname{G}(\mathbb{A})\in\mathcal{G}$ and $\mathbb{C}$ is a Max-Sol
structure.

For example, Weighted Maximum Independent Set is equivalent to the Max-Sol
case where $\mathbb{C}$ is the structure with domain $\\{0,1\\}$, with a 2-ary
function $f^{\mathbb{C}}(1,1)=-\infty$,
$f^{\mathbb{C}}(0,0)=f^{\mathbb{C}}(1,0)=f^{\mathbb{C}}(0,1)=0$, and a unary
function $u^{\mathbb{C}}(0)=0$, $u^{\mathbb{C}}(1)=1$ (so $c_{\bot}=0$).

Our main result for maximisation (proved in Section 5) is the following.

######  Theorem 1.2.

Let $\mathcal{G}$ be a class of graphs that is fractionally-treewidth-fragile.
Then $\mbox{Max-Sol}_{\mathcal{G}}$ admits a PTAS.

More precisely, for all $\varepsilon>0$, there is an algorithm that given
$(\mathbb{A},\mathbb{C})$, outputs a value between
$\operatorname{maxval}(\mathbb{A},\mathbb{C})$ and
$(1+\varepsilon)\cdot\operatorname{maxval}(\mathbb{A},\mathbb{C})$ in time
${(|\mathbb{A}|+|\mathbb{C}|)}^{k(\varepsilon)}$, where $k(\varepsilon)$ is a
function depending on $\mathcal{G}$ only.

The algorithm in Theorem 1.2 does nothing more than solve a
$\Theta(k(\varepsilon))$-th level of the Sherali-Adams linear programming
relaxation. This allows the algorithm to be oblivious to the graph structure,
i.e. we do not assume that the fractional-treewidth-fragility of $\mathcal{G}$
can be efficiently certified. Thus the left-hand side restriction on Gaifman
graphs is the most general for which a PTAS is known; as discussed earlier, it
includes excluded-minor classes and more. In fact similarly to [RWŽ21], we
conjecture that $\mbox{Max-Sol}_{\mathcal{G}}$ does not admit a PTAS for any
$\mathcal{G}$ that is not fractionally-treewidth-fragile. Since $\mbox{Max-
Sol}_{\mathcal{G}}$ is strictly more general (by allowing negative infinite
values), this conjecture might be easier to prove than the one in [RWŽ21].

On the other hand, this approach does not give an EPTAS even when $\mathbb{C}$
is fixed (i.e. the exponent of $|\mathbb{A}|$ increases with $\varepsilon$),
and it does not construct an assignment — it only approximates the optimum
value. In contrast, given a class of graphs $\mathcal{G}$ for which
fractional-treewidth-fragility can be efficiently certified (which includes
essentially all known examples), it is straightforward to construct solutions
to $\mbox{Max-Sol}_{\mathcal{G}}$ of value at least
$(1-\varepsilon)\cdot\operatorname{maxval}(\mathbb{A},\mathbb{C})$ in time
$\lvert\mathbb{A}\rvert\cdot{\lvert\mathbb{C}\rvert}^{k(\varepsilon)}$.

We complement Theorem 1.2 with simple constructions which show that it is
impossible to extend other results of [RWŽ21] to the setting of crisp
constraints. In [RWŽ21] the notion of _pliability_ is defined, which is a
left-hand side restriction that takes the whole structure $\mathbb{A}$ into
account, not only its Gaifman graph; this allowed the authors to show that the
same framework applies not only to sparse, fractionally-treewidth-fragile
instances, but also to dense structures. While we define an analogous notion
of _strong pliability_ , in Appendix C we show that even the simplest class of
dense structures, namely the class of $\\{0,1\\}$-valued cliques, does not
satisfy it. In fact, it is easy to show that the Max-Sol problem is hard to
approximate even when the left-hand side structures are restricted to cliques.

##  2 Preliminaries

For an integer $k$, we denote by $[k]$ the set $\\{1,\ldots,k\\}$. For a tuple
$\mathbf{x}$, we denote by $x_{i}$ its $i$-th coordinate and by
$\operatorname{Set}(\mathbf{x})$ the set of elements appearing in
$\mathbf{x}$. For two tuples $\mathbf{x}$ and $\mathbf{y}$ of length $n$, we
write $(\mathbf{x},\mathbf{y})$ as a shorthand for
$((x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{n},y_{n}))$. For a tuple $\mathbf{x}$
of length $n$ and a map $h$, we denote by $h(\mathbf{x})$ the coordinate-wise
application of $h$; i.e., $h(\mathbf{x})=(h(x_{1}),\ldots,h(x_{n}))$.

#### General-valued CSPs

A _signature_ is a finite set $\sigma$ of (function) symbols such as $f$, each
with a specified arity $\operatorname{ar}(f)$. For a set of values
$\Omega\subseteq\mathbb{Q}\cup\\{-\infty,+\infty\\}$, an _$\Omega$ -valued
structure_ $\mathbb{A}$ over a signature $\sigma$ (or $\sigma$-structure, for
short) is a finite domain $A$ together with a function
$f^{\mathbb{A}}:A^{\operatorname{ar}(f)}\to\Omega$ for each symbol
$f\in\sigma$. We denote by $A,B,C,\dots$ the domains of structures
$\mathbb{A},\mathbb{B},\mathbb{C},\dots$.

We define $\operatorname{tup}(\mathbb{A})$ to be the set of all pairs
$(f,\mathbf{x})$ such that $f\in\sigma$ and $\mathbf{x}\in
A^{\operatorname{ar}(f)}$; and $\operatorname{tup}_{>0}(\mathbb{A})$ to be the
set of all pairs $(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A})$ with
$f^{\mathbb{A}}(\mathbf{x})>0$.

We consider the following computational problem.

######  Definition 2.1.

An instance of the _general-valued CSP_ (VCSP) consists of an ordered pair of
$\sigma$-structures $(\mathbb{A},\mathbb{C})$. For a mapping $h\colon A\to C$,
we define the value of $h$ to be

$\displaystyle\operatorname{val}(h)=\sum_{(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A})}f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(h(\mathbf{x})).$

The goal is to find the minimum or maximum value over all possible mappings
$h\colon A\to C$, denoted $\operatorname{minval}(\mathbb{A},\mathbb{C})$ or
$\operatorname{maxval}(\mathbb{A},\mathbb{C})$, respectively.

On the left-hand side we will only use $\mathbb{Q}_{\geq 0}$-valued
structures, with letters $\mathbb{A},\mathbb{B}$; on the right-hand side we
will only use $\mathbb{Q}_{\geq 0}\cup\\{\infty\\}$ or $\mathbb{Q}_{\geq
0}\cup\\{-\infty\\}$-valued structures, respectively, for minimisation and
maximisation, with letters $\mathbb{C},\mathbb{D}$.

For $\lambda\geq 0$ we write $\lambda\mathbb{A}$ for the _rescaled_
$\sigma$-structure with domain $A$ and
$f^{\lambda\mathbb{A}}(\mathbf{x}):=\lambda f^{\mathbb{A}}(\mathbf{x})$, for
$(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A})$. For a $\sigma$-structure
$\mathbb{A}$ and subset of the domain $X\subseteq A$, we define
$\mathbb{A}[X]$ to be the restriction of $\mathbb{A}$ to $X$. That is,
$\mathbb{A}[X]$ is a $\sigma$-structure over the domain $X$, and
$f^{\mathbb{A}[X]}(\mathbf{x})=f^{\mathbb{A}}(\mathbf{x})$ for each
$f\in\sigma$ and $\mathbf{x}\in X^{\operatorname{ar}(f)}$.

Following the influential work on decision CSPs by Grohe, Schwentick, and
Segoufin [GSS01], and Grohe [Gro07], we will focus on fragments of the VCSP
parametrised by the class of left-hand side structures (or their underlying
class of graphs). Given a $\sigma$-structure $\mathbb{A}$, the _Gaifman graph_
(or _primal graph_), denoted by $\operatorname{G}(\mathbb{A})$, is the graph
whose vertex set is the domain $A$, and whose edges are the pairs $\\{u,v\\}$
for which there is a tuple $\mathbf{x}$ and a symbol $f\in\sigma$ such that
$u,v$ appear in $\mathbf{x}$ and $f^{\mathbb{A}}(\mathbf{x})>0$.

For a graph parameter $\operatorname{p}$ and a structure $\mathbb{A}$, we
define
$\operatorname{p}(\mathbb{A})\coloneqq\operatorname{p}(\operatorname{G}(\mathbb{A}))$
to be the parameter of the Gaifman graph of $\mathbb{A}$. In particular, the
_treewidth_ of $\mathbb{A}$ is defined as
$\operatorname{tw}(\mathbb{A})\coloneqq\operatorname{tw}(\operatorname{G}(\mathbb{A}))$.
(We will only use treewidth and excluded minors as black-boxes and thus will
not need their definitions. The reader is referred to Diestel’s textbook for
details [Die10].)

#### Relational structures

A _relational $\sigma$-structure_ $\mathbb{C}$ includes for each symbol
$f\in\sigma$ a relation $f^{\mathbb{C}}\subseteq C^{\operatorname{ar}(f)}$. We
will view relational structures as $\\{0,\infty\\}$-valued structures by
associating each function
$f^{\mathbb{C}}:C^{\operatorname{ar}(f)}\to\\{0,\infty\\}$ to the relation
given by the zero-valued tuples $\\{\mathbf{x}\mid
f^{\mathbb{C}}(\mathbf{x})=0\\}$. A _homomorphism_ from a relational
$\sigma$-structure $\mathbb{C}$ to a relational $\sigma$-structure
$\mathbb{D}$ is a map $\psi:C\to D$ that satisfies, for every $f\in\sigma$ and
every $\mathbf{x}\in C^{\operatorname{ar}(f)}$,
$f^{\mathbb{D}}(\psi(\mathbf{x}))\leq f^{\mathbb{C}}(\mathbf{x})$.

For an $n$-ary function $f$, we denote by $\operatorname{Feas}(f)$ and
$\operatorname{Opt}(f)$ the $n$-ary relations defined by
$\operatorname{Feas}(f)=\\{\mathbf{x}\mid f(\mathbf{x})<\infty\\}$ and
$\operatorname{Opt}(f)=\\{\mathbf{x}\mid f(\mathbf{x})=0\\}$, respectively.
Let $\mathbb{C}$ be a $\sigma$-structure. The relational $\sigma$-structure
$\operatorname{Feas}(\mathbb{C})$ contains, for each $f\in\sigma$, the
relation $\operatorname{Feas}(f^{\mathbb{C}})$; similarly, the relational
$\sigma$-structure $\operatorname{Opt}(\mathbb{C})$ contains, for every
$f\in\sigma$, the relation $\operatorname{Opt}(f^{\mathbb{C}})$.

Our results will be concerned with two particular types of right-hand side
structures.

### Maximum Solution

######  Definition 2.2 ($\sqsubseteq_{c}$).

For an element $c$ of a set $C$, we denote by $\sqsubseteq_{c}$ the partial
ordering on $C$ defined by $c\sqsubseteq_{c}x$ and $x\sqsubseteq_{c}x$ for all
$x\in C$. This induces a partial ordering on $C^{n}$ coordinate-wise: we write
$\mathbf{x}\sqsubseteq_{c}\mathbf{y}$ for $\mathbf{x},\mathbf{y}\in C^{n}$ if
we can obtain $\mathbf{x}$ from $\mathbf{y}$ by changing some (possibly none
or all) of its coordinates to $c$.

######  Definition 2.3 (Max-Sol).

Let $\sigma$ be a finite signature. A $\sigma$-structure $\mathbb{C}$ is
called a _Max-Sol structure_ if it is $(\mathbb{Q}_{\geq
0}\cup\\{-\infty\\})$-valued and there is an element $c_{\bot}\in C$ such that
for all $f\in\sigma$, the following holds: whenever
$f^{\mathbb{C}}(\mathbf{y})\geq 0$, we have $f^{\mathbb{C}}(\mathbf{x})\geq
0$, for all $\mathbf{x}\sqsubseteq_{c_{\bot}}\mathbf{y}$ in
$C^{\operatorname{ar}(f)}$. Equivalently, if a tuple $\mathbf{y}$ has non-
negative value (not $-\infty$), then changing some of its coordinates to
$c_{\bot}$ still gives a non-negative value. To avoid clutter, we write
$\sqsubseteq_{{}_{\bot}}$ in place of $\sqsubseteq_{c_{\bot}}$, with the
choice of $c_{\bot}\in C$ implicit.

We denote by $\mbox{Max-Sol}_{\mathcal{G}}$ the restriction of the VCSP to
instances $(\mathbb{A},\mathbb{C})$ where $\mathbb{A}$ is a $\mathbb{Q}_{\geq
0}$-valued structure with $\operatorname{G}(\mathbb{A})\in\mathcal{G}$ and
$\mathbb{C}$ is a Max-Sol structure.

Observe that every $\mathbb{Q}_{\geq 0}$-valued structure is a Max-Sol
structure; thus $\mbox{Max-Sol}_{\mathcal{G}}$ is more general than the
restriction to $\mathbb{Q}_{\geq 0}$-valued right-hand side structures, which
is the problem considered in [RWŽ21].

######  Remark 2.4.

The “downward monotone Strict-CSP” from [Kum+11] corresponds to Definition 2.3
with some extra conditions. Firstly, there is a special unary symbol
$u\in\sigma$ such that $u^{\mathbb{C}}$ is $\mathbb{Q}_{\geq 0}$ valued and
all other symbols $f\in\sigma$ are $\\{0,-\infty\\}$-valued (hence they
express “strict” constraints). Secondly, there is a total order on $C$, and
for each symbol $f\in\sigma$ other than $u$, $f^{\mathbb{C}}$ is anti-
monotone; in other words, lowering some coordinates of a tuple in
$C^{\operatorname{ar}(f)}$ can not change its value from $0$ to $-\infty$.
(Hence the minimum element plays the role of the bottom label $c_{\bot}\in
C$.)

### Minimum Solution

######  Definition 2.5 (Min-Sol).

Let $\sigma$ be a finite signature. A $\sigma$-structure $\mathbb{C}$ is
called Min-Sol if it is $(\mathbb{Q}_{\geq 0}\cup\\{\infty\\})$-valued and
there is a total order $\leq_{\top}$ on $C$ such that: for all $f\in\sigma$
with $\operatorname{ar}(f)>1$ and all tuples $\mathbf{x},\mathbf{y}\in C^{n}$
with $\mathbf{x}\leq_{\top}\mathbf{y}$ (coordinate-wise) we have:

  * •

$f^{\mathbb{C}}(\mathbf{x})<\infty$ implies
$f^{\mathbb{C}}(\mathbf{y})<\infty$, and

  * •

$f^{\mathbb{C}}(\mathbf{x})=0$ implies $f^{\mathbb{C}}(\mathbf{y})=0$.

We denote by $\mbox{Min-Sol}_{\mathcal{G}}$ the restriction of the VCSP to
instances $(\mathbb{A},\mathbb{C})$ where $\mathbb{A}$ is a $\mathbb{Q}_{\geq
0}$-valued structure with $\operatorname{G}(\mathbb{A})\in\mathcal{G}$ and
$\mathbb{C}$ is a Min-Sol structure.

######  Remark 2.6.

The “upward monotone Strict-CSP” from [Kum+11] correspond to Definition 2.5
with the extra conditions that there is only one unary symbol $u$,
$u^{\mathbb{C}}$ is monotone and injective, and all other cost functions
$f^{\mathbb{C}}$ are $\\{0,\infty\\}$-valued (hence they express “strict”
constraints).

######  Remark 2.7.

We observe that _some_ structure (such as a total order) on the domain of a
right-hand side Min-Sol structure is needed: We show how to encode 3-colouring
of planar graphs, which doesn’t admit a PTAS (assuming P$\neq$NP).

Let $G$ be a planar graph. Let $\mathbb{A}$ be a structure with domain $V(G)$
over the signature $\sigma=\\{u,f\\}$ of of arities 1 and 2 respectively. Let
$u^{\mathbb{A}}(x)=1$ for all $x\in V(G)$, and $f^{\mathbb{A}}(x,y)=1$ if
$\\{x,y\\}\in E(G)$ and $0$ otherwise. Let $\mathbb{C}$ be a right-hand side
structure with domain $C=\\{R,G,B,c_{\top}\\}$. Here we think of $R,G,B$ as
three colours, and $c_{\top}$ as a fourth extra colour we want to avoid using.
We allow a monochromatic $c_{\top}$ edge. Let $u^{\mathbb{C}}(x)=1$ for
$x=c_{\top}$ and $0$ otherwise;
$f^{\mathbb{C}}(R,R)=f^{\mathbb{C}}_{e}(G,G)=f^{\mathbb{C}}_{e}(B,B)=\infty$,
and $0$ for other pairs of values (including $(c_{\top},c_{\top})$). If $G$ is
3-colourable then $\operatorname{minval}(\mathbb{A},\mathbb{C})=0$. Otherwise,
$\operatorname{minval}(\mathbb{A},\mathbb{C})\geq 1$. Note that
$f^{\mathbb{C}}$ respects the partial order $\sqsubseteq_{c_{\top}}$, but it
does not respect any total order on $C$.

##  3 Minimisation on planar structures

###  3.1 Diagonalisability

Briceño, Bulatov, Dalmau, and Larose defined the concepts of product
structure, dismantlability, homomorphisms, adjacency, and link graph for
relational structures [Bri+19]. In this section, we will extend these concepts
to valued structures in a natural way. In particular, our definitions (for
structures) coincide with the definitions in [Bri+19] (for relational
structures) when viewed as $\\{0,\infty\\}$-valued structures.

The intuition is that, given two (valued) $\sigma$-structures $\mathbb{C}$ and
$\mathbb{D}$, we call $\psi:C\to D$ a _homomorphism_ from $\mathbb{C}$ to
$\mathbb{D}$ if $\psi$ is a homomorphism from
$\operatorname{Feas}(\mathbb{C})$ to $\operatorname{Feas}(\mathbb{D})$ and
from $\operatorname{Opt}(\mathbb{C})$ to $\operatorname{Opt}(\mathbb{D})$. It
will be more convenient to consider both the $\operatorname{Feas}(\mathbb{C})$
and $\operatorname{Opt}(\mathbb{C})$ simultaneously. Thus with every structure
$\mathbb{C}$ we will associate a relational structure
$\mathrm{Rel}[\mathbb{C}]$, defined as follows.

######  Definition 3.1.

If $\mathbb{C}$ is a $\sigma$-structure, let
$\sigma^{\prime}=\bigcup_{f\in\sigma}\\{f_{1},f_{2}\\}$ be the signature that
for each $f\in\sigma$ includes the relational symbols $f_{1}$ of $f_{2}$ of
the same arity as $f$. Define the relational $\sigma^{\prime}$-structure
$\mathrm{Rel}[\mathbb{C}]$ over the domain $C$ as follows: for each
$f\in\sigma$, let
$f_{1}^{\mathrm{Rel}[\mathbb{C}]}=\operatorname{Feas}(f^{\mathbb{C}})=\\{\mathbf{x}\mid
f^{\mathbb{C}}(\mathbf{x})<\infty\\}$ and
$f_{2}^{\mathrm{Rel}[\mathbb{C}]}=\operatorname{Opt}(f^{\mathbb{C}})=\\{\mathbf{x}\mid
f^{\mathbb{C}}(\mathbf{x})=0\\}$.

We can now define the concepts of interests for structures $\mathbb{C}$ via
the already existing concepts for relational structures
$\mathrm{Rel}[\mathbb{C}]$ from [Bri+19]. We use the following observation.

######  Observation 3.2.

For $x,y\in\mathbb{Q}_{\geq 0}\cup\\{\infty\\}$, there exists $M>0$ such that
$y\leq M\cdot x$ if and only if:

  * •

if $x<\infty$, then $y<\infty$, and

  * •

if $x=0$, then $y=0$.

Given $\sigma$-structures $\mathbb{C}$ and $\mathbb{D}$, we say that
$\psi:C\to D$ is a _homomorphism_ if $\psi$ is a homomorphism from
$\mathrm{Rel}[\mathbb{C}]$ to $\mathrm{Rel}[\mathbb{D}]$. Equivalently, $\psi$
is a homomorphism if there exists $M>0$ such that for all
$(f,\mathbf{x})\in\operatorname{tup}(\mathbb{C})$,

$f^{\mathbb{D}}(\psi(\mathbf{x}))\leq M\cdot f^{\mathbb{C}}(\mathbf{x}).$

Here we can use a uniform bound $M$ because we only work with finite
structures; it will be convenient to use this equivalent definition to keep
track of the bound $M$.

Given $\sigma$-structures $\mathbb{C}$ and $\mathbb{D}$ we define the _product
structure_ $\mathbb{C}\times\mathbb{D}$ as a $\sigma$-structure with domain
$C\times D$ and for each $f\in\sigma$,

$f^{\mathbb{C}\times\mathbb{D}}((\mathbf{x},\mathbf{y}))=f^{\mathbb{C}}(\mathbf{x})+f^{\mathbb{D}}(\mathbf{y}).$

Let $\pi_{1}(x,y)=x$ and $\pi_{2}(x,y)=y$ be the projections to the first and
second coordinate, respectively. Note that $\pi_{1},\pi_{2}$ are homomorphisms
from $\mathbb{C}^{2}$ to $\mathbb{C}$ for any $\mathbb{C}$.

We say that $a\in C$ is _dominated_ by $b\in C$ if there is an $M>0$ such that
for all $(f,\mathbf{x})\in\operatorname{tup}(\mathbb{C})$ with $x_{i}=a$, we
have

$f^{\mathbb{C}}(x_{1},\dots,x_{i-1},b,x_{i+1},\dots)\leq M\cdot
f^{\mathbb{C}}(\mathbf{x}).$

A sequence of $\sigma$-structures $\mathbb{C}_{0},\dots,\mathbb{C}_{\ell}$ is
a _dismantling sequence_ if there exists $a_{i}\in C_{i}$ such that $a_{i}$ is
dominated in $\mathbb{C}_{i}$, and $\mathbb{C}_{i+1}$ is the substructure of
$\mathbb{C}_{i}$ induced by $C_{i}\setminus\\{a_{i}\\}$, for
$i\in\\{0,\dots,\ell-1\\}$. In this case, we say that $\mathbb{C}_{0}$
dismantles to $\mathbb{C}_{\ell}$. A structure $\mathbb{C}$ is
_diagonalisable_ if $\mathbb{C}^{2}$ dismantles to the substructure induced by
its diagonal $\Delta(C^{2})=\\{(c,c)\mid c\in C\\}$.

Homomorphisms $\psi,\phi$ from $\mathbb{C}$ to $\mathbb{D}$ are _adjacent_ if
there exists $M>0$ such that for all
$(f,\mathbf{x})\in\operatorname{tup}(\mathbb{C})$ and $\mathbf{y}\in
D^{\operatorname{ar}(f)}$ with $y_{i}\in\\{\psi(x_{i}),\phi(x_{i})\\}$, we
have

$f^{\mathbb{D}}(\mathbf{y})\leq M\cdot f^{\mathbb{C}}(\mathbf{x}).$ (1)

Thus $a$ dominated by $b$ in $\mathbb{C}$ if and only if the function $s\colon
C\to C\setminus\\{a\\}$ that maps $a$ to $b$ and everything else identically
is a homomorphism from $\mathbb{C}$ to $\mathbb{C}$, and $s$ is adjacent to
the identity homomorphism. (This is stronger than just $s$ being a
homomorphism, since $f^{\mathbb{C}}(a,a,a)=0$ implies not only
$f^{\mathbb{C}}(b,b,b)=0$, but also $f^{\mathbb{C}}(a,a,b)=0$, for example).
Note that adjacency is not a transitive property.

Finally, for $\sigma$-structures $\mathbb{C}$ and $\mathbb{D}$, we define the
_link graph_ $L(\mathbb{C},\mathbb{D})$ to be the simple graph whose vertices
are the homomorphisms from $\mathbb{C}$ to $\mathbb{D}$, with edges between
adjacent homomorphisms.

The following theorem was proved in [Bri+19, Theorem 3.6] for relational
structures but the result easily extends to structures.

######  Theorem 3.3.

Let $\mathbb{C}$ be a $\sigma$-structure. Then, the following are equivalent.

  * •

$\mathbb{C}$ is diagonalisable;

  * •

$\pi_{1}$ and $\pi_{2}$ are connected in $L(\mathbb{C}^{2},\mathbb{C})$ by a
path of adjacent idempotent homomorphisms.
(We say a function $\psi:C^{2}\to C$ is idempotent if $\psi(c,c)=c$ for all
$c\in C$.)

###### Proof.

This follows from the fact that
$\mathrm{Rel}[\mathbb{C}^{2}]=\mathrm{Rel}[\mathbb{C}]^{2}$ and that our
definitions are the same as those of [Bri+19, Theorem 3.6] applied to
$\mathbb{H}=\mathbb{C}$ and $J=\Delta(C)$. Specifically a function $\phi:C\to
C$ is a homomorphism $\mathbb{C}\to\mathbb{C}$ if and only if it is a
homomorphism $\mathrm{Rel}[\mathbb{C}]\to\mathrm{Rel}[\mathbb{C}]$. Similarly,
$a$ is dominated by $b$ in $\mathbb{C}^{2}$ if and only if $a$ is dominated by
$b$ in $\mathrm{Rel}[\mathbb{C}^{2}]=\mathrm{Rel}[\mathbb{C}]^{2}$. Thus
$\mathbb{C}$ is diagonalisable if and only if $\mathrm{Rel}[\mathbb{C}]^{2}$
dismantles to its full diagonal (not just any subset of it). Further
$\phi,\psi:C\to C$ are adjacent homomorphisms from $\mathbb{C}$ to
$\mathbb{C}$ if and only if they are adjacent homomorphisms from
$\mathrm{Rel}[\mathbb{C}]$ to $\mathrm{Rel}[\mathbb{C}]$. Finally,
$\pi_{1},\pi_{2}$ are connected by a path of adjacent idempotent homomorphisms
if and only if they are $J$-connected by any homomorphisms in
$L(\mathrm{Rel}[\mathbb{C}]^{2},\mathbb{C})$ in the sense of [Bri+19]. ∎

We now show that diagonalisability is more general than the Min-Sol condition.

######  Lemma 3.4.

Let $\mathbb{C}$ be a Min-Sol structure. Then $\mathbb{C}$ is diagonalisable.
Moreover, there is a path on 3 vertices between $\pi_{1}$ and $\pi_{2}$ in
$L(\mathbb{C}^{2},\mathbb{C})$.

###### Proof.

Define $\phi:C^{2}\to\Delta(C^{2})$ by $\phi(x,y)=(\max(x,y),\max(x,y))$,
where $\max$ is with respect to the total order on $C$. We claim for each
$(x,y)\in C^{2}$, $a\coloneqq(x,y)$ is dominated by $b\coloneqq\phi(x,y)$.
Indeed, for each
$(f,(\mathbf{x},\mathbf{y}))\in\operatorname{tup}(\mathbb{C}^{2})$ with
$(x_{i},y_{i})=a$ and $n\coloneqq\operatorname{ar}(f)>1$, we have

$\displaystyle
f^{\mathbb{C}^{2}}\left((x_{1},y_{1}),\dots,(b,b),\dots,(x_{n},y_{n})\right)$
$\displaystyle={}$ $\displaystyle
f^{\mathbb{C}}(x_{1},\dots,\max(x_{i},y_{i}),\dots,x_{n})+f^{\mathbb{C}}(y_{1},\dots,\max(x_{i},y_{i}),\dots,y_{n})$
$\displaystyle\leq{}$ $\displaystyle M\cdot
f^{\mathbb{C}}(x_{1},\dots,x_{i},\dots,x_{n})+M\cdot
f^{\mathbb{C}}(y_{1},\dots,y_{i},\dots,y_{n})$ $\displaystyle={}$
$\displaystyle M\cdot f^{\mathbb{C}^{2}}\left((\mathbf{x},\mathbf{y})\right),$

for some $M>0$, where the inequality follows from the assumption that
$\mathbb{C}$ is a Min-Sol structure. For $f\in\sigma$ with
$\operatorname{ar}(f)=1$, we have that $a$ dominates $b$ because with $M\geq
2$ we always have

$f^{\mathbb{C}^{2}}(b)=f^{\mathbb{C}}(\max(x,y))+f^{\mathbb{C}}(\max(x,y))\leq
M\cdot(f^{\mathbb{C}}(x)+f^{\mathbb{C}}(y))=M\cdot f^{\mathbb{C}^{2}}(a).$

Therefore, we can dismantle the non-diagonal elements $(x,y)$ in any order to
obtain a dismantling sequence from $\mathbb{C}^{2}$ to the substructure
induced by $\Delta(C^{2})$.

Let $\mu:C^{2}\to C$ be defined by $\mu(x,y)=\max(x,y)$, where $\max$ is with
respect to the total order defined on $C$. Then similarly as above, one can
check $\pi_{1},\mu,\pi_{2}$ is a path in $L(\mathbb{C}^{2},\mathbb{C})$. ∎

We remark that [Bri+19] show many other equivalent formulations, including a
property known as _finite duality_. They also discuss how finite duality
allows to efficiently solve many problems such as homomorphism extensions.
However, in our setting it is $\mathrm{Rel}[\mathbb{C}]$ rather than
$\mathbb{C}$ that is restricted, so such a property would not take finite,
positive values of $\mathbb{C}$ into account.

Instead, our approach is based on Baker’s technique: we partition graph into
breadth-first-search layers and use the fact that the problem can be solved
exactly on a subgraph induced by a few consecutive layers. To merge such
solutions into one, we use a small number of overlapping layers and use the
path between projections $\pi_{1},\pi_{2}$ given by Theorem 3.3 to “blend in”
two solutions. By increasing the number of exactly solved, non-overlapping
layers, we can reduce any loss due to differences between finite, positive
values.

###  3.2 PTAS

Baker’s approach relies on the following structural property of planar graphs,
which is e.g. a direct consequence of [Bod98, Theorem 83].

######  Lemma 3.5.

Let $G$ be a planar graph and $v_{0}\in V(G)$ an arbitrary vertex. Let $L_{i}$
be the set of vertices at distance exactly $i$ from $v_{0}$ (i.e. the $i$th
layer of a BFS from $v_{0}$). Then, the subgraph induced by any $t$
consecutive layers $G[L_{i}\cup L_{i+1}\cup\dots\cup L_{i+t+1}]$ has treewidth
at most $3t$.

######  Theorem 3.6.

Let $\mathcal{P}$ be the class of planar graphs. Then, for any $\varepsilon>0$
and any VCSP instance $(\mathbb{A},\mathbb{C})$ with
$\operatorname{G}(\mathbb{A})\in\mathcal{P}$ and $\mathbb{C}$ diagonalisable,
we can find a solution of value at most
$(1+\varepsilon)\operatorname{minval}(\mathbb{A},\mathbb{C})$ in time
$\lvert\mathbb{A}\rvert\cdot c^{1/\varepsilon}$ where $c$ depends on
$\mathbb{C}$ only.

###### Proof.

Let $(\mathbb{A},\mathbb{C})$ be a VCSP instance as per the theorem.
Generally, for any left-hand side structure $\mathbb{B}$, we will write
$\operatorname{val}_{\mathbb{B}}(h)$ for the value of an assignment $h:B\to C$
with respect to the instance $(\mathbb{B},\mathbb{C})$, and write
$\operatorname{val}(\cdot)$ for $\operatorname{val}_{\mathbb{A}}(\cdot)$ by
default.

By Theorem 3.3 there is a sequence of adjacent homomorphisms
$\psi_{1},\dots,\psi_{\ell}$ from $\mathbb{C}^{2}$ to $\mathbb{C}$ such that
$\psi_{1}=\pi_{1}$ and $\psi_{\ell}=\pi_{2}$. Let $M\geq 1$ be sufficiently
large such that 1 holds for all adjacent homomorphisms $\psi_{i}$ and
$\psi_{i+1}$, $i\in\\{1,\dots,\ell-1\\}$. Let
$k\coloneqq\lceil\frac{2M}{\varepsilon}\rceil$.

Let $\mathbb{A}$ let be a $\mathbb{Q}_{\geq 0}$-valued structure and let
$G=\operatorname{G}(\mathbb{A})\in\mathcal{P}$ be its Gaifman graph. Fix an
arbitrary vertex $v_{0}\in A$ in $\operatorname{G}(\mathbb{A})$. For
$n\in\mathbb{Z}$, let $L_{n}\subseteq A$ be the set of vertices whose distance
from $v_{0}$ is in $\\{n\ell+1,\dots,n\ell+\ell\\}$. So $L_{n}$ are intervals
of $\ell$ layers, which partition the vertex set $A$. For each
$j\in\mathbb{Z}$ and $i\in[k]$ let

$B_{j}^{i}\coloneqq L_{jk-i}\cup\dots\cup L_{jk-i+k},$

so that $B_{j}^{i}$ is a block of $(k+1)\cdot\ell$ consecutive layers.
Iterating through the indices $j$ gives consecutive blocks that overlap on
$\ell$ layers; the index $i$ shifts which layers are in the overlap. That is,

$B_{j}^{i}\cap B_{j+1}^{i}=L_{(j+1)k-i}.$

Define the overlaps $O^{i}=\bigcup_{j}B_{j}^{i}\cap B_{j+1}^{i}$ for
$i\in[k]$. We note that the $O^{1},\dots,O^{k}$ are disjoint. Consider an
optimal solution $h^{*}:A\to C$ for the VCSP instance
$(\mathbb{A},\mathbb{C})$. As the $O^{i}$ are all disjoint, there exists
${i^{*}}\in[k]$ with

$\operatorname{val}_{\mathbb{A}[O^{i^{*}}]}({\left.\kern-1.2pth^{*}\right|_{O^{i^{*}}}})\leq\frac{1}{k}\operatorname{val}(h^{*})\leq\frac{\varepsilon}{2M}\operatorname{val}(h^{*}).$

We henceforth write $B_{j}=B_{j}^{i^{*}}$ and $O=O^{i^{*}}$. Note that, just
as in Baker’s original approach, the choice of ${i^{*}}$ is not available to
the algorithm, as we do not know $h^{*}$. However, as the number of choices
for $i\in[k]$ is linear in $1/\varepsilon$, we can proceed with each possible
$i$, construct the solution $h^{\prime}$ as discussed below and output the one
with the lowest value $\operatorname{val}(h^{\prime})$.

Let $\mathbb{A}^{+}$ be a $\sigma$-structure with domain $A$ defined by

$f^{\mathbb{A}^{+}}(\mathbf{x})=\begin{cases}M\cdot
f^{\mathbb{A}}(\mathbf{x})&\text{if $\operatorname{Set}(\mathbf{x})\subseteq
O$}\\\ f^{\mathbb{A}}(\mathbf{x})&\text{otherwise},\end{cases}$

so that tuples which lie within $O$ are amplified by a factor of $M$.

For each $j$, the Gaifman graph $\operatorname{G}(\mathbb{A}^{+}[B_{j}])$ has
treewidth at most
$\mathcal{O}\left\lparen(k+1)\ell\right\rparen=\mathcal{O}\left\lparen
M\ell/\varepsilon\right\rparen$ by Lemma 3.5. Thus for each $j$, we can find a
treewidth decomposition [Bod93] and compute an optimal solution $h_{j}$ to
$(\mathbb{A}^{+}[B_{j}],\mathbb{C})$ in total time
$\lvert\mathbb{A}\rvert\cdot{\lvert\mathbb{C}\rvert}^{\mathcal{O}\left\lparen
M\ell/\varepsilon\right\rparen}$ via standard dynamic programming. Then by
optimality of $h_{j}$,

$\operatorname{val}_{\mathbb{A}^{+}[B_{j}]}(h_{j})\leq\operatorname{val}_{\mathbb{A}^{+}[B_{j}]}({\left.\kern-1.2pth^{*}\right|_{B_{j}}}).$

Therefore, summing over all $j$, we count the contribution of every constraint
once, except for constraints whose scope is contained in $O$ (and thus in
exactly two sets $B_{j}$), which are counted $2M$ times in total:

$\begin{split}\sum_{j}\operatorname{val}_{\mathbb{A}^{+}[B_{j}]}(h_{j})&\
\leq\
\sum_{j}\operatorname{val}_{\mathbb{A}^{+}[B_{j}]}({\left.\kern-1.2pth^{*}\right|_{B_{j}}})\\\
&\ =\
\operatorname{val}_{\mathbb{A}}(h^{*})+(2M-1)\cdot\operatorname{val}_{\mathbb{A}[O]}({\left.\kern-1.2pth^{*}\right|_{O}})\
\leq\ (1+\varepsilon)\operatorname{val}(h^{*}).\end{split}$ (2)

Observe that for each $x\in A$, either $x\not\in O$ and there is a unique $j$
for which $x\in B_{j}$, or $x\in O$ and there is a unique $j$ for which $x\in
B_{j}\cap B_{j+1}$. In the latter case, $x\in L_{(j+1)k-{i^{*}}}$ and we let
$s\in[\ell]$ denote the unique $s$ for which $x$ is at distance exactly
$((j+1)k-{i^{*}})\ell+s$ from $v_{0}$. Let $h^{\prime}:A\to C$ be defined as
follows

$h^{\prime}(x)=\begin{cases}h_{j}(x)&\qquad\text{if $x\in B_{j}$ for a unique
$j$}\\\ \psi_{s}\big{(}h_{j}(x),h_{j+1}(x)\big{)}&\qquad\text{if $x\in
B_{j}\cap B_{j+1}$ and $d(x,v_{0})=((j+1)k-{i^{*}})\ell+s$.}\end{cases}$

We claim that $h^{\prime}$ is a solution to $(\mathbb{A},\mathbb{C})$ with
$\operatorname{val}(h^{\prime})\leq(1+\varepsilon)\operatorname{minval}(\mathbb{A},\mathbb{C})$.
Let $(f,\mathbf{x})\in\operatorname{tup}_{>0}(\mathbb{A})$. Note that by
definition of the Gaifman graph $\operatorname{G}(\mathbb{A})$, all $x_{i}$
are adjacent to each other, so $\operatorname{Set}(\mathbf{x})$ is contained
in one or two consecutive layers. Consider the following two cases.

  1. 1.

If $\operatorname{Set}(\mathbf{x})\not\subseteq O$, then there is a unique $j$
such that $\operatorname{Set}(\mathbf{x})\subseteq B_{j}$, and so
$h^{\prime}(x_{i})=h_{j}(x_{i})$ for each $i$, because either: $x_{i}\not\in
O$ and so $h^{\prime}(x_{i})=h_{j}(x_{i})$ by definition of $h^{\prime}$, or
$x_{i}$ is in the last layer of $B_{j-1}\cap B_{j}$ and
$h^{\prime}(x)=\psi_{\ell}\big{(}h_{j-1}(x),h_{j}(x)\big{)}=\pi_{2}\big{(}h_{j-1}(x),h_{j}(x)\big{)}=h_{j}(x)$,
or analogously $x_{i}$ is in the first layer of $B_{j}\cap B_{j+1}$ and
$\psi_{1}=\pi_{1}$. Thus

$f^{\mathbb{C}}(h^{\prime}(\mathbf{x}))=f^{\mathbb{C}}(h_{j}(\mathbf{x})).$
(3)

  2. 2.

Else, if $\operatorname{Set}(\mathbf{x})\subseteq O$, then there is a unique
$j$ such that $\operatorname{Set}(\mathbf{x})\subseteq B_{j}\cap
B_{j+1}=L_{(j+1)k-{i^{*}}}$. Since $\operatorname{Set}(\mathbf{x})$ is
contained in two consecutive layers, there is some $s$ such that all vertices
in $\operatorname{Set}(\mathbf{x})$ are at distance $((j+1)k-{i^{*}})\ell+s$
or $((j+1)k-{i^{*}})\ell+s+1$ from $v_{0}$. Thus

$h(x_{i})\in\left\\{\psi_{s}\big{(}h_{j}(x_{i}),h_{j+1}(x_{i})\big{)},\,\psi_{s+1}\big{(}h_{j}(x_{i}),h_{j+1}(x_{i})\big{)}\right\\}$

for each $x_{i}$. Finally, as $\psi_{s}$ and $\psi_{s+1}$ are adjacent

$f^{\mathbb{C}}(h(\mathbf{x}))\leq M\cdot
f^{\mathbb{C}^{2}}\big{(}h_{j}(\mathbf{x}),h_{j+1}(\mathbf{x})\big{)}=M\cdot\left(f^{\mathbb{C}}\big{(}h_{j}(\mathbf{x}))+f^{\mathbb{C}}(h_{j+1}(\mathbf{x})\big{)}\right).$
(4)

Thus, by 3, 4 and 2,

$\displaystyle\operatorname{val}_{\mathbb{A}}(h^{\prime})\leq\sum_{j}\operatorname{val}_{\mathbb{A}^{+}[B_{j}]}(h_{j})\leq(1+\varepsilon)\operatorname{val}(h^{*})=(1+\varepsilon)\operatorname{minval}(\mathbb{A},\mathbb{C}),$

and so $h^{\prime}$ is the solution we seek. ∎

######  Remark 3.7.

In Theorem 3.6 it would be sufficient to require that $\mathbb{C}^{2}$
dismantles to any substructure of its diagonal, as opposed to its full
diagonal (as in the definition of diagonalisability). By [Bri+19, Theorem 3.6]
(extended as in Theorem 3.3) this is equivalent to saying that $\mathbb{C}$
dismantles to a substructure $\mathbb{I}$ such that $\mathbb{I}$ is
diagonalisable.

In this case, $\pi_{1}$ and $\pi_{2}$ are still connected in
$L(\mathbb{C}^{2},\mathbb{C})$, but the homomorphisms in the path connecting
them will not be necessarily idempotent. However, the above proof (for the
case of planar graphs) did not rely on this property. This is in contrast with
Theorem 1.1 (for Baker classes) where we actually use the fact that the
homomorphisms are idempotent.

Since a Min-Sol structure $\mathbb{C}$ is diagonalisable by Lemma 3.4, we have
the following corollary.

######  Corollary 3.8.

Let $\mathcal{P}$ be the class of planar graphs. Given any $\varepsilon>0$ and
instance $(\mathbb{A},\mathbb{C})$ of $\mbox{Min-Sol}_{\mathcal{P}}$, we can
find a solution of value at most
$(1+\varepsilon)\operatorname{minval}(\mathbb{A},\mathbb{C})$ in time
$\lvert\mathbb{A}\rvert\cdot c^{1/\varepsilon}$, where $c$ depends on
$\mathbb{C}$ only.

We remark the proof yields
$c^{1/\varepsilon}={\lvert\mathbb{C}\rvert}^{\mathcal{O}\left\lparen
M\ell/\varepsilon\right\rparen}$, and for Min-Sol structures Lemma 3.4 yields
$\ell=3$; hence when the bound $M$ is a constant (e.g. for
$\\{0,1,\infty\\}$-valued Min-Sol structures) the dependency on $\mathbb{C}$
is simply ${\lvert\mathbb{C}\rvert}^{\mathcal{O}\left\lparen
1/\varepsilon\right\rparen}$.

##  4 Minimisation on Baker classes

###  4.1 Definition of Baker classes

A _layering_ of a graph $G$ is a function $\lambda\colon V(G)\to\mathbb{Z}$
such that $|\lambda(u)-\lambda(v)|\leq 1$ for adjacent vertices $u,v$ in $G$.
That is, vertices of $G$ are partitioned into _layers_ $\lambda^{-1}(i)$ for
$i\in\mathbb{Z}$ and edges only go within one layer or between two consecutive
layers.

Baker’s technique [Bak94] relies on a layering of planar graphs such that the
subgraph induced by $\lambda^{-1}(I)$, for any interval $I$ (a set of a few
consecutive integers), has bounded treewidth (the bound depending only on
$|I|$), as formally stated in Lemma 3.5. As one might imagine, this can be
iterated: it would suffice that the subgraph induced by $\lambda^{-1}(I)$
itself has such a “bounded treewidth layering”. Consider now the class of
graphs obtained from planar graphs by adding a single vertex, adjacent to all
the others; then a layering can only have three non-empty layers;
nevertheless, an algorithm can easily circumvent this by guessing the
assignment to the single new vertex (i.e. iterating through all
possibilities).

Dvořák [Dvo20] defined a _Baker class_ as any class of graphs that can be
dealt with in the above ways. Informally, a class of graphs is Baker if any
graph in the class can be reduced to an empty graph by a bounded number of
operations: either removing a single vertex, or selecting some layering
$\lambda$ and continuing separately with every interval in that layering (each
subgraph induced by $\lambda^{-1}(I)$ for intervals $I$ of at most some size).
It turns out the notion of treewidth is not necessary here, as graphs of
bounded treewidth also form a Baker class.

Before we state the definition formally, let us make a few remarks. The idea
of iteratively going through “some layering” and then into “every interval” is
conveniently phrased as a strategy winning a game (this will be particularly
useful when we will want to state an assumption that the choices, including
layerings, can be constructed efficiently). Dvořák’s definition considers
graphs with a total ordering of their vertex set. Roughly speaking, this is to
restrict the definition to “monotone” strategies, where the single vertices to
be deleted are decided upfront — this restriction won’t be important for us,
but we will state it as in [Dvo20] (let us also remark that layerings are not
restricted by the ordering). Finally, the definition is made a bit complicated
by the fact that the number of consecutive layers we may need to include in an
interval may depend on how deep we go (how many iterations of the game are
done). This dependency is formalised as a function $r$ below: for a fixed
problem and approximation ratio the reader should think of some arbitrarily
quickly increasing function $r\colon\mathbb{N}\to\mathbb{N}$. We now proceed
with the formal definition.

######  Definition 4.1.

For a graph $G$ and a function $r\colon\mathbb{N}\to\mathbb{N}$, the _Baker
game_ on $(G,r)$ is defined as follows, for two players I and II. Player I
starts by selecting a total ordering of $V(G)$. A state of the game is a pair
$(G^{\prime},t)$ where $G^{\prime}$ is an induced subgraph of $G$ (with its
ordering inherited from $G$) and $t$ is an integer describing how many rounds
have passed. The initial state is $(G,0)$ and Player I wins in $t$ rounds if
the state $(\emptyset,t)$ is reached, for any $t$. Otherwise, in state
$(G^{\prime},t)$, Player I chooses one of the following actions:

  * •

delete the first vertex $v$ of $G^{\prime}$, according to the ordering; Player
II then takes no action and the game continues in state $(G^{\prime}-v,t+1)$;

  * •

select a layering $\lambda$ of $G^{\prime}$; Player II then selects an
interval $I$ of at most $r(t)$ (and no more than $|V(G)|$) consecutive
integers and the game continues in state $(G^{\prime}[\lambda^{-1}(I)],t+1)$.

We say a function $f\colon\mathbb{N}\to\mathbb{N}$ is _sub-additive_ if
$f(x)+f(y)\leq f(x+y)$.

######  Definition 4.2.

For sub-additive functions $f_{1},f_{2}\colon\mathbb{N}\to\mathbb{N}$, we say
a class of graphs $\mathcal{G}$ is _( $f_{1},f_{2}$)-efficiently Baker_ if for
every function $r\colon\mathbb{N}\to\mathbb{N}$ there exists an integer
$t_{\max}$ and an algorithm such that: for all $G\in\mathcal{G}$, the
algorithm wins as Player I in the Baker game on $(G,r)$ in at most $t_{\max}$
rounds, using time $f_{1}(\lvert G\rvert)$ to compute the initial ordering and
using time $f_{2}(\lvert G\rvert)$ to determine the action at each state of
the game.

As discussed in the introduction, efficiently Baker classes generalise
excluded-minor classes.

######  Theorem 4.3 (Dvořák [Dvo20, Theorem 2.1]).

Let $\mathcal{G}$ be a class of graphs that excludes a minor. Then
$\mathcal{G}$ is $(\mathcal{O}\left\lparen
n^{2}\right\rparen,\mathcal{O}\left\lparen n\right\rparen)$-efficiently Baker.

###  4.2 PTAS

The proof for Baker classes largely follows the proof for planar graphs. To
main difference is that in order to handle exceptional vertices (also known as
“apex” vertices) we will need to guess and fix a partial assignment $\rho$ on
them. When “blending in” two assignments $h_{j}(x)$ and $h_{j+1}(x)$ to some
variable $x$ into a single assignment
$\psi_{s}\big{(}h_{j}(x),h_{j+1}(x)\big{)}$, we will need to preserve the
partial assignment $\rho$, if it is defined on $x$. This is why we need the
homomorphisms $\psi_{s}:\mathbb{C}^{2}\to\mathbb{C}$ to be idempotent, so that
$\psi_{s}(\rho(x),\rho(x))=\rho(x)$.

######  Theorem (Theorem 1.1 restated).

Let $\mathcal{G}$ be an $(f_{1},f_{2})$-efficiently Baker class. Then, for any
$\varepsilon>0$ and any instance $(\mathbb{A},\mathbb{C})$ of general-valued
CSP where $\mathbb{A}$ is a $\mathbb{Q}_{\geq 0}$-valued structured with
$\operatorname{G}(\mathbb{A})\in\mathcal{G}$ and $\mathbb{C}$ is
diagonalisable, we can find a solution of value at most
$(1+\varepsilon)\operatorname{minval}(\mathbb{A},\mathbb{C})$ in time
$f_{1}(\lvert\mathbb{A}\rvert)+f_{2}(c\lvert\mathbb{A}\rvert)\cdot
c^{1/\varepsilon}$ where $c$ depends on $\mathbb{C}$ and $\mathcal{G}$ only.

###### Proof.

For a structure $\mathbb{A}$ and an induced subgraph $G^{\prime}$ of
$\operatorname{G}(\mathbb{A})$, we write $\mathbb{A}[G^{\prime}]$ as a
shorthand for the induced substructure $\mathbb{A}[V(G^{\prime})]$ of
$\mathbb{A}$.

Since $\mathbb{C}$ is diagonalisable, there is a sequence
$\psi_{1},\dots,\psi_{\ell}$ of adjacent idempotent homomorphisms
$\mathbb{C}\to\mathbb{C}$ from $\psi_{1}=\pi_{1}$ to $\psi_{\ell}=\pi_{2}$.
Let $M$ be sufficiently large such that 1 holds for all adjacent homomorphisms
$\psi_{i}$ and $\psi_{i+1}$. For $\varepsilon>0$, define $r(t)\coloneqq
2M\ell\cdot\lceil\frac{1}{\varepsilon}\rceil\cdot 2^{t}$. Let $\mathtt{Algo}$
be the algorithm certifying that $\mathcal{G}$ is efficiently Baker and let
$t_{\max}$ be the integer that is guaranteed to exists for $r$. Our algorithm
starts by using $\mathtt{Algo}$ to compute the vertex ordering of
$\operatorname{G}(\mathbb{A})$.

We then proceed with a recursive procedure. The input of the procedure
consists of an instance $\mathbb{A}^{\prime}$, a partial assignment $\rho$
from at most $t_{\max}$ elements $\operatorname{dom}(\rho)$ in
$\mathbb{A}^{\prime}$ to $\mathbb{C}$, and a state $(G^{\prime},t)$ of the
Baker game where $G^{\prime}$ is equal to the Gaifman graph of
$\mathbb{A}^{\prime}\setminus\operatorname{dom}(\rho)$. We describe the
procedure and claim inductively that it computes a solution of value at most
$e^{\varepsilon/2^{t}}$ times the optimum (among all total assignments that
agree with $\rho$ on $\operatorname{dom}(\rho)$). Moreover, we claim the
procedure finishes in time at most ${(2|C|\cdot
M\cdot\lceil\frac{1}{\varepsilon}\rceil\cdot 2^{t_{\max}})}^{t_{\max}}\cdot
f_{2}(\lvert G^{\prime}\rvert\cdot 2^{t_{\max}})$. Starting the recursive
procedure with the instance $\mathbb{A}$, the state
$(\operatorname{G}(\mathbb{A}),0)$, and empty $\rho$, this will conclude the
proof.

Let $\operatorname{val}(\rho)$ be the value of constraints fully contained in
$\operatorname{dom}(\rho)$:

$\operatorname{val}(\rho)\coloneqq\sum_{\begin{subarray}{c}(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A})\\\
\operatorname{Set}(\mathbf{x})\subseteq\operatorname{dom}(\rho)\end{subarray}}f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(\rho(\mathbf{x})).$

Since all the assignment we consider will agree with $\rho$,
$\operatorname{val}(\rho)$ will be a common part of all of them. We will not
include it in the approximation we inductively claim to get; that is, we claim
the recursive procedure will output an assignment $h$ from
$\mathbb{A}^{\prime}$ to $\mathbb{C}$ such that

$\operatorname{val}^{\rho}(h)\leq
e^{\varepsilon/2^{t}}\cdot\operatorname{val}^{\rho}(h^{*}),$

where $\operatorname{val}^{\rho}(h)$ is a shorthand notation for
$\operatorname{val}(h)-\operatorname{val}(\rho)$ and $h^{*}$ is an optimal
solution, among solutions that agree with $\rho$ on
$\operatorname{dom}(\rho)$.

In state $(\emptyset,t)$ for any $t$, our algorithm outputs the assignment
$\rho$, which is a total assignment since
$\mathbb{A}^{\prime}\setminus\operatorname{dom}(\rho)$ is empty. It is
trivially optimal (among assignments that agree with $\rho$).

In state $(G^{\prime},t)$, if $\mathtt{Algo}$ selects to delete the minimum
vertex $v$ of $G^{\prime}$, we consider each possible assignment to $v$ in
$C$, and recursively call the procedure with the state $(G^{\prime}-v,t+1)$,
the instance $\mathbb{A}^{\prime}$, and the assignment $\rho$ extended to $v$.
We output the best solution found this way: since we consider all possible
assignments, we get a solution as close to optimum as guaranteed inductively
for $t+1$. In the final running time, the branching over all assignments to
$v$ in $C$ will contribute at most a factor of $|C|^{t_{\max}}$.

If $\mathtt{Algo}$ selects a layering $\lambda$ of $G^{\prime}$, we consider
each possible shift index $i\in[k]$, where
$k\coloneqq(2M-1)\cdot\lceil\frac{1}{\varepsilon}\rceil\cdot 2^{t}$. This
branching will contribute to the final running time a factor of at most
${(2M\cdot\lceil\frac{1}{\varepsilon}\rceil\cdot 2^{t_{\max}})}^{t_{\max}}$.
For $n\in\mathbb{Z}$, let

$L_{n}\coloneqq\\{n\ell+1,\dots,n\ell+\ell\\},$

so $L_{n}$ are intervals of length $\ell$ which partition $\mathbb{Z}$;

$B^{i}_{j}\coloneqq L_{jk-i}\cup\dots\cup L_{jk-i+k},$

so $B^{i}_{j}$ consists of $k+1$ such intervals, of which the last one
overlaps with $B^{i}_{j+1}$;

$O^{i}\coloneqq\bigcup_{j}B^{i}_{j}\cap B^{i}_{j+1}=\bigcup_{j}L_{(j+1)k-i},$

so $O^{i}$ are disjoint for different $i\in[k]$. Note that we chose $r(t)$ to
satisfy $|B_{j}|=(k+1)\ell\leq r(t)$.

For a subset of integers $I$ (such as $B^{i}_{j}$ or $O^{i}$) we henceforth
abuse notation and write $\mathbb{A}^{\prime}[I]$ as a shorthand for
$\mathbb{A}^{\prime}[\lambda^{-1}(I)\cup\operatorname{dom}(\rho)]$ and
${\left.\kern-1.2pth\right|_{I}}$ as a shorthand for
${\left.\kern-1.2pth\right|_{\lambda^{-1}(I)\cup\operatorname{dom}(\rho)}}$.

Let $h^{*}$ be an optimal solution to $(\mathbb{A}^{\prime},\mathbb{C})$ that
agrees with $\rho$. Since $O^{i}$ are disjoint for different $i\in[k]$, so are
the constraints of $\mathbb{A}^{\prime}[O^{i}]$ (i.e. those contained in
$\lambda^{-1}(O^{i})\cup\operatorname{dom}(\rho)$), except for those fully
contained in $\operatorname{dom}(\rho)$ (and accounted for in
$\operatorname{val}(\rho)$). This implies there exists a shift index
${i^{*}}\in[k]$ such that

$\operatorname{val}^{\rho}_{\mathbb{A}^{\prime}[O^{i^{*}}]}({\left.\kern-1.2pth^{*}\right|_{O^{i^{*}}}})\
\leq\ \frac{1}{k}\operatorname{val}^{\rho}_{\mathbb{A}^{\prime}}(h^{*}).$

We henceforth only consider the recursion branch where this holds and skip the
superscript ${i^{*}}$.

Let $\mathbb{A}^{+}$ be a $\sigma$-structure with the same domain as
$\mathbb{A}^{\prime}$, defined by

$f^{\mathbb{A}^{+}}(\mathbf{x})=\begin{cases}M\cdot
f^{\mathbb{A}^{\prime}}(\mathbf{x})&\text{if
$\operatorname{Set}(\mathbf{x})\subseteq\lambda^{-1}(O)\cup\operatorname{dom}(\rho)$}\\\
f^{\mathbb{A}^{\prime}}(\mathbf{x})&\text{otherwise},\end{cases}$

so that tuples which lie within $\lambda^{-1}(O)\cup\operatorname{dom}(\rho)$
are amplified by a factor of $M$.

For each $j$, we recurse into state $(G^{\prime}[\lambda^{-1}(B_{j})],t+1)$
computing solutions $h_{j}$ to $(\mathbb{A}^{+}[B_{j}],\mathbb{C})$ which
agree with $\rho$ and which by inductive assumption are almost optimal:

$\operatorname{val}^{\rho}_{\mathbb{A}^{+}[B_{j}]}(h_{j})\leq
e^{\varepsilon/2^{t+1}}\cdot\operatorname{val}^{\rho}_{\mathbb{A}^{+}[B_{j}]}({\left.\kern-1.2pth^{*}\right|_{B_{j}}}).$

Therefore, summing over $j$ we get (by observing that every constraint is
either fully contained in $\operatorname{dom}(\rho)$, or contained in
$\mathbb{A}^{+}[B_{j}]$ for exactly one $j$, or contained in
$\mathbb{A}^{+}[O]$)

$\displaystyle\sum_{j}\operatorname{val}^{\rho}_{\mathbb{A}^{+}[B_{j}]}(h_{j})$
$\displaystyle\leq
e^{\varepsilon/2^{t+1}}\cdot\sum_{j}\operatorname{val}^{\rho}_{\mathbb{A}^{+}[B_{j}]}({\left.\kern-1.2pth^{*}\right|_{B_{j}}})$
$\displaystyle=e^{\varepsilon/2^{t+1}}\cdot\left(\operatorname{val}^{\rho}_{\mathbb{A}^{\prime}}(h^{*})+(2M-1)\cdot\operatorname{val}^{\rho}_{\mathbb{A}^{\prime}[O]}({\left.\kern-1.2pth^{*}\right|_{O}})\right)$
$\displaystyle\leq
e^{\varepsilon/2^{t+1}}\cdot(1+\frac{2M-1}{k})\operatorname{val}^{\rho}_{\mathbb{A}^{\prime}}(h^{*})$
$\displaystyle\leq
e^{\varepsilon/2^{t}}\cdot\operatorname{val}^{\rho}_{\mathbb{A}^{\prime}}(h^{*}).$

(the last inequality holds because we chose $k$ to satisfy
$1+\frac{2M-1}{k}\leq 1+\frac{\varepsilon}{2^{t+1}}\leq
e^{\varepsilon/2^{t+1}}$).

Observe that for each $x\in A^{\prime}$ either $\lambda(x)\not\in O$ there is
a unique $j$ for which $\lambda(x)\in B_{j}$, or $\lambda(x)\in O$ and there
is a unique $j$ for which $\lambda(x)\in B_{j}\cap
B_{j+1}=L_{(j+1)k-{i^{*}}}$. In the latter case we let $s(x)$ denote the
unique $s\in\\{1,\dots,\ell\\}$ for which $\lambda(x)=((j+1)k-{i^{*}})\ell+s$.
Let $h^{\prime}\colon A^{\prime}\to C$ be defined as follows

$h^{\prime}(x)\coloneqq\begin{cases}\rho(x)&\qquad\text{if
$x\in\operatorname{dom}(\rho)$}\\\ h_{j}(x)&\qquad\text{if $\lambda(x)\in
B_{j}$ for a unique $j$}\\\ \psi_{s(x)}(h_{j}(x),h_{j+1}(x))&\qquad\text{if
$\lambda(x)\in B_{j}\cap B_{j+1}$.}\end{cases}$

We claim that $h^{\prime}$ is a solution to $(\mathbb{A}^{\prime},\mathbb{C})$
satisfying
$\operatorname{val}^{\rho}(h^{\prime})\leq\sum_{j}\operatorname{val}^{\rho}_{\mathbb{A}^{+}[B_{j}]}(h_{j})$.
This will imply

$\operatorname{val}^{\rho}_{\mathbb{A}^{\prime}}(h^{\prime})\leq\sum_{j}\operatorname{val}^{\rho}_{\mathbb{A}^{+}[B_{j}]}(h_{j})\leq
e^{\varepsilon/2^{t}}\operatorname{val}(h^{*}),$

concluding that $h^{\prime}$ it is the solution we seek.

Let $(f,\mathbf{x})\in\operatorname{tup}_{>0}(\mathbb{A}^{\prime})$. Note that
since $\lambda$ is a layering of
$G^{\prime}=\operatorname{G}(\mathbb{A}^{\prime})\setminus\operatorname{dom}(\rho)$,
there are two consecutive levels which contain all
$x_{i}\in\operatorname{Set}(\mathbf{x})\setminus\operatorname{dom}(\rho)$.
Consider the three cases.

  1. 1.

If $\operatorname{Set}(\mathbf{x})\subseteq\operatorname{dom}(\rho)$, then for
all $j$,

$f^{\mathbb{C}}(h^{\prime}(\mathbf{x}))=f^{\mathbb{C}}(\rho(\mathbf{x}))=f^{\mathbb{C}}(h_{j}(\mathbf{x})).$

  2. 2.

Otherwise, if
$\operatorname{Set}(\mathbf{x})\not\subseteq\lambda^{-1}(O)\cup\operatorname{dom}(\rho)$,
then there is a unique $j$ such that
$\operatorname{Set}(\mathbf{x})\subseteq\lambda^{-1}(B_{j})\cup\operatorname{dom}(\rho)$,
and so $h^{\prime}(x_{i})=h_{j}(x_{i})$ for each $i$ (as some $x_{i}$ might be
in the first or the last layer of an overlap, but for those layers we have
$\psi_{1}=\pi_{1}$ and $\psi_{\ell}=\pi_{2}$). Thus

$f^{\mathbb{C}}(h^{\prime}(\mathbf{x}))=f^{\mathbb{C}}(h_{j}(\mathbf{x})).$

  3. 3.

Else, if
$\operatorname{Set}(\mathbf{x})\subseteq\lambda^{-1}(O)\cup\operatorname{dom}(\rho)$
(but $\operatorname{Set}(\mathbf{x})\not\subseteq\operatorname{dom}(\rho)$),
then there is a unique $j$ such that

$\operatorname{Set}(\mathbf{x})\subseteq\lambda^{-1}(B_{j}\cap
B_{j+1})\cup\operatorname{dom}(\rho)$

and there is some $s$ such that

$\operatorname{Set}(\mathbf{x})\setminus\operatorname{dom}(\rho)\subseteq\lambda^{-1}\left(\big{\\{}((j+1)k-{i^{*}})\ell+s,((j+1)k-{i^{*}})\ell+s+1\big{\\}}\right).$

Thus

$h^{\prime}(x_{i})\in\\{\psi_{s}(h_{j}(x_{i}),h_{j+1}(x_{i})),\,\psi_{s+1}(h_{j}(x_{i}),h_{j+1}(x_{i}))\\}$

for each
$x_{i}\in\operatorname{Set}(\mathbf{x})\setminus\operatorname{dom}(\rho)$.
Moreover, since $\psi_{s}$ is idempotent, we can also write for
$x_{i}\in\operatorname{dom}(\rho)$ that

$h^{\prime}(x_{i})=\rho(x_{i})=\psi_{s}(\rho(x_{i}),\rho(x_{i}))=\psi_{s}(h_{j}(x_{i}),h_{j+1}(x_{i})).$

Therefore, as $\psi_{t}$ and $\psi_{t+1}$ are adjacent, we have by definition
of adjacency that

$f^{\mathbb{C}}(h^{\prime}(\mathbf{x}))\leq M\cdot
f^{\mathbb{C}^{2}}(h_{j}(\mathbf{x}),h_{j+1}(\mathbf{x}))=M\cdot(f^{\mathbb{C}}(h_{j}(\mathbf{x}))+f^{\mathbb{C}}(h_{j+1}(\mathbf{x}))).$

This concludes the proof that
$\operatorname{val}^{\rho}_{\mathbb{A}^{\prime}}(h^{\prime})\leq\sum_{j}\operatorname{val}^{\rho}_{\mathbb{A}^{+}[B_{j}]}(h_{j})$
and hence $h^{\prime}$ is the solution we seek.

To check the running time, observe that every vertex of $G^{\prime}$ is
contained in $\lambda^{-1}(B_{j})$ for at most two $j$. Hence the total size
of graphs $G^{\prime}[\lambda^{-1}(B_{j})]$ is at most $2\lvert
G^{\prime}\rvert$. Since $f_{2}$ is sub-additive, the total time required to
consider those graphs in this recursive call and all sub-calls contributes a
factor of at most $f_{2}(2^{t_{\max}}\lvert G^{\prime}\rvert)$. ∎

##  5 Maximisation

To present our algorithm for maximisation, we first define what it means for
two left-hand side structures $\mathbb{A},\mathbb{B}$ to be “close”, in a
sense relevant to approximately solving Max-Sol. We then show that there is a
dual view which allows to certify “closeness” by a fairly concrete mapping: a
distribution of partial homomorphisms. This is then used to show that values
given by Sherali-Adams linear programming relaxations of Max-Sol instances on
$\mathbb{A}$ and on $\mathbb{B}$ are also close. Since the level-$k$ Sherali-
Adams relaxation solves the problem exactly on instances of treewidth
$\mathcal{O}\left\lparen k\right\rparen$, it gives a PTAS for classes of
structures that are “close” to bounded treewidth, as formalised by the notion
of “strong pliability” below. The proofs are similar to those in [RWŽ21]; the
main new contribution is finding a suitable “dual” definition (a distribution
of partial homomorphisms) that makes the proofs work in the Max-Sol setting.
We remark we were unable to find an analogue for the Min-Sol setting.

###  5.1 Pliability

######  Definition 5.1.

For two left-hand side $\sigma$-structures $\mathbb{A},\mathbb{B}$, we say
$\mathbb{A}$ _strongly overcasts_ $\mathbb{B}$, denoted
$\mathbb{A}\mathrel{\succeq}\mathbb{B}$, if for all Max-Sol
$\sigma$-structures $\mathbb{C}$,
$\operatorname{maxval}(\mathbb{A},\mathbb{C})\geq\operatorname{maxval}(\mathbb{B},\mathbb{C})$.

In contrast, [RWŽ21] defined (weak) overcasting in terms of $\mathbb{Q}_{\geq
0}$-valued structures $\mathbb{C}$ only, in place of the wider class of Max-
Sol structures. The “strong” qualifier is only to avoid confusion with
[RWŽ21]: we will not consider weak overcasts in this paper, nor analogous weak
variants of the definitions given below.

######  Definition 5.2.

The _strong opt-distance_ between two left-hand side $\sigma$-structures
$\mathbb{A}$ and $\mathbb{B}$ is defined as

$\operatorname{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B})\coloneqq\inf\\{\varepsilon\mid\mathbb{A}\mathrel{\succeq}e^{-\varepsilon}\mathbb{B}\text{
and }\mathbb{B}\mathrel{\succeq}e^{-\varepsilon}\mathbb{A}\\}$

######  Observation 5.3.

Using the fact that
$\operatorname{maxval}(\lambda\mathbb{A},\mathbb{C})=\lambda\operatorname{maxval}(\mathbb{A},\mathbb{C})$,
it is an easy exercise to see that
$\operatorname{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B})=\infty$ if exactly one
of
$\operatorname{maxval}(\mathbb{A},\mathbb{C}),\operatorname{maxval}(\mathbb{B},\mathbb{C})$
is $-\infty$, or exactly one of them is $0$, for some Max-Sol
$\sigma$-structure $\mathbb{C}$; otherwise

$\displaystyle\operatorname{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B})=\sup\\{\varepsilon\mid\mathbb{A}\not\mathrel{\succeq}e^{-\varepsilon}\mathbb{B}\text{
or
}\mathbb{B}\not\mathrel{\succeq}e^{-\varepsilon}\mathbb{A}\\}=\sup_{\mathbb{C}}\lvert\ln\operatorname{maxval}(\mathbb{A},\mathbb{C})-\ln\operatorname{maxval}(\mathbb{B},\mathbb{C})\rvert.$

where the latter supremum is over all Max-Sol $\sigma$-structures $\mathbb{C}$
such that neither is $-\infty$ nor $0$. It follows that
$\operatorname{d}_{\mathrm{opt}}$ is symmetric and satisfies the triangle
inequality.

The only graph parameter $\operatorname{p}$ we consider in this paper will be
treewidth, $\operatorname{tw}$. Just as in [RWŽ21], one can prove that
treedepth, or the Hadwiger number, give rise to equivalent definitions.

######  Definition 5.4.

A class of $\mathbb{Q}_{\geq 0}$-valued structures $\mathcal{A}$ is _strongly
$\operatorname{p}$-pliable_ with respect to a graph parameter
$\operatorname{p}$ if for all $\varepsilon>0$ there exists $k=k(\varepsilon)$
such that for every $\sigma$-structure $\mathbb{A}\in\mathcal{A}$ there exists
a $\mathbb{Q}_{\geq 0}$-valued $\sigma$-structure $\mathbb{B}$ with
$\operatorname{p}(\mathbb{B})\leq k$ and
$\operatorname{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B})\leq\varepsilon$.

###  5.2 Duality

######  Definition 5.5 (partial functions and homomorphisms).

For a partial function $g\colon A\to B$ and a tuple $\mathbf{x}\in A^{n}$,
$g(\mathbf{x})$ is defined as $(g(x_{1}),\dots,g(x_{n}))\in B^{n}$ if all
coordinates are defined, and is undefined otherwise. For $\mathbf{y}\in
B^{n}$, we define $g^{-1}(\mathbf{x})\coloneqq\\{\mathbf{x}\in A^{n}\mid
g(\mathbf{x})\text{ is defined and equal to }\mathbf{y}\\}$.

For left-hand side $\sigma$-structures $\mathbb{A},\mathbb{B}$, a _partial
homomorphism_ from $\mathbb{A}$ to $\mathbb{B}$ is a partial function $g\colon
A\to B$ such that: for any positive tuple
$(f,\mathbf{x})\in\operatorname{tup}_{>0}(\mathbb{A})$, there is a positive
tuple $(f,\mathbf{y})\in\operatorname{tup}_{>0}(\mathbb{B})$ such that
$y_{i}=g(x_{i})$ whenever $g(x_{i})$ is defined (and $y_{i}$ is arbitrary
otherwise — in particular $y_{i}\neq y_{j}$ is allowed even if $x_{i}=x_{j}$).
We denote the set of partial homomorphisms from $\mathbb{A}$ to $\mathbb{B}$
by $\operatorname{p-hom}(\mathbb{A},\mathbb{B})$.

######  Remark 5.6.

Partial homomorphisms can also be understood as follows. For a left-hand side
$\sigma$-structure $\mathbb{B}$, let $\mathbb{B}^{+}$ be the left-hand side
$\sigma$-structure with domain $B\cup\\{\star\\}$, where $\star$ is a new
element, where the value for $f\in\sigma$ of arity $n$ and an input
$\mathbf{x}\in{(B\cup\\{\star\\})}^{n}$ is defined as

$f^{\mathbb{B}^{+}}(\mathbf{x})\coloneqq\max_{\begin{subarray}{c}\mathbf{y}\in
B^{n}\\\
\mathbf{x}\sqsubseteq_{\star}\mathbf{y}\end{subarray}}f^{\mathbb{B}}(\mathbf{y}).$

In particular $f^{\mathbb{B}^{+}}(\mathbf{x})=f^{\mathbb{B}}(\mathbf{x})$ for
$\mathbf{x}\in B^{n}$. Let $\operatorname{Pos}(\mathbb{A})$ be the relational
$\sigma$-structure consisting of positive tuples of $\mathbb{A}$. Then a
partial homomorphism $g$ from $\mathbb{A}$ to $\mathbb{B}$ is the same as a
homomorphism from $\operatorname{Pos}(\mathbb{A})$ to
$\operatorname{Pos}(\mathbb{B}^{+})$ (undefined assignments are the same as
assignments to $\star$).

######  Lemma 5.7.

Let $\mathbb{A},\mathbb{B}$ be left-hand side $\sigma$-structures. Then, the
following are equivalent:

  * •

$\mathbb{A}$ strongly overcasts $\mathbb{B}$, i.e. for all Max-Sol
$\sigma$-structures $\mathbb{C}$,
$\operatorname{maxval}(\mathbb{A},\mathbb{C})\geq\operatorname{maxval}(\mathbb{B},\mathbb{C})$;

  * •

there is a distribution of partial homomorphisms
$\omega\colon\operatorname{p-hom}(\mathbb{A},\mathbb{B})\to\mathbb{Q}_{\geq
0}$ $(\sum_{g}\omega(g)=1)$ such that

$\operatorname*{\mathrm{E}}_{g\sim\omega}f^{\mathbb{A}}(g^{-1}(\mathbf{y}))\geq
f^{\mathbb{B}}(\mathbf{y})\quad\quad\text{ for all
}(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B}).$

(Here $f^{\mathbb{A}}(g^{-1}(\mathbf{y}))$ is a shorthand for $\sum
f^{\mathbb{A}}(\mathbf{x})$ over all $\mathbf{x}\in g^{-1}(\mathbf{y})$, i.e.
all $\mathbf{x}\in A^{\operatorname{ar}(f)}$ such that $g(\mathbf{x})$ is
defined and equal to $\mathbf{y}$.)

###### Proof.

For one direction, suppose there is a distribution $\omega$ as in the second
bullet and let $\mathbb{C}$ be a Max-Sol $\sigma$-structure with a bottom
label $c_{\bot}$. Let $h\colon B\to C$ be a function achieving
$\operatorname{maxval}(\mathbb{B},\mathbb{C})$. For
$g\in\operatorname{p-hom}(\mathbb{A},\mathbb{B})$, let
$h\circ_{\scriptscriptstyle\bot}g\colon A\to C$ denote the function which maps
$a\in A$ to $h(g(a))$ if $g(a)$ is defined and to $c_{\bot}$ otherwise.

Therefore,

$\operatorname{maxval}(\mathbb{A},\mathbb{C})\geq\operatorname*{\mathrm{E}}_{g\sim\omega}\operatorname{val}(h\circ_{\scriptscriptstyle\bot}g)=\operatorname*{\mathrm{E}}_{g\sim\omega}\sum_{(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A})}f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(h\circ_{\scriptscriptstyle\bot}g(\mathbf{x})).$

We claim the expression Section 5.2 is greater or equal to

$\operatorname{maxval}(\mathbb{B},\mathbb{C})=\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})}f^{\mathbb{B}}(\mathbf{y})f^{\mathbb{C}}(h(\mathbf{y})).$

Indeed, suppose first that Section 5.2 is $-\infty$, or equivalently, some
summand in Section 5.2 is negative. Then there exists
$(f,\mathbf{x})\in\operatorname{tup}_{>0}(\mathbb{A})$ and
$g\in\operatorname{supp}(\omega)$ with
$f^{\mathbb{C}}(h\circ_{\scriptscriptstyle\bot}g(\mathbf{x}))=-\infty$. Since
$g$ is a partial homomorphism, by definition there exists a positive tuple
$\mathbf{y}\in B^{\operatorname{ar}(f)}$ such that $y_{i}=g(x_{i})$ whenever
$g(x_{i})$ is defined. That is, $f^{\mathbb{B}}(\mathbf{y})>0$ and
$h\circ_{\scriptscriptstyle\bot}g(\mathbf{x})\sqsubseteq_{{}_{\bot}}h(\mathbf{y})$.
By the assumption that $\mathbb{C}$ is a Max-Sol structure,
$f^{\mathbb{C}}(h(\mathbf{y}))=-\infty$. Since $f^{\mathbb{B}}(\mathbf{y})$ is
positive, this gives a $-\infty$ summand in Section 5.2 and thus the
inequality holds.

Otherwise, we can assume that every summand in Section 5.2 is non-negative. In
that case

Section 5.2
$\displaystyle=\operatorname*{\mathrm{E}}_{g\sim\omega}\sum_{(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A})}f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(h\circ_{\scriptscriptstyle\bot}g(\mathbf{x}))$
$\displaystyle\geq\operatorname*{\mathrm{E}}_{g\sim\omega}\sum_{\begin{subarray}{c}(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A})\\\
g(\mathbf{x})\text{ is
defined}\end{subarray}}f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(h\circ_{\scriptscriptstyle\bot}g(\mathbf{x}))$
$\displaystyle=\operatorname*{\mathrm{E}}_{g\sim\omega}\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})}f^{\mathbb{A}}(g^{-1}(\mathbf{y}))f^{\mathbb{C}}(h(\mathbf{y}))$
$\displaystyle=\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})}f^{\mathbb{C}}(h(\mathbf{y}))\operatorname*{\mathrm{E}}_{g\sim\omega}f^{\mathbb{A}}(g^{-1}(\mathbf{y}))$
$\displaystyle\geq\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})}f^{\mathbb{C}}(h(\mathbf{y}))f^{\mathbb{B}}(\mathbf{y})=\lx@cref{creftype~refnum}{eq:D_right},$

where after the first inequality it is still true that all summands are non-
negative, and hence the last inequality follows from the assumption about
$\omega$. This concludes the proof that
$\operatorname{maxval}(\mathbb{A},\mathbb{C})\geq\operatorname{maxval}(\mathbb{B},\mathbb{C})$.

For the converse, we will use the following variant of Farkas’ Lemma [RWŽ20,
Lemma A.2]: _ Let $A$ be an $m\times n$ rational matrix and
$\bar{b}\in\mathbb{Q}^{m}$. Exactly one of the following holds:_

  * •

_there are_ $x_{i}\in\mathbb{Q}_{\geq 0}$ ($i=1,\dots,n$) such that
$\sum_{i}x_{i}=1$ and $\sum_{i}A_{i,j}x_{i}\geq b_{j}$ for $j=1,\dots,m$;

  * •

_there are_ $y_{j}\in\mathbb{Q}_{\geq 0}$ ($j=1,\dots,m$) such that
$\sum_{j}A_{i,j}y_{j}<\sum_{j}b_{j}y_{j}$ for $i=1,\dots,n$.

Suppose there is no distribution $\omega$ as in the second bullet. This means
there are no numbers $\omega(g)\in\mathbb{Q}_{\geq 0}$ (for
$g\in\operatorname{p-hom}(\mathbb{A},\mathbb{B})$) such that
$\sum_{g}\omega(g)=1$ and

$\sum_{g\in\operatorname{p-hom}(\mathbb{A},\mathbb{B})}\omega(g)f^{\mathbb{A}}(g^{-1}(\mathbf{y}))\geq
f^{\mathbb{B}}(\mathbf{y})\quad\quad\text{ for all
}(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B}).$

Thus by Farkas’ Lemma, there are numbers $c(f,\mathbf{y})\in\mathbb{Q}_{\geq
0}$ (for $(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})$) such that

$\displaystyle\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})}f^{\mathbb{A}}(g^{-1}(\mathbf{y}))\,c(f,\mathbf{y})<\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})}f^{\mathbb{B}}(\mathbf{y})c(f,\mathbf{y})\quad\quad\text{for
all }g\in\operatorname{p-hom}(\mathbb{A},\mathbb{B}).$ (5)

Let $\mathbb{C}$ be the $\sigma$-structure with domain $B\cup\\{c_{\bot}\\}$,
where $c_{\bot}$ is a new label, and with values defined as follows for
$f\in\sigma$ of arity $n$ and $\mathbf{y}\in C^{n}$:

$\displaystyle
f^{\mathbb{C}}(\mathbf{y})\coloneqq\begin{cases}-\infty&\text{if
}\forall_{\mathbf{y}^{\prime}\in
B^{n}\colon\mathbf{y}^{\prime}\sqsupseteq_{{}_{\bot}}\mathbf{y}}\
f^{\mathbb{B}}(\mathbf{y}^{\prime})=0\\\ &\text{ (in particular if
}\mathbf{y}\in B^{n}\text{ and }f^{\mathbb{B}}(\mathbf{y})=0\text{)}\\\
c(f,\mathbf{y})&\text{if }\mathbf{y}\in B^{n}\text{ and
}f^{\mathbb{B}}(\mathbf{y})>0\\\ 0&\text{otherwise; that is, if\
}c_{\bot}\in\mathbf{y}\text{ and }\exists_{\mathbf{y}^{\prime}\in
B^{n}\colon\mathbf{y}^{\prime}\sqsupseteq_{{}_{\bot}}\mathbf{y}}\
f^{\mathbb{B}}(\mathbf{y}^{\prime})>0.\end{cases}$

Observe that $\mathbb{C}$ is a Max-Sol structure: for each $f\in\sigma$,
$f^{\mathbb{C}}$ satisfies that $f^{\mathbb{C}}(\mathbf{y})\geq 0$ implies
$f^{\mathbb{C}}(\mathbf{x})\geq 0$ for all
$\mathbf{x}\sqsubseteq_{{}_{\bot}}\mathbf{y}$. To show that
$\operatorname{maxval}(\mathbb{A},\mathbb{C})<\operatorname{maxval}(\mathbb{B},\mathbb{C})$,
we claim that for every function $g$ from $A$ to $C=B\cup\\{c_{\bot}\\}$, we
have the following strict inequality:

$\displaystyle\operatorname{val}(g)$
$\displaystyle=\sum_{(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A})}f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(g(\mathbf{x}))\
=\
\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{C})}f^{\mathbb{A}}(g^{-1}(\mathbf{y}))f^{\mathbb{C}}(\mathbf{y})$
$\displaystyle<\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})}f^{\mathbb{B}}(\mathbf{y})f^{\mathbb{C}}(\mathbf{y})\
=\ \operatorname{val}(\iota)\ \leq\
\operatorname{maxval}(\mathbb{B},\mathbb{C}),$

where $\iota$ denotes the inclusion function from $B$ to $C$.

Indeed, suppose first that $g$, as a partial function from $A$ to $B$, is not
a partial homomorphism. Then there is an
$(f,\mathbf{x})\in\operatorname{tup}_{>0}(\mathbb{A})$ such that for all
$\mathbf{y}\in B^{\operatorname{ar}(f)}$ with
$\mathbf{y}\sqsupseteq_{{}_{\bot}}g(\mathbf{x})$ we have
$f^{\mathbb{B}}(\mathbf{y})=0$. Thus $f^{\mathbb{C}}(g(\mathbf{x}))=-\infty$
by definition. Thus the left-hand side of the inequality is $-\infty$, while
the right-hand side is always non-negative.

Otherwise, we have

$\displaystyle\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{C})}f^{\mathbb{A}}(g^{-1}(\mathbf{y}))f^{\mathbb{C}}(\mathbf{y})\leq\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})}f^{\mathbb{A}}(g^{-1}(\mathbf{y}))f^{\mathbb{C}}(\mathbf{y})\leq\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})}f^{\mathbb{A}}(g^{-1}(\mathbf{y}))c(f,\mathbf{y})$
$\displaystyle<\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})}f^{\mathbb{B}}(\mathbf{y})c(f,\mathbf{y})=\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})}f^{\mathbb{B}}(\mathbf{y})f^{\mathbb{C}}(\mathbf{y}).$

The first inequality follows from the fact that for
$(f,\mathbf{y})\in\operatorname{tup}(\mathbb{C})\setminus\operatorname{tup}(\mathbb{B})$
we have $f^{\mathbb{C}}(\mathbf{y})\leq 0$. The second follows from
$f^{\mathbb{C}}(\mathbf{y})\leq c(f,\mathbf{y})$. The third, strict inequality
follows from 5 since $g$ (as a partial function from $A$ to $B$) is a partial
homomorphism. The final equality follows from the fact that if
$f^{\mathbb{C}}(\mathbf{y})\neq c(f,\mathbf{y})$ for
$(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})$, then
$f^{\mathbb{B}}(\mathbf{y})=0$. This concludes the proof that
$\operatorname{maxval}(\mathbb{A},\mathbb{C})<\operatorname{maxval}(\mathbb{B},\mathbb{C})$.
∎

###  5.3 PTAS

We first define the Sherali-Adams LP hierarchy [SA90] for Max-Sol. Let
$(\mathbb{A},\mathbb{C})$ be an instance of Max-Sol over a signature $\sigma$
and let $k\geq\max_{f\in\sigma}\operatorname{ar}(f)$. We write $\binom{A}{\leq
k}$ for the set of subsets of $A$ with at most $k$ elements. The _Sherali-
Adams relaxation of level $k$_ [SA90] of $(\mathbb{A},\mathbb{C})$ is the
linear program given in Fig. 1, denoted by
$\operatorname{SA}_{k}(\mathbb{A},\mathbb{C})$, which has one variable
$\lambda(X,s)$ for each $X\in\binom{A}{\leq k}$ and each $s\colon X\to C$. We
denote by $\operatorname{maxval}_{k}(\mathbb{A},\mathbb{B})$ the optimum value
of $\operatorname{SA}_{k}(\mathbb{A},\mathbb{C})$, and define
$\operatorname{maxval}_{k}(\mathbb{A},\mathbb{B})=-\infty$ if
$\operatorname{SA}_{k}(\mathbb{A},\mathbb{C})$ is infeasible.

$\displaystyle\max\sum_{(f,\mathbf{x})\in\operatorname{tup}{\mathbb{A}},\;s\colon\operatorname{Set}(\mathbf{x})\to
C}$
$\displaystyle\lambda(\operatorname{Set}(\mathbf{x}),s)f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(s(\mathbf{x}))$
$\displaystyle\lambda(X,s)$ $\displaystyle=\sum_{r\colon Y\to
C,\,r|_{X}=s}\lambda(Y,r)$ for $X\subseteq Y\in\textstyle\binom{A}{\leq k}$
and $s\colon X\to C$ $\displaystyle\sum_{s\colon X\to C}\lambda(X,s)$
$\displaystyle=1$ for $X\in\textstyle\binom{A}{\leq k}$
$\displaystyle\lambda(\operatorname{Set}(\mathbf{x}),s)$ $\displaystyle=0$
$\forall(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A})$ with
$f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(s(\mathbf{x}))=-\infty$
$\displaystyle\lambda(X,s)$ $\displaystyle\geq 0$ for
$X\in\textstyle\binom{A}{\leq k}$ and $s\colon X\to C$

Figure 1: $\operatorname{SA}_{k}(\mathbb{A},\mathbb{C})$, the Sherali-Adams
relaxation of level $k\geq\max_{f\in\sigma}\operatorname{ar}(f)$ of
$(\mathbb{A},\mathbb{C})$.

######  Observation 5.8.

Let $(\mathbb{A},\mathbb{C})$ be an instance of Max-Sol,
$k\geq\max_{f\in\sigma}\operatorname{ar}(f)$ and $\lambda\geq 0$. Then,
$\operatorname{maxval}(\lambda\mathbb{A},\mathbb{C})=\lambda\operatorname{maxval}(\mathbb{A},\mathbb{C})$
and
$\operatorname{maxval}_{k}(\lambda\mathbb{A},\mathbb{C})=\lambda\operatorname{maxval}_{k}(\mathbb{A},\mathbb{C})$.

######  Observation 5.9.

Let $(\mathbb{A},\mathbb{C})$ be an instance of Max-Sol. Then, for any
$k\geq\max_{f\in\sigma}\operatorname{ar}(f)$,
$\operatorname{maxval}_{k}(\mathbb{A},\mathbb{C})\geq\operatorname{maxval}(\mathbb{A},\mathbb{C})$.

###### Proof.

Let $h\colon A\to C$ be an optimal solution to $(\mathbb{A},\mathbb{C})$.
Consider the solution
$\lambda(X,s)=\mathbf{1}\left[s={\left.\kern-1.2pth\right|_{X}}\right]$ for
$\operatorname{SA}_{k}(\mathbb{A},\mathbb{C})$. It is trivially feasible and
achieves the value $\operatorname{maxval}(\mathbb{A},\mathbb{C})$. ∎

The following easy result (proved in Appendix B) shows that an appropriate
level of the Sherali-Adams relaxation is exact for bounded treewidth.

######  Proposition 5.10.

Let $(\mathbb{A},\mathbb{C})$ be an instance of Max-Sol and
$k\geq\operatorname{tw}(\mathbb{A})$. Then,
$\operatorname{maxval}_{k}(\mathbb{A},\mathbb{C})=\operatorname{maxval}(\mathbb{A},\mathbb{C})$.

######  Definition 5.11.

Let $\mathbb{A}$ and $\mathbb{B}$ be left-hand side $\sigma$-structures, and
$k\geq\max_{f\in\sigma}\operatorname{ar}(f)$. We write
$\mathbb{A}\mathrel{\succeq}_{k}\mathbb{B}$ if for all Max-Sol
$\sigma$-structures $\mathbb{C}$ we have
$\operatorname{maxval}_{k}(\mathbb{A},\mathbb{C})\geq\operatorname{maxval}_{k}(\mathbb{B},\mathbb{C})$.

Using the dual characterisation of strong overcasts (Lemma 5.7), we can show
(and prove in Appendix A) the following.

######  Proposition 5.12.

Let $\mathbb{A}$ and $\mathbb{B}$ be left-hand side $\sigma$-structures, and
$k\geq\max_{f\in\sigma}\operatorname{ar}(f)$. If
$\mathbb{A}\mathrel{\succeq}\mathbb{B}$, then
$\mathbb{A}\mathrel{\succeq}_{k}\mathbb{B}$.

We are now ready to prove our main tractability result for maximisation
problems.

######  Proposition 5.13.

Let $\mathbb{A}$ be a left-hand side $\sigma$-structure, $\varepsilon\geq 0$
be small and $k\geq\max_{f\in\sigma}\operatorname{ar}(f)$. Suppose that there
exists a left-hand side $\sigma$-structure $\mathbb{B}$ such that
$\operatorname{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B})\leq\varepsilon$ and
$\operatorname{tw}(\mathbb{B})\leq k$. Then, for every right-hand side
$\sigma$-structure $\mathbb{C}$, we have that

$\operatorname{maxval}(\mathbb{A},\mathbb{C})\leq\operatorname{maxval}_{k}(\mathbb{A},\mathbb{C})\leq(1+\mathcal{O}\left\lparen\varepsilon\right\rparen)\operatorname{maxval}(\mathbb{A},\mathbb{C}).$

###### Proof.

By definition of $\operatorname{d}_{\mathrm{opt}}$ we have that,

$\mathbb{A}\mathrel{\preceq}e^{\varepsilon}\mathbb{B}\mathrel{\preceq}e^{2\varepsilon}\mathbb{A},\vspace*{-.5\baselineskip}$

and so

$\mathbb{A}\mathrel{\preceq}_{k}e^{\varepsilon}\mathbb{B}\mathrel{\preceq}_{k}e^{2\varepsilon}\mathbb{A}$

by Proposition 5.12. From Observations 5.9, 5.10 and 5.8 we obtain that,

$\operatorname{maxval}(\mathbb{A},\mathbb{C})\leq\operatorname{maxval}_{k}(\mathbb{A},\mathbb{C})\leq
e^{\varepsilon}\operatorname{maxval}_{k}(\mathbb{B},\mathbb{C})=e^{\varepsilon}\operatorname{maxval}(\mathbb{B},\mathbb{C})\leq
e^{2\varepsilon}\operatorname{maxval}(\mathbb{A},\mathbb{C}).$

Finally, for $\varepsilon$ small we have
$e^{2\varepsilon}=1+\mathcal{O}\left\lparen\varepsilon\right\rparen$,
completing the proof. ∎

Since $\operatorname{maxval}_{k}(\mathbb{A},\mathbb{C})$ can be computed in
time
${(\lvert\mathbb{A}\rvert\cdot\lvert\mathbb{C}\rvert)}^{\mathcal{O}\left\lparen
k\right\rparen}$, this means any strongly $\operatorname{tw}$-pliable class of
structures admits a PTAS. In the following subsection, we show that when we
look at the class of Gaifman graphs only, the appropriate condition is
fractional treewidth-fragility.

###  5.4 Fragility and pliability

To give Dvořák’s definition of fractional fragility [Dvo16] we first define
$\varepsilon$-thin distributions.

######  Definition 5.14.

Let $\mathcal{F}$ be a family of subsets of a set $V$ and $\varepsilon>0$. We
say a distribution $\pi$ over $\mathcal{F}$ is _$\varepsilon$ -thin_ if
$\Pr_{X\sim\pi}[v\in X]\leq\varepsilon$ for all $v\in V$.

######  Definition 5.15.

For a graph parameter $\operatorname{p}$ and a number $k$, we define a
_$(\operatorname{p}\leq k)$ -modulator_ of a graph $G$ to be a set $X\subseteq
V(G)$ such that $\operatorname{p}(G-X)\leq k$. A _fractional
$(\operatorname{p}\leq k)$-modulator_ is a distribution $\pi$ of such
modulators $X$. We say that a class of graphs $\mathcal{G}$ is _fractionally-
$\operatorname{p}$-fragile_ if for every $\varepsilon>0$ there is a $k$ such
that every $G\in\mathcal{G}$ has an $\varepsilon$-thin fractional
$(\operatorname{p}\leq k)$-modulator.

We need some more notation. We denote the disjoint union of graphs $G$ and $H$
by $G\uplus H$. For $\sigma$ structures $\mathbb{A}_{1},\dots,\mathbb{A}_{k}$,
we define the $\sigma$-structure
$\mathbb{B}=\biguplus_{i=1}^{k}\mathbb{A}_{i}$ to be over the domain
$B=\biguplus_{i=1}^{k}A_{i}$ and by
$f^{\mathbb{B}}(\mathbf{x})=f^{\mathbb{A}_{i}}(\mathbf{x})$ whenever
$(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A}_{i})$, and 0 otherwise.

While we are mostly interested in the following result with treewidth as the
graph parameter, we state it more generally since the proof is the same.

######  Lemma 5.16.

Let $\operatorname{p}$ be a
monotone222$\operatorname{p}(H)\leq\operatorname{p}(G)$ for all graphs $G$ and
subgraphs $H$ of $G$. graph parameter such that $\operatorname{p}(G\uplus
H)\leq\max(\operatorname{p}(G),\operatorname{p}(H))$ for all graphs $G$ and
$H$ and $\operatorname{p}(G)\leq\operatorname{p}(G-v)+1$ for all $v\in V(G)$.
Let $\mathcal{A}$ be a class of structures with bounded arity $r$ such that
the class $\mathcal{G}$ of their Gaifman graphs is
fractionally-$\operatorname{p}$-fragile. Then $\mathcal{A}$ is strongly
$\operatorname{p}$-pliable.

The proof closely follows the proof of [RWŽ20, Lemma 4.6], where the same
result was shown for several particular monotone graph parameters.

###### Proof.

Given $\varepsilon>0$, $\mathbb{A}\in\mathcal{A}$, let $\pi$ be a fractional
$(\operatorname{p}\leq k)$-modulator such that for every $v\in V(G)$,

$\Pr_{X\sim\pi}[v\in X]\leq\varepsilon.$ (6)

For each $X\subseteq V(G)=A$ in the support of $\pi$ ($\pi(X)>0$), define
$\mathbb{A}_{/X}$ to be the $\sigma$-structure obtained by contracting $X$ to
a single vertex and summing values. That is, let $\\{\star_{X}\\}$ be a new
element and define $g_{X}:A\to(A-X)\cup\\{\star_{X}\\}$ that maps $X$ to
$\star_{X}$ and $A-X$ identically. Let $\mathbb{A}_{/X}$ be over the domain
$(A-X)\cup\\{\star_{X}\\}$ and

$f^{\mathbb{A}_{/X}}(\mathbf{y})\coloneqq
f^{\mathbb{A}}(g_{X}^{-1}(\mathbf{y}))=\sum_{\mathbf{x}\in
g_{X}^{-1}(\mathbf{y})}f^{\mathbb{A}}(\mathbf{x})$

for each $f\in\sigma$ of arity $n$ and each
$\mathbf{y}\in{((A-X)\cup\\{\star_{X}\\})}^{n}$.

Define $\mathbb{B}_{X}=\pi(X)\cdot\mathbb{A}_{/X}$, and let
$\mathbb{B}=\biguplus\mathbb{B}_{X}$. By definition of $\pi$ and properties of
$\operatorname{p}$, we have
$\operatorname{p}(\operatorname{G}(\mathbb{B}_{X}))\leq\operatorname{p}(\operatorname{G}(\mathbb{A})-X)+1\leq
k+1$, and so $\operatorname{p}(\operatorname{G}(\mathbb{B}))\leq k+1$.

View $g_{X}$ as a function to $B$ (instead of as function to $B_{X}\subseteq
B$), so that $g_{X}\colon A\to B$ is the (total) function mapping $A-X$
identically to its copy in $B_{X}$ and mapping $X$ to $\star_{X}$. It is clear
that $g_{X}\in\operatorname{p-hom}(\mathbb{A},\mathbb{B})$. Define the strong
overcast $\omega\colon\mathbb{A}\to\mathbb{B}$ to take the value $g_{X}$ with
probability $\pi(X)$. To check this is indeed a strong overcast, observe that
for $(f,\mathbf{y})\in\operatorname{tup}_{>0}(\mathbb{B})$, there is a unique
$X$ such that $(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B}_{X})$, hence

$\operatorname*{\mathrm{E}}_{g\sim\omega}f^{\mathbb{A}}(g^{-1}(\mathbf{y}))=\pi(X)f^{\mathbb{A}}(g_{X}^{-1}(\mathbf{y}))=f^{\mathbb{B}}(\mathbf{y}).$

Define $g\colon B\to A$ to be the partial function mapping each element of
$B_{X}-\\{\star_{X}\\}$ identically to $A$, leaving it undefined on
$\star_{X}$. It is clear that
$g\in\operatorname{p-hom}(\mathbb{B},\mathbb{A})$. Consider the overcast
$\omega^{\prime}\colon\mathbb{B}\to(1-r\varepsilon)\mathbb{A}$ that is
deterministically $g$. To check that $\omega^{\prime}$ is indeed a strong
overcast, let $(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A})$. Then
$\mathbf{x}$ is covered by copies in $\mathbb{B}_{X}$ for those $X$ that do
not intersect $\mathbf{x}$, hence

$\displaystyle f^{\mathbb{B}}(g^{-1}(\mathbf{x}))$
$\displaystyle=\operatorname*{\mathrm{E}}_{X\sim\pi}\left[\mathbf{1}\left[X\cap\mathbf{x}=\emptyset\right]\cdot
f^{\mathbb{A}}(\mathbf{x})\right]$
$\displaystyle=f^{\mathbb{A}}(\mathbf{x})\Pr_{X\sim\pi}(X\cap\mathbf{x}=\emptyset)$
$\displaystyle\geq f^{\mathbb{A}}(\mathbf{x})\cdot(1-r\varepsilon),$

where the final inequality follows by 6, the union bound, and the fact that
$\lvert\mathbf{x}\rvert\leq r$. Hence by Lemma 5.7 applied to $\omega$ and
$\omega^{\prime}$,

$\mathbb{A}\mathrel{\succeq}\mathbb{B}\mathrel{\succeq}(1-r\varepsilon)\mathbb{A}.$

By construction $\operatorname{p}(\operatorname{G}(\mathbb{B}))\leq k+1$. As
$r$ is fixed and $\varepsilon>0$ was arbitrary, this implies that
$\mathcal{A}$ is strongly $\operatorname{p}$-pliable. ∎

In particular, treewidth satisfies the assumptions of Lemma 5.16 and thus
Lemma 5.16 implies strong $\operatorname{tw}$-pliability. This concludes the
proof of our PTAS for maximisation, Theorem 1.2.

Conversely, if we only look at Gaifman graphs, one cannot use this approach to
go beyond fractionally $\operatorname{tw}$-fragile classes. This is because
[RWŽ20, Lemma 6.1] together with the above Lemma 5.16 implies that for a class
of graph $\mathcal{G}$ and an integer $r$, if
$\mathcal{A}^{(r)}_{\mathcal{G}}$ denotes the class of all $\mathbb{Q}_{\geq
0}$-valued structures of arity at most $r$ and whose Gaifman graphs are in
$\mathcal{G}$, then $\mathcal{A}^{(r)}_{\mathcal{G}}$ is strongly
$\operatorname{tw}$-pliable if and only if $\mathcal{G}$ fractionally
$\operatorname{tw}$-fragile. In Appendix C, we give a simple example of a
class of structures (not parametrised by their Gaifman graphs) that is stronly
tw-pliable but not captured by fractional-treewidth-fragility.

## References

  * [Bak94] Brenda S. Baker  “Approximation Algorithms for NP-Complete Problems on Planar Graphs”  In _J. ACM_ 41.1, 1994, pp. 153–180  DOI: 10.1145/174644.174650
  * [BK99] Piotr Berman and Marek Karpinski  “On Some Tighter Inapproximability Results (Extended Abstract)”  In _Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP’99)_ 1644, Lecture Notes in Computer Science  Springer, 1999, pp. 200–209  DOI: 10.1007/3-540-48523-6˙17
  * [BKL08] Andrei A. Bulatov, Andrei A. Krokhin and Benoît Larose  “Dualities for Constraint Satisfaction Problems”  In _Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar]_ 5250, Lecture Notes in Computer Science  Springer, 2008, pp. 93–124  DOI: 10.1007/978-3-540-92800-3˙5
  * [Bod93] Hans L. Bodlaender  “A Linear Time Algorithm for Finding Tree-Decompositions of Small Treewidth”  In _Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC’93)_ Association for Computing Machinery, 1993, pp. 226–234  DOI: 10.1145/167088.167161
  * [Bod98] Hans L. Bodlaender  “A Partial $k$-Arboretum of Graphs with Bounded Treewidth”  In _Theoretical Computer Science_ 209, 1998, pp. 1–45  DOI: 10.1016/S0304-3975(97)00228-4
  * [Bri+19] Raimundo Briceño, Andrei A. Bulatov, Víctor Dalmau and Benoît Larose  “Dismantlability, Connectedness, and Mixing in Relational Structures”  In _Proc. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)_ 132, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, pp. 29:1–29:15  DOI: 10.4230/LIPIcs.ICALP.2019.29
  * [BW00] Graham R. Brightwell and Peter Winkler  “Gibbs Measures and Dismantlable Graphs”  In _J. Comb. Theory, Ser. B_ 78.1, 2000, pp. 141–166  DOI: 10.1006/jctb.1999.1935
  * [CRŽ18] Clément Carbonnel, Miguel Romero and Stanislav Živný  “The complexity of general-valued CSPs seen from the other side”  In _Proc. 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS’18)_ IEEE Computer Society, 2018, pp. 236–246  DOI: 10.1109/FOCS.2018.00031
  * [CŽ17] Martin C. Cooper and Stanislav Živný  “Hybrid Tractable Classes of Constraint Problems”  In _The Constraint Satisfaction Problem: Complexity and Approximability_ 7, Dagstuhl Follow-Ups  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 113–135  DOI: 10.4230/DFU.Vol7.15301.4
  * [Dai80] David P. Dailey  “Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete”  In _Discret. Math._ 30.3, 1980, pp. 289–293  DOI: 10.1016/0012-365X(80)90236-8
  * [DeV+04] Matt DeVos, Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Bruce Reed, Paul Seymour and Dirk Vertigan  “Excluding any graph as a minor allows a low tree-width 2-coloring”  In _J. Comb. Theory B_ 91.1, 2004, pp. 25–41  DOI: 10.1016/j.jctb.2003.09.001
  * [DHK05] Erik D. Demaine, Mohammad Taghi Hajiaghayi and Ken-ichi Kawarabayashi  “Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring”  In _Proc. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05)_ IEEE Computer Society, 2005, pp. 637–646  DOI: 10.1109/SFCS.2005.14
  * [Die10] Reinhard Diestel  “Graph Theory”  Springer, 2010
  * [Dvo16] Zdeněk Dvořák  “Sublinear separators, fragility and subexponential expansion”  In _Eur. J. Comb._ 52, 2016, pp. 103–119  DOI: 10.1016/j.ejc.2015.09.001
  * [Dvo20] Zdeněk Dvořák  “Baker game and polynomial-time approximation schemes”  In _Proc. 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’20)_ SIAM, 2020, pp. 2227–2240  DOI: 10.1137/1.9781611975994.137
  * [FUŽ19] Peter Fulla, Hannes Uppman and Stanislav Živný  “The Complexity of Boolean Surjective General-Valued CSPs”  In _ACM Trans. Comput. Theory_ 11.1, 2019, pp. 4:1–4:31  DOI: 10.1145/3282429
  * [GB07] Alexander Grigoriev and Hans L. Bodlaender  “Algorithms for Graphs Embeddable with Few Crossings per Edge”  In _Algorithmica_ 49.1, 2007, pp. 1–11  DOI: 10.1007/s00453-007-0010-x
  * [Gro03] Martin Grohe  “Local Tree-Width, Excluded Minors, and Approximation Algorithms”  In _Combinatorica_ 23.4, 2003, pp. 613–632  DOI: 10.1007/s00493-003-0037-9
  * [Gro07] Martin Grohe  “The complexity of homomorphism and constraint satisfaction problems seen from the other side”  In _J. ACM_ 54.1, 2007, pp. 1–24  DOI: 10.1145/1206035.1206036
  * [GSS01] Martin Grohe, Thomas Schwentick and Luc Segoufin  “When is the evaluation of conjunctive queries tractable?”  In _Proc. 33rd Annual ACM Symposium on Theory of Computing (STOC’01)_ ACM, 2001, pp. 657–666  DOI: 10.1145/380752.380867
  * [Gut+08] Gregory Gutin, Pavol Hell, Arash Rafiey and Anders Yeo  “A dichotomy for minimum cost graph homomorphisms”  In _European Journal of Combinatorics_ 29.4, 2008, pp. 900–911  DOI: 10.1016/j.ejc.2007.11.012
  * [Hel+12] Pavol Hell, Monaldo Mastrolilli, Mayssam Mohammadi Nevisi and Arash Rafiey  “Approximation of Minimum Cost Homomorphisms”  In _Proceddings of the 20th Annual European Symposium on Algorithms (ESA12)_ 7501, Lecture Notes in Computer Science  Springer, 2012, pp. 587–598  DOI: 10.1007/978-3-642-33090-2˙51
  * [HR12] Pavol Hell and Arash Rafiey  “The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs”  In _SIAM Journal on Discrete Mathematics_ 26.4, 2012, pp. 1597–1608  DOI: 10.1137/100783856
  * [Hun+98] Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, S.S Ravi, Daniel J. Rosenkrantz and Richard E. Stearns  “NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs”  In _J. Algorithms_ 26.2, 1998, pp. 238 –274  DOI: https://doi.org/10.1006/jagm.1997.0903
  * [JKK09] Peter Jonsson, Andrei A. Krokhin and Fredrik Kuivinen  “Hard constraint satisfaction problems have hard gaps at location 1”  In _Theor. Comput. Sci._ 410.38-40, 2009, pp. 3856–3874  DOI: 10.1016/j.tcs.2009.05.022
  * [JKN08] Peter Jonsson, Fredrik Kuivinen and Gustav Nordh  “MAX ONES Generalized to Larger Domains”  In _SIAM Journal on Computing_ 38.1, 2008, pp. 329–365  DOI: 10.1137/060669231
  * [JKŽ14] Peter Jeavons, Andrei A. Krokhin and Stanislav Živný  “The Complexity of Valued Constraint Satisfaction”  In _Bull. EATCS_ 113, 2014  URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/266
  * [JN08] Peter Jonsson and Gustav Nordh  “Introduction to the Maximum Solution Problem”  In _Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar]_ 5250, Lecture Notes in Computer Science  Springer, 2008, pp. 255–282  DOI: 10.1007/978-3-540-92800-3˙10
  * [Kha+01] Sanjeev Khanna, Madhu Sudan, Luca Trevisan and David P. Williamson  “The Approximability of Constraint Satisfaction Problems”  In _SIAM Journal on Computing_ 30.6, 2001, pp. 1863–1920  DOI: 10.1137/S0097539799349948
  * [Kho02] Subhash Khot  “On the power of unique 2-prover 1-round games”  In _Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC’02)_ ACM, 2002, pp. 767–775  DOI: 10.1145/509907.510017
  * [KKR17] Vladimir Kolmogorov, Andrei A. Krokhin and Michal Rolínek  “The Complexity of General-Valued CSPs”  In _SIAM J. Comput._ 46.3, 2017, pp. 1087–1110  DOI: 10.1137/16M1091836
  * [KM96] Sanjeev Khanna and Rajeev Motwani  “Towards a Syntactic Characterization of PTAS”  In _Proc. 28th Annual ACM Symposium on the Theory of Computing (STOC’96)_ , 1996, pp. 329–337  DOI: 10.1145/237814.237979
  * [KO15] Marcin Kozik and Joanna Ochremiak  “Algebraic Properties of Valued Constraint Satisfaction Problem”  In _Proceeding of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP’15)_ 9134, Lecture Notes in Computer Science  Springer, 2015, pp. 846–858  DOI: 10.1007/978-3-662-47672-7˙69
  * [Kum+11] Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani and Nisheeth K Vishnoi  “On LP-based approximability for strict CSPs”  In _Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’11)_ SIAM, 2011, pp. 1560–1573  DOI: 10.1137/1.9781611973082.121
  * [MHS97] Madhav V. Marathe, Harry B. Hunt III and Richard E. Stearns  “Level-treewidth property, exact algorithms and approximation schemes”  In _Proc. ACM Symposium on Theory of Computing (STOC’97)_ , 1997  URL: https://www.osti.gov/biblio/471394
  * [MM17] Konstantin Makarychev and Yury Makarychev  “Approximation Algorithms for CSPs”  In _The Constraint Satisfaction Problem: Complexity and Approximability_ 7, Dagstuhl Follow-Ups  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 287–325  DOI: 10.4230/DFU.Vol7.15301.11
  * [Rag08] Prasad Raghavendra  “Optimal algorithms and inapproximability results for every CSP?”  In _Proc. 40th Annual ACM Symposium on Theory of Computing (STOC’08)_ , 2008, pp. 245–254  DOI: 10.1145/1374376.1374414
  * [RRS19] Akbar Rafiey, Arash Rafiey and Thiago Santos  “Toward a Dichotomy for Approximation of H-Coloring”  In _Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP’19)_ 132, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, pp. 91:1–91:16  DOI: 10.4230/LIPIcs.ICALP.2019.91
  * [RWŽ20] Miguel Romero, Marcin Wrochna and Stanislav Živný  “Treewidth-Pliability and PTAS for Max-CSPs”, 2020  arXiv:1911.03204
  * [RWŽ21] Miguel Romero, Marcin Wrochna and Stanislav Živný  “Treewidth-Pliability and PTAS for Max-CSPs”  In _Proc. of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’21)_ , 2021  arXiv:1911.03204
  * [SA90] Hanif D. Sherali and Warren P. Adams  “A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems”  In _SIAM J. Discrete Math._ 3.3, 1990, pp. 411–430  DOI: 10.1137/0403036
  * [Tak10] Rustem Takhanov  “A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem”  In _Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS’10)_ , 2010, pp. 657–668  DOI: 10.4230/LIPIcs.STACS.2010.2493
  * [Zuc07] David Zuckerman  “Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number”  In _Theory Comput._ 3.1, 2007, pp. 103–128  DOI: 10.4086/toc.2007.v003a006

##  Appendix A Proof of Proposition 5.12

We closely follow the proof of [RWŽ20, Proposition 5.3] but, given we are in a
more general setting, we have to be more careful.

###### Proof.

Let $\mathbb{C}$ be a Max-Sol $\sigma$-structure, and let $\omega$ be an
overcast from $\mathbb{A}$ to $\mathbb{B}$. Recall that for a tuple
$\mathbf{x}$ we denote by $\operatorname{Set}(\mathbf{x})$ the set of elements
appearing in $\mathbf{x}$. For a partial function $g\colon A\to B$ and a
subset $X\subseteq A$, $g(X)$ denotes the set $\\{g(x)\mid x\in X\text{ and
}g(x)\text{ is defined}\\}$. For a function $s\colon g(X)\to C$,
$s\circ_{\scriptscriptstyle\bot}g$ denotes the function from $X$ to $C$
defined as $s(g(x))$ when $g(x)$ is defined and $c_{\bot}$ otherwise.

Let $\lambda$ be an optimal solution to
$\operatorname{SA}_{k}(\mathbb{B},\mathbb{C})$. That is, for each subset $Y$
of $B$ of size at most $k$, $\lambda$ describes a distribution of functions to
$C$ using probabilities $\lambda(Y,s)\in\mathbb{Q}_{\geq 0}$ for $s\colon Y\to
C$. For fixed $g\in\operatorname{supp}(\omega)$, we define a solution
$\lambda_{g}$ to $\operatorname{SA}_{k}(\mathbb{A},\mathbb{C})$ by sampling
$s$ from this distribution and outputting $s\circ_{\scriptscriptstyle\bot}g$.
Formally, for $X\in\binom{A}{\leq k}$ and $r\colon X\to C$, we define

$\lambda_{g}(X,r)\coloneqq\sum_{s\colon g(X)\to
C}\mathbf{1}\left[r=s\circ_{\scriptscriptstyle\bot}g\right]\cdot\lambda(g(X),s).$

Note that $\lambda_{g}$ is a feasible solution. Indeed, for
$X\in\binom{A}{\leq k}$ the total probability is

$\sum_{r\colon X\to C}\lambda_{g}(X,r)=\sum_{s\colon g(X)\to
C}\left(\sum_{r\colon X\to
C}\mathbf{1}\left[r=s\circ_{\scriptscriptstyle\bot}g\right]\right)\cdot\lambda(g(X),s)=\sum_{s\colon
g(X)\to C}1\cdot\lambda(g(X),s)=1;$

while for $Z\subseteq X\in\binom{A}{\leq k}$ and $r\colon Z\to C$, the
marginal probability of obtaining $r$ is

$\displaystyle\sum_{\begin{subarray}{c}t\colon X\to C\\\
t|_{Z}=r\end{subarray}}\lambda_{g}(X,t)$
$\displaystyle=\sum_{\begin{subarray}{c}t\colon X\to C\\\
t|_{Z}=r\end{subarray}}\ \sum_{s\colon g(X)\to
C}\mathbf{1}\left[t=s\circ_{\scriptscriptstyle\bot}g\right]\cdot\lambda(g(X),s)$
$\displaystyle=\sum_{s\colon g(X)\to C}\ \sum_{\begin{subarray}{c}t\colon X\to
C\\\
t|_{Z}=r\end{subarray}}\mathbf{1}\left[t=s\circ_{\scriptscriptstyle\bot}g\right]\cdot\lambda(g(X),s)$
$\displaystyle=\sum_{s\colon g(X)\to
C}\mathbf{1}\left[r=(s\circ_{\scriptscriptstyle\bot}g)|_{Z}\right]\cdot\lambda(g(X),s)$
$\displaystyle=\sum_{s\colon g(X)\to
C}\mathbf{1}\left[r=(s|_{g(Z)})\circ_{\scriptscriptstyle\bot}g\right]\cdot\lambda(g(X),s)$
$\displaystyle=\sum_{s^{\prime}\colon g(Z)\to
C}\Big{(}\mathbf{1}\left[r=s^{\prime}\circ_{\scriptscriptstyle\bot}g\right]\sum_{\begin{subarray}{c}s\colon
g(X)\to C\\\ s|_{g(Z)}=s^{\prime}\end{subarray}}\lambda(g(X),s)\Big{)}$
$\displaystyle=\sum_{s^{\prime}\colon g(Z)\to
C}\mathbf{1}\left[r=s^{\prime}\circ_{\scriptscriptstyle\bot}g\right]\cdot\lambda(g(Z),s^{\prime})$
$\displaystyle=\lambda_{g}(Z,r).$

Therefore $\operatorname{maxval}_{k}(\mathbb{A},\mathbb{C})$ is at least the
expected value of the solution $\lambda_{g}$ with $g$ sampled from $\omega$:

$\displaystyle\operatorname{maxval}_{k}(\mathbb{A},\mathbb{C})$
$\displaystyle\geq\operatorname*{\mathrm{E}}_{g\sim\omega}\sum_{\begin{subarray}{c}(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A})\\\
r\colon\operatorname{Set}(\mathbf{x})\to
C\end{subarray}}\lambda_{g}(\operatorname{Set}(\mathbf{x}),r)f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(r(\mathbf{x}))$
$\displaystyle=\operatorname*{\mathrm{E}}_{g\sim\omega}\sum_{\begin{subarray}{c}(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A})\\\
s\colon g(\operatorname{Set}(\mathbf{x}))\to
C\end{subarray}}\lambda(g(\operatorname{Set}(\mathbf{x})),s)f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(s\circ_{\scriptscriptstyle\bot}g(\mathbf{x})),$
($\ast_{L}$)

by definition of $\lambda_{g}$. We claim the expression $\ast_{L}$ is at least

$\operatorname{maxval}_{k}(\mathbb{B},\mathbb{C})=\sum_{\begin{subarray}{c}(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B})\\\
s\colon\operatorname{Set}(\mathbf{y})\to
C\end{subarray}}\lambda(\operatorname{Set}(\mathbf{y}),s)f^{\mathbb{B}}(\mathbf{y})f^{\mathbb{C}}(s(\mathbf{y})).$

Indeed, suppose first that some summand in $\ast_{L}$ is negative. Then there
exist $g\in\operatorname{supp}(\omega)$,
$(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A})$, and $s\colon
g(\operatorname{Set}(\mathbf{x}))\to C$ such that
$\lambda(g(\operatorname{Set}(\mathbf{x})),s),f^{\mathbb{A}}(\mathbf{x})>0$
and $f^{\mathbb{C}}(s\circ_{\scriptscriptstyle\bot}g(\mathbf{x}))=-\infty$.
Since $g\in\operatorname{p-hom}(\mathbb{A},\mathbb{B})$, there is some
$\mathbf{y}\in A^{\operatorname{ar}(f)}$ with $f^{\mathbb{B}}(\mathbf{y})>0$
such that $g(x_{i})$ equals $y_{i}$ whenever it is defined. In particular
$g(\operatorname{Set}(\mathbf{x}))\subseteq\operatorname{Set}(\mathbf{y})$,
hence $\lambda(\operatorname{Set}(\mathbf{y}),s^{\prime})>0$ for some
$s^{\prime}\colon\operatorname{Set}(\mathbf{y})\to C$ such that
$s^{\prime}|_{g(\operatorname{Set}(\mathbf{x}))}=s$. This implies
$s^{\prime}(\mathbf{y})\sqsupseteq_{{}_{\bot}}s\circ_{\scriptscriptstyle\bot}g(\mathbf{x})$,
hence $f^{\mathbb{C}}(s^{\prime}(\mathbf{y}))=-\infty$ by the assumption that
$\mathbb{C}$ is a Max-Sol structure. Therefore Appendix A has a summand
$\lambda(\operatorname{Set}(\mathbf{y}),s^{\prime})f^{\mathbb{B}}(\mathbf{y})f^{\mathbb{C}}(s^{\prime}(\mathbf{y}))=-\infty$,
so the claimed inequality $\ast_{L}$ ${}\geq{}$ Appendix A holds.

Otherwise, we can assume that every summand in $\ast_{L}$ is non-negative. In
that case

$\displaystyle\lx@cref{creftype~refnum}{eq:SA_left}=$
$\displaystyle\operatorname*{\mathrm{E}}_{g\sim\omega}\sum_{(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A}),\,s\colon
g(\operatorname{Set}(\mathbf{x}))\to
C}\lambda(g(\operatorname{Set}(\mathbf{x})),s)f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(s\circ_{\scriptscriptstyle\bot}g(\mathbf{x}))$
$\displaystyle\geq$
$\displaystyle\operatorname*{\mathrm{E}}_{g\sim\omega}\sum_{(f,\mathbf{x})\in\operatorname{tup}(\mathbb{A}),\,s\colon
g(\operatorname{Set}(\mathbf{x}))\to
C}\lambda(g(\operatorname{Set}(\mathbf{x})),s)f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(s\circ_{\scriptscriptstyle\bot}g(\mathbf{x}))\cdot\mathbf{1}\left[g(\mathbf{x})\text{
is defined}\right]$ $\displaystyle=$
$\displaystyle\operatorname*{\mathrm{E}}_{g\sim\omega}\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B}),\,s\colon\operatorname{Set}(\mathbf{y})\to
C}\lambda(\operatorname{Set}(\mathbf{y}),s)f^{\mathbb{A}}(g^{-1}(\mathbf{y}))f^{\mathbb{C}}(s(\mathbf{y}))$
$\displaystyle=$
$\displaystyle\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B}),\,s\colon\operatorname{Set}(\mathbf{y})\to
C}\lambda(\operatorname{Set}(\mathbf{y}),s)\operatorname*{\mathrm{E}}_{g\sim\omega}\left[f^{\mathbb{A}}(g^{-1}(\mathbf{y}))\right]f^{\mathbb{C}}(s(\mathbf{y}))$
$\displaystyle\geq$
$\displaystyle\sum_{(f,\mathbf{y})\in\operatorname{tup}(\mathbb{B}),\,s\colon\operatorname{Set}(\mathbf{y})\to
C}\lambda(\operatorname{Set}(\mathbf{y}),s)f^{\mathbb{B}}(\mathbf{y})f^{\mathbb{C}}(s(\mathbf{y}))=\lx@cref{creftype~refnum}{eq:SA_right},$

where after the first inequality it is still true that all summands are non-
negative, and hence the last inequality follows from the fact that $\omega$ is
an overcast. This concludes the proof that
$\operatorname{maxval}_{k}(\mathbb{A},\mathbb{C})\geq\operatorname{maxval}_{k}(\mathbb{B},\mathbb{C})$.
∎

##  Appendix B Proof of Proposition 5.10

###### Proof.

We reduce to [CRŽ18, Theorem V.1], which shows that bounded treewidth implies
exact solvability for minimisation of VCSPs with $\mathbb{Q}_{\geq
0}\cup\\{\infty\\}$-valued right-hand side structures. We recast our
relaxation into the framework of [CRŽ18], which gives a more fine-grained
relaxation. The SA relaxation in that paper is found in Figure 2. As we
restrict to $k\geq\max_{f\in\sigma}\operatorname{ar}(f)$, in this case
variables $\lambda(f,\mathbf{x},s)$ in [CRŽ18, Figure 2] may be replaced by
variables $\lambda(\operatorname{Set}(\mathbf{x}),s)$ by equation (SA3) and
the inclusion of the dummy function $\rho_{k}$ in $\sigma_{k}$. The linear
programs are now equivalent, except in [CRŽ18] right-hand side
$\sigma$-structures are $\mathbb{Q}_{\geq 0}\cup\\{\infty\\}$-valued, and it
is cast as a minimisation problem.

Let
$K\coloneqq\max_{(f,\mathbf{x})\in\operatorname{tup}(\mathbb{C})}f^{\mathbb{C}}(\mathbf{x})\in\mathbb{Q}_{\geq
0}$. Consider a new $\sigma$-structure $\mathbb{C}^{\prime}$ defined by

$f^{\mathbb{C}^{\prime}}(\mathbf{x})=K-f^{\mathbb{C}}(\mathbf{x}),$

so that $\mathbb{C}^{\prime}$ is $\mathbb{Q}_{\geq 0}\cup\\{\infty\\}$-valued,
and thus a valued $\sigma$-structure in the framework of [CRŽ18].

We have,

$\displaystyle\max\sum_{(f,\mathbf{x})\in\operatorname{tup}{\mathbb{A}},\;s\colon\operatorname{Set}(\mathbf{x})\to
C}\lambda(\operatorname{Set}(\mathbf{x}),s)f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}}(s(\mathbf{x}))=$
$\displaystyle
K\sum_{(f,\mathbf{x})\in\operatorname{tup}{\mathbb{A}}}f^{\mathbb{A}}(\mathbf{x})-\min\sum_{(f,\mathbf{x})\in\operatorname{tup}{\mathbb{A}},\;s\colon\operatorname{Set}(\mathbf{x})\to
C}\lambda(\operatorname{Set}(\mathbf{x}),s)f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{C}^{\prime}}(s(\mathbf{x})).$

The left term does not depend on the LP variables $\lambda(X,s)$. Thus
$\operatorname{SA}_{k}$ relaxation is exact by [CRŽ18, Theorem V.1]. ∎

##  Appendix C Max-CSP vs. Max-Sol on cliques

In [RWŽ21], the PTAS results for Max-CSPs, with non-negative rational-valued
right-hand side structures, applied do certain classes of dense structures as
well. This is because the class of cliques (as a $\\{0,1\\}$-valued
structures) and in fact any class of graphs with $\Omega(n^{2})$ edges, was
shown to be “$\operatorname{tw}$-pliable”. In our case, because we consider
more general right-hand side structures, the definition of “overcasts” and
“$\operatorname{tw}$-pliability” changed to “strong overcasts” and “strong
$\operatorname{tw}$-pliability” accordingly (simply by considering all Max-Sol
right-hand side structures in place of just $\mathbb{Q}_{\geq 0}$-valued
structures). It turns out even the simplest class of dense structures, the
class of cliques, is not strongly $\operatorname{tw}$-pliable.

######  Proposition C.1.

Let $\sigma$ be the signature with one symbol $f$ of arity 2. Let
$\mathcal{A}=\\{\mathbb{K}_{n}\mid n\in\mathbb{N}\\}$ be the class of cliques,
as $\sigma$-structures with $f^{\mathbb{K}_{n}}(x,y)=1$ if $x\neq y$ and $0$
otherwise, for $x,y\in[n]$. Then, $\mathcal{A}$ is not strongly tw-pliable.

###### Proof.

Suppose that $\mathcal{A}$ is strongly tw-pliable. Let $\varepsilon=1/10$.
There exists some $k$ such that for all $n$ there exists a structure
$\mathbb{B}$ with $\operatorname{tw}(\mathbb{B})\leq k-1$ and
$\operatorname{d}_{\mathrm{opt}}(\mathbb{K}_{n},\mathbb{B})\leq\varepsilon$.

Let $n\coloneqq 2k$ and $\mathbb{B}$ be such that
$\operatorname{tw}(\mathbb{B})\leq k$ and
$\operatorname{d}_{\mathrm{opt}}(\mathbb{K}_{n},\mathbb{B})\leq\varepsilon$.
It is an easy exercise that for any graph $G$,
$\chi(G)\leq\operatorname{tw}(G)+1$, and therefore
$\chi(\operatorname{G}(\mathbb{B}))\leq k$, where $\chi(G)$ denotes the
chromatic number of $G$.

Consider the following class of Max-Sol structures: for each $i$, let
$\mathbb{C}_{i}$ be a $\sigma$-structure over the domain
$[i]\cup\\{c_{\bot}\\}$, and let

$f^{\mathbb{C}_{i}}(x,y)=\begin{cases}-\infty&\qquad\text{if $x=y$,
$x,y\in[i]$,}\\\ 0&\qquad\text{if $x=y=c_{\bot}$,}\\\
1&\qquad\text{otherwise.}\end{cases}$

In other words, for a structure $\mathbb{A}$ the instance
$(\mathbb{A},\mathbb{C}_{i})$ asks to colour the vertices of $\mathbb{A}$ with
$i$ colours (or assign it no colour, $c_{\bot}$), such that there are no
monochromatic edges and the total weight of edges with at least one endpoint
coloured is maximised. Then,
$\operatorname{maxval}(\mathbb{K}_{n},\mathbb{C}_{i})=i(n-1)$ for $i\leq n$.
Further, for all $i\geq\chi(\operatorname{G}(\mathbb{B}))$,
$\operatorname{maxval}(\mathbb{B},\mathbb{C}_{i})=\operatorname{maxval}(\mathbb{B},\mathbb{C}_{\chi(\operatorname{G}(\mathbb{B}))})$:
the optimal solution corresponds to any proper colouring of
$\operatorname{G}(\mathbb{B})$ with colours $[i]$. As
$k\geq\chi(\operatorname{G}(\mathbb{B}))$, we have that
$\operatorname{maxval}(\mathbb{K}_{n},\mathbb{C}_{2k})/\operatorname{maxval}(\mathbb{K}_{n},\mathbb{C}_{k})=2$,
but
$\operatorname{maxval}(\mathbb{B},\mathbb{C}_{2k})/\operatorname{maxval}(\mathbb{B}_{n},\mathbb{C}_{k})=1$,
contradicting
$\operatorname{d}_{\mathrm{opt}}(\mathbb{K}_{n},\mathbb{B})\leq\varepsilon$. ∎

In view of Proposition C.1, one may ask whether it is possible to obtain a
PTAS on cliques via different means, not relying on our notion of strong tw-
pliability. It turns ous that this is not possible. This follows from an easy
reduction from the Maximum Clique problem.

######  Lemma C.2 ([Zuc07, Theorem 1.1]).

It is NP-hard to approximate Maximum Clique within a factor
$\mathrm{opt}^{1-\varepsilon}$ for any $\varepsilon>0$. That is, unless P=NP,
for any $\varepsilon>0$ there is no polynomial-time algorithm taking a graph
$G$ and an integer $r$ as input, that can distinguish between the following
cases:

  * •

$G$ has a clique of size at least $r$,

  * •

$G$ has no clique of size $r^{\varepsilon}$.

######  Proposition C.3.

Let $\mathcal{A}=\\{\mathbb{K}_{n}\mid n\in\mathbb{N}\\}$ be the class of
cliques (as defined in Proposition C.1). Then VCSP restricted to instances
$(\mathbb{A},\mathbb{C})$ where $\mathbb{A}\in\mathcal{A}$ and $\mathbb{C}$ is
a Max-Sol structure, does not admit a PTAS unless P=NP.

###### Proof.

We reduce an instance $G$ of Maximum Clique to a suitable VCSP instance. Given
a graph $G$ on $n$ vertices, define a $\sigma$-structure $\mathbb{C}$ over the
domain $V(G)\cup\\{\star\\}\ \cup\\{c_{\bot}\\}$ as follows. Let

$\displaystyle f^{\mathbb{C}}(x,y)=\begin{cases}-\infty&\qquad\text{if $x,y\in
V(G)$ and $xy\not\in E(G)$, or $x=y=\star$}\\\ 1&\qquad\text{if $x=\star$ and
$y\in V(G)$}\\\ 0&\qquad\text{otherwise.}\end{cases}$

It is clear that $\mathbb{C}$ is a Max-Sol structure, and it is easy to see
that $\operatorname{maxval}(\mathbb{K}_{n+1},\mathbb{C})=\mbox{Max-
Clique}(G)$: in any feasible homomorphism from $\mathbb{K}_{n+1}$ to
$\mathbb{C}$, at most one vertex may map to each element in
$V(G)\cup\\{\star\\}$, and vertices that are not mapped to $c_{\bot}$ or
$\star$ have to map to a clique in $G$. The optimal solution is achieved by
mapping exactly one vertex to $\star$, one to each vertex of a maximum clique
in $G$ and the remaining to $c_{\bot}$.

Thus by Lemma C.2, unless P=NP there is no polynomial-time algorithm
approximating $\operatorname{maxval}(\mathbb{K}_{n+1},\mathbb{C})$ within any
sublinear factor, let alone a constant factor approximation or a PTAS. ∎

Finally, we give a simple example showing that there are strongly tw-pliable
(and therefore, by Proposition 5.13, tractable) classes of structures that are
not captured by fractional-treewidth-fragility. Note that this does not
contradict our conjecture made after Theorem 1.2 in Section 1, as the
conjecture is restricted only to classes parametrised by their Gaifman graphs.
The class of structures in the following proposition does _not_ include all
possible structures over the Gaifman graphs.

######  Proposition C.4.

Let $\sigma$ be the signature with one function symbol $f$ of arity 2. Let
$\mathbb{A}_{n}$ be $\sigma$-structure over the domain $[n]$ defined by
$f^{\mathbb{A}_{n}}(x,x)=1$ and $f^{\mathbb{A}_{n}}(x,y)=1/n$ if $x\neq y$,
$x,y\in[n]$. (That is, $\mathbb{A}_{n}$ is clique with loops around each
vertex, loops have weight 1, and simple edges have weight $1/n$.) Then,
$\mathcal{A}=\\{\mathbb{A}_{n}\mid n\in\mathbb{N}\\}$ is strongly tw-pliable
but $\operatorname{G}(\mathcal{A})$ is not fractionally-tw-fragile.

###### Proof.

First note that $\operatorname{G}(\mathcal{A})$ is the class of cliques with a
loop on each vertex. As for any (non-empty) $X\subseteq V(K_{n})$ we have
$\operatorname{tw}(K_{n}-X)=n-1-\lvert X\rvert$, it is easy to see that
$\operatorname{G}(\mathcal{A})$ is not fractionally-treewidth-fragile —
alternatively, it follows from Propositions C.1 and 5.16 that the class of
cliques is not fractionally-treewidth-fragile, and thus neither is the class
of cliques with a loop around each vertex, i.e.
$\operatorname{G}(\mathcal{A})$.

We now show that $\mathcal{A}$ is strongly tw-pliable. Let $\varepsilon>0$ be
small, $k\coloneqq\lceil 2/\varepsilon\rceil$ and $n>k$ arbitrary. We show
that
$\operatorname{d}_{\mathrm{opt}}(\mathbb{A}_{n},\lambda\mathbb{A}_{k})\leq\varepsilon$
where $\lambda\coloneqq\frac{n}{k}$.

Let $\omega$ be a random map from $V(\mathbb{A}_{n})=[n]$ to
$V(\mathbb{A}_{k})=[k]$ and we check that it is an overcast from
$\mathbb{A}_{n}$ to $\lambda\mathbb{A}_{k}$. It is clear that $\omega$ maps
positive tuples to positive tuples. Further, for $e\in E(\mathbb{A}_{k})$ that
is a simple edge (i.e. $e=(x,y)$ for some $x\neq y$),

$\operatorname*{\mathrm{E}}_{g\sim\omega}f^{\mathbb{A}_{n}}(g^{-1}(e))=\frac{1}{n}{n\choose
2}\frac{2}{k^{2}}=\frac{n-1}{k^{2}}=\lambda\frac{1}{k}\cdot(1-1/n).$

For $e\in E(\mathbb{A}_{k})$ that is a loop (i.e. $e=(x,x)$ for some $x$),

$\operatorname*{\mathrm{E}}_{g\sim\omega}f^{\mathbb{A}_{n}}(g^{-1}(e))=\frac{n}{k}+\frac{1}{n}{n\choose
2}\frac{1}{k^{2}}\geq\lambda.$

As $n>\frac{2}{\varepsilon}$, therefore
$\mathbb{A}_{n}\mathrel{\succeq}(1-\varepsilon)\lambda\mathbb{A}_{k}$. By
symmetry (as $k>\frac{2}{\varepsilon}$ also),
$\lambda\mathbb{A}_{k}\mathrel{\succeq}(1-\varepsilon)\mathbb{A}_{n}$. Thus,
$\operatorname{d}_{\mathrm{opt}}(\mathbb{A}_{n},\lambda\mathbb{A}_{k})\leq\varepsilon$
as claimed. It follows that $\mathcal{A}$ is strongly tw-pliable. ∎