# Treewidth-Pliability and PTAS for Max-CSPs††thanks: An extended abstract of
this work will appear in the Proceedings of SODA’21. Stanislav Živný was
supported by a Royal Society University Research Fellowship. Work done while
Miguel Romero was at the University of Oxford. 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.

Miguel Romero
Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez
Santiago, Chile
<EMAIL_ADDRESS>Marcin Wrochna
University of Oxford, UK
<EMAIL_ADDRESS>Stanislav Živný
University of Oxford, UK
<EMAIL_ADDRESS>
###### Abstract

We identify a sufficient condition, _treewidth-pliability_ , that gives a
polynomial-time approximation scheme (PTAS) for a large class of Max-2-CSPs
parametrised by the class of allowed constraint graphs (with arbitrary
constraints on an unbounded alphabet). Our result applies more generally to
the maximum homomorphism problem between two rational-valued structures.

The condition unifies the two main approaches for designing PTASes. One is
Baker’s layering technique, which applies to sparse graphs such as planar or
excluded-minor graphs. The other is based on Szemerédi’s regularity lemma and
applies to dense graphs. We extend the applicability of both techniques to new
classes of Max-CSPs.

Treewidth-pliability turns out to be a robust notion that can be defined in
several equivalent ways, including characterisations via size, treedepth, or
the Hadwiger number. We show connections to the notions of fractional-
treewidth-fragility from structural graph theory, hyperfiniteness from the
area of property testing, and regularity partitions from the theory of dense
graph limits. These may be of independent interest. In particular we show that
a monotone class of graphs is hyperfinite if and only if it is fractionally-
treewidth-fragile and has bounded degree.

##  1 Introduction

The problem of finding a _maximum cut_ in a graph (Max-Cut) is one of the most
studied problems from Karp’s original list of 21 NP-complete problems [Kar72].
While Max-Cut is NP-hard to solve optimally, there is a trivial
$0.5$-approximation algorithm [SG76] and the celebrated $0.878$-approximation
algorithm of Goemans and Williamson [GW95]. Papadimitriou and Yannakakis
established that Max-Cut is Max-SNP-hard [PY91]. By the work of Arora, Lund,
Motwani, Sudan, and Szegedy [Aro+98] this implies that, unless P=NP, there is
no polynomial-time approximation scheme (PTAS) for Max-Cut in general graphs.
However, non-trivial results exist for important special cases. On the one
hand, Max-Cut is solvable exactly in planar graphs, as shown by Hadlock
[Had75], and more generally, Max-Cut admits a PTAS on graph classes excluding
a fixed minor, as shown by Demaine, Hajiaghayi, and Kawarabayashi [DHK05]. On
the other hand, Arora, Karger, and Karpinski showed a PTAS for Max-Cut in
dense graphs [AKK99], where a graph class is dense if every graph in it
contains at least a constant fraction of all possible edges.

Max-Cut is an example of _maximum constraint satisfaction problem_ (Max-CSP),
although a very special one (the alphabet size is $2$, in particular constant,
and every constraint uses the same symmetric predicate “$x\neq y$” of arity
2). Another well-known example is Max-$r$-SAT, with alphabet size 2 and
$r$-ary clauses. Motivated by results on planar, excluded-minor, and dense
graph classes, our goal in this paper is to understand the following question:

> _What structure allows for the existence of a PTAS for Max-CSPs?_

We focus on two computational problems. First, we study the general
$\mbox{Max-}2\mbox{-CSP}(\mathcal{G})$ problem parameterised by the class of
underlying constraint graphs (a.k.a. _primal_ or _Gaifman_ graphs). The input
is a graph $G\in\mathcal{G}$, an alphabet $\Sigma_{v}$ for each vertex, and
for each edge $uv$ a valued constraint
$f_{uv}\colon\Sigma_{u}\times\Sigma_{v}\to\mathbb{Q}_{\geq 0}$. The goal is to
find an assignment $h(v)\in\Sigma_{v}$ maximising
$\sum_{uv}f_{uv}(h(u),h(v))$. Similarly, in
$\mbox{Max-}r\mbox{-CSP}(\mathcal{G})$ a constraint may appear on any
$r$-clique in $G$. The constraints are arbitrary (non-negative) and the
alphabets are not fixed, making the problem very expressive.111One could
attempt to generalise counting problems by maximizing
$\prod_{uv}f_{uv}(h(u),h(v))$ instead, or equivalently its logarithm
$\sum_{uv}\log f_{uv}(h(u),h(v))$. However, the requirement $f_{uv}\geq 0$ and
the approximation ratio change. This changes the complexity: for example,
approximating the number of 3-colourings requires deciding whether there is at
least one in polynomial time, which is NP-hard already in 4-regular planar
graphs [Dai80].

Second, we consider a more general framework called the _maximum homomorphism
problem_ (Max-Hom) of computing the maximum value of any map between two given
$\mathbb{Q}_{\geq 0}$-valued structures $\mathbb{A}$ and $\mathbb{B}$; the
value will be denoted by $\mathrm{opt}(\mathbb{A},\mathbb{B})$ (see Section 2
for precise definitions). Intuitively, the left-hand-side structure describes
the (weighted) scopes of the constraints and the right-hand-side structure
describes the different types of constraints. Following Grohe’s notation
[Gro07], for a class of structures $\mathcal{A}$ we denote by $\mbox{Max-
Hom}(\mathcal{A},-)$ the restriction of Max-Hom to instances
$(\mathbb{A},\mathbb{B})$ with $\mathbb{A}\in\mathcal{A}$ and $\mathbb{B}$
arbitrary. This framework captures the $\mbox{Max-}r\mbox{-CSP}(\mathcal{G})$
problem as a particular case: it is equivalent to $\mbox{Max-
Hom}(\mathcal{A}_{\mathcal{G}}^{(r)},-)$, where by
$\mathcal{A}_{\mathcal{G}}^{(r)}$ we denote the class of all valued structures
with an underlying graph in $\mathcal{G}$ and arity $r$. Another example is
the case of _graph_ Max-CSP, by which we mean a $\mbox{Max-}2\mbox{-CSP}$ that
uses the same symmetric predicate in all constraints (as in Max-Cut or
Max-$q$-Cut); this case is equivalent to $\mbox{Max-Hom}(\mathcal{A},-)$ where
the structures in $\mathcal{A}$ are graphs.

The question of what structure allows to solve Max-CSPs _exactly_ in
polynomial time is well understood. A standard dynamic approach works for
$\mbox{Max-}r\mbox{-CSP}(\mathcal{G})$ when $\mathcal{G}$ is a class of graphs
of bounded treewidth. Grohe, Schwentick, and Segoufin [GSS01] in fact proved
the converse: if $\mathcal{G}$ has unbounded treewidth then
$\mbox{Max-}r\mbox{-CSP}(\mathcal{G})$, in fact already deciding the existence
of a solution satisfying all constraints, cannot be solved in polynomial time
(assuming FPT$\neq$W[1]). Grohe’s theorem [Gro07] then extended it to the more
general framework: for a class of relational (or $\\{0,1\\}$-valued)
structures $\mathcal{A}$ of bounded arity, the decision problem
Hom$(\mathcal{A},-)$ can be solved in polynomial time if and only if the
_cores_ of structures in $\mathcal{A}$ have bounded treewidth. (The core is
the smallest homomorphically equivalent substructure; for example, bipartite
graphs all have the single edge graph $K_{2}$ as a core, so
Hom$(\mathcal{A},-)$ is easy when $\mathcal{A}$ is a class of bipartite
graphs). This was recently extended further to optimisation with valued
structures by Carbonnel, Romero, and Živný [CRZ18, CRZ18a].

$\mbox{Max-}r\mbox{-CSPs}$ do not admit a PTAS in general, since already Max-
Cut does not. On the other hand, the techniques that give PTASes for Max-Cut
on sparse and dense graphs apply more generally (in fact to a variety of
problems beyond Max-CSPs). Our main contribution is a unifying condition,
_treewidth-pliability_ , that captures all known PTASes for
$\mbox{Max-}r\mbox{-CSP}(\mathcal{G})$ and $\mbox{Max-Hom}(\mathcal{A},-)$
problems.

We call a class of structures $\mathcal{A}$ $\operatorname{tw}$-pliable if it
is uniformly close to structures of bounded treewidth. More formally, for any
$\varepsilon>0$ there is a $k=k(\varepsilon)$ such that every structure in
$\mathcal{A}$ has an $\varepsilon$-close structure with treewidth at most $k$.
Here we consider two structures $\mathbb{A}$ and $\mathbb{B}$ to be
$\varepsilon$-close if $\mathrm{opt}(\mathbb{A},\mathbb{C})$ is
$\varepsilon$-close to $\mathrm{opt}(\mathbb{B},\mathbb{C})$ for all
$\mathbb{C}$ (details in Section 2.3; this notion of distance, which we also
characterise combinatorially, may be of independent interest). While the
structure of bounded treewidth is not known and cannot be efficiently
computed, we show that the Sherali-Adams LP relaxation gives a PTAS for
$\mbox{Max-Hom}(\mathcal{A},-)$.

######  Theorem 1.1.

If $\mathcal{A}$ is a $\operatorname{tw}$-pliable class of structures of
bounded arity, then $\mbox{Max-Hom}(\mathcal{A},-)$ admits a PTAS.

We emphasise the generality of Theorem 1.1. Firstly, the computational problem
(Max-Hom) captures many fundamental problems. Secondly, the notion of
pliability captures many previously discovered cases of structures that admit
a PTAS. In particular, we now discuss how Theorem 1.1 extends the
applicability of the two main approaches for obtaining PTASes.

###  1.1 Sparse structures: Baker’s technique and fragility

Perhaps the best known technique for solving problems on planar graphs is
Lipton and Tarjan’s planar separator theorem [LT79] and the divide & conquer
approach it enables [LT80]. It can be used to give a PTAS for Max-CSPs with
fixed alphabet size on planar graphs (this extends to excluded-minor graphs
[AST90] and more [DN16]) of bounded degree.

This approach was superseded by Baker’s technique [Bak94], which provides
better running times and is easily applied to general
$\mbox{Max-}r\mbox{-CSPs}$ on arbitrary planar graphs (see e.g. [KM96]). The
idea is very elegant: we partition a planar graph into Breadth-First-Search
layers, remove every $\ell$-th layer, and show that the remaining components
of $\ell-1$ consecutive layers have bounded treewidth (and so can be solved
exactly). By trying different starting layers we can ensure that the removed
layers intersect an unknown optimal solution at most
$\mathcal{O}(\frac{1}{\ell})$ times, giving a
$1\pm\mathcal{O}(\frac{1}{\ell})$ approximation.

From planar graphs this was extended to graphs of bounded genus by Eppstein
[Epp00] and later to all graph classes excluding a fixed minor by Grohe
[Gro03] and Demaine et al. [DHK05]. The structural property needed for this
approach, originally proved for excluded-minor graphs by DeVos, Ding,
Oporowski, Sanders, Reed, Seymour, and Vertigan [DeV+04], is
$\operatorname{tw}$-_fragility_ : they can be partitioned into any constant
number of parts such that removing any one part leaves a graph of bounded
treewidth. As shown by Hunt, Marathe, and Stearns [MHS97, Hun+98a] (see also
[Hun+98]) as well as Grigoriev and Bodlaender [GB07], the same property
applies to some geometrically-defined graph classes that do not exclude any
minor. One example is intersection graphs of unit disks whose centers are at
least some constant apart (capturing some applications of the closely related
shifting technique of Hochbaum and Maass [HM85] for geometric packing and
covering problems). Another example is 1-planar graphs, or more generally
graphs drawn on a fixed surface with a bounded number of intersections per
edge.

An important generalisation, _fractional- $\operatorname{tw}$-fragility_, was
introduced by Dvořák [Dvo16]: it suffices that the parts whose removal results
in a graph of bounded treewidth are nearly-disjoint (Definition 4.2). This
applies to $d$-dimensional variants of the geometric classes mentioned above
(for any constant $d$), in particular to $d$-dimensional grids, which are not
$\operatorname{tw}$-fragile [BDN18]. For such concrete examples of fragile
classes, known proofs show that the nearly-disjoint parts can be computed
efficiently. A PTAS can then easily be designed from the definition [Dvo16].

We show that the assumption about efficient construction is not needed. We do
this by proving that if $\mathcal{G}$ is _any_
fractionally-$\operatorname{tw}$-fragile class of graphs (intuitively, any
class where a Baker-like technique is known to work), then the class
$\mathcal{A}_{\mathcal{G}}^{(r)}$ of all possible structures with Gaifman
graph in $\mathcal{G}$ and bounded arity $r$ is $\operatorname{tw}$-pliable.

######  Theorem 1.2.

Let $\mathcal{G}$ be a fractionally-$\operatorname{tw}$-fragile class of
graphs. Then $\mathcal{A}_{\mathcal{G}}^{(r)}$ is $\operatorname{tw}$-pliable
for every $r$. Consequently, $\mbox{Max-}r\mbox{-CSP}(\mathcal{G})$ admits a
PTAS.

This captures all graph classes $\mathcal{G}$ where a PTAS for
$\mbox{Max-}r\mbox{-CSP}(\mathcal{G})$ is known.

###  1.2 Dense structures: the regularity lemma

It is perhaps more surprising that dense structures admit a PTAS. Here a class
is _dense_ if a constant factor of all possible constraints is present in
every structure in the class, e.g. graphs with $\Omega(n^{2})$ edges. Arora,
Karger, and Karpinski [AKK99] showed that $\mbox{Max-}r\mbox{-CSPs}$ admit a
PTAS in the dense regime if the alphabet size is constant (in fact Boolean);
de la Vega [Veg96] independently gave a PTAS for dense Max-Cut. Frieze and
Kannan [FK96] proved that these results are essentially possible because of
Szemerédi’s regularity lemma [Sze78]: intuitively, every graph can be
approximated to within an additive $\pm\varepsilon n^{2}$ error by a random
graph (with a constant number of parts, depending on $\varepsilon$ only, so
that the edges between two parts form a uniformly random graph of some
density). For dense graphs, the additive error translates to a relative error,
giving a PTAS. They also showed a variant of the regularity lemma that is
still applicable to $\mbox{Max-}r\mbox{-CSPs}$ with constant alphabet size,
yet avoids its infamous tower-type dependency on $\varepsilon$.

Goldreich, Goldwasser, and Ron [GGR98] connected these results to the area of
_property testing_ , spawning an entirely new direction of research. They gave
constant-time algorithms estimating the optimum value of some graph Max-CSPs.
In fact, Alon, de la Vega, Kannan, and Karpinski [Alo+03] (see also Andersson
and Engebretsen [AE02]) showed that $\mbox{Max-}r\mbox{-CSPs}$ with a fixed
alphabet can be approximated with accuracy $\pm\varepsilon n^{r}$ by sampling
a constant number of vertices (polynomial in $\frac{1}{\varepsilon}$) and
finding the optimum on the resulting (constant-size) induced substructure.

None of these results apply to any $\mbox{Max-}r\mbox{-CSP}(\mathcal{G})$ and
$\mbox{Max-Hom}(\mathcal{A},-)$ problem, that is, to unbounded alphabets. We
give the first such example: undirected graphs with $\Omega(n^{2})$ edges.

######  Theorem 1.3.

Let $c>0$ and let $\mathcal{A}$ be a class of graphs with at least $cn^{2}$
edges. Then $\mathcal{A}$ is $\operatorname{tw}$-pliable. Consequently,
$\mbox{Max-Hom}(\mathcal{A},-)$ admits a PTAS.

(Note here the graphs in $\mathcal{A}$ are input structures, not just Gaifman
graphs of input structures). We also show that this cannot be extended to non-
graph CSPs: already for the class of tournaments—that is, orientations of
complete graphs—a PTAS is impossible, assuming Gap-ETH (Corollary E.5 in
Appendix E).

###  1.3 Robustness of pliability

The notion of treewidth-pliability not only unifies the different existing
algorithmic techniques but it is also quite robust: treewidth-pliability
captures a valued analogue of “homomorphic equivalence” (e.g. bipartite
graphs, or 3-colourable graphs where each edge is contained in exactly one
triangle, cf. Examples D.5, D.6) as well as small edits: if $\mathcal{A}$ is
an pliable class of graphs, say, then the class of graphs obtained by adding
or removing $o(m)$ edges from $m$-edge graphs in $\mathcal{A}$ is again
pliable (Corollary D.4). However, this generality comes at a price. First, we
show that even for fixed alphabet size, although the approximate optimum value
can be found, an approximate solution cannot be constructed (unless
$\text{P}=\text{NP}$, cf. Example D.7). Second, unlike in some of the previous
results for more restricted classes, our result does not give an EPTAS (i.e.,
with the degree of the polynomial time bound independent of $\varepsilon$) for
fixed alphabet size (cf. Question D.8). Finally, the use of strong versions of
the regularity lemma yields tower-type dependencies on the approximation ratio
$\varepsilon$ in the dense case.

In the definition of treewidth-pliability we approximate structures by
comparing their $\mathrm{opt}($) values and we ask them to be close to
structures where the problem can be solved exactly. This is a non-constructive
and very general definition. In fact, it is not inconceivable that this
captures all tractable cases, i.e., that $\mbox{Max-Hom}(\mathcal{A},-)$ has a
PTAS if and only if $\mathcal{A}$ is $\operatorname{tw}$-pliable.
Nevertheless, we show a variety of equivalent combinatorial definitions, which
allow us place a fairly tight bound on what pliability is, structurally.

For classes of the form $\mathcal{A}_{\mathcal{G}}^{(r)}$, that is, if we only
restrict the underlying Gaifman graphs, we show that pliability collapses to
fractional fragility. In this sense we understand the “sparse” setting
exactly.

######  Lemma 1.4.

Let $\mathcal{G}$ be a class of graphs. The following are equivalent, for any
$r\geq 2$:

  * •

$\mathcal{G}$ is fractionally-$\operatorname{tw}$-fragile;

  * •

$\mathcal{A}_{\mathcal{G}}^{(r)}$ is $\operatorname{tw}$-pliable.

In general, we can replace treewidth with other parameters of the Gaifman
graph: size (number of vertices), treedepth $\operatorname{td}$, Hadwiger
number (maximum clique minor size), or maximum connected component size, which
we denote by $\operatorname{cc}$.

######  Theorem 1.5.

Let $\mathcal{A}$ be any class of structures. The following are equivalent:

  *   * •

$\mathcal{A}$ is $\operatorname{td}$-pliable;

  * •

$\mathcal{A}$ is $\operatorname{tw}$-pliable;

  * •

$\mathcal{A}$ is Hadwiger-pliable.

If structures in $\mathcal{A}$ have bounded signatures, then the following are
equivalent to the above as well:

  *   * •

$\mathcal{A}$ is $\operatorname{size}$-pliable;

  * •

$\mathcal{A}$ is $\operatorname{cc}$-pliable.

Classes of structures with bounded signatures (see Section 2 for precise
definitions) correspond to Max-CSP instances with a bounded number of
constraint types; e.g. maximum graph homomorphism. For example any class of
dense graphs as in Theorem 1.3 is in fact $\operatorname{size}$-pliable. An
example of a class with unbounded signatures is any class of the form
$\mathcal{A}_{\mathcal{G}}^{(r)}$. Theorem 1.5 allows us to give concrete and
general examples of classes that are _not_ $\operatorname{tw}$-pliable: the
class of orientations of graphs in $\mathcal{G}$, where $\mathcal{G}$ is _any_
class of unbounded average degree, or any class of 3-regular graphs with
unbounded girth (Lemmas 10.3, 10.8).

Finally, as a side result, we connect _hyperfiniteness_ to fragility. A class
of graphs $\mathcal{G}$ is called _hyperfinite_ if for every $\varepsilon>0$
there is a $k=k(\varepsilon)$ such that in every $G\in\mathcal{G}$ one can
remove an at-most-$\varepsilon$ fraction of edges to obtain a graph with
connected components of size at most $k$. For a monotone class of graphs
(closed under taking subgraphs), hyperfiniteness easily implies bounded
degree. It is an important notion in property testing: many results in sparse
graphs were generalised by the statement that every property of hyperfinite
graphs is testable [NS13]. The idea, originating in the work of Benjamini,
Schramm, and Shapira [BSS08] and Kassidim, Kelner, Nguyen, and Onak [Has+09],
is that following the approach of Lipton and Tarjan, graphs with sufficiently
sublinear separators, such as planar or excluded-minor graphs [AST90], can be
recursively partitioned into bounded-size components, which for bounded-degree
graphs gives hyperfiniteness (see e.g. [CSS09, Cor. 3.2] for a slightly
stronger property, cf. [MS18]). This allows, analogously as in the dense case,
to give a constant-size approximate description of such graphs by sampling
constant-radius balls in them [NS13]. See [Gol17] for a book on property
testing and [KSS19] for a recent improvement for excluded-minor graphs.

We show that a monotone class $\mathcal{G}$ is hyperfinite if and only if it
is fractionally-$\operatorname{tw}$-fragile and has bounded degree. In fact,
replacing the parameter treewidth by the maximum size of a connected component
in a graph, we have:

######  Theorem 1.6.

Let $\mathcal{G}$ be a monotone class of graphs. The following are equivalent,
for any $r\geq 2$:

  * •

$\mathcal{G}$ is hyperfinite;

  * •

$\mathcal{G}$ is fractionally-$\operatorname{tw}$-fragile and has bounded
degree;

  * •

$\mathcal{G}$ is fractionally-$\operatorname{cc}$-fragile;

  * •

$\mathcal{A}_{\mathcal{G}}^{(r)}$ is $\operatorname{cc}$-pliable.

The equivalence of the second and third bullet points was shown by Dvořák
[Dvo16, Observation 15, Corollary 20], while for the third and fourth the
proof is established by the same proof as Lemma 1.4.

###  1.4 Related work

While this paper focuses on $\mbox{Max-}r\mbox{-CSPs}$, Baker’s technique and
the regularity lemma apply to many more problems. In fact Khanna and Motwani
[KM96] argued that most known PTAS algorithms can be derived from three
canonical optimisation problems on planar graphs, the first being Max-CSP and
the latter two being so-called Max-Ones and Min-Ones CSPs (also solvable with
Baker’s technique). One of the very few results that did not fit their
framework was the PTAS for dense Max-Cut.

Generic frameworks extending Baker’s technique include the bidimensionality
theory of Demaine, Fomin, Hajiaghayi, and Thilikos [Dem+05] and its
application in the design of PTASes by Demaine and Hajiaghayi [DH05] (which is
however limited to minor-closed graph classes); monotone FO problems on minor-
closed graph classes by Dawar, Grohe, Kreutzer, and Schweikardt [Daw+06]; and
the very recent idea of Baker games, introduced by Dvořák [Dvo20] (see also
[Dvo18]). The latter gives conditions stronger than
fractional-$\operatorname{tw}$-fragility, but useful for problems beyond Max-
CSPs, and achievable for all examples known to be fractionally fragile.

De la Vega and Karpinski [VK02, VK06] extended the dense approach to subdense
cases ($\Omega(\frac{n^{2}}{\log n})$ edges) for specific problems such as
MaxCut and Max-2-SAT. In contrast, they show that Max-Cut on graphs with
$\Omega(n^{2-\delta})$ edges is hard to approximate, for any $\delta>0$.

The best known approximation algorithm for general $\mbox{Max-}2\mbox{-CSPs}$
is due to Charikar, Hajiaghayi, and Karloff [CHK11] and achieves an
approximation factor of $\mathcal{O}((nq)^{1/3})$, where $n$ is the number of
variables and $q$ is the alphabet size. On the hardness side, Dinur, Fischer,
Kindler, Raz, and Safra [Din+11] showed that
$\mathcal{O}(2^{\log^{1-\delta}(nq)})$-approximation of
$\mbox{Max-}2\mbox{-CSPs}$ is NP-hard. Manurangsi and Moshkovitz [MM15] gave
approximation algorithms for _dense_ $\mbox{Max-}2\mbox{-CSPs}$ with large
alphabet size (but not PTASes). Manurangsi and Raghavendra [MR17] establish a
tight trade-off between running time and approximation ratio for dense
$\mbox{Max-}r\mbox{-CSPs}$ for $r>2$.

CSPs have also been extensively studied for fixed constraint types, i.e.,
$\mbox{Max-Hom}(-,\mathbb{B})$ problems for fixed $\mathbb{B}$. Raghavendra
showed that the best approximation ratio is always achieved by the basic SDP
relaxation [Rag08], assuming Khot’s unique games conjecture [Kho02]. The
exactly solvable cases were characterised by Thapper and Živný [TZ16]. The
approximation factor of graph Max-CSPs was studied by Langberg, Rabani, and
Swamy [LRS06].

###  1.5 Overview

In Section 2, we give formal definitions and present our basic tool: two
structures $\mathbb{A},\mathbb{B}$ have similar values of
$\mathrm{opt}(-,\mathbb{C})$ if and only if there is a certain fractional
cover, which we call an _overcast_ , from $\mathbb{A}$ to $\mathbb{B}$ and
from $\mathbb{B}$ to $\mathbb{A}$. To prove that treewidth-pliability leads to
a PTAS (Theorem 1.1) the main idea is that an overcast allows to show that the
values of $\mathrm{opt}(-,\mathbb{C})$ are still similar when we look at
linear programming relaxations. We delay the details to Section 5.

Section 3 sketches our approach to dense graphs and to Theorem 1.3. In Section
4, we introduce equivalent definitions of fractional fragility and prove
Theorem 1.2 by showing how the definition implies suitable overcasts. This
also allows us to conclude half of Lemma 1.4 and Theorem 1.5, and to outline
the remainder of their proofs.

Sections 5 defines the Sherali-Adams linear programming relaxation and gives
the proof of Theorem 1.1. Section 6 shows the other half of Lemma 1.4 on
pliability vs fragility. Section 7 concludes the second, harder half of
Theorem 1.5. Section 8 shows Theorem 1.6 on hyperfiniteness. Section 9 proves
Theorem 1.3 on dense graphs.

Finally, in Section 10, we provide examples of non-pliable classes. We
conclude with open questions in Section 11.

##  2 Preliminaries

###  2.1 Structures

A _signature_ is a finite set $\sigma$ of (function) symbols $f$, each with a
specified arity $\operatorname{ar}(f)$. We denote by $|\sigma|$ the number of
symbols in the signature $\sigma$. A _structure_ $\mathbb{A}$ over a signature
$\sigma$ (or $\sigma$-structure $\mathbb{A}$, for short) is a finite domain
$A$ together with a function
$f^{\mathbb{A}}:A^{\operatorname{ar}(f)}\to\mathbb{Q}_{\geq 0}$ for each
symbol $f\in\sigma$.

We denote by $A,B,C,\dots$ the domains of structures
$\mathbb{A},\mathbb{B},\mathbb{C},\dots$. For sets $A$ and $B$, we denote by
$B^{A}$ the set of all mappings from $A$ to $B$. We define
$\text{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 by
$\text{tup}(\mathbb{A})_{>0}$ the pairs
$(f,\mathbf{x})\in\text{tup}(\mathbb{A})$ with $f^{\mathbb{A}}(\mathbf{x})>0$.

We denote
$\|\mathbb{A}\|_{\infty}:=\max_{(f,\mathbf{x})\in\text{tup}(\mathbb{A})}f^{\mathbb{A}}(x)$
and
$\|\mathbb{A}\|_{1}:=\sum_{(f,\mathbf{x})\in\text{tup}(\mathbb{A})}f^{\mathbb{A}}(x)$.
For $\lambda\geq 0$ we write $\lambda\mathbb{A}$ for the _rescaled_
$\sigma$-structure with domain $A$ and
$f^{\lambda\mathbb{A}}(\mathbf{x})\vcentcolon=\lambda
f^{\mathbb{A}}(\mathbf{x})$, for $(f,\mathbf{x})\in\text{tup}(\mathbb{A})$.

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 $r\geq 2$ and a class
of graphs $\mathcal{G}$, we denote by $\mathcal{A}_{\mathcal{G}}^{(r)}$ the
class of $\sigma$-structures $\mathbb{A}$ with
$\operatorname{G}(\mathbb{A})\in\mathcal{G}$ and $\operatorname{ar}(f)\leq r$
for every $f\in\sigma$.

The _maximum homomorphism problem_ (Max-Hom) is the following computational
problem. An instance of Max-Hom consists of two structures $\mathbb{A}$ and
$\mathbb{B}$ over the same signature. For a mapping $h:A\to B$, we define
$\operatorname{value}(h)=\sum_{(f,\mathbf{x})\in\text{tup}(\mathbb{A})}f^{\mathbb{A}}(\mathbf{x})f^{\mathbb{B}}(h(\mathbf{x}))$.
The goal is to find the maximum value over all possible mappings $h:A\to
B$.222While called maximum homomorphism, we note that the maximisation is over
all possible maps, not only homomorphisms, i.e. those that map non-zero tuples
into non-zero tuples. We denote this value by
$\mathrm{opt}(\mathbb{A},\mathbb{B})$. Note that when seen as a Max-CSP
instance, the domain of the left-hand side structure $\mathbb{A}$ is the
variable set, while the domain of the right-hand side structure $\mathbb{B}$
is the _alphabet_.

Given a class $\mathcal{A}$ of structures, $\mbox{Max-Hom}(\mathcal{A},-)$ is
the problem restricted to instances $(\mathbb{A},\mathbb{B})$ of Max-Hom with
$\mathbb{A}\in\mathcal{A}$ (it is a promise problem: algorithms are allowed to
do anything when $\mathbb{A}\not\in\mathcal{A}$). Recall that for a class of
graphs $\mathcal{G}$, the problem $\mbox{Max-}r\mbox{-CSP}(\mathcal{G})$ is
equivalent to $\mbox{Max-Hom}(\mathcal{A}_{\mathcal{G}}^{(r)},-)$.333Note that
$\mbox{Max-Hom}(\mathcal{A}_{\mathcal{G}}^{(r)},-)$ is different from the
maximum graph homomorphism problem $\mbox{Max-Hom}(\mathcal{G},-)$. Indeed,
graphs are also structures over the signature $\\{e\\}$ with one symbol of
arity 2 (where $e^{G}(u,v)=[uv\text{ is an edge of }G]$, if the graph is not
weighted). To avoid confusion, we use $\mathcal{G}$ for a class of Gaifman
graphs of some structures and $\mathcal{A}$ for a class of graphs that are
themselves used as input structures.

###  2.2 Overcasts

Before we define pliability formally, it is useful to consider the following
relation. The starting point of all our results is the equivalence of this
relation to a more combinatorial notion: the existence of a certain fractional
cover, which we shall call an _overcast_.

######  Definition 2.1.

Let $\mathbb{A}$ and $\mathbb{B}$ be $\sigma$-structures. We say that
$\mathbb{A}$ _overcasts_ $\mathbb{B}$, denoted
$\mathbb{A}\mathbin{\succeq}\mathbb{B}$ if, for all $\sigma$-structures
$\mathbb{C}$, we have that $\mathrm{opt}(\mathbb{A},\mathbb{C})\ \geq\
\mathrm{opt}(\mathbb{B},\mathbb{C})$.

A distribution over a finite set $U$ is a function $\pi\colon
U\to\mathbb{Q}_{\geq 0}$ such that $\sum_{x\in U}\pi(x)=1$. The support of
$\pi$ is the set $\operatorname{supp}(\pi):=\\{x\in U\colon\pi(x)>0\\}$. We
write $\operatorname*{\mathbb{E}}_{x\sim\pi}f(x)$ for $\sum_{x\in
U}\pi(x)\cdot f(x)$ and $\Pr_{x\sim\pi}[\phi(x)]$ for
$\operatorname*{\mathbb{E}}_{x\sim\pi}[\phi(x)]$, where $[\phi(x)]$ is 1 if
$x$ satisfies the predicate $\phi$ and 0 otherwise.

######  Definition 2.2.

Let $\mathbb{A}$ and $\mathbb{B}$ be $\sigma$-structures. An _overcast_ from
$\mathbb{A}$ to $\mathbb{B}$ is a distribution $\omega$ over $B^{A}$ such that
for each $(f,\mathbf{x})\in\text{tup}(\mathbb{B})$ we have that

$\operatorname*{\mathbb{E}}_{g\sim\omega}f^{\mathbb{A}}(g^{-1}(\mathbf{x}))\
\geq\ f^{\mathbb{B}}(\mathbf{x}).$

Here $f^{\mathbb{A}}(g^{-1}(\mathbf{x}))$ denotes the sum of
$f^{\mathbb{A}}(\mathbf{y})$ over $\mathbf{y}\in g^{-1}(\mathbf{x})\subseteq
A^{\operatorname{ar}(f)}$.

The following is a consequence of Farkas’ Lemma (or LP duality), as shown in
Appendix B.444 The definitions of the $\mathbin{\succeq}$ relation and of an
overcast are analogous to the “improvement” relation and “inverse fractional
homomorphisms” from [CRZ18a]. Here, however, $\mathrm{opt}($) is maximising,
not minimising, so inequalities in definitions are swapped. This has
consequences such as the fact that mappings in the support of an overcast are
in general not homomorphisms (mapping non-zero tuples to non-zero tuples),
unlike for inverse fractional homomorphisms. The proof of Proposition 2.3
nevertheless is identical to the proof of [CRZ18a, Proposition 6].

######  Proposition 2.3.

$\mathbb{A}\mathbin{\succeq}\mathbb{B}$ if and only if there is an overcast
from $\mathbb{A}$ to $\mathbb{B}$.

###  2.3 Pliability

Our definition of pliability involves a notion of distance which may be of
independent interest. It quantifies the _relative_ difference between two
structures (as measured from the right by weighted multicut densities, in the
language of Lovász’ book on graph limits [Lov12, Ch. 12]).

######  Definition 2.4.

The _opt-distance_ between two structures with the same signature is defined
as:

$\mathrm{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B}):=\textstyle\sup_{\mathbb{C}}\left|\ln\mathrm{opt}(\mathbb{A},\mathbb{C})-\ln\mathrm{opt}(\mathbb{B},\mathbb{C})\right|.$

Here $\ln 0=-\infty$ and $\left|\ln 0-\ln 0\right|=0$. Equivalently, we can
compare rescaled structures; by definition of $\succeq$ and the fact that
$\mathrm{opt}(\lambda\mathbb{A},\mathbb{C})=\lambda\mathrm{opt}(\mathbb{A},\mathbb{C})$,
we have:

$\mathrm{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B})=\inf\big{\\{}\varepsilon\bigm{|}\mathbb{A}\,\mathbin{\succeq}\,e^{-\varepsilon}\,\mathbb{B}\
\text{ and }\
\mathbb{B}\,\mathbin{\succeq}\,e^{-\varepsilon}\,\mathbb{A}\,\big{\\}}.$

One may think of $e^{\pm\varepsilon}$ as close to $1\pm\varepsilon$. Formally
$\textstyle 1-\varepsilon\ \leq\ e^{-\varepsilon}\ \leq\
\frac{1}{1+\varepsilon}\ =\ 1-\varepsilon+\mathcal{O}(\varepsilon^{2})$ for
$\varepsilon\geq 0$.

Finally, a class is treewidth-pliable if it is uniformly close to structures
of bounded treewidth:

######  Definition 2.5.

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

Thus to show $\operatorname{tw}$-pliability of various classes, we will
construct overcasts from structures $\mathbb{A}$ in the class to
$(1-\varepsilon)\mathbb{B}$, for some $\mathbb{B}$ of bounded treewidth, and
from $\mathbb{B}$ back to $(1-\varepsilon)\mathbb{A}$.

In this paper we only consider graph parameters:
$\operatorname{size}(\mathbb{A})=|V(\operatorname{G}(\mathbb{A}))|=|A|$,
$\operatorname{cc}(\mathbb{A})$ – the maximum size of a connected component of
$\operatorname{G}(\mathbb{A})$, treedepth $\operatorname{td}(\mathbb{A})$ as
defined in Section 7.3, treewidth $\operatorname{tw}(\mathbb{A})$, and finally
the Hadwiger number $\text{Hadwiger}(\mathbb{A})$, which is the maximum
$K_{k}$ minor of $\operatorname{G}(\mathbb{A})$. The treewidth of a structure
$\mathbb{A}$ is the treewidth of its Gaifman graph:
$\operatorname{tw}(\mathbb{A})=\operatorname{tw}(\operatorname{G}(\mathbb{A}))$,
similarly for other graph parameters. We refer to [Die10] for definitions of
treewidth and minors.

##  3 Dense graphs: sketch of Theorem 1.3

We start with simple examples of dense graphs. Observe that large cliques can
be arbitrarily well approximated by cliques of constant size
$\lceil\frac{2}{\varepsilon}\rceil$ (up to normalising total edge weights).

######  Example 3.1.

Let $0<\varepsilon<1$ and let $n,k\geq\frac{2}{\varepsilon}$. Then
$\mathrm{d}_{\mathrm{opt}}(K_{n},\lambda K_{k})\leq\varepsilon$, for
$\lambda=\binom{n}{2}/\binom{k}{2}$.

###### Proof.

For $n,k\geq 2$, define an overcast $\omega$ by taking a random function
$V(K_{n})\to V(K_{k})$ (each vertex is placed independently uniformly at
random). Then for each $e\in E(K_{k})$,

$\operatorname*{\mathbb{E}}_{g\sim\omega}|g^{-1}(e)|=\sum_{e^{\prime}\in
E(K_{n})}\operatorname*{\mathbb{E}}_{g\sim\omega}[g(e^{\prime})=e]=\binom{n}{2}\frac{2}{k^{2}}=\lambda\cdot\binom{k}{2}\cdot\frac{2}{k^{2}}=(1-\frac{1}{k})\lambda.$

Therefore $K_{n}\mathbin{\succeq}(1-\frac{1}{k})\lambda K_{k}$. Symmetrically
$\lambda K_{k}\mathbin{\succeq}(1-\frac{1}{n})K_{n}$. Since $1-x\geq e^{-2x}$
for $0\leq x\leq\frac{1}{2}$, this means
$\mathrm{d}_{\mathrm{opt}}(K_{n},\lambda K_{k})\leq\frac{2}{\min(n,k)}$.
Consequently if $n,k\geq\frac{2}{\varepsilon}$, then
$\mathrm{d}_{\mathrm{opt}}(K_{n},\lambda K_{k})\leq\varepsilon$. ∎

In particular, this means the class $\mathcal{A}$ consisting of all clique
graphs is size-pliable. This corresponds to an easy PTAS for graph $\mbox{Max-
Hom}(\mathcal{A},-)$: the maximum graph homomorphism from $K_{n}$ to $G$ is
well approximated by finding the maximum graph homomorphism from a constant
size $K_{k}$ to $G$ and mapping $K_{n}$ randomly to the resulting $\leq k$
vertices in $G$. The situation is very different for Densest Subgraph
problems, because they disallow choosing two equal vertices in $G$ (see
Observation E.2).

As another important example, consider Erdős-Rényi random graphs $G(n,p)$ (for
constant $p\in(0,1)$; each pair in $\binom{n}{2}$ becomes an edge
independently with probability $p$). They are similar to each other (and in
fact to $pK_{n}$, as well as to $\lambda K_{k}$ for constant $k$ and suitable
$\lambda$):

######  Example 3.2.

Let $p,\varepsilon>0$ be constants. Let $G_{1},G_{2}$ be independent Erdős-
Rényi random graphs $G(n,p)$. Then
$\Pr[\mathrm{d}_{\mathrm{opt}}(G_{1},G_{2})<\varepsilon]\to 1$ as
$n\to\infty$.

###### Proof sketch.

Let $k$ be a sufficiently large constant depending on $\varepsilon$ only. It
is sufficient to prove that $\Pr[\mathrm{d}_{\mathrm{opt}}(G_{1},\lambda
K_{k})<\frac{\varepsilon}{2}]\to 1$ as $n\to\infty$. The rescaling factor here
is $\lambda:=p\binom{n}{2}/\binom{k}{2}$. The number of edges of $G(n,p)$ is
concentrated around $p\binom{n}{2}$, so just as before a random function gives
$G(n,p)\mathbin{\succeq}(1-\frac{1}{k})\lambda
K_{k}\mathbin{\succeq}e^{-\varepsilon/2}\lambda K_{k}$ with high probability
(tending to 1 as $n\to\infty$).

For the other direction, we use the fact that the number of $k$-cliques in
$G(n,p)$ is concentrated around the mean $\binom{n}{k}p^{\binom{k}{2}}$ and,
more strongly, the number of $k$-cliques containing any given edge of $G(n,p)$
(conditioned on it being an edge) is concentrated around the mean
$\binom{n-2}{k-2}p^{\binom{k}{2}-1}$. The concentration is good enough that
with high probability, _every_ edge of $G(n,p)$ is contained in
$(1\pm\frac{\varepsilon}{4})\binom{n-2}{k-2}p^{\binom{k}{2}-1}$ $k$-cliques
(see e.g. [Spe90]). Thus if we take $\omega$ by mapping $\lambda K_{k}$
injectively to a random $k$-clique in $G(n,p)$, then w.h.p. for each edge $e$
of $G(n,p)$ we have

$\operatorname*{\mathbb{E}}_{g\sim\omega}|g^{-1}(e)|\geq(1-\frac{\varepsilon}{4})\binom{n-2}{k-2}p^{\binom{k}{2}-1}/\binom{n}{k}p^{\binom{k}{2}}=(1-\frac{\varepsilon}{4})\frac{k(k-1)}{n(n-1)}p^{-1}=(1-\frac{\varepsilon}{4})\lambda^{-1}.$

Thus $\lambda K_{k}\mathbin{\succeq}e^{-\varepsilon/2}G_{1}$ and consequently
$\mathrm{d}_{\mathrm{opt}}(G_{1},\lambda K_{k})\leq\frac{\varepsilon}{2}$
w.h.p. ∎

To show Theorem 1.3, we extend the above informal proof to any class of dense
graphs. This is possible because of the _Szemerédi’s regularity lemma_
[Sze78], which, very roughly speaking, guarantees that all such graphs are
random-like. This allows to provide similar bounds on the number of
$k$-cliques containing any given edge, a fact known as the _extension lemma_ ,
though we prove a variant that is somewhat tighter than usual. More details
and the full proof follow in Section 9.

Note that the above proof sketch does not work for random tournaments
(orientations of cliques): if we try to approximate them by the small graph
$\frac{1}{2}\overset{\leftrightarrow}{K_{k}}$ (each arc taken with weight
$\frac{1}{2}$), then every overcast from it to a tournament will always lose
at least half of the total weight. If instead we tried to take a small random
tournament, no overcast to it from the big random tournament would work.
Indeed, Lemma 10.3 in Section 10 shows the class of tournaments is not pliable
(neither are “random tournaments”, i.e. the proof can be adapted to show that
any class which contains a random tournament with constant probability cannot
be pliable) and in fact the problem $\mbox{Max-Hom}(\mathcal{A},-)$ for the
class of tournaments $\mathcal{A}$ is hard to approximate, as we show in Lemma
E.4 in Appendix E. This is why, even though variants of the regularity lemma
exist for directed graphs and even more general structures, we limit our
discussion to undirected graphs (the proofs do extend to $[0,1]$-weighted
undirected graphs, however).

##  4 Fractional fragility: proof of Theorem 1.2

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

######  Definition 4.1.

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 4.2.

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 can analogously define
$(\operatorname{p}\leq k)$-edge-modulators $F\subseteq E(G)$ and
_fractionally- $\operatorname{p}$-edge-fragility_.

One crucial property of fractional fragility is that it allows a dual
definition by a variant of Farkas’ Lemma (cf. Appendix A for details); this is
already implicit in [DS19, Lemma 5].

######  Lemma 4.3.

Let $\mathcal{F}$ be a family of subsets of a set $V$. The following are
equivalent:

  * •

there is an $\varepsilon$-thin distribution $\pi$ of sets in $\mathcal{F}$;

  * •

for all non-negative weights $\left(w(v)\right)_{v\in V}$, there is an
$X\in\mathcal{F}$ such that $w(X)\leq\varepsilon\cdot w(V)$.

Thus a class of graphs $\mathcal{G}$ is
fractionally-$\operatorname{tw}$-fragile if and only if for every
$\varepsilon>0$ there is a $k$ such that for every graph $G\in\mathcal{G}$ and
every vertex-weight function $w$, one can remove a set of vertices of weight
at most $\varepsilon\cdot w(V)$ to obtain a graph with $\operatorname{tw}\leq
k$. Here $w(X)\vcentcolon=\sum_{x\in X}w(x)$.

Another useful property is that the edge version is equivalent to the vertex
version, for most parameters of interest. A parameter is _monotone_ if
$\operatorname{p}(H)\leq\operatorname{p}(G)$ for $H$ a subgraph of $G$. The
proof of the following is in Section 6.

######  Lemma 4.4.

Let $\operatorname{p}$ be a monotone graph parameter such that the average
degree $\frac{2|E(G)|}{|V(G)|}$ of a graph is bounded by a function of
$\operatorname{p}(G)$. Let $\mathcal{G}$ be a class of graphs. Then the
following are equivalent:

  * •

$\mathcal{G}$ is fractionally-$\operatorname{p}$-fragile;

  * •

$\mathcal{G}$ is fractionally-$\operatorname{p}$-edge-fragile;

  * •

$\forall_{\varepsilon>0}\exists_{k}\forall_{G\in\mathcal{G}}\forall_{w\colon
V(G)\to\mathbb{Q}_{\geq 0}}\exists_{X\subseteq V(G)}\ w(X)\leq\varepsilon
w(V(G))\ \text{and}\ \operatorname{p}(G-X)\leq k$;

  * •

$\forall_{\varepsilon>0}\exists_{k}\forall_{G\in\mathcal{G}}\forall_{w\colon
E(G)\to\mathbb{Q}_{\geq 0}}\exists_{F\subseteq E(G)}\ w(F)\leq\varepsilon
w(E(G))\ \text{and}\ \operatorname{p}(G-F)\leq k$.

Dvořák and Sereni [DS19, Theorem 28] showed that graphs of bounded treewidth
are fractionally-$\operatorname{td}$-fragile. It follows from a result of
DeVos et al. [DeV+04, Theorem 1.2] that for every graph $H$, $H$-minor-free
graphs are fractionally-$\operatorname{tw}$-fragile. In fact, as shown by
Dvořák [Dvo20], a proof of van den Heuvel et al. [Heu+17, Lemma 4.1] can be
adapted to show this without the Graph Minors Structure Theorem.

######  Theorem 4.5 ([DS19, DeV+04]).

For every $H$, the class of $H$-minor-free graphs is
fractionally-$\operatorname{tw}$-fragile. For every $k$, the class of graphs
of treewidth at most $k$ is fractionally-$\operatorname{td}$-fragile.

Consequently (cf. [Dvo16, Lemma 12]), the following are equivalent for a class
of graphs $\mathcal{G}$:

  * •

$\mathcal{G}$ is fractionally-$\operatorname{td}$-fragile;

  * •

$\mathcal{G}$ is fractionally-$\operatorname{tw}$-fragile;

  * •

$\mathcal{G}$ is fractionally-Hadwiger-fragile.

###  4.1 Fragility implies pliability

We denote by $G\uplus H$ the disjoint union of graphs $G$ and $H$.

######  Lemma 4.6.

Let $\operatorname{p}$ be a graph parameter such that
$\operatorname{p}(G\uplus H)=\max(\operatorname{p}(G),\operatorname{p}(H))$
for all $G,H$. Let $\mathcal{A}$ be a class of structures of bounded arity $r$
such that the class $\mathcal{G}$ of their Gaifman graphs is
fractionally-$\operatorname{p}$-fragile. Then $\mathcal{A}$ is
$\operatorname{p}$-pliable.

###### Proof.

By definition of fractional-$\operatorname{p}$-fragility,
$\forall_{\varepsilon>0}\exists_{k(\varepsilon)}\forall_{G\in\mathcal{G}}$ $G$
has an $\varepsilon$-thin fractional $(\operatorname{p}\leq k)$-modulator, for
some function $k(\varepsilon)$. For $\varepsilon>0$, let
$\varepsilon^{\prime}:=\frac{\varepsilon}{1+\varepsilon}\cdot\frac{1}{r}$ and
let $k:=k(\varepsilon^{\prime})$. Let $\mathbb{A}\in\mathcal{A}$ be a
structure with Gaifman graph $G\in\mathcal{G}$. By assumption, $G$ has a
fractional $(\operatorname{p}\leq k)$-modulator $\pi$ such that for every
$v\in V(G)$, $\Pr_{X\sim\pi}[v\in X]\leq\varepsilon^{\prime}$. For $X\subseteq
V(G)=A$ in the support of $\pi$, let $\mathbb{B}_{X}$ be the rescaling of
$\mathbb{A}-X$ by a factor of $\pi(X)$; let $\mathbb{B}$ be the disjoint union
of all $\mathbb{B}_{X}$. Since each $X$ in the support of $\pi$ is a
$(\operatorname{p}\leq k)$-modulator and $\operatorname{p}$ is closed under
disjoint union, $\operatorname{p}(\operatorname{G}(\mathbb{B}))\leq k$.

We define overcasts $\omega\colon\mathbb{A}\to\mathbb{B}$ and
$\omega^{\prime}\colon\mathbb{B}\to(1-r\varepsilon^{\prime})\mathbb{A}$. The
first, $\omega$, maps $\mathbb{A}$ identically to each component
$\mathbb{B}_{X}$ of $\mathbb{B}$ with probability $\pi(X)$ (vertices of
$\mathbb{A}$ in $X$ are mapped arbitrarily). The second, $\omega^{\prime}$,
deterministically maps each component $\mathbb{B}_{X}$ of $\mathbb{B}$
identically to $\mathbb{A}$. To check that $\omega^{\prime}$ is indeed an
overcast, consider a tuple $(f,\mathbf{x})\in\text{tup}(\mathbb{A})$. The
tuple is covered by its copies in $\mathbb{B}_{X}$ with weight $\pi(X)\cdot
f^{\mathbb{A}}(X)$ for all $X$ which do not intersect $\mathbf{x}$. In total,
the fraction of $f^{\mathbb{A}}(\mathbf{x})$ lost is hence exactly
$\Pr_{X\sim\pi}[X\cap\mathbf{x}\neq\emptyset]$, which is (by union bound and
by the assumption $|\mathbf{x}|\leq r$) at most $\varepsilon^{\prime}r$. Since
$1-\varepsilon^{\prime}r=\frac{1}{1+\varepsilon}\geq e^{-\varepsilon}$, we
have
$\mathbb{A}\mathbin{\succeq}\mathbb{B}\mathbin{\succeq}(1-\varepsilon^{\prime}r)\mathbb{A}\mathbin{\succeq}e^{-\varepsilon}\mathbb{A}$,
which means $\mathbb{B}$ is a structure at opt-distance $\leq\varepsilon$ from
$\mathbb{A}$. ∎

This concludes Theorem 1.2: structures on
fractionally-$\operatorname{tw}$-fragile graphs are
$\operatorname{tw}$-pliable.

For Lemma 1.4, we need the other direction: that if all structures on Gaifman
graphs in $\mathcal{G}$ are $\operatorname{tw}$-pliable, then $\mathcal{G}$ is
fractionally-$\operatorname{tw}$-fragile. To do this, we consider, for a graph
$G\in\mathcal{G}$, a structure $\mathbb{A}$ where each edge is used by a
different symbol of a signature. If we have a structure $\mathbb{B}$ (of
bounded treewidth) close to $\mathbb{A}$ in opt-distance, this implies
overcasts from $\mathbb{A}$ to $e^{-\varepsilon}\mathbb{B}$ and from
$\mathbb{B}$ to $e^{-\varepsilon}\mathbb{A}$; composing the two gives an
overcast from $e^{+\varepsilon}\mathbb{A}$ to $e^{-\varepsilon}\mathbb{A}$ in
which (since each edge is used by a different symbol) an edge can only be
covered by itself. This shows that the overcasts are mostly injective and that
$\mathbb{B}$, sandwiched between $e^{+\varepsilon}\mathbb{A}$ and
$e^{-\varepsilon}\mathbb{A}$, must be close in edit distance. The bounded
treewidth of $\mathbb{B}$ then implies that the graph $G$ underlying
$\mathbb{A}$ is in fact fractionally-$\operatorname{tw}$-edge-fragile, which
by Lemma 4.4 concludes the proof. Details are deferred to Section 6.

The first half of Theorem 1.5 already follows easily as a corollary of Theorem
4.5, Lemma 4.6 and the following simple observation. Details are deferred to
Section 7.

######  Observation 4.7 (Transitivity of pliability).

Let $\mathcal{A}$ be a class of structures with signatures from a set
$\Sigma$. Suppose $\mathcal{A}$ is $\operatorname{p}$-pliable and that for
each $k$, $\\{\mathbb{A}\colon\operatorname{p}(\mathbb{A})\leq k\\}$ is
$\operatorname{p}^{\prime}$-pliable, where $\mathbb{A}$ runs over all
structures with signatures in $\Sigma$. Then $\mathcal{A}$ is
$\operatorname{p}^{\prime}$-pliable.

The second half of Theorem 1.5 similarly reduces to showing that structures of
bounded treedepth with a bounded signature are $\operatorname{size}$-pliable.
The strategy for the proof is similar to a proof of Nešetřil and Ossona de
Mendez [NM06, Corollary 3.3] that relational structures of bounded treedepth
have bounded cores. However the argument is much more intricate due to the
fact that we consider valued structures: the statement that there are only
finitely many structures of size at most $C$, for every $C$, is not true
anymore. The main difficulty is proving an approximate version of it: we do
this in Section 7.

##  5 Pliable structures admit a PTAS: proof of Theorem 1.1

We first define the Sherali-Adams LP hierarchy [SA90] for Max-Hom. Let
$(\mathbb{A},\mathbb{B})$ be an instance of Max-Hom over a signature $\sigma$
and let $k\geq\max_{f\in\sigma}\operatorname{ar}(f)$. For a tuple
$\mathbf{x}$, we denote by $\text{Set}(\mathbf{x})$ the set of elements
appearing in $\mathbf{x}$. 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{B})$ is the linear program given in Figure 1,
which has one variable $\lambda(X,s)$ for each $X\in\binom{A}{\leq k}$ and
each $s\colon X\to B$.

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

Figure 1: The Sherali-Adams relaxation of level $k$ of
$(\mathbb{A},\mathbb{B})$.

We denote by $\mathrm{opt}_{k}(\mathbb{A},\mathbb{B})$ the optimum value of
this linear program.

######  Observation 5.1.

Let $\mathbb{A}$ be a $\sigma$-structure, $\lambda\geq 0$ and
$k\geq\max_{f\in\sigma}\operatorname{ar}(f)$. Then for all $\sigma$-structures
$\mathbb{C}$, we have
$\mathrm{opt}(\lambda\mathbb{A},\mathbb{C})=\lambda\mathrm{opt}(\mathbb{A},\mathbb{C})$
and
$\mathrm{opt}_{k}(\lambda\mathbb{A},\mathbb{C})=\lambda\mathrm{opt}_{k}(\mathbb{A},\mathbb{C})$.

######  Definition 5.2.

Let $\mathbb{A}$ and $\mathbb{B}$ be $\sigma$-structures and
$k\geq\max_{f\in\sigma}\operatorname{ar}(f)$. We write
$\mathbb{A}\mathbin{\succeq}_{k}\mathbb{B}$ if, for all $\sigma$-structures
$\mathbb{C}$, we have
$\mathrm{opt}_{k}(\mathbb{A},\mathbb{C})\geq\mathrm{opt}_{k}(\mathbb{B},\mathbb{C})$.

The proof of the following is analogous to the proof of [CRZ18a, Proposition
27]. For completeness, it is given in Appendix C.

######  Proposition 5.3.

Let $\mathbb{A}$ and $\mathbb{B}$ be $\sigma$-structures and
$k\geq\max_{f\in\sigma}\operatorname{ar}(f)$. If there is an overcast from
$\mathbb{A}$ to $\mathbb{B}$ then $\mathbb{A}\mathbin{\succeq}_{k}\mathbb{B}$.

Using Observation 5.1 and Proposition 5.3, we are ready to prove the
following.

######  Proposition 5.4.

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

$\mathrm{opt}(\mathbb{A},\mathbb{C})\ \leq\
\mathrm{opt}_{k}(\mathbb{A},\mathbb{C})\ \leq\
(1+\mathcal{O}(\varepsilon))\mathrm{opt}(\mathbb{A},\mathbb{C}).$

###### Proof.

The left-hand side inequality is from the definition of Sherali-Adams. For the
right-hand side inequality, observe first that, by definition of
$\mathrm{d}_{\mathrm{opt}}$,
$\mathbb{A}\mathbin{\succeq}e^{-\varepsilon}\mathbb{B}$ and
$\mathbb{B}\mathbin{\succeq}e^{-\varepsilon}\mathbb{A}$. By Proposition 2.3,
there is an overcast from $\mathbb{B}$ to $e^{-\varepsilon}\mathbb{A}$, so by
Proposition 5.3, it follows that
$\mathbb{B}\mathbin{\succeq}_{k}e^{-\varepsilon}\mathbb{A}$. By Observation
5.1, we have that $\mathrm{opt}_{k}(\mathbb{B},\mathbb{C})\geq
e^{-\varepsilon}\mathrm{opt}_{k}(\mathbb{A},\mathbb{C})$. Since
$\operatorname{tw}(\mathbb{B})\leq k$, we have
$\mathrm{opt}_{k}(\mathbb{B},\mathbb{C})=\mathrm{opt}(\mathbb{B},\mathbb{C})$
– this follows, for example, from [CRZ18a, Theorem 33].555Our definition of
the LP slightly differs from [CRZ18, CRZ18a], where there are additional
variables $\lambda(f,\mathbf{x},s)$ associated with tuples $(f,\mathbf{x})$
with $f^{\mathbb{A}}(\mathbf{x})>0$. However, since we are assuming without
loss of generality that $k\geq\max_{f\in\sigma}\operatorname{ar}(f)$, the two
definitions are equivalent.  Since moreover
$\mathbb{A}\mathbin{\succeq}e^{-\varepsilon}\mathbb{B}$, by Observation 5.1,
it follows that $\mathrm{opt}(\mathbb{A},\mathbb{C})\geq
e^{-\varepsilon}\mathrm{opt}(\mathbb{B},\mathbb{C})$. Together,
$\mathrm{opt}(\mathbb{A},\mathbb{C})\geq
e^{-\varepsilon}\mathrm{opt}(\mathbb{B},\mathbb{C})=e^{-\varepsilon}\mathrm{opt}_{k}(\mathbb{B},\mathbb{C})\geq
e^{-2\varepsilon}\mathrm{opt}_{k}(\mathbb{A},\mathbb{C})$. Hence
$\mathrm{opt}_{k}(\mathbb{A},\mathbb{C})\leq
e^{2\varepsilon}\mathrm{opt}(\mathbb{A},\mathbb{C})$. ∎

Since $\mathrm{opt}_{k}(\mathbb{A},\mathbb{C})$ can be computed in time
$(|A|\cdot|C|)^{\mathcal{O}(k)}$, this concludes the proof of Theorem 1.1.

##  6 Pliability vs fragility: proof of Lemma 1.4

We need the following lemma, already advertised in Section 4: vertex and edge
variants of fractional fragility are equivalent.

######  Lemma (Lemma 4.4 restated).

Let $\operatorname{p}$ be a monotone graph parameter such that the average
degree $\frac{2|E(G)|}{|V(G)|}$ of a graph is bounded by a function of
$\operatorname{p}(G)$. Let $\mathcal{G}$ be a class of graphs. Then the
following are equivalent:

  1. (i)

$\mathcal{G}$ is fractionally-$\operatorname{p}$-fragile;

  2. (ii)

$\mathcal{G}$ is fractionally-$\operatorname{p}$-edge-fragile;

  3. (iii)

$\forall_{\varepsilon>0}\exists_{k}\forall_{G\in\mathcal{G}}\forall_{w\colon
V(G)\to\mathbb{Q}_{\geq 0}}\exists_{X\subseteq V(G)}\ w(X)\leq\varepsilon
w(V(G))\ \text{and}\ \operatorname{p}(G-X)\leq k$;

  4. (iv)

$\forall_{\varepsilon>0}\exists_{k}\forall_{G\in\mathcal{G}}\forall_{w\colon
E(G)\to\mathbb{Q}_{\geq 0}}\exists_{F\subseteq E(G)}\ w(F)\leq\varepsilon
w(E(G))\ \text{and}\ \operatorname{p}(G-F)\leq k$.

###### Proof.

As discussed in Section 4, $(i)$ is equivalent to $(iii)$ and $(ii)$ is
equivalent to $(iv)$ by Lemma 4.3.

It is easy to see that $(i)$ implies $(iv)$: suppose 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 $\pi$. Let $w\colon
E(G)\to\mathbb{Q}_{\geq 0}$ be any edge-weight function. If we take a set $X$
from the distribution $\pi$ and remove the set $F$ of all edges incident to
$X$, this yields a graph with $\operatorname{p}(G-F)\leq k$. Every vertex is
in $X$ with probability $\leq\varepsilon$, so every edge is in $F$ with
probability $\leq 2\varepsilon$. Hence the expected weight of $F$ is $\leq
2\varepsilon w(E(G))$. So there exists a set $F\subseteq E(G)$ such that
$w(F)\leq 2\varepsilon w(E(G))$ and $\operatorname{p}(G-F)\leq k$.

It remains to show that $(iv)$ implies $(iii)$. Let
$f\colon\mathbb{N}\to\mathbb{N}$ be such that $\frac{2|E(G)|}{|V(G)|}\leq
f(\operatorname{p}(G))$ for all graphs $G$.

We first show that $(iv)$ implies that $\mathcal{G}$ has bounded _maximum
average degree_ $\operatorname{mad}(G):=\max_{H\subseteq
G}\frac{2|E(H)|}{|V(H)|}$. Indeed, let $k:=k(\varepsilon)$ be a number
satisfying $(iv)$ for $\varepsilon=\frac{1}{2}$. Then for any
$G\in\mathcal{G}$ and any $H\subseteq G$, let $w\colon E(G)\to\mathbb{Q}_{\geq
0}$ assign 1 to edges in $H$ and 0 to edges not in $H$. By assumption there is
a set $F\subseteq E(G)$ such that $w(F)\leq\varepsilon w(E(G))$ and
$\operatorname{p}(G-F)\leq k$. Let $F^{\prime}:=F\cap E(H)$; then
$|F^{\prime}|=w(F)\leq\varepsilon w(E(G))=\varepsilon|E(H)|$ and
$\operatorname{p}(H-F^{\prime})\leq\operatorname{p}(G-F)\leq k$. Hence
$(1-\varepsilon)|E(H)|\leq|E(H-F^{\prime})|\leq\frac{f(k)}{2}\cdot|V(H-F^{\prime})|$,
which means
$\frac{2|E(H)|}{|V(H)|}\leq\frac{f(k(\varepsilon))}{1-\varepsilon}=2f(k(\frac{1}{2}))$.
That is, every subgraph $H$ of every graph $G$ in $\mathcal{G}$ has average
degree at most $D:=2f(k(\frac{1}{2}))$.

This implies that every subgraph has some vertex of degree at most $D$ (this
is called the _degeneracy_ of graph: it is upper bounded by
$\operatorname{mad}$). Hence every graph $G$ in $\mathcal{G}$ has an
orientation $\vec{G}$ with maximum in-degree at most $D$ (obtained by
iteratively finding a vertex of degree at most $D$, orienting all remaining
edges towards it, and removing the vertex).

To show $(iii)$, let $\varepsilon>0$, $k^{\prime}:=k(\frac{\varepsilon}{D})$,
$G\in\mathcal{G}$. Choose an orientation $\vec{G}$ of $G$ with maximum in-
degree at most $D$. Given $w\colon V(G)\to\mathbb{Q}_{\geq 0}$, we can define
$w^{\prime}\colon E(G)\to\mathbb{Q}_{\geq 0}$ as $w^{\prime}(uv):=w(v)$ if
$uv$ is directed towards $v$. By assumption, there is a set of edges $F$ such
that $\operatorname{p}(G-F)\leq k^{\prime}$ and

$w^{\prime}(F)\leq\frac{\varepsilon}{D}w^{\prime}(E(G)).$

Let $X:=\\{v\colon\exists\,uv\in F\text{ directed towards }v\\}$; then
$G-X\subseteq G-F$, so $\operatorname{p}(G-X)\leq k^{\prime}$. Note that

$w^{\prime}(E(G))=\sum_{\vec{uv}\in E(\vec{G})}w(v)=\sum_{v\in
V(G)}\operatorname{in-deg}(v)\cdot w(v)\leq D\cdot w(V(G))$

and

$w^{\prime}(F)=\sum_{\vec{uv}\in F}w(v)\geq\sum_{v\in X}w(v)=w(X)$

Hence

$w(X)\leq
w^{\prime}(F)\leq\frac{\varepsilon}{D}w^{\prime}(E(G))\leq\varepsilon\cdot
w(V(G)).$

This concludes the proof that $(iv)$ implies $(iii)$. ∎

We are now ready to show Lemma 1.4: pliability collapses to fragility when we
only restrict Gaifman graphs (and arity). We prove this here for any
reasonable parameter, including $\operatorname{tw}$ and $\operatorname{cc}$;
the conclusion is the edge variant of fractional fragility, but the two are
equivalent by Lemma 4.4.

######  Lemma 6.1 (Lemma 1.4 more generally).

Let $\operatorname{p}$ be a monotone graph parameter such that
$\operatorname{p}(G\uplus H)=\max(\operatorname{p}(G),\operatorname{p}(H))$.
For every integer $r\geq 2$, a class of graph $\mathcal{G}$ is
fractionally-$\operatorname{p}$-edge-fragile if and only if
$\mathcal{A}_{\mathcal{G}}^{(r)}$ is $\operatorname{p}$-pliable.

###### Proof.

If $\mathcal{G}$ is fractionally-$\operatorname{p}$-fragile, then by Lemma 4.6
$\mathcal{A}_{\mathcal{G}}^{(r)}$ is $\operatorname{p}$-pliable.

For the other direction, suppose $\mathcal{A}_{\mathcal{G}}^{(r)}$ is
$\operatorname{p}$-pliable:

$\forall_{\varepsilon>0}\exists_{k(\varepsilon)}\forall_{\mathbb{A}\in\mathcal{A}_{\mathcal{G}}^{(r)}}\exists_{\mathbb{B}\vphantom{\mathcal{A}_{\mathcal{G}}^{(r)}}}\
\operatorname{p}(\mathbb{B})\leq k\text{ and
}\mathrm{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B})\leq\varepsilon.$

Let $\varepsilon>0$ and let $k:=k(\frac{\varepsilon}{2})$. For a graph
$G\in\mathcal{G}$, let $\sigma$ be the signature with a different binary
symbol $f_{e}$ for each $e\in E(G)$. Let $\mathbb{A}$ be the
$\sigma$-structure with domain $V(G)$ and values $f_{e}^{\mathbb{A}}(u,v)=1$
if $\\{u,v\\}=e$, 0 otherwise. (The arity can be increased to exactly $r$ by
adding dummy or repeated variables). By assumption, there is a
$\sigma$-structure $\mathbb{B}$ such that $\operatorname{p}(\mathbb{B})\leq k$
and
$\mathrm{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B})\leq\frac{\varepsilon}{2}$.
Let $\omega,\omega^{\prime}$ be overcasts from $\mathbb{A}$ to
$\exp(-\frac{\varepsilon}{2})\cdot\mathbb{B}$ and from $\mathbb{B}$ to
$\exp(-\frac{\varepsilon}{2})\cdot\mathbb{A}$, respectively.

For
$g\in\operatorname{supp}(\omega),g^{\prime}\in\operatorname{supp}(\omega^{\prime})$,
let $F_{gg^{\prime}}\subseteq E(G)$ be the subset of edges $e$ such that
$g^{\prime}(g(e))\neq e$ or $f^{\mathbb{B}}_{e}(g(e))=0$. (For an edge $e=uv$
we write $g(e)$ for the edge $g(u)g(v)$). Since $g^{\prime}\circ g$ is the
identity on $E(G)-F_{gg^{\prime}}$, the functions $g^{\prime}$ and $g$ are
bijections between this set and a subset of edges of
$\operatorname{G}(\mathbb{B})$. Hence $G-F_{gg^{\prime}}$ is isomorphic to a
subgraph of $\operatorname{G}(\mathbb{B})$, which implies
$\operatorname{p}(G-F_{gg^{\prime}})\leq k$.

Let $e\in E(G)$. We claim that $\Pr\limits_{\begin{subarray}{c}g\sim\omega\\\
g^{\prime}\sim\omega^{\prime}\end{subarray}}[e\in
F_{gg^{\prime}}]\leq\varepsilon$. This holds essentially because the
composition of $\omega$ and $\omega^{\prime}$ is an overcast from $\mathbb{A}$
to $\exp(-\varepsilon)\cdot\mathbb{A}$ and because the only edge with non-zero
value of $f^{\mathbb{A}}_{e}$ is $e$ itself. Formally, since $\omega$ is an
overcast, we have:

$\text{for each }e_{B}\in
E(\operatorname{G}(\mathbb{B}))\quad\quad\operatorname*{\mathbb{E}}_{g\sim\omega}f^{\mathbb{A}}_{e}(g^{-1}(e_{B}))\geq\exp(-\textstyle\frac{\varepsilon}{2})f_{e}^{\mathbb{B}}(e_{B}).$

Note that by construction of $\mathbb{A}$,
$f^{\mathbb{A}}_{e}(g^{-1}(e_{B}))=[g(e)=e_{B}]$. Hence for each $e_{B}\in
E(\operatorname{G}(\mathbb{B}))$,

$\operatorname*{\mathbb{E}}_{g\sim\omega}[g(e)=e_{B}]\geq\exp(-\textstyle\frac{\varepsilon}{2})f_{e}^{\mathbb{B}}(e_{B}).$

Moreover, since $\omega^{\prime}$ is an overcast, we have:

$\operatorname*{\mathbb{E}}_{g^{\prime}\sim\omega^{\prime}}f^{\mathbb{B}}_{e}(g^{\prime-1}(e))\geq\exp(-\textstyle\frac{\varepsilon}{2})f_{e}^{\mathbb{A}}(e).$

That is:

$\operatorname*{\mathbb{E}}_{g^{\prime}\sim\omega^{\prime}}\sum_{\begin{subarray}{c}e_{B}\in
E(\operatorname{G}(\mathbb{B}))\\\
g^{\prime}(e_{B})=e\end{subarray}}f^{\mathbb{B}}_{e}(e_{B})\geq\exp(-\textstyle\frac{\varepsilon}{2}).$

Putting the two together:

$\displaystyle\Pr_{\begin{subarray}{c}g\sim\omega\\\
g^{\prime}\sim\omega^{\prime}\end{subarray}}[e\not\in F_{gg^{\prime}}]$
$\displaystyle=\Pr_{\begin{subarray}{c}g\sim\omega\\\
g^{\prime}\sim\omega^{\prime}\end{subarray}}[g^{\prime}(g(e))=e\text{ and
}g(e)\in E(\operatorname{G}(\mathbb{B}))]$
$\displaystyle=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}g\sim\omega\\\
g^{\prime}\sim\omega^{\prime}\end{subarray}}\sum_{\begin{subarray}{c}e_{B}\in
E(\operatorname{G}(\mathbb{B}))\\\
g^{\prime}(e_{B})=e\end{subarray}}[g(e)=e_{B}]$
$\displaystyle\geq\operatorname*{\mathbb{E}}_{g^{\prime}\sim\omega^{\prime}}\sum_{\begin{subarray}{c}e_{B}\in
E(\operatorname{G}(\mathbb{B}))\\\
g^{\prime}(e_{B})=e\end{subarray}}\exp(-\textstyle\frac{\varepsilon}{2})f_{e}^{\mathbb{B}}(e_{B})$
$\displaystyle\geq\exp(-\varepsilon)\geq 1-\varepsilon.$

Therefore, we obtained a distribution of edge sets $F_{gg^{\prime}}\subseteq
E(G)$ such that $\operatorname{p}(G-F_{gg^{\prime}})\leq k$ satisfying
$\Pr\limits_{\begin{subarray}{c}g\sim\omega\\\
g^{\prime}\sim\omega^{\prime}\end{subarray}}[e\in
F_{gg^{\prime}}]\leq\varepsilon$. This is an $\varepsilon$-thin fractional
$(\operatorname{p}\leq k)$-edge-modulator. ∎

##  7 From Hadwiger- to size-pliability: proof of Theorem 1.5

In this section, we prove Theorem 1.5: pliability with respect to different
parameters yields equivalent definitions.

###  7.1 Treewidth-, treedepth-, and Hadwiger-pliability

As mentioned in Section 4, the first half of Theorem 1.5, that is, the
equivalence of $\operatorname{p}$-pliability for
$\operatorname{p}\in\\{\operatorname{tw},\operatorname{td},\text{Hadwiger}\\}$,
follows easily from the equivalence of fractional-$\operatorname{p}$-fragility
for these parameters (Theorem 4.5), the fact that fragility implies pliability
(Lemma 4.6), and transitivity of pliability, in the following sense.

######  Observation (Transitivity of pliability, Lemma 4.7 restated).

Let $\mathcal{A}$ be a class of structures with signatures from a set
$\Sigma$. Suppose $\mathcal{A}$ is $\operatorname{p}$-pliable and for each $k$
$\\{\mathbb{A}\colon\operatorname{p}(\mathbb{A})\leq k\\}$ is
$\operatorname{p}^{\prime}$-pliable, where $\mathbb{A}$ runs over all
structures with signatures in $\Sigma$. Then $\mathcal{A}$ is
$\operatorname{p}^{\prime}$-pliable.

###### Proof.

Suppose a class $\mathcal{A}$ is $\operatorname{p}$-pliable. Then every
$\mathbb{A}\in\mathcal{A}$ is $\frac{\varepsilon}{2}$-close (in
$\mathrm{d}_{\mathrm{opt}}$ distance) to some $\mathbb{B}$ with
$\operatorname{p}(\mathbb{B})\leq k$ (for some $k$ depending on
$\frac{\varepsilon}{2}$). By assumption, every $\mathbb{B}$ with
$\operatorname{p}(\mathbb{B})\leq k$ is $\frac{\varepsilon}{2}$-close to some
$\mathbb{C}$ with $\operatorname{p}^{\prime}(\mathbb{C})\leq k^{\prime}$ (for
some $k^{\prime}$ depending on $\frac{\varepsilon}{2}$ and $k$). Hence
$\mathbb{A}$ is $\varepsilon$-close to some structure $\mathbb{C}$ with
$\operatorname{p}^{\prime}(\mathbb{C})\leq
k^{\prime}(\frac{\varepsilon}{2},k(\frac{\varepsilon}{2}))$, which only
depends on $\varepsilon$. ∎

######  Corollary 7.1.

Let $\mathcal{A}$ be any class of structures. The following are equivalent:

  * •

$\mathcal{A}$ is $\operatorname{td}$-pliable;

  * •

$\mathcal{A}$ is $\operatorname{tw}$-pliable;

  * •

$\mathcal{A}$ is Hadwiger-pliable.

###### Proof.

Since $\operatorname{td}(G)\geq\operatorname{tw}(G)+1\geq\text{Hadwiger}(G)$
for any graph $G$, each bullet point implies the next. It suffices to show
that Hadwiger-pliability implies $\operatorname{td}$-pliability. By
Observation 4.7 it suffices to show that for every $k$, the class
$\mathcal{A}$ of all structures with Hadwiger number at most $k$ (and
arbitrary signatures) is $\operatorname{td}$-pliable. These are structures
whose Gaifmann graphs exclude the clique $K_{k+1}$ as a minor. Their Gaifman
graphs are thus fractionally-$\operatorname{td}$-fragile by Theorem 4.5. Since
their Gaifman graphs do not include cliques $K_{k+1}$ the arity of symbols
with non-zero tuples is bounded by $k$. By Lemma 4.6, this implies that
$\mathcal{A}$ is $\operatorname{td}$-pliable (high-arity symbols with no non-
zero tuples can be ignored). ∎

###  7.2 From cc-pliability to size-pliability

To show the second half of Theorem 1.5, i.e. the equivalence of
$\operatorname{td}$-pliability, $\operatorname{cc}$-pliability, and
$\operatorname{size}$-pliability (for structures with bounded signatures), it
will be easier to first focus on the latter two. Since there are only finitely
many distinct signatures of bounded size and arity, we can focus on a single
fixed signature (as finite unions of pliable classes are pliable).

Proving equivalence of $\operatorname{cc}$-pliability and
$\operatorname{size}$-pliability would be trivial if there were only a bounded
number of distinct values of tuples, since then there can be only a bounded
number of components up to isomorphism, and isomorphic components can be
merged.

######  Observation 7.2.

For any structure $\mathbb{A}$ and numbers
$\lambda_{1},\dots,\lambda_{n}\in\mathbb{Q}_{\geq 0}$, the disjoint union
$\lambda_{1}\mathbb{A}\uplus\dots\uplus\lambda_{n}\mathbb{A}$ is equivalent
(i.e. at $\mathrm{d}_{\mathrm{opt}}$-distance zero) to $\lambda\mathbb{A}$,
where $\lambda=\lambda_{1}+\dots+\lambda_{n}$.

###### Proof.

An overcast in one direction deterministically maps each component
$\lambda_{i}\mathbb{A}$ to $\lambda\mathbb{A}$ identically. An overcast in the
other direction maps $\lambda\mathbb{A}$ to the component
$\lambda_{i}\mathbb{A}$ with probability $\lambda_{i}/\lambda$. ∎

For a structure $\mathbb{A}$ with components of bounded size and
$\mathbb{Q}_{\geq 0}$-values, we can try to change the values slightly to find
a structure $\mathbb{B}$ at small edit distance which uses a bounded number of
different values (and then proceed as above). This works if the ratio of the
maximum value to the minimum non-zero value is bounded. If this ratio is
large, we could try to change the extremely small values to zero, hoping the
edit distance is small (relative to the extremely large values). However, this
does not always work: consider structures $\mathbb{A}$ with few large values
and many small values (for example a structure having $2^{i}$ tuples of value
$2^{n-i}$, for $i=0\dots n$). So the general case cannot be reduced to the
case of finitely many distinct values just by finding a structure close in
edit distance. Nevertheless, instead of requiring the modified structure
$\mathbb{B}$ to have a bounded number of components up to isomorphism, it
suffices to require a bounded number of components up to rescaling (two
structures $\mathbb{B}_{1},\mathbb{B}_{2}$ being the same up to rescaling if
$\mathbb{B}_{1}=\lambda\mathbb{B}_{2}$ for some $\lambda>0$). This minor
weakening turns out to be sufficient to fix our problem. We formalise this
first as a statement on sequences of vectors of bounded dimension (which will
encode a sequence of components of bounded size).

######  Lemma 7.3.

Let $d\in\mathbb{N},\varepsilon>0$. There is a $k$ such that for every
sequence of vectors $v^{(1)},\dots,v^{(n)}\in\mathbb{Q}_{\geq 0}^{d}$, there
is a sequence $w^{(1)},\dots,w^{(n)}\in\mathbb{Q}_{\geq 0}^{d}$ such that for
each coordinate $i=1,\dots,d$, ${\sum_{j=1\dots
n}|v^{(j)}_{i}-w^{(j)}_{i}|}\leq\varepsilon{\sum_{j=1\dots n}v^{(j)}_{i}}$,
and such that up to rescaling, there are only $k$ distinct vectors in
$w^{(1)},\dots,w^{(n)}$.

###### Proof.

The proof is by induction on $d$. Let $d\in\mathbb{N},\varepsilon>0$ and
consider a sequence $v_{1},\dots,v_{n}\in\mathbb{Q}_{\geq 0}^{d}$. For $d=1$,
the sequence already has only one vector up to rescaling (or two, if it
contains the zero vector), so let $d\geq 2$.

Let $J=\\{1,\dots,n\\}$. For a subset $X\subseteq J$, denote
$\textrm{mass}_{i}(X):=\sum_{j\in X}v^{(j)}_{i}$. We focus on the first two
coordinates and in particular the ratio of the second to the first. For
$c\in\mathbb{R}$, let $J_{<c}:=\\{j\in J\colon v^{(j)}_{2}<c\cdot
v^{(j)}_{1}\\}$. Define $J_{\leq c},J_{>c},J_{\geq c}$ analogously.

Let $c$ be maximum such that
$\textrm{mass}_{2}(J_{<c})\leq\frac{\varepsilon}{3}\cdot\textrm{mass}_{2}(J)$.
For $j\in J_{<c}$, let $w_{j}$ be the vector obtained from $v_{j}$ be zeroing
the 2nd coordinate. The resulting difference is

$\sum_{j\in
J_{<c}}|v^{(j)}_{2}-w^{(j)}_{2}|\leq\frac{\varepsilon}{3}\sum_{j\in
J}v^{(j)}_{2}.$

By maximality of $c$ we have

$\textrm{mass}_{2}(J_{\leq
c})>\frac{\varepsilon}{3}\cdot\textrm{mass}_{2}(J).$

Observe that the left hand side can be bounded as follows:

$\textrm{mass}_{2}(J_{\leq c})\leq c\cdot\textrm{mass}_{1}(J_{\leq c})\leq
c\cdot\textrm{mass}_{1}(J)$

and similarly the right hand side can be bounded as follows, for
$c^{\prime}:=c\cdot\frac{3d}{\varepsilon^{2}}$:

$\frac{\varepsilon}{3}\cdot\textrm{mass}_{2}(J)\geq\frac{\varepsilon}{3}\cdot\textrm{mass}_{2}(J_{\geq
c^{\prime}})\geq c\cdot\frac{d}{\varepsilon}\cdot\textrm{mass}_{1}(J_{\geq
c^{\prime}}).$

Altogether, this implies

$c\cdot\textrm{mass}_{1}(J)>c\cdot\frac{d}{\varepsilon}\cdot\textrm{mass}_{1}(J_{\geq
c^{\prime}}),$

which after rearranging gives

$\textrm{mass}_{1}(J_{\geq
c^{\prime}})<\frac{\varepsilon}{d}\cdot\textrm{mass}_{1}(J).$

For $j\in J_{\geq c^{\prime}}$, let $w_{j}$ be the vector obtained from
$v_{j}$ by zeroing the 1st coordinate. The resulting difference is $\sum_{j\in
J_{\geq
c^{\prime}}}|v^{(j)}_{1}-w^{(j)}_{1}|\leq\frac{\varepsilon}{d}\sum_{j\in
J}v^{(j)}_{1}$.

The only remaining vectors, in $J_{mid}:=J\setminus(J_{<c}\cup J_{\geq
c^{\prime}})$, satisfy $c\cdot v^{(1)}\leq v^{(2)}<c^{\prime}\cdot v^{(1)}$.
We can round down their 2nd coordinate to $c\cdot v^{(1)}$ times an integer
power of $e^{\varepsilon/3}$. That is, for $j\in J_{mid}$, let $w_{j}$ be the
vector obtained from $v_{j}$ by decreasing the 2nd coordinate to
$w^{(j)}_{2}:=c\cdot e^{a\varepsilon/3}\cdot v^{(j)}_{1}$ with
$a\in\mathbb{N}$ maximum such that $w^{(j)}_{2}\leq v^{(j)}_{2}$. Observe that
$a\geq 0$ and since $c\cdot e^{a\varepsilon/3}\cdot v^{(j)}_{1}\leq
v^{(j)}_{2}\leq c^{\prime}\cdot v^{(j)}_{1}$, we have
$e^{a\varepsilon/3}\leq\frac{c^{\prime}}{c}=\frac{3d}{\varepsilon^{2}}$ and
thus $a\leq\frac{3}{\varepsilon}\cdot\ln(\frac{3d}{\varepsilon^{2}})$. Note
also that $1\geq\frac{w^{(j)}_{2}}{v^{(j)}_{2}}>e^{-\varepsilon/3}$, hence
$\frac{|v^{(j)}_{2}-w^{(j)}_{2}|}{v^{(j)}_{2}}\leq
1-e^{-\varepsilon/3}<\frac{\varepsilon}{3}$, so the resulting difference is
$\sum_{j\in
J_{mid}}|v^{(j)}_{2}-w^{(j)}_{2}|\leq\frac{\varepsilon}{3}\sum_{j\in
J}v^{(j)}_{2}$

To summarise, all vectors $w_{j}$ satisfy $w_{j}\leq v_{j}$ (coordinate-wise)
and when limited to their first two coordinates as
$\left(\begin{smallmatrix}w^{(j)}_{1}\\\ w^{(j)}_{2}\end{smallmatrix}\right)$,
are either multiples of $(\begin{smallmatrix}1\\\ 0\end{smallmatrix})$ (if
$j\in J_{<c}$), or multiples of $(\begin{smallmatrix}0\\\ 1\end{smallmatrix})$
(if $j\in J_{\geq c^{\prime}}$), or multiples of $(\begin{smallmatrix}1\\\
c\cdot e^{a\varepsilon/3}\end{smallmatrix})$, for some $a\in\\{0,1,\dots,K\\}$
for
$K:=\lfloor\frac{3}{\varepsilon}\cdot\ln(\frac{3d}{\varepsilon^{2}})\rfloor$.
The resulting differences in the first and second coordinate, respectively,
are bounded by as

$\sum_{j\in J_{\geq
c^{\prime}}}|v^{(j)}_{1}-w^{(j)}_{1}|\leq\frac{\varepsilon}{d}\sum_{j\in
J}v^{(j)}_{1}$ $\sum_{j\in J_{<c}}|v^{(j)}_{2}-w^{(j)}_{2}|+\sum_{j\in
J_{mid}}|v^{(j)}_{2}-w^{(j)}_{2}|\leq(\frac{\varepsilon}{3}+\frac{\varepsilon}{3})\sum_{j\in
J}v^{(j)}_{2}.$

We replace the sequence $v^{(j)}$ with the sequence $w^{(j)}$ and repeat the
same process for the 1st and $i$-th coordinate, for $i=3,\dots,d$. Since each
step only zeroes the 1st coordinate of some vectors and decreases the other
coordinates, the final resulting sequence $w^{(j)}$, when compared to the
initial sequence $v^{(j)}$ satisfies:

$\sum_{j\in
J}|v^{(j)}_{1}-w^{(j)}_{1}|\leq(d-1)\cdot\frac{\varepsilon}{d}\sum_{j\in
J}v^{(j)}_{1}$ $\sum_{j\in
J}|v^{(j)}_{i}-w^{(j)}_{i}|\leq(\frac{\varepsilon}{2}+\frac{\varepsilon}{2})\sum_{j\in
J}v^{(j)}_{i}\quad\mbox{for }i=2,\dots,d.$

Each vector $w^{(j)}$ either has its 1st coordinate zeroed, or all its other
coordinates are determined as $w^{(j)}_{1}$ times one of $2+K$ possible
ratios. Among vectors with $w^{(j)}_{1}\neq 0$ there are thus at most
$(2+K)^{d-1}$ different vectors, up to rescaling. The vectors with
$w^{(j)}_{1}=0$ can be inductively reduced as $(d-1)$-dimensional vectors to
${w^{(j)}}^{\prime}$ containing $k(d-1,\frac{\varepsilon}{3})$ distinct
vectors up to rescaling and satisfying

$\sum_{j}|w^{(j)}_{i}-{w^{(j)}_{i}}^{\prime}|\leq\frac{\varepsilon}{3}\sum_{j}w^{(j)}_{i}\leq\frac{\varepsilon}{3}\sum_{j\in
J}v^{(j)}_{i}.$

Altogether, the difference is bounded by
$\frac{2\varepsilon}{3}+\frac{\varepsilon}{3}=\varepsilon$ and the number of
distinct vectors up to rescaling is bounded by
$(2+K)^{d-1}+k(d-1,\frac{\varepsilon}{3})$. ∎

######  Lemma 7.4.

For a fixed signature $\sigma$ and $d\in\mathbb{N}$, the class of
$\sigma$-structures with maximum connected component size at most $d$ is size-
pliable.

###### Proof.

We simply present each component $\mathbb{A}_{i}$ of $\mathbb{A}$ as a vector
encoding the value of all tuples
$(f,\mathbf{x})\in\text{tup}(\mathbb{A}_{i})$. The dimension of such a vector,
for a component of size $d$, is
$d^{\prime}:=\sum_{f\in\sigma}d^{\operatorname{ar}(f)}$. Smaller components be
can treated as components of size $d$ by adding dummy vertices and tuples.

For any $\varepsilon>0$, let
$\varepsilon^{\prime}:=\frac{\varepsilon/C_{\sigma}}{1+\varepsilon/C_{\sigma}}$,
where
$C_{\sigma}=\max_{f\in\sigma}\operatorname{ar}(f)^{\operatorname{ar}(f)}$ .
The previous lemma guarantees the existence of a number
$k=k(\varepsilon^{\prime},d^{\prime})$ such that for every $\sigma$-structure
$\mathbb{A}$ with $n$ components of size at most $d$, the corresponding
vectors $v^{(1)},\dots,v^{(n)}$ are approximated by vectors
$w^{(1)},\dots,w^{(n)}$ such that there are at most $k$ distinct vectors up to
rescaling and such that, for $i=1\dots d^{\prime}$,

$\ {\sum_{j=1\dots
n}|v^{(j)}_{i}-w^{(j)}_{i}|}\leq\varepsilon^{\prime}{\sum_{j=1\dots
n}v^{(j)}_{i}}.$

These vectors encode a $\sigma$-structure $\mathbb{B}$ with only at most $k$
distinct components up to rescaling, all of size at most $d$, which is hence
(by Observation 7.2) equivalent to a $\sigma$-structure $\mathbb{B}^{\prime}$
bounded in size by $k\cdot d$. Moreover, the guarantee on
$\varepsilon^{\prime}$ allows us to bound edit distance as follows:

$\sum_{j=1\dots
n}|v^{(j)}_{i}-w^{(j)}_{i}|\leq\varepsilon^{\prime}\sum_{j=1\dots
n}v^{(j)}_{i}\leq\varepsilon^{\prime}\sum_{j=1\dots
n}\big{(}\min(v^{(j)}_{i},w^{(j)}_{i})+|v^{(j)}_{i}-w^{(j)}_{i}|\big{)}$

(for $i=1\dots d^{\prime}$), hence the edit distance (as defined in Section D)
is

$\operatorname{d_{1}}(\mathbb{A},\mathbb{B})\leq\max_{i=1\dots
d^{\prime}}\frac{\sum_{j=1\dots
n}\left|v^{(j)}_{i}-w^{(j)}_{i}\right|}{\min(\sum_{j=1\dots
n}v^{(j)}_{i},\sum_{j=1\dots
n}w^{(j)}_{i})}\leq\frac{\varepsilon^{\prime}}{1-\varepsilon^{\prime}}=\frac{\varepsilon}{C_{\sigma}}.$

By Lemma D.2,
$\mathrm{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B}^{\prime})\leq\mathrm{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B})+\mathrm{d}_{\mathrm{opt}}(\mathbb{B},\mathbb{B}^{\prime})=\mathrm{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B})\leq
C_{\sigma}\cdot\operatorname{d_{1}}(\mathbb{A},\mathbb{B})\leq\varepsilon$.
(While Lemma D.2 assumes the structures to be clean, this can be ensured by
replacing tuples with repeated elements like $(f,(x_{1},x_{1},x_{2}))$, say,
with $(f^{\prime},(x_{1},x_{2}))$ for a new symbol $f^{\prime}$). ∎

By Observation 4.7 (transitivity of pliability), we conclude that for a fixed
signature $\sigma$, a class of $\sigma$-structures $\mathcal{A}$ is size-
pliable if and only if it is cc-pliable.

###  7.3 From treedepth-pliability to size-pliability

In order to finish the proof of Theorem 1.5, it remains to show the
equivalence of $\operatorname{td}$\- and $\operatorname{size}$-pliability. We
do this by extending the above proof for $\operatorname{cc}$\- and
$\operatorname{size}$-pliability.

The concept of treedepth is due to Nešetřil and Ossona de Mendez [NM06].

######  Definition 7.5.

The _treedepth_ $\operatorname{td}(G)$ of a graph $G$ is defined recursively
as:

  * •

$\ \max\limits_{i}\ \ \operatorname{td}(G_{i})$, if $G$ is disconnected with
components $G_{i}$;

  * •

$\min\limits_{v\in V(G)}\operatorname{td}(G-v)+1$, if $G$ is connected and has
more than one vertex;

  * •

$1$, if $G$ has one vertex.

The treedepth $\operatorname{td}(\mathbb{A})$ of a structure $\mathbb{A}$ is
the treedepth of its Gaifman graph.

An equivalent definition is as follows: a _treedepth decomposition_ of a graph
$G$ is a rooted forest $T$ (a disjoint union of rooted trees) with $V(T)=V(G)$
such that for each $uv\in E(G)$, $u$ is an ancestor or descendant of $v$ in
$G$. In other words, $G$ is a subgraph of the transitive closure of a forest
$T$ directed towards roots. The treedepth of $G$ is equal to the minimum depth
among all such decompositions of $G$.

A short proof shows that a class of graphs has bounded treedepth if and only
if the length of the longest path is bounded [NM06]. Bounded
$\operatorname{td}{}$ implies bounded pathwidth ($\operatorname{pw}$) implies
bounded $\operatorname{tw}$, more precisely:

$\operatorname{tw}(G)\leq\operatorname{pw}(G)\leq\operatorname{td}(G)\leq\operatorname{tw}(G)\cdot\log|G|.$

One of the main reasons for which treedepth is useful (and easier to work with
than, say, treewidth) is that the only way for a graph of small treedepth to
be large is to have many repeating parts, like in a large star graph (see e.g.
[NM06, Theorem 3.1]). This implies that in a class of graphs of bounded
treedepth, homomorphic cores have bounded size. This does not extend to
weighted graphs or structures in general, but we can approximate the weights
or values as before.

######  Lemma 7.6.

For a fixed signature $\sigma$ and $d\in\mathbb{N}$, the class of
$\sigma$-structures $\\{\mathbb{A}\colon\operatorname{td}(\mathbb{A})\leq
d\\}$ is size-pliable.

###### Proof.

We prove by induction on $d$ that statement holds for each signature $\sigma$.
It suffices to prove the statement for connected $\sigma$-structures of
treedepth at most $d$. Indeed, this implies that disconnected
$\sigma$-structures of treedepth at most $d$ are $\operatorname{cc}$-pliable,
which we already known implies $\operatorname{size}$-pliability.

For $d=1$, each component of the Gaifman graph is a single vertex and we are
done. So let $d>1$ and assume that for each signature $\sigma$ and each
$\varepsilon>0$, there is a $k=k(d-1,\sigma,\varepsilon)$ such that every
$\sigma$-structure with treedepth $\leq d-1$ has a $\sigma$-structure of size
$\leq k$ at opt-distance at most $\varepsilon$. Let $\sigma$ be a signature
and $\mathbb{A}$ a $\sigma$-structure of treedepth $d$. Let $G$ be the Gaifman
graph of $\mathbb{A}$. Since it is connected, we can find a vertex $v\in
V(G)=A$ such that $\operatorname{td}(G-v)=d-1$.

We now define a new signature $\sigma^{\prime}$ and a
$\sigma^{\prime}$-structure $\mathrm{pack}(\mathbb{A})$ whose Gaifman graph
will be $G-v$, but will contain all the information about $\mathbb{A}$. Let
$\sigma^{\prime}=\\{(f,I)\colon
f\in\sigma,I\subseteq\\{1,\dots,\operatorname{ar}(f)\\}\\}$ and
$\operatorname{ar}((f,I)):=\operatorname{ar}(f)-|I|$, for
$(f,I)\in\sigma^{\prime}$. For
$\mathbf{x}\in(A-v)^{\operatorname{ar}((f,I))}$, let
$(f,I)^{\mathrm{pack}(\mathbb{A})}(\mathbf{x}):=f^{\mathbb{A}}(\mathbf{x^{\prime}})$
where $\mathbf{x^{\prime}}\in A^{\operatorname{ar}(f)}$ is the tuple obtained
from $\mathbf{x}$ by introducing $v$ at positions $I$. Note that
$\sigma^{\prime}$ is bounded:
$|\sigma^{\prime}|\leq\sum_{f\in\sigma}2^{\operatorname{ar}(f)}$.

The $\sigma^{\prime}$-structure $\mathrm{pack}(\mathbb{A})$ has treedepth
$d-1$, so by inductive assumption there is a $\sigma^{\prime}$-structure
$\mathbb{B}$ at opt-distance at most $\varepsilon$ with size at most
$k=k(d-1,\sigma^{\prime},\varepsilon)$. We define
$\mathrm{unpack}(\mathbb{B})$ to be the $\sigma$-structure with domain
$B\cup\\{v\\}$ and
$f^{\mathrm{unpack}(\mathbb{B})}(\mathbf{x}):=(f,I)^{\mathbb{B}}(\mathbf{x^{\prime}})$,
where $I$ is the set of positions in $\mathbf{x}$ containing $v$ and
$\mathbf{x^{\prime}}$ is the tuple obtained by removing these positions. It is
straightforward to check that $\mathrm{unpack}(\mathrm{pack}(\mathbb{A}))$ is
equal to $\mathbb{A}$ and that for any $\sigma^{\prime}$-structures
$\mathbb{A}^{\prime},\mathbb{B}^{\prime}$ we have
$\mathrm{d}_{\mathrm{opt}}(\mathrm{unpack}(\mathbb{A}^{\prime}),\mathrm{unpack}(\mathbb{B}^{\prime}))\leq\mathrm{d}_{\mathrm{opt}}(\mathbb{A}^{\prime},\mathbb{B}^{\prime})$,
hence

$\mathrm{d}_{\mathrm{opt}}(\mathbb{A},\mathrm{unpack}(\mathbb{B}))=\mathrm{d}_{\mathrm{opt}}(\mathrm{unpack}(\mathrm{pack}(\mathbb{A})),\mathrm{unpack}(\mathbb{B}))\leq\mathrm{d}_{\mathrm{opt}}(\mathrm{pack}(\mathbb{A}),\mathbb{B})\leq\varepsilon.$

Hence $\mathrm{unpack}(\mathbb{B})$ is a $\sigma$-structure at opt-distance
$\leq\varepsilon$ from $\mathbb{A}$ of size $\leq k+1$. ∎

By Observation 4.7 (transitivity of pliability), this concludes the proof of
Theorem 1.5:

######  Corollary 7.7.

A class of $\sigma$-structures in $\operatorname{td}$-pliable if and only if
it is size-pliable.

##  8 Hyperfinite classes are fractionally fragile: proof of Theorem 1.6

Recall that class of graphs is if _hyperfinite_ if for every $\varepsilon>0$
there is a $k\in\mathbb{N}$ such that every graph in the class can be turned
into a graph with connected components of size at most $k$ by removing an at-
most-$\varepsilon$ fraction of all edges.666In other work, the definition of
_hyperfinite_ often considers the number removed edges divided by the total
number of vertices. However, they only deal with bounded degree graphs, which
makes the two definitions essentially equivalent. A class of graphs is
_monotone_ if it is closed under subgraphs. In this section, we prove the
following result.

######  Theorem (Theorem 1.6 restated).

Let $\mathcal{G}$ be a monotone class of graphs. The following are equivalent,
for any $r\geq 2$:

  * •

$\mathcal{G}$ is hyperfinite;

  * •

$\mathcal{G}$ is fractionally-$\operatorname{tw}$-fragile and has bounded
degree;

  * •

$\mathcal{G}$ is fractionally-$\operatorname{cc}$-fragile;

  * •

$\mathcal{A}_{\mathcal{G}}^{(r)}$ is $\operatorname{cc}$-pliable.

As discussed in the introduction, the last two bullets are shown equivalent by
Lemma 6.1; the middle two bullets were shown equivalent by Dvořák [Dvo16,
Observation 15, Corollary 20]. It remains to prove their equivalence with the
first bullet point.

######  Lemma 8.1.

Let $\mathcal{G}$ be a monotone class of graphs. $\mathcal{G}$ is hyperfinite
if and only if it is fractionally-$\operatorname{cc}$-fragile.

###### Proof.

Hyperfiniteness of a monotone class $\mathcal{G}$ equivalent to
hyperfiniteness of 0-1-edge weighted graphs in $\mathcal{G}$:

$\forall_{\varepsilon>0}\exists_{k}\forall_{G\in\mathcal{G}}\forall_{w\colon
E(G)\to\\{0,1\\}}\exists_{F\subseteq E(G)}\ w(F)\leq\varepsilon w(E(G))\
\text{and}\ \operatorname{cc}(G-F)\leq k.$

Hence it is trivially implied by the edge version of
fractional-$\operatorname{cc}$-fragility (which allows arbitrary nonnegative
weights) in Lemma 4.4. It remains to show the other direction.

By definition of hyperfiniteness, for every $\varepsilon>0$ there is a
$k=k(\varepsilon)$ such that for all graphs $G\in\mathcal{G}$, one can remove
a set of edges $F$ with $|F|\leq\varepsilon|E(G)|$ so that
$\operatorname{cc}(G-F)\leq k$. Observe that graphs in $\mathcal{G}$ have
degree bounded by $\Delta:=2k(\frac{1}{2})$; otherwise, a graph with degree
$\geq 2k(\frac{1}{2})+1$ would contain a star with that many edges as a
subgraph and removing half of these edges always leaves a component with at
least $k(\frac{1}{2})+1$ edges and vertices.

We aim to show that

$\forall_{\varepsilon>0}\exists_{k}\forall_{G\in\mathcal{G}}\forall_{w\colon
E(G)\to\mathbb{Q}_{\geq 0}}\exists_{F\subseteq E(G)}\ w(F)\leq\varepsilon
w(E(G))\ \text{and}\ \operatorname{cc}(G-F)\leq k.$

For $\varepsilon>0$, let $\varepsilon^{\prime}$ be chosen later and let
$k^{\prime}=k(\varepsilon^{\prime})$. Let $G\in\mathcal{G}$ and $w\colon
E(G)\to\mathbb{Q}_{\geq 0}$. We want to find a set $F\subseteq E(G)$ such that
$w(F)\leq\varepsilon w(E(G))$ and $\operatorname{cc}(G-F)\leq k^{\prime}$.
Note that our task would be trivial if the weights of all edges were within a
constant factor $\alpha$ of each other: just set
$\varepsilon^{\prime}=\frac{\varepsilon}{\alpha}$, find $F\subseteq E(G)$ such
that $|F|\leq\varepsilon^{\prime}|E(G)|$ and $\operatorname{cc}(G-F)\leq
k^{\prime}$ and conclude that
$w(F)\leq\alpha\varepsilon^{\prime}w(E(G)))=\varepsilon w(E(G))$.

In general, let us partition the edges of $G$ into buckets depending on their
weight: for $i\in\mathbb{Z}$, let $B_{i}:=\\{e\in
E(G)\mid\left(\frac{\varepsilon}{6\Delta}\right)^{i}\geq
w(e)>\left(\frac{\varepsilon}{6\Delta}\right)^{i+1}\\}$ (edges with weight
zero can be removed w.l.o.g.). For $L:=\lceil\frac{3}{\varepsilon}\rceil$, we
will remove every $L$-th bucket from $G$. That is, for
$j\in\\{0,\dots,L-1\\}$, let
$B^{\prime}_{j}:=\bigcup_{i\in\mathbb{Z}}B_{iL+j}$. Let
$j^{*}\in\\{0,\dots,L-1\\}$ be such that $w(B^{\prime}_{j^{*}})$ is minimum;
since $B^{\prime}_{0}\cup\dots B^{\prime}_{L-1}$ is a partition of $E(G)$,
$w(B^{\prime}_{j^{*}})\leq\frac{1}{L}w(E(G))\leq\frac{\varepsilon}{3}w(E(G))$.
We can thus remove the edges $B^{\prime}_{j^{*}}$ from $G$. Since this removes
every $L$-th bucket, the remaining edges are partitioned into blocks
$C_{i}:=B_{iL+j^{*}+1}\cup\dots\cup B_{iL+j^{*}+L-1}$ of $L-1$ buckets for
$i\in\mathbb{Z}$. Each block contains weights within a constant factor of each
other: $\min\\{w(e)\colon e\in
C_{i}\\}\geq\left(\frac{\varepsilon}{6\Delta}\right)^{L-1}\cdot\max\\{w(e)\colon
e\in C_{i}\\}$. Moreover, since there is a gap of one bucket in between one
block and the next, $\max\\{w(e)\colon e\in
C_{i+1}\\}<\frac{\varepsilon}{6\Delta}\cdot\min\\{w(e)\colon e\in C_{i}\\}$.

The latter property allows us to disconnect the blocks from each other.
Indeed, for each $C_{i}$ with increasing $i$ (starting from the smallest $i$
such that $C_{i}$ is non-empty), we shall remove all remaining edges on the
boundary of $C_{i}$:

$F_{i}:=\\{e\colon e\in C_{j}\text{ for some }j>i,\ e\text{ shares a vertex
with some }e^{\prime}\in C_{i}\\}.$

Since $|F_{i}|\leq 2\Delta|C_{i}|$ and $\max\\{w(e)\colon e\in
F_{i}\\}<\frac{\varepsilon}{6\Delta}\cdot\min\\{w(e)\colon e\in C_{i}\\}$, we
have $w(F_{i})<\frac{\varepsilon}{3}w(C_{i})$. In total, for
$F:=\bigcup_{i\in\mathbb{Z}}F_{i}$, we have
$w(F)<\frac{\varepsilon}{3}w(E(G))$. For all $i\in\mathbb{Z}$, the edges of
$C_{i}-F$ are disjoint from edges of $C_{j}-F$ for all $j>i$. Since the sets
$C_{i}-F$ partition edges of $G-B^{\prime}_{j^{*}}-F$, this means that every
connected component of $G-B^{\prime}_{j^{*}}-F$ is contained in one of the
edge sets $C_{i}-F$.

Finally, since $\min\\{w(e)\colon e\in
C_{i}-F\\}\geq\alpha\cdot\max\\{w(e)\colon e\in C_{i}-F\\}$ for
$\alpha:=\left(\frac{\varepsilon}{3\Delta}\right)^{L-1}$, we have reduced our
problem to the trivial case when weights are all within a constant factor of
each other. That is, let $\varepsilon^{\prime}:=\frac{\alpha\varepsilon}{3}$.
For each $i\in\mathbb{Z}$, let $G_{i}$ be the subgraph of
$G-B^{\prime}_{j^{*}}-F$ formed from connected components contained in
$C_{i}-F$. By assumption, there is a set $F^{\prime}_{i}\subseteq E(G_{i})$
such that $|F^{\prime}_{i}|\leq\varepsilon^{\prime}|E(G_{i})|$ and
$\operatorname{cc}(G_{i}-F^{\prime}_{i})\leq
k(\varepsilon^{\prime})=k^{\prime}$. Then
$w(F^{\prime}_{i})\leq\max\\{w(e)\colon e\in
E(G_{i})\\}\cdot|F^{\prime}_{i}|\leq\frac{1}{\alpha}\cdot\min\\{w(e)\colon
e\in
E(G_{i})\\}\cdot\varepsilon^{\prime}\cdot|E(G_{i})|\leq\frac{\varepsilon^{\prime}}{\alpha}w(E(G_{i}))=\frac{\varepsilon}{3}w(E(G_{i}))$.
In total, for $F^{\prime}:=\bigcup_{i\in\mathbb{Z}}F^{\prime}_{i}$ we have
$w(B^{\prime}_{j^{*}}\cup F\cup
F^{\prime})\leq(\frac{\varepsilon}{3}+\frac{\varepsilon}{3}+\frac{\varepsilon}{3})w(E(G))$
and $\operatorname{cc}(G-B^{\prime}_{j^{*}}-F-F^{\prime})\leq k^{\prime}$. ∎

##  9 Dense graphs are pliable: proof of Theorem 1.3

In this section, we prove the following result.

######  Theorem (Theorem 1.3 restated).

For every $c>0$, the class of (unweighted, undirected) graphs with $\geq
cn^{2}$ edges is size-pliable.

While we only prove this for unweighted graphs, it will be notationally
convenient to treat them as $\\{0,1\\}$-weighted graphs, with
$w_{G}(u,v):=[uv\in E(G)]$. For sets $U,V\subseteq V(G)$, we denote by
$w_{G}(U,V):=\sum_{u\in U}\sum_{v\in V}w_{G}(u,v)$ the number of edges between
$U$ and $V$ (or their total weight). The regularity lemma states that every
graph can be partitioned into a bounded number of parts so that the bipartite
graph between every two parts is random-like in the following strong sense:

######  Definition 9.1.

A bipartite graph $G=(V_{1},V_{2},E)$ of density
$d:=\frac{w_{G}(V_{1},V_{2})}{|V_{1}||V_{2}|}$ is _$\varepsilon$ -homogeneous_
if for all $W_{1}\subseteq V_{1}$, $W_{2}\subseteq V_{2}$,

$w_{G}(W_{1},W_{2})=d|W_{1}||W_{2}|\,\pm\,\varepsilon|V_{1}||V_{2}|.$

For an $n$-vertex graph $G$ and an integer $k$, an _$\varepsilon$ -regular
$k$-partition_ of $G$ is a partition $V_{1},\dots,V_{k}$ of $V(G)$ such that
$|V_{i}|\in\\{\lfloor\frac{n}{k}\rfloor,\lceil\frac{n}{k}\rceil\\}$ for
$i\in[k]$ and the bipartite graph $(V_{i},V_{j},E(G)\cap V_{i}\times V_{j})$
is $\varepsilon$-homogeneous777The usual statement of the regularity lemma
replaces $\varepsilon$-homogeneity (with additive error) by a notion called
_$\varepsilon$ -regularity_ (with relative error, but holding only for
$|W_{i}|\geq\varepsilon|V_{i}|$). The two are however easily shown to be
equivalent, up to a change from $\varepsilon$ to $\varepsilon^{1/3}$., for all
$ij\in\binom{[k]}{2}$.

We use the following strong version of Szemerédi’s regularity lemma (see
Theorem 2.2 in [RS07], Lemma 5.2. in [LS07], or Chapter 9 in [Lov12] for a
detailed discussion).

######  Theorem 9.2 (Regularity Lemma).

For every $\varepsilon_{1}>0$ and every non-decreasing
$f\colon\mathbb{N}\to\mathbb{N}$, there is an integer $k$ such that for every
sufficiently large graph $G$, one can add/remove $\varepsilon_{1}|V(G)|^{2}$
edges to obtain a graph which admits an $\frac{1}{f(k^{\prime})}$-regular
$k^{\prime}$-partition for some $\frac{1}{\varepsilon_{1}}\leq k^{\prime}\leq
k$.

Another way to view this is to define, for a partition
$\mathcal{P}=(V_{1},\dots,V_{k})$ of a graph $G$, the _quotient graph
$G_{/\mathcal{P}}$_ as the weighted graph with vertex set $k$ and weights
$w_{G_{/\mathcal{P}}}(i,j):=w_{G}(V_{i},V_{j})$ for $(i,j)\in[k]^{2}$. The
quotient graph for an $\varepsilon$-regular partition is then a graph of
bounded size that is _close_ to the original graph: the notion of closeness
arising from the definition of $\varepsilon$-homogeneity is known as _cut
distance_ (see Chapter 8 in [Lov12]), but later we show the same holds for
opt-distance:

######  Theorem 9.3.

Let $G$ be a graph with density $c:=\frac{|E(G)|}{n^{2}}$. For
$0<\varepsilon_{0}<1$, suppose $G$ has an $\varepsilon$-regular $k$-partition
$\mathcal{P}=(V_{1},\dots,V_{k})$ with
$\frac{1}{k}\leq\frac{c}{10}\frac{\varepsilon_{0}}{1+\varepsilon_{0}}$ and
$\varepsilon\leq\left(\frac{1}{k}\right)^{8k^{2}}$. Then
$\mathrm{d}_{\mathrm{opt}}(G,G_{/\mathcal{P}})\leq\varepsilon_{0}$.

With this view it is easy to see that classes of dense graphs are pliable.
Formally:

###### Proof of Theorem 1.3 assuming Theorem 9.3.

Let $\mathcal{A}$ be a class of graphs with $\geq cn^{2}$ edges. We want to
show that for every $\varepsilon_{0}>0$ there is a $k$ such that every
$G\in\mathcal{A}$ has a weighted graph $H$ of size at most $k$ with
$\mathrm{d}_{\mathrm{opt}}(G,H)\leq\varepsilon_{0}$.

For $\varepsilon_{0}>0$, let
$\varepsilon_{1}:=\frac{c}{10}\cdot\frac{\varepsilon_{0}/2}{1+\varepsilon_{0}/2}$.
Note that we can assume all sufficiently large graphs $G\in\mathcal{A}$ have
no loops: if $|V(G)|\geq\frac{1}{\varepsilon_{1}}$, then the number of loops
is at most
$|V(G)|\leq\frac{1}{c|V(G)|}|E(G)|\leq\frac{\varepsilon_{1}}{c}|E(G)|$. Hence
by removing them we obtain a graph $G^{\prime}$ such that
$\operatorname{d_{1}}(G,G^{\prime})\leq\frac{|E(G)|-|E(G^{\prime})|}{\min(|E(G)|,|E(G^{\prime})|)}\leq\frac{\varepsilon_{1}/c}{1-\varepsilon_{1}/c}\leq\varepsilon_{0}/20$.
By Lemma D.2, $\mathrm{d}_{\mathrm{opt}}(G,G^{\prime})\leq\varepsilon_{0}/5$
(the direction $G\mathbin{\succeq}G^{\prime}$ is trivial, while the other
direction only requires $G^{\prime}$ to have no loops).

Let $f(k):=k^{8k^{2}}$. By the Regularity Lemma (Theorem 9.2), there is an
integer $k\geq\frac{1}{\varepsilon_{1}}$ such that for every graph $G$ of size
$>k$, one can add/remove $\varepsilon_{1}|V(G)|^{2}$ edges to obtain a graph
$H$ which admits an $\frac{1}{f(k^{\prime})}$-regular $k^{\prime}$-partition
$\mathcal{P}$ for some $\frac{1}{\varepsilon_{1}}\leq k^{\prime}\leq k$. If
$G\in\mathcal{A}$, then $G$ has at least $cn^{2}$ edges, so
$\operatorname{d_{1}}(G,H)\leq\frac{\varepsilon_{1}}{c-\varepsilon_{1}}\leq\varepsilon_{0}/20$.
Since we can assume $G$ is loopless, by Lemma D.2,
$\mathrm{d}_{\mathrm{opt}}(G,H)\leq\varepsilon_{0}/5$. By Theorem 9.3,
$\mathrm{d}_{\mathrm{opt}}(H,H_{/\mathcal{P}})\leq\varepsilon_{0}/2$. Hence
$H_{/\mathcal{P}}$ is the graph of size at most $k$ we seek, at opt-distance
at most $\varepsilon_{0}$ from $G$. ∎

The strategy of the proof of Theorem 9.3 is very similar to Example 3.2. One
direction is trivial: an overcast from $G$ to $G_{/\mathcal{P}}$ is given
simply by deterministically mapping all of $V_{i}$ to $i$, for $i\in[k]$. For
the other direction, we will take a subgraph $F$ of $G_{/\mathcal{P}}$
obtained by removing edges of small weight (keeping $F$ close to
$G_{/\mathcal{P}}$) and removing weights, and then map $G_{/\mathcal{P}}$ to a
random copy of $F$ in $G$. We need to estimate the number of such copies (this
is known as the _counting lemma_) and, more generally, the number of such
copies containing any given edge of $G$ (the _extension lemma_). Both are
standard lemmas in the theory of dense graph limits, in particular our proof
of the counting lemma mimics Lemma 10.22 in [Lov12]. However, we will prove a
version of the extension lemma with somewhat tighter bounds than usual
(depending on all $\binom{k}{2}$ edge densities between parts of the
regularity partition).

For a graph $F$ on vertex set $[k]\vcentcolon=\\{1,\dots,k\\}$, we will treat
$F$ as a subset of $\binom{[k]}{2}$. For a partition
$\mathcal{P}=(V_{1},\dots,V_{k})$ of a graph $G$, a _$\mathcal{P}$ -map_ is a
function $g\colon[k]\to V(G)$ such that $g(i)\in V_{i}$ for all $i\in[k]$. We
denote $\hom_{g}(F,G):=\prod_{ij\in F}w_{G}(g(i),g(j))$; for
$\\{0,1\\}$-weighted graphs, this is equal to 1 if $g$ is a homomorphism from
$F$ to $G$ and 0 otherwise.

Let us first observe two consequences of $\varepsilon$-homogeneity. First, the
notion can be extended from subsets $W_{1}\subseteq V_{1}$ to any functions
$f\colon V_{1}\to[0,1]$ simply by considering subsets where the function takes
at least a given number (here $\|f\|_{1}\vcentcolon=\sum_{x}f(x)$):

######  Observation 9.4.

Let $G=(V_{1},V_{2},E)$ be $\varepsilon$-homogeneous of density $d$. Then for
every $f\colon V_{1}\to[0,1]$ and $g\colon V_{2}\to[0,1]$,

$\sum\limits_{x_{1}\in V_{1}}\sum\limits_{x_{2}\in
V_{2}}f(x_{1})g(x_{2})w_{G}(x_{1},x_{2})=d\|f\|_{1}\|g\|_{1}\ \pm\
\varepsilon|V_{1}||V_{2}|.$

###### Proof.

For $y\in[0,1]$, let $V_{1}^{y}:=\\{x\in V_{1}\colon f(x)\geq y\\}$ and define
$V_{2}^{y}$ analogously for $g$. Notice that $f(x)=\int_{0}^{1}[y\leq
f(x)]\,dy=\int_{0}^{1}[x\in V_{1}^{y}]\,dy$. Hence

$\displaystyle\sum_{x_{1}\in V_{1}}\sum_{x_{2}\in
V_{2}}f(x_{1})g(x_{2})w_{G}(x_{1},x_{2})=$
$\displaystyle\int_{0}^{1}\int_{0}^{1}\sum_{x_{1}\in V_{1}}\sum_{x_{2}\in
V_{2}}[x_{1}\in V_{1}^{y_{1}}][x_{2}\in
V_{2}^{y_{2}}]w_{G}(x_{1},x_{2})\,dy_{1}\,dy_{2}=$
$\displaystyle\int_{0}^{1}\int_{0}^{1}w_{G}(V_{1}^{y_{1}},V_{2}^{y_{2}})\,dy_{1}\,dy_{2}=$
$\displaystyle\int_{0}^{1}\int_{0}^{1}\big{(}d|V_{1}^{y_{1}}||V_{2}^{y_{2}}|\pm\varepsilon|V_{1}||V_{2}|\big{)}\,dy_{1}\,dy_{2}=$
$\displaystyle
d\cdot\Big{(}\int_{0}^{1}|V_{1}^{y_{1}}|\,dy_{1}\Big{)}\Big{(}\int_{0}^{1}|V_{2}^{y_{2}}|\,dy_{2}\Big{)}\pm\varepsilon|V_{1}||V_{2}|.$

Since $\displaystyle\int_{0}^{1}|V_{1}^{y}|dy=\int_{0}^{1}\sum_{x\in
V_{1}}[y\leq f(x)]dy=\sum_{x\in V_{1}}f(x)=\|f\|_{1}$, the claim follows. ∎

Second, while we cannot say much about any one fixed vertex, we can make
similar approximations for most vertices:

######  Observation 9.5.

Let $G=(V_{1},V_{2},E)$ be $\varepsilon$-homogeneous with density $d$. For
every $g\colon V_{2}\to[0,1]$, there are at least
$(1-2\sqrt{\varepsilon})|V_{1}|$ vertices $x_{1}$ in $V_{1}$ such that
$\sum_{x_{2}}g(x_{2})w_{G}(x_{1},x_{2})=d\|g\|_{1}\ \pm\
\sqrt{\varepsilon}|V_{2}|$.

###### Proof.

Let $W_{1}^{-}$ be the set of those $x_{1}$ in $V_{1}$ for which the sum is
too small:

$\textstyle\sum_{x_{2}}g(x_{2})w_{G}(x_{1},x_{2})<d\|g\|_{1}-\sqrt{\varepsilon}|V_{2}|.$

Let $f\colon V_{1}\to[0,1]$ be the characteristic function of $W_{1}^{-}$.
Then

$\textstyle\sum_{x_{1}}\sum_{x_{2}}f(x_{1})g(x_{2})w_{G}(x_{1},x_{2})<\|f\|_{1}\cdot\left(d\|g\|_{1}-\sqrt{\varepsilon}|V_{2}|\right).$

By Observation 9.4, this implies
$\|f\|_{1}\cdot\sqrt{\varepsilon}|V_{2}|<\varepsilon|V_{1}||V_{2}|$. Hence
$|W_{1}^{-}|=\|f\|_{1}<\sqrt{\varepsilon}|V_{1}|$. We can define and bound
$W_{1}^{+}$ analogously. Then $V_{1}\setminus(W_{1}^{-}\cup W_{1}^{+})$ is a
set of size at least $(1-2\sqrt{\varepsilon})|V_{1}|$ as claimed. ∎

The counting lemma says that the number of $\mathcal{P}$-maps that are
homomorphisms from $F$ to $G$ is close to what one would expect in a purely
random graph with the same densities. Note that the number of all
$\mathcal{P}$-maps $g\colon[k]\to V(G)$ is exactly $\prod_{i\in[k]}|V_{i}|$.

######  Lemma 9.6 (Counting Lemma).

Let $\mathcal{P}=(V_{1},\dots,V_{k})$ be an $\varepsilon$-regular
$k$-partition of an $n$-vertex graph $G$. Let
$d_{ij}:=\frac{w_{G}(V_{i},V_{j})}{|V_{i}||V_{j}|}$. For each
$F\subseteq\binom{[k]}{2}$,

$\sum_{g}\hom_{g}(F,G)=\Big{(}\prod_{i\in[k]}|V_{i}|\Big{)}\Big{(}\prod_{ij\in
F}d_{ij}\ \pm\ \varepsilon|F|\Big{)},$

where the sum is over all $\mathcal{P}$-maps $g\colon[k]\to V(G)$.

###### Proof.

Let us write $\sum_{(x_{i})_{i\in[k]}}$ as a shorthand for $\sum_{x_{1}\in
V_{1}}\dots\sum_{x_{k}\in V_{k}}$. We wish to approximate

$\sum_{(x_{i})_{i\in[k]}}\prod_{ij\in F}w_{G}(x_{i},x_{j}).$

We do so by replacing each factor $w_{G}(x_{i},x_{j})$ by its average value
$d_{ij}$, one by one. That is, we prove for all subsets $F^{\prime}\subseteq
F$ by induction that

$\sum_{(x_{i})_{i\in[k]}}\prod_{ij\in
F}w_{G}(x_{i},x_{j})\quad=\quad\sum_{(x_{i})_{i\in[k]}}\prod_{ij\in
F-F^{\prime}}w_{G}(x_{i},x_{j})\prod_{ij\in
F^{\prime}}d_{ij}\quad\pm\quad|F^{\prime}|\cdot\varepsilon\prod_{i\in[k]}|V_{i}|.$
(*)

Clearly this is true initially for $F^{\prime}=\emptyset$ and eventually by
reaching $F^{\prime}=F$ we will have proved that

$\begin{gathered}\sum_{(x_{i})_{i\in[k]}}\prod_{ij\in
F}w_{G}(x_{i},x_{j})\quad=\quad\sum_{(x_{i})_{i\in[k]}}\prod_{ij\in
F}d_{ij}\quad\pm\quad|F|\cdot\varepsilon\prod_{i\in[k]}|V_{i}|;\end{gathered}$

which proves the claim, as
$\sum_{(x_{i})_{i\in[k]}}1=\prod_{i\in[k]}|V_{i}|\simeq\left(\frac{n}{k}\right)^{k}$.

To prove the induction step, suppose (* ‣ 9) holds for some $F^{\prime}\subset
F$ and let $ab\in F-F^{\prime}$. Let $w^{\prime}_{G}(x_{i},x_{j})$ denote
$w_{G}(x_{i},x_{j})$ if $ij\not\in F^{\prime}$ and $d_{ij}$ otherwise. Then
the main summand in (* ‣ 9) is

$\begin{gathered}\sum_{(x_{i})_{i\in[k]}}\prod_{ij\in
F}w^{\prime}_{G}(x_{i},x_{j})=\\\
\sum_{(x_{i})_{i\in[k]-a-b}}h\sum_{x_{a}}\sum_{x_{b}}f(x_{a})g(x_{b})w^{\prime}_{G}(x_{a},x_{b}),\end{gathered}$

where for any fixed choice of $(x_{i})_{i\in[k]-a-b}$, we let

$\begin{gathered}h:=\prod_{\begin{subarray}{c}ij\in F-F^{\prime}\\\ i\neq
a,j\neq b\end{subarray}}w^{\prime}_{G}(x_{i},x_{j}),\quad\quad
f(x_{a}):=\prod_{\begin{subarray}{c}ij\in F-F^{\prime}\\\ i=a,j\neq
b\end{subarray}}w^{\prime}_{G}(x_{a},x_{j}),\quad\quad
g(x_{b}):=\prod_{\begin{subarray}{c}ij\in F-F^{\prime}\\\ i\neq
a,j=b\end{subarray}}w^{\prime}_{G}(x_{i},x_{b}).\end{gathered}$

Since $h,f,g\leq 1$, the claim then follows from Observation 9.4: replacing
$w_{G}(x_{a},x_{b})$ with $d_{ab}$ adds an error of at most
$\sum_{(x_{i})_{i\in[k]-a-b}}h\cdot\varepsilon|V_{a}||V_{b}|\leq\varepsilon|V_{a}||V_{b}|\cdot\sum_{(x_{i})_{i\in[k]-a-b}}1=\varepsilon\prod_{i\in[k]}|V_{i}|$.
∎

######  Lemma 9.7 (Extension Lemma).

Let $\mathcal{P}=(V_{1},\dots,V_{k})$ be an $\varepsilon$-regular
$k$-partition of an $n$-vertex graph $G$. Let
$d_{ij}:=\frac{w_{G}(V_{i},V_{j})}{|V_{i}||V_{j}|}$. For each
$F\subseteq\binom{[k]}{2}$ and each $ab\in F$, all but
$2k\sqrt{\varepsilon}|V_{a}||V_{b}|$ edges $x_{a}x_{b}\in V_{a}\times V_{b}$
satisfy

$\sum_{g}\hom_{g}(F,G)=\Big{(}\prod_{i\in[k]-a-b}|V_{i}|\Big{)}\cdot\Big{(}w_{G}(x_{a},x_{b})\cdot\prod_{ij\in
F-ab}d_{ij}\quad\pm\quad\sqrt{\varepsilon}|F|\Big{)}$

where the sum is over all $\mathcal{P}$-maps $g\colon[k]\to V(G)$ such that
$g(a)=x_{a}$ and $g(b)=x_{b}$.

###### Proof.

The argument is the same as in the counting lemma, except that edges incident
to $a,b$ have to be handled differently. First note that for every
$c\in[k]-a-b$ and every fixed $x_{b}\in V_{b}$, by Observation 9.5 (with
$g(x_{c}):=w_{G}(x_{c},x_{b})$), the following holds for all but at
$2\sqrt{\varepsilon}|V_{a}|$ vertices $x_{a}$ in $V_{a}$:

$\sum_{x_{c}}w_{G}(x_{a},x_{c})w_{G}(x_{c},x_{b})=d_{ac}\Big{(}\sum_{x_{c}}w_{G}(x_{c},x_{b})\Big{)}\pm\sqrt{\varepsilon}|V_{c}|.$
(**)

For each $c\in[k]-a-b$ and each $x_{b}\in V_{b}$, we will ignore those edges
going to $x_{a}\in V_{a}$ that fail (** ‣ 9).

Similarly for each $c\in[k]-a-b$, by Observation 9.5 (with $g(x_{c}):=1$) the
following holds for all but at most $\sqrt{\varepsilon}|V_{b}|$ vertices
$x_{b}\in V_{b}$:

$\sum_{x_{c}}w_{G}(x_{b},x_{c})=d_{bc}|V_{c}|\pm\sqrt{\varepsilon}|V_{c}|.$
(***)

We ignore all edges $x_{a}x_{b}\in E(V_{a},V_{b})$ incident to $x_{b}$ for
which (*** ‣ 9) fails. Thus for all but $\leq 2\cdot k\cdot|V_{b}|\cdot
2\sqrt{\varepsilon}|V_{a}|$ edges $x_{a}x_{b}\in E(V_{a},V_{b})$, (** ‣ 9) and
(*** ‣ 9) hold for all $c\in[k]-a-b$.

Fix any such $x_{a}\in V_{a},x_{b}\in V_{b}$. We wish to approximate

$\begin{gathered}\sum_{(x_{i})_{i\in[k]-a-b}}\prod_{ij\in
F}w_{G}(x_{i},x_{j})=\\\
w_{G}(x_{a},x_{b})\cdot\sum_{(x_{i})_{i\in[k]-a-b}}\prod_{ij\in
F-ab}w_{G}(x_{i},x_{j})=\dots{}\end{gathered}$

Just as in the proof of the counting lemma, we replace factors
$w_{G}(x_{i},x_{j})$ by $d_{ij}$ one by one. We first do this for pairs in
$F_{0}:=\\{ij\in F\mid i,j\neq a,b\\}$, since the argument works without
change, incurring an error of
$\pm\varepsilon|F_{0}|\prod_{i\in[k]-a-b}|V_{i}|$. Since $d_{ij}$ does not
depend on the choice of $x_{i}\in V_{i},x_{j}\in V_{j}$, we can rearrange:

$\dots\simeq w_{G}(x_{a},x_{b})\Big{(}\prod_{ij\in
F_{0}}d_{ij}\Big{)}\cdot\sum_{(x_{i})_{i\in[k]-a-b}}\prod_{i\in[k]-a-b}w_{G}(x_{a},x_{i})w_{G}(x_{i},x_{b})=\dots$

Then, for each $c\in[k]-a-b$ we can replace $ac$ by isolating the factors that
depend on $x_{c}$ and applying (** ‣ 9) (as before
$w^{\prime}_{G}(x_{a},x_{i})$ denotes either $w_{G}(x_{a},x_{i})$ or $d_{ai}$
depending on whether we have already replaced $ai$):

$\dots=w_{G}(x_{a},x_{b})\Big{(}\prod_{ij\in
F_{0}}d_{ij}\Big{)}\cdot\sum_{x_{c}}w_{G}(x_{a},x_{c})w_{G}(x_{c},x_{b})\
\cdot\\\
\sum_{(x_{i})_{i\in[k]-a-b-c}}\prod_{i\in[k]-a-b-c}w^{\prime}_{G}(x_{a},x_{i})w_{G}(x_{i},x_{b})\simeq\dots{}$

Having thus replaced all edges $ac$ for $c\in[k]-a-b$, the only remaining
edges are of the form $ib$ for $i\in[k]-a-b$, so by denoting $F_{1}:=\\{ij\in
F\mid i,j\neq b\\}$ the expression becomes:

$\begin{gathered}\dots\simeq w_{G}(x_{a},x_{b})\Big{(}\prod_{ij\in
F_{1}}d_{ij}\Big{)}\cdot\sum_{(x_{i})_{i\in[k]-a-b}}\prod_{i\in[k]-a-b}w_{G}(x_{i},x_{b})=\\\
w_{G}(x_{a},x_{b})\Big{(}\prod_{ij\in
F_{1}}d_{ij}\Big{)}\cdot\prod_{i\in[k]-a-b}\Big{(}\sum_{x_{i}\in
V_{i}}w_{G}(x_{i},x_{b})\Big{)}\simeq\\\ w_{G}(x_{a},x_{b})\Big{(}\prod_{ij\in
F}d_{ij}\Big{)}\cdot\prod_{i\in[k]-a-b}|V_{i}|,\end{gathered}$

where the last approximation follows from (*** ‣ 9). For each of the $|F|$
approximations used, the incurred additive error on the whole expression was
at most $\pm\sqrt{\varepsilon}\prod_{i\in[k]-a-b}|V_{i}|$. ∎

We are now ready to prove Theorem 9.3. The proof strategy was outlined above:
map $G_{/\mathcal{P}}$ to a random copy of $F$ in $G$, where $F$ marks heavy-
enough edges of $G_{/\mathcal{P}}$.

###### Proof of Theorem 9.3.

Let $G$ be a graph with density $c:=\frac{E(G)}{n^{2}}$. Let
$\varepsilon_{0}<1$,
$\frac{1}{k}\leq\frac{c}{10}\frac{\varepsilon_{0}}{1+\varepsilon_{0}}$ and
$\varepsilon\leq\left(\frac{1}{k}\right)^{8k^{2}}$, and suppose $G$ has an
$\varepsilon$-regular $k$-partition $\mathcal{P}=(V_{1},\dots,V_{k})$. We
claim that $\mathrm{d}_{\mathrm{opt}}(G,G_{/\mathcal{P}})\leq\varepsilon_{0}$.
As mentioned above, $G\mathbin{\succeq}G_{/\mathcal{P}}$ holds trivially, so
it remains to show an overcast from $G_{/\mathcal{P}}$ to
$e^{-\varepsilon_{0}}G$.

Let $d_{ij}:=\frac{w_{G}(V_{i},V_{j})}{|V_{i}||V_{j}|}$ for $ij\in[k]^{2}$.
Let $F\subseteq\binom{[k]}{2}$ be the set of edges $ij$ such that $i\neq j$
and $d_{ij}\geq\frac{1}{k}$. Note that $\prod_{ij\in
F}d_{ij}\geq(\frac{1}{k})^{|F|}\geq\varepsilon^{1/8}$. Let $G^{\prime}$ be the
subgraph of $G$ obtained by removing:

  * •

$E(G[V_{i}])$, for $i\in[k]$ (the total weight removed in this step is $\leq
k\left(\frac{n}{k}\right)^{2}$)

  * •

$E_{G}(V_{i},V_{j})$, for $ij\not\in F$ (their total weight is $\leq
k^{2}\cdot\frac{1}{k}\cdot\left(\frac{n}{k}\right)^{2}$)

  * •

edges of weight $<\varepsilon^{1/8}$ (if $G$ is $[0,1]$-weighted; their total
weight is $\leq\varepsilon^{1/8}n^{2}$)

  * •

edges $x_{a}x_{b}\in V_{a}\times V_{b}$ for which the Extension Lemma 9.7 does
not hold, for each $ab\in F$ (their total weight is $\leq|F|\cdot
2k\sqrt{\varepsilon}\left(\frac{n}{k}\right)^{2}$).

The total weight of removed edges is

$\|G\|_{1}-\|G^{\prime}\|_{1}\leq
n^{2}(\frac{1}{k}+\frac{1}{k}+\varepsilon^{1/8}+2k\sqrt{\varepsilon})\leq
n^{2}\cdot\frac{5}{k}.$

By our assumption on $k$,
$\frac{5}{ck}\leq\frac{1}{2}\frac{\varepsilon_{0}}{1+\varepsilon_{0}}<1$.
Since $\|G\|_{1}\geq cn^{2}$,
$\operatorname{d_{1}}(G,G^{\prime})\leq\frac{\|G\|_{1}-\|G^{\prime}\|_{1}}{\min(\|G\|_{1},\|G^{\prime}\|_{1})}\leq\frac{n^{2}\cdot\frac{5}{k}}{n^{2}(c-\frac{5}{k})}=\frac{5/ck}{1-5/ck}\leq\varepsilon_{0}/2.$
Therefore, by Lemma D.2, $G^{\prime}\mathbin{\succeq}e^{-\varepsilon_{0}/2}G$
(this direction requires only $G^{\prime}$ to be clean, i.e. loop-less, which
is true because we removed $E(G[V_{i}])$ for all $i$). Thus it remains to show
that $G_{/\mathcal{P}}\mathbin{\succeq}e^{-\varepsilon_{0}/2}G^{\prime}$.

We define an overcast $\omega$ from $G_{/\mathcal{P}}$ to
$(1-\frac{\varepsilon_{0}}{1+\varepsilon_{0}})G^{\prime}$ as follows: every
$\mathcal{P}$-map $g\colon[k]\to V(G)$ is taken with probability proportional
to $\hom_{g}(F,G)$; that is, $\omega(g):=\hom_{g}(F,G)/N$ where by the
Counting Lemma 9.6, the normalisation factor is (using $\prod_{ij\in
F}d_{ij}\geq\varepsilon^{1/8}$):

$N:=\sum_{g}\hom_{g}(F,G)=\Big{(}\prod_{i\in[k]}|V_{i}|\Big{)}\Big{(}\prod_{ij\in
F}d_{ij}\ \pm\
\varepsilon|F|\Big{)}\leq\Big{(}\prod_{i\in[k]}|V_{i}|\Big{)}\Big{(}\prod_{ij\in
F}d_{ij}\Big{)}(1+\varepsilon^{7/8}k^{2}).$

To verify that $\omega$ is indeed an overcast, we need to check that for each
edge $uv$ of $G^{\prime}$

$\operatorname*{\mathbb{E}}_{g\sim\omega}w_{G_{/\mathcal{P}}}(g^{-1}(uv))\geq(1-\varepsilon^{\prime})w_{G}(u,v).$

Let $a,b\in[k]$ be such that $u\in V_{a}$ and $v\in V_{b}$. By the Extension
Lemma 9.7, since we removed from $G^{\prime}$ edges that don’t satisfy it and
edges with $w_{G}(u,v)<\varepsilon^{1/8}$, we have:

$\begin{gathered}N\cdot\operatorname*{\mathbb{E}}_{g\sim\omega}w_{G_{/\mathcal{P}}}(g^{-1}(uv))=\sum_{g\colon
g(a)=u,g(b)=v}\hom_{g}(F,G)w_{G_{/\mathcal{P}}}(a,b)=\\\
w_{G}(V_{a},V_{b})\sum_{g\colon g(a)=u,g(b)=v}\hom_{g}(F,G)=\\\
d_{ab}|V_{a}||V_{b}|\Big{(}\prod_{i\in[k]-a-b}|V_{i}|\Big{)}\Big{(}w_{G}(u,v)\prod_{ij\in
F-ab}d_{ij}\quad\pm\quad\sqrt{\varepsilon}|F|\Big{)}\geq\\\
\Big{(}\prod_{i\in[k]}|V_{i}|\Big{)}\Big{(}w_{G}(u,v)\prod_{ij\in F}d_{ij}\ -\
\sqrt{\varepsilon}k^{2}\Big{)}\geq\\\
\Big{(}\prod_{i\in[k]}|V_{i}|\Big{)}w_{G}(u,v)\Big{(}\prod_{ij\in
F}d_{ij}\Big{)}(1-\varepsilon^{1/4}k^{2}).\end{gathered}$

(The last inequality following from $w_{G}(u,v)\cdot\prod_{ij\in
F}d_{ij}\geq\varepsilon^{1/8}\cdot\varepsilon^{1/8}=\varepsilon^{1/4}$).
Dividing by the upper bound on $N$, we conclude:

$\operatorname*{\mathbb{E}}_{g\sim\omega}w_{G_{/\mathcal{P}}}(g^{-1}(uv))\geq
w_{G}(u,v)\frac{1-\varepsilon^{1/4}k^{2}}{1+\varepsilon^{7/8}k^{2}}$

The ratio here can be bounded quite brutally:

$\geq\frac{1-\varepsilon^{1/4}k^{2}}{1+\varepsilon^{1/4}k^{2}}\geq
1-2\varepsilon^{1/4}k^{2}\geq 1-\frac{2}{k}\geq
1-\frac{1}{2}\frac{\varepsilon_{0}}{1+\varepsilon_{0}}\geq\frac{1}{1+\varepsilon_{0}/2}\geq
e^{-\varepsilon_{0}/2}.$

This concludes the proof that
$G_{/\mathcal{P}}\mathbin{\succeq}e^{-\varepsilon_{0}/2}G^{\prime}$ and hence
$\mathrm{d}_{\mathrm{opt}}(G_{/\mathcal{P}},G)\leq\varepsilon_{0}$. ∎

##  10 Non-pliable structures

In this section we give examples of non-pliable classes. In the process we
show further equivalent definitions of pliability (Lemmas 10.5 and 10.6).

Recall that by Lemma 1.4, for a class of Gaifman graphs $\mathcal{G}$, the
class $\mathcal{A}_{\mathcal{G}}^{(2)}$ of all structures over $\mathcal{G}$
is $\operatorname{tw}$-pliable if and only if $\mathcal{G}$ is
fractionally-$\operatorname{tw}$-fragile. So the simplest examples of non-
pliable classes are $\mathcal{A}_{\mathcal{G}}^{(2)}$ for some non-
fractionally-fragile $\mathcal{G}$. Fractional-$\operatorname{tw}$-fragility
implies bounded expansion (a notion from the theory of sparse graphs
introduced by Nešetřil and Ossona de Mendez [NM08]) and sublinear separators,
e.g., 3-regular expander graphs are not
fractionally-$\operatorname{tw}$-fragile, see [Dvo16]. Hence for $\mathcal{G}$
the class of all 3-regular graphs, $\mathcal{A}_{\mathcal{G}}^{(2)}$ is not
$\operatorname{tw}$-pliable.

A somewhat more direct proof is to consider any class of 3-regular graphs of
high girth. Thomassen [Tho83] showed that such graphs behave much like graphs
of high average degree. We use essentially the same proof below:

######  Lemma 10.1.

For $\delta>0$ and $g\in\mathbb{N}$, every graph with average degree $\geq
2+\delta$ and girth $\geq 3g$ has a minor with average degree $\geq
g\delta+2$.

###### Proof.

Let $G=(V,E)$. Let $A_{1},\dots,A_{m}$ be a partition of $V$ into parts of
size $|A_{i}|\geq g$ that induce connected subgraphs, with $m$ maximum among
such partitions (clearly one exists with $m=1$).

We claim that each set $A_{i}$ induces a tree. Indeed, consider any spanning
tree $T$ of $G[A_{i}]$ and let $e$ be an edge of $G[A_{i}]$ outside of $T$.
Then $T+e$ contains a unique cycle, which must have length $\geq 3g\geq 2g$.
Hence one can remove $e$ and some other edge from this cycle to split it into
two intervals with $\geq g$ vertices. Removing these two edges from $T+e$
splits it into two components parts spanning $A_{i}$ with $\geq g$ vertices
each. Hence $A_{i}$ could be replaced with the vertex sets of these two
components, contradicting the choice of $m$.

Similarly, we claim that every two sets $A_{i},A_{j}$ are connected by at most
one edge. Otherwise two such edges together with spanning trees of $A_{i}$ and
$A_{j}$ would form a unicyclic graph, which could be split as above into three
connected parts with $\geq g$ vertices each.

Let $G^{\prime}=(E^{\prime},V^{\prime})$ be the graph resulting by contracting
the sets $A_{i}$. Since we contract sets of $\geq g$ vertices,
$|V^{\prime}|=m\leq\frac{|V|}{g}$. Since no two edges get identified and no
loop gets created/removed in the process, the number of contractions is equal
to $|E|-|E^{\prime}|$ and to $|V|-|V^{\prime}|$. Hence
$|E^{\prime}|=|E|-|V|+|V^{\prime}|\geq(\frac{2+\delta}{2}-1)|V|+|V^{\prime}|\geq(g\frac{\delta}{2}+1)|V^{\prime}|$,
so $G^{\prime}$ has average degree $\geq g\delta+2$. (We note that each
$G[A_{i}]$ had diameter $<2g-1$, as otherwise it could be split into two
parts; hence the minor we obtain is relatively _shallow_). ∎

######  Proposition 10.2.

Let $\delta>0$ and let $\mathcal{G}$ be a class of graphs with unbounded girth
and average degree $\geq 2+\delta$. Then $\mathcal{G}$ is not
fractionally-$\operatorname{tw}$-fragile.

###### Proof.

Suppose that $\mathcal{G}$ is fractionally-$\operatorname{tw}$-fragile. Then
for $\varepsilon=\frac{\delta}{2(2+\delta)}$ there is a $k=k(\varepsilon)$
such that every graph in $\mathcal{G}$ has a subset $F\subseteq E(G)$ with
$|F|\leq\varepsilon|E(G)|$ such that $\operatorname{tw}(G-F)\leq k$. Let
$G\in\mathcal{G}$ be a graph with girth $\geq\frac{12k}{\delta}$. Let $F$ be
as above. Then $\operatorname{tw}(G-F)\leq k$ and
$2|E(G-F)|\geq(1-\varepsilon)\cdot
2|E(G)|\geq(1-\varepsilon)(2+\delta)|V(G)|=(2+\frac{\delta}{2})|V(G-F)|$.
Therefore, $G-F$ has average degree $\geq(2+\frac{\delta}{2})$ and girth $\geq
3\cdot\frac{4k}{\delta}$, so by Lemma 10.1 it has a minor with average degree
$\geq 2+\frac{4k}{\delta}\frac{\delta}{2}>2k$. But a minor of $G-F$ must have
treewidth at most $\operatorname{tw}(G-F)\leq k$, so average degree $\leq 2k$,
a contradiction. ∎

We now turn to classes of structures with a fixed signature $\sigma$. We will
show that the class of tournaments is not $\operatorname{tw}$-pliable (or
equivalently, $\operatorname{size}$-pliable, by Theorem 1.5), in contrast to
cliques and dense graphs (Example 3.1 and Theorem 1.3).

######  Lemma 10.3.

Let $\mathcal{G}$ be a class of graphs of unbounded average degree. Let
$\mathcal{A}$ be the class of (unweighted) orientations of graphs in
$\mathcal{G}$. Then $\mathcal{A}$ is not size-pliable.

In order to prove Lemma 10.3, we will need some preparations and in particular
alternative characterisations of size-pliability.

For two $\sigma$-structures $\mathbb{A},\mathbb{B}$ and a function $g\colon
A\to B$, we define $\operatorname{\mathbb{I}m}(g)$ to be the
$\sigma$-structure on $B$ with
$f^{\operatorname{\mathbb{I}m}(g)}(\mathbf{x}):=\min\left(f^{\mathbb{A}}(g^{-1}(\mathbf{x})),f^{\mathbb{B}}(\mathbf{x})\right)$.
Note that $\operatorname{\mathbb{I}m}(g)\subseteq\mathbb{B}$ (meaning each
tuple has value in $\operatorname{\mathbb{I}m}(g)$ less than or equal its
value in $\mathbb{B}$).

######  Definition 10.4.

For a graph parameter $\operatorname{p}$, let $\bar{\operatorname{p}}$ be the
parameter defined as
$\bar{\operatorname{p}}(G):=\max_{i}(\operatorname{p}(G_{i}))$, where $G_{i}$
are the connected components of $G$. A parameter $\operatorname{p}$ is _good_
if $\bar{p}$-pliability is the same as size-pliability.

For example if $\operatorname{p}$ is size, then $\bar{\operatorname{p}}$ is
max component size, so size is a good parameter. All the other parameters in
Theorem 1.5 (cc, $\operatorname{td}$, $\operatorname{tw}$, Hadwiger) satisfy
$\bar{\operatorname{p}}=\operatorname{p}$ and are hence also good.

######  Lemma 10.5.

Let $\operatorname{p}$ be a good parameter. Then a class of
$\sigma$-structures $\mathcal{A}$ is size-pliable if and only if
$\forall_{\varepsilon>0}\exists_{k}\forall\mathbb{A}\in\mathcal{A}$ there is
an overcast $\omega$ from $\mathbb{A}$ to $(1-\varepsilon)\mathbb{A}$ such
that every $g\colon A\to A$ in its support has
$\operatorname{p}(\operatorname{\mathbb{I}m}(g))\leq k$.

###### Proof.

For one direction, suppose that for every $\varepsilon>0$ there is an integer
$k$ such that all $\mathbb{A}\in\mathcal{A}$ have an overcast $\omega$ from
$\mathbb{A}$ to $(1-\varepsilon)\mathbb{A}$ such that every $g:A\to A$ in its
support has $\operatorname{p}(\operatorname{\mathbb{I}m}(g))\leq k$. Then for
these $\varepsilon,k,\mathbb{A}$ we can take $\mathbb{B}$ to be the disjoint
union of rescaled structures
$\mathbb{B}_{g}:=\omega(g)\operatorname{\mathbb{I}m}(g)$. We have
$\bar{\operatorname{p}}(\mathbb{B})\leq k$. The overcast $\omega$ naturally
induces overcasts showing
$\mathbb{A}\mathbin{\succeq}\mathbb{B}\mathbin{\succeq}(1-\varepsilon)\mathbb{A}$.
Namely, we can define an overcast $\omega^{\prime}$ from $\mathbb{A}$ to
$\mathbb{B}$ by letting $\omega^{\prime}(g^{\prime})=\omega(g)$ for
$g^{\prime}$ mapping $A$ to $B_{g}\subseteq B$ just as $g$ maps $A$ to
$\operatorname{\mathbb{I}m}(g)\subseteq\mathbb{A}$. We can also define an
overcast $\omega^{\prime\prime}$ from $\mathbb{B}$ to
$(1-\varepsilon)\mathbb{A}$ by letting
$\omega^{\prime\prime}(g^{\prime\prime})=1$ for one function
$g^{\prime\prime}$ mapping each $\mathbb{B}_{g}\subseteq\mathbb{B}$ to
$\operatorname{\mathbb{I}m}(g)\subseteq\mathbb{A}$. Hence
$\mathrm{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B})\leq\mathcal{O}(\varepsilon)$,
which concludes the proof that $\mathcal{A}$ is
$\bar{\operatorname{p}}$-pliable.

In the other direction, suppose $\mathcal{A}$ is size-pliable, meaning for
every $\varepsilon>0$ there is an integer $k$ such that all $\mathbb{A}$ have
a $\mathbb{B}$ with
$\mathrm{d}_{\mathrm{opt}}(\mathbb{A},\mathbb{B})\leq\varepsilon$ and $|B|\leq
k$. This means there are overcast $\omega$ and $\omega^{\prime}$ showing
$\mathbb{A}\mathbin{\succeq}e^{-\varepsilon}\mathbb{B}$ and
$\mathbb{B}\mathbin{\succeq}e^{-\varepsilon}\mathbb{A}$, respectively. Then
composing $\omega$ with $\omega^{\prime}$ gives an overcast from $\mathbb{A}$
to $(1-2\varepsilon)\mathbb{A}$ (since $e^{-2\varepsilon}\geq
1-2\varepsilon$), with the property that all images of functions $g$ in the
support are of size at most $|B|\leq k$, which implies
$\operatorname{p}(\operatorname{\mathbb{I}m}(g))$ is bounded by some function
of $k$ (namely $\max\operatorname{p}(H)$ over all $k$-vertex graphs $H$). ∎

We can now use Farkas’ lemma to deduce another equivalent formulation:

######  Lemma 10.6.

Let $\operatorname{p}$ be a good parameter. Then a class of
$\sigma$-structures $\mathcal{A}$ is not size-pliable if and only if
$\exists_{\varepsilon>0}\forall_{k\in\mathbb{N}}$ there is a pair of
$\sigma$-structures $\mathbb{A}\in\mathcal{A}$ and $\mathbb{C}$ with $C=A$,
such that for every $g\colon A\to C$ with
$\operatorname{p}(\operatorname{\mathbb{I}m}(g))\leq k$,
$\operatorname{value}(g)<(1-\varepsilon)\operatorname{value}(\operatorname{id})$.
(Here $\operatorname{id}$ is the identity map from $A$ to $C=A$).

###### Proof.

By Lemma 10.5, $\mathbb{A}$ is not size-pliable if and only if
$\exists_{\varepsilon>0}\forall_{k\in\mathbb{N}}$ the following LP over
variables $\\{\omega(g)\colon g\in V\\}$, where $V:=\\{g\in
A^{A}\colon\operatorname{p}(\operatorname{\mathbb{I}m}(g))\leq k\\}$, has no
non-negative rational solution:

$\displaystyle\sum_{g\in
V}\omega(g)f^{\mathbb{A}}(g^{-1}(\mathbf{x}))\geq(1-\varepsilon)f^{\mathbb{A}}(\mathbf{x})$
$\displaystyle\forall(f,\mathbf{x})\in\text{tup}(\mathbb{A})$
$\displaystyle\sum_{g\in V}\omega(g)=1$

By applying Lemma Lemma (Farkas’ lemma), this is equivalent to the existence
of a non-negative vector
$(y(f,\mathbf{x}))_{(f,\mathbf{x})\in\text{tup}(\mathbb{A})}$ such that

$\sum_{(f,\mathbf{x})\in\text{tup}(\mathbb{A})}y(f,\mathbf{x})f^{\mathbb{A}}(g^{-1}(\mathbf{x}))<(1-\varepsilon)\sum_{(f,\mathbf{x})\in\text{tup}(\mathbb{A})}y(f,\mathbf{x})f^{\mathbb{A}}(\mathbf{x})\quad\quad\quad\forall
g\in V$

Let $\mathbb{C}$ be the $\sigma$-structure on $C=A$ with
$f^{\mathbb{C}}(\mathbf{x}):=y(f,\mathbf{x})$. Then the above inequality is
restated as follows (interpreting $g\in V$ and $\operatorname{id}$ as maps
from $\mathbb{A}$ to $\mathbb{C}$):

$\operatorname{value}(g)<(1-\varepsilon)\operatorname{value}(\operatorname{id})\quad\quad\quad\forall{g\in
V}.\qed$

######  Remark 10.7.

The structures $\mathbb{A},\mathbb{C}$ obtained above can be assumed to
satisfy $\operatorname{G}(\mathbb{A})=\operatorname{G}(\mathbb{C})$ without
loss of generality, because for any $(f,\mathbf{x})\in\text{tup}(\mathbb{A})$
such that one of $f^{\mathbb{A}}(\mathbf{x})$ or $f^{\mathbb{C}}(\mathbf{x})$
is zero, decreasing the other to zero will not change
$\operatorname{value}(\operatorname{id})$ and can only decrease
$\operatorname{value}(g)$.

###### Proof of Lemma 10.3.

Let $\varepsilon$ be a constant to be chosen later ($\frac{1}{10}$ will do).
Given any $k$, let $G\in\mathcal{G}$ be a graph with $m\geq
20\cdot\binom{k}{2}$ edges, $n$ vertices, and average degree $\frac{2m}{n}\geq
100\log_{2}k$. Let $\mathbb{A}$ be a random orientation of $G$ (each edge is
independently oriented in either direction with probability $\frac{1}{2}$). We
claim that with positive probability $\mathbb{A}$ admits no map $g\colon A\to
A$ to itself with image of size at most $k$ such that
$\operatorname{value}(g)\geq(1-\varepsilon)\operatorname{value}(\operatorname{id})$.
This will prove that $\mathcal{A}$ satisfies the conditions of Lemma 10.6 and
hence is not size-pliable.

If a map as above existed, it would imply the existence of an oriented graph
$D$ (with at most one arc between every two vertices) on at most $k$ vertices
and a function $g\colon A\to V(D)$ with
$\operatorname{value}(g)\geq(1-\varepsilon)m$. Observe that
$\operatorname{value}(g)$ is the number of arcs of $\mathbb{A}$ that are
correctly mapped by $g$ (i.e. to an arc of $D$ with the same orientation).
Hence there would be a set $F$ of at most $\varepsilon m$ arcs of $\mathbb{A}$
such that $g$ maps all arcs of $\mathbb{A}-F$ correctly. Let us bound the
probability that there exists such $D,F,g$. The number of possible $D$ is
$\leq 3^{\binom{k}{2}}$; the number of possible $F$ is
$\leq\sum_{i=0}^{\varepsilon m}\binom{m}{i}\leq 2^{H(\varepsilon)m}$ for a
certain function $H(\varepsilon)$ satisfying $\lim_{\varepsilon\to
0}H(\varepsilon)=0$ (specifically,
$H(\varepsilon)=\varepsilon\log_{2}(\frac{1}{\varepsilon})+(1-\varepsilon)\log_{2}(\frac{1}{1-\varepsilon})$
is the binary entropy function); the number of possible $g$ is $\leq k^{n}$.
Note that $\frac{2m}{n}\geq 100\log_{2}k$ and $3^{\binom{k}{2}}\leq 2^{m/10}$
by our choice of $G$. For fixed $D,F,g$, the probability that $g$ maps all
arcs of $\mathbb{A}-F$ correctly to $D$ is at most
$(\frac{1}{2})^{(1-\varepsilon)m}$. Hence in total the probability that some
such $D,F,g$ exist is at most

$3^{\binom{k}{2}}\cdot 2^{H(\varepsilon)m}\cdot k^{n}\cdot
2^{-(1-\varepsilon)m}\leq
2^{n\log_{2}k-(1-\varepsilon-H(\varepsilon)-\frac{1}{10})m}\leq
2^{-(1-\varepsilon-H(\varepsilon)-\frac{1}{10}-\frac{1}{50})\cdot m}.$

This is less than 1 for $\varepsilon$ small enough so that
$1-\varepsilon-H(\varepsilon)-\frac{1}{10}-\frac{1}{50}>0$. ∎

Finally, not all classes of bounded degree give pliable classes, even with a
fixed signature.

######  Lemma 10.8.

Let $\mathcal{G}$ be a class of graphs with unbounded girth and average degree
$\geq 2+\delta$ ($\delta>0$). Let $\mathcal{A}$ be the class of (unweighted)
orientations of graphs in $\mathcal{G}$. Then $\mathcal{A}$ is not size-
pliable.

###### Proof.

We show there exists an $\varepsilon$ such that for all $k$, there is an
orientation $\mathbb{A}\in\mathcal{A}$ of a graph in $\mathcal{G}$ such that
every function $g\colon\mathbb{A}\to\mathbb{A}$ with
$\operatorname{cc}(\operatorname{\mathbb{I}m}(g))\leq k$ has
$\operatorname{value}(g)<(1-\varepsilon)\operatorname{value}(\operatorname{id})$.
We choose $\varepsilon$ later depending on $\delta$ only.

For any given $k$, let $G\in\mathcal{G}$ be a graph of girth $>k$. Let
$m=|E(G)|$. Let $\mathcal{A}$ be a random orientation of $G$: every edge is
independently oriented in one direction or the other. We claim that the
probability that there exists a $g\colon\mathbb{A}\to\mathbb{A}$ with
$\operatorname{cc}(\operatorname{\mathbb{I}m}(g))\leq k$ and
$\operatorname{value}(g)\geq(1-\varepsilon)\operatorname{value}(\operatorname{id})$
is strictly less than one (so there exists an orientation that satisfies our
goal). Note that $\operatorname{value}(\operatorname{id})=m$ and