paraNP [ie]i.e [eg]e.g

# Parameterized Algorithms for Zero Extension and Metric Labelling Problems

Felix Reidl  Royal Holloway, University of London, TW20 0EX, UK
<EMAIL_ADDRESS>Magnus Wahlström  Royal Holloway,
University of London, TW20 0EX, UK
<EMAIL_ADDRESS>
###### Abstract

We consider the problems Zero Extension and Metric Labelling under the
paradigm of parameterized complexity. These are natural, well-studied problems
with important applications, but have previously not received much attention
from parameterized complexity.

Depending on the chosen cost function $\mu$, we find that different
algorithmic approaches can be applied to design -algorithms: for arbitrary
$\mu$ we parameterized by the number of edges that cross the cut (not the
cost) and show how to solve Zero Extension in time $O(|D|^{O(k^{2})}n^{4}\log
n)$ using randomized contractions. We improve this running time with respect
to both parameter and input size to $O(|D|^{O(k)}m)$ in the case where $\mu$
is a metric. We further show that the problem admits a polynomial _sparsifier_
, that is, a kernel of size $O(k^{|D|+1})$ that is _independent of the metric_
$\mu$.

With the stronger condition that $\mu$ is described by the distances of leaves
in a tree, we parameterize by a _gap parameter_ $(q-p)$ between the cost of a
true solution $q$ and a ‘discrete relaxation’ $p$ and achieve a running time
of $O(|D|^{q-p}|T|m+|T|\phi(n,m))$ where $T$ is the size of the tree over
which $\mu$ is defined and $\phi(n,m)$ is the running time of a max-flow
computation. We achieve a similar running for the more general Metric
Labelling, while also allowing $\mu$ to be the distance metric between an
arbitrary subset of nodes in a tree using tools from the theory of VCSPs. We
expect the methods used in the latter result to have further applications.

##  1 Introduction

The task of extending a partial labelling of a few data points to a full data
set while minimizing some error function is a natural computational step for
scientific and engineering tasks. For the particular case of data imposed with
a (binary) relationship, we find that the problems Zero Extension and Metric
Labelling are well-suited for optimization in image processing111The recent
advent of convolutional neural networks seems to have lessened the importance
here, but Metric Labelling is still used (for a recent example see [20]) [1],
Markov Random Fields [32], social network classification [27, 2], or sentiment
analysis in natural language processing [29].

The problem settings are as follow. For Zero Extension, we are given a graph
$G$ and a partial labelling $\tau\colon S\to D$, for some set of terminals
$S\subseteq V(G)$, alongside a cost function $\mu\colon D\times
D\to\mathbb{R}^{+}$. Our task is to compute a labelling $\lambda\colon V(G)\to
D$ which agrees with $\tau$ on $S$, subject to the following cost: for each
edge $uv\in G$ we pay the cost $\mu(\lambda(u),\lambda(v))$. In Metric
Labelling, we are given a graph $G$, a cost function $\mu$ as above, and a
_labelling cost_ $\sigma\colon V(G)\times D\to\mathbb{R}^{+}$. Again we are
asked to compute a labelling $\lambda$ and in addition to the above edge-costs
we now also pay $\sigma(v,\lambda(v))$ for each vertex. Note that this model
allows us to emulate terminals, by making the cost $\sigma(v,\lambda(v))$
prohibitive for all but the required label $\lambda(v)$. Both problems are
generalizations of the Multiway Cut problem (we simply let $\mu$ be
identically one for all distinct pairs), which has garnered considerable
attention from the $\FPT$ community in the past and formed a crystallization
nucleus for the very fruitful research of cut-based problems (see [23, 19, 4,
13, 25]).

We will find application for most of these tools in our results listed below,
but we wish to particularly highlight the use of tools and relaxations from
_Valued CSPs_ (VCSPs) for designing $\FPT$ algorithms under gap parameters.
VCSPs are a general framework for expressing optimisation problems, via the
specification of a set $\Gamma$ of _cost functions_ (also referred to as a
_constraint language_). Many important problems correspond to VCSP for a
specific language $\Gamma$, including every choice of a specific metric for
the problems above. Thapper and Živný [33] characterized the languages
$\Gamma$ for which the resulting VCSP is tractable.

The use of a tractable VCSP as a _discrete relaxation_ of an NP-hard
optimisation problem has previously been used for the design of surprisingly
powerful $\FPT$ algorithms [13] (see also related improvements [14, 35]). In
this paper, we advance this research in two ways. First, previous algorithms
of this type have required the relaxation to have a _persistence_ property,
which allows an optimum to be found by sequentially fixing variables. In this
paper, we relax this condition to a weaker _domain consistency_ property.
Second, we use a folklore result from VCSP research to restrict the behaviour
of optimal solutions to a VSCP instance in order to facilitate the proof that
the domain consistency property holds for the relevant VCSPs. See Section 5
for details.

Related work. So far, Zero Extension and Metric Labelling have been researched
primarily from the perspective of efficient and approximation algorithms (for
a more complete overview and hardness results we refer to the paper by
Manokaran, Naor, Raghavendra and Schwartz [22]). Kleinberg and Tardos [32]
introduced Metric Labelling and provided a $O(\log|S|\log\log|S|)$
approximation. A result by Fakcharoenphol, Rao, and Talwar regarding embedding
general metrics into tree metrics [8] improves the ratio of this algorithm to
$O(\log|S|)$ and a lower bound of
$O((\log|S|)^{\nicefrac{{1}}{{2}}-\varepsilon})$ was proved by Chuzhoy and
Naor [5]. Karzanov [16] introduced Zero Extension with the specific case of
$\mu$ being a graph metric, that is, equal to the distance metric of some
graph $H$. The central question of his work—for which graphs $H$ the problem
is tractable—was just recently fully answered by Hirai [11]. Picard and
Ratliff much earlier showed that an equivalent problem is tractable on trees
[30]. Fakcharoenphol, Harrelson, Rao, and Talwar showed that the problem can
be approximation to within a factor of $O(\log|S|/\log\log|S|)$ [7]. Karloff,
Khot, Mehta, Rabani used the approach by Chuzhoy and Naor to show that no
factor of $O((\log|S|)^{\nicefrac{{1}}{{4}}-\varepsilon})$ for any
$\varepsilon>0$ is possible unless $\NP\subseteq\QP$ [15]. More recently,
Hirai and Pap [10, 12] studied the problem from a more structural angle and we
make use of their duality result in the following.

Our results. In this paper we study both problems from the perspective of
parameterized complexity. As the choice of metric has a strong effect on the
complexity of the problem, we give a range of results, ranging from the more
generally applicable to the algorithmically stronger, both in terms of running
time and parameterization. In the most general setting, when $\mu$ is a
general cost function or a metric, we will parametrize not by the _cost_ of a
solution but by the number of _crossing edges_ which are precisely the
bichromatic edges under a labelling $\lambda$. This in particular allows us to
include the case of zero cost pairs under $\mu$. For general cost functions,
we employ the technique of randomized contractions [4] and prove the
following:

######  Theorem 1.1.

Zero Extension can be solved in time $O(|D|^{O(k^{2})}n^{4}\log n)$ where $k$
is a given upper bound on the number of crossing edges in the solution.

When $\mu$ is a metric, we are able to give a linear-time $\FPT$ algorithm,
while also improving the dependency on the parameter, using important
separators [23]:

######  Theorem 1.2.

Zero Extension with metric cost functions can be solved in time
$O(|D|^{O(k)}\cdot m)$ where $k$ is a given upper bound on the number of
crossing edges in the solution.

For the general metric setting, we also have our most surprising result,
demonstrating that Zero Extension admits a _sparsifier_ ; that is, we prove
that it admits a polynomial kernel _independent of the metric $\mu$_. This
result crucially builds on the technique of _representative sets_ [19, 24,
21]. The exact formulation of the result is somewhat technical and we defer it
to Section 4.3, but roughly, we obtain a kernel of size $O(k^{|S|+1})$,
independent of $\mu$, where $k$ is again the number of crossing edges. This
result is a direct, seemingly far-reaching generalization of the polynomial
kernel for $s$-Multiway Cut [19].

Next, we consider the case when $\mu\colon D\to\mathbb{Z}^{+}$ is induced by
the distance in a tree $T$ with $D\subset V(T)$. Here, relaxing the problem to
allow all labels $V(T)$ as vertex values defines a tractable discrete
relaxation, in the sense discussed above. Using techniques from VCSP, we
design a gap-parameter algorithm:

######  Theorem 1.3.

Let $I=(G,\tau,\mu,q)$ be an instance of Zero Extension where $\mu$ is an
induced tree metric on a set of labels $D$ in a tree $T$, and let
$\hat{I}=(G,\tau,\hat{\mu},q)$ be the relaxed instance. Let
$p=\operatorname{\mathbf{cost}}(\hat{I})$. Then we can solve $I$ in time
$O(|D|^{q-p}|T||D|nm)$.

For the further restriction when $\mu$ corresponds to the distances of the
leaves $D$ of a tree $T$, we obtain an algorithm with a slightly better
polynomial dependence. Moreover, it uses only elementary operations like
computing cuts and flows:

######  Theorem 1.4.

Let $I=(G,\tau,\mu,q)$ be an instance of Zero Extension where $\mu$ is a leaf
metric on a set of labels $D$ in a tree $T$, and let
$\hat{I}=(G,\tau,\hat{\mu},q)$ be the relaxed instance. Let
$p=\operatorname{\mathbf{cost}}(\hat{I})$. Then we can solve $I$ in time
$O(|D|^{q-p}|T|m+|T|\phi(n,m))$, where $\phi$ is the time needed to run a max-
flow algorithm.

Finally, we apply the VCSP toolkit to Metric Labelling and obtain a similar
gap algorithm (see Section 5 for undefined terms).

######  Theorem 1.5.

Let $I=(G,\sigma,\mu,q)$ be an instance of Metric Labelling where $\mu$ is an
induced tree metric for a tree $T$ and a set of nodes $D\subseteq V(T)$, and
where every unary cost $\sigma(v,\cdot)$ admits an interpolation on $T$. Let
$\hat{I}=(G,\hat{\sigma},\hat{\mu},q)$ be the relaxed instance, and let
$\rho=\operatorname{\mathbf{cost}}(\hat{I})$. Then the instance $I$ can be
solved in time $O^{*}(|D|^{q-\rho})$. In particular, this applies for any
$\sigma$ if $D$ is the set of leaves of $T$.

##  2 Preliminaries

For a graph $G=(V,E)$ we will use $n_{G}=|V|$ and $m_{G}=|E|$ to denote the
number of vertices and edges, respectively. We write $\operatorname{d}_{G}$
for the distance-metric induced by $G$, that is, $\operatorname{d}_{G}(u,v)$
is the length of a shortest path between vertices $u,v\in V(G)$. We denote by
$N_{G}(v)$ and $N_{G}[v]$ the open and closed neighbourhood of a vertex. For a
vertex set $S\subseteq V(G)$ we write $\delta(S)$ to denote the set of edges
with exactly one endpoint in $S$. We omit the subscript $G$ if clear from the
context all these notations.

For a tree $T$ we call a sequence of nodes $x_{1}x_{2}\ldots x_{p}$ a
_monotone sequence_ if
$x_{1}\leqslant_{P}x_{2}\leqslant_{P}\ldots\leqslant_{P}x_{p}$ where $P$ is a
path in $T$ and $\leqslant_{P}$ is the linear order induced by $P$. Note that
$x_{i}=x_{i+1}$ is explicitly allowed. For two nodes $x,y\in T$ we will denote
the unique $x$-$y$-path in $T$ by $T[x,y]$. For a vertex set $S$, an _$S$
-path packing_ is a collection of edge-disjoint paths $\mathcal{P}$ that
connect pairs of vertices in $S$. We will also consider _half-integral_ path
packings, here every edge of the graph is allowed to be used by up to two
paths.

Let $D$ be a set of labels. For a graph $G$ we call a function $\tau\colon
S\to D$ for $S\subseteq V(G)$ a _partial labelling_ and a function
$\lambda\colon V(G)\to D$ a _labelling_. The labelling $\lambda$ is an
_extension_ of $\tau$ if $\lambda$ and $\tau$ agree on $S$, that is, for every
vertex $u\in S$ we have that $\lambda(u)=\tau(u)$. Given a graph $G$ and a
labelling $\lambda$ we call an edge $uv\in E(G)$ _crossing_ if
$\lambda(u)\neq\lambda(v)$. A _$\tau$ -path packing_ is a collection
$\mathcal{P}$ of edge-disjoint paths such that every path $P\in\mathcal{P}$
connects to vertices that receive distinct labels under $\tau$ (and both are
labelled).

###  2.1 Cost functions, metrics, and extensions

A _cost function_ over $D$ is a symmetric positive function $\mu\colon D\times
D\to\mathbb{R}^{+}$. We call it _simple_ if $\mu(x,x)=0$. A cost function is a
a _metric_ if further it obeys the triangle inequality and it is a _tree
metric_ if it corresponds to the distance metric of a tree. We derive an
_induced tree metric_ from a tree metric by restricting its domain to a subset
$D$ of the nodes of the underlying tree. A _leaf metric_ is an induced tree
metric where $D$ is the set of leaves of the tree. Given a cost function
$\mu$, we define the cost of a labelling $\lambda$ of a graph $G$ under a cost
function $\mu$ as

$\operatorname{\mathbf{cost}}_{\mu}(\lambda,G)=\sum_{uv\in
G}\mu(\lambda(u),\lambda(v)).$

With these definitions in place, we can now define the problem in question:

Input: A graph $G$ with a partial labelling $\tau$ over a finite domain $D$, a
simple cost function $\mu$ over $D$ and an integer $q$. Problem: Does $G$
admit an extension $\lambda$ of $\tau$ such that
$\operatorname{\mathbf{cost}}_{\mu}(\lambda,G)\leqslant q$? Zero Extension
parametrised by

For cost functions $\mu$ that are uniform on all non-diagonal values we
recover (up to some constant scaling of the parameter) the problem Multiway
Cut. Picard and Ratliff proved that for tree metrics, the problem222They prove
it for a variant of the Facility Location problem. is solvable in polynomial
time [30]. We will call the special case in which the distance function is
restricted to a leaf metric Zero Leaf Extension.

##  3 Cost functions: Randomized Contractions

We will apply the framework by Chitnis [4] to show that the most general case
of Zero Extension is in $\FPT$ when parameterized by the number of crossing
edges. Note that in this setting crossing edges could incur an arbitrary cost,
including zero. However, the stronger parameterization of only counting the
number of crossing edges at non-zero cost makes for an intractable problem:
With such zero-cost edges, we can express the problem $H$-Retraction for
reflexive graphs $H$, which asks us to compute a retraction of a graph $G$
into the fixed graph $H$. This problem is already -complete for $H$ being the
reflexive $4$-cycle [34] and thus Zero Extension is -complete for parameter
$k=0$ if parameterized by the number of non-zero-cost crossing edges (or
indeed if parameterized by the total cost).

A  _$(\sigma,\kappa)$ -good_ separation is a partition $(L,R)$ of $V(G)$ such
that $|L|,|R|>\sigma$, $|E(L,R)|\leqslant\kappa$, and both $G[L]$ and $G[R]$
are connected. There exists an algorithm that finds a $(\sigma,\kappa)$-good
separation in time $O((\sigma+\kappa)^{O(\min(\sigma,\kappa))}n^{3}\log n)$
(Lemma 2.2 in [4]) or concludes that the graph is _$(\sigma,\kappa)$
-connected_, that is, no such separation exists. The following lemma is a
slight reformulation of Lemma 1.1 in [4] which in turn is based on splitters
as defined by Noar [26]:

######  Lemma 3.1 (Edge splitter).

Given a set $E$ of size $m$ and integers $0\leqslant a,b\leqslant m$ one can
in time $O((a+b)^{O(\min\\{a,b\\})}m\log m)$ construct a set family
$\mathcal{F}$ over $E$ of size at most $O((a+b)^{O(\min\\{a,b\\})}\log m)$
with the following property: for any disjoint sets $A,B\subseteq E$ with
$|A|\leqslant a$ and $|B|\leqslant b$ there exists a set $H\in\mathcal{F}$
with $A\subseteq H$ and $B\cap H=\emptyset$.

Let us first demonstrate how Zero Extension can be solved on such highly
connected instances and then apply the ‘recursive understanding’ framework to
handle graphs with good separations. In the following, let $I=(G,\tau,\mu,q)$
be the input instance with $\mu$ being a cost function over the domain $D$.

######  Lemma 3.2.

Let $G$ be $(\sigma,k)$-connected for some $\sigma>k$. Then we can find an
optimal solution in time $O((|D|+2\sigma k+k)^{O(k)}(n+m)\log n)$.

###### Proof.

Let $\lambda\in\operatorname{\mathbf{opt}}(I)$ be an optimal solution and let
$E_{\lambda}$ be the crossing edges. We write $V(E_{\lambda})$ to denote the
endpoints of these edges. Let $C_{0},C_{1},\ldots,C_{\ell}$ be the connected
components of $G-E_{\lambda}$ with $C_{0}$ being the largest one. Since the
sets $C_{i}$ have only one label each under $\lambda$, each one contains at
most one terminal.

Since $G$ is $(\sigma,k)$-connected, we know that $\ell\leqslant k$ and that
all components $C_{1},\ldots,C_{\ell}$ have size at most $\sigma$ (Lemma 3.6
[4]). We will assume in the following that $C_{0}$ contains more than $\sigma$
vertices, otherwise $G$ contains less than $\sigma k$ vertices and we find the
set $E_{\lambda}$ in time $O((\sigma k)^{2k})$ by brute-force.

Otherwise, we proceed by colouring the edges of $G$ using an edge splitter
(details below). Such a colouring is _successful_ if

  1. 1.

the crossing edges $E_{\lambda}$ are red;

  2. 2.

each component $C_{i}$, $1\leqslant i\leqslant\ell$, contains a blue spanning
tree; and

  3. 3.

each vertex $u\in C_{0}\cap V(E_{\lambda})$ is contained in a blue tree of
size at least $\sigma+1$.

By fixing a collection of (arbitrary) spanning trees for the components
$C_{i}$, $1\leqslant i\leqslant\ell$ and a collection of trees in $C_{0}$ with
$\sigma+1$ vertices that contain the $\leqslant k$ boundary vertices
$C_{0}\cap V(E_{\lambda})$ we can see that we need to correctly colour a set
$B\subseteq E(G)$ of at most $(\sigma-1)\ell+\sigma k\leqslant 2\sigma k$
edges blue while colouring a set $R\subseteq E(G)$ of at most $k$ edges red.
We apply Lemma 3.1 with $a=2\sigma k$ and $b=k$ to construct an edge splitter
$\mathcal{F}$ of size at most $O((2\sigma k+k)^{O(k)}\log m)$ in time
$O((2\sigma k+k)^{O(k)}m\log m)$ for which we are guaranteed that at least one
member $H\in\mathcal{F}$ will contain $B$ while avoiding $R$.

It is left to show that we can easily find a solution in successfully coloured
graph. Let $G_{B}$ be the graph induced by the blue edges. We will call a
component of $G_{B}$ _small_ if it contains $q$ or less vertices and _big_
otherwise. Our task is to recover the solution-induced components
$C_{0},C_{1},\ldots,C_{\ell}$. First notice that every $C_{i}$, $i\geqslant 1$
must be a small component in $G_{B}$ and further that all components reachable
from $C_{i}$ via red edges must either be another component $C_{j}$,
$j\geqslant 1$, _or_ be a big component in $G_{B}$. Thus, we ‘discover’ the
sets $C_{1},\ldots,C_{\ell}$ by the following marking algorithm:

  1. 1.

Guess which terminal $x$ lies in the big component $C_{0}$

  2. 2.

Mark all small components of $G_{B}$ that contain terminals other than $x$

  3. 3.

Repeat exhaustively: mark all small components of $G_{B}$ which have a red
edge into an already marked component.

If our initial guess of $x$ is correct this procedure will exactly mark the
components $C_{1},\ldots,C_{\ell}$. Indeed, any small component $C_{i}$ not
marked by this process would be a small component containing no terminal and
with all edges of $E_{\lambda}$ connecting to the big component, in which case
there is a solution with at most the same cost which merges $C_{i}$ with
$C_{0}$. The same holds for any collection of small components with no red
edge to a marked component. From this we can deduce $C_{0}$, the crossing
edges $E_{\lambda}$, and $\lambda$ itself. In case the colouring step was
unsuccessful or our guess of $x$ was wrong, the above procedure will produce
some set of edges $E_{\lambda}$ of non-minimal cost.

This verification step, given a colouring, is possible in time $O((n+m)|S|)$.
Since $G$ is connected, we can assume that $|S|\leqslant k$ and the total
running time to identify $E_{\lambda}$ is $(2\sigma k+k)^{O(k)}(n+m)\log n$.
Given $E_{\lambda}$, the final step is to find an optimal assignment. While
the assigment for components $C_{i}$ containing terminals is fixed, we need to
try all possible assigments for the remaining components in time
$O(|D|^{\ell}k)=O(|D|^{k}k)$. Taken both steps together yields the claimed
running time. ∎

With the well-connected cases handled we can now proceed to solve the general
problem.

See 1.1

###### Proof.

We will assume that $G$ is connected (otherwise we compute an optimal solution
for every connected component), therefore the number of terminals $|S|$ is
bounded by $k+1$. Let $\sigma:=|D|^{k}+1$. We run the algorithm of Chitnis [4]
to find a $(\sigma,k)$-good separation. Assume for now that such a good
separation $(V_{1},V_{2})$ is found with at most $k$ edges $E(V_{1},V_{2})$
crossing it.

Let $S_{1}:=E(V_{1},V_{2})\cap V_{1}$ be the $\leqslant k$ vertices in $S_{1}$
on the border of the separation. We iterate through all
$|D|^{|S_{1}|}\leqslant|D|^{k}$ ways the vertices $S_{1}$ could receive
colours by a solution. For each such colouring $\tau$, we construct a sub-
instance $G_{\tau}$ by identifying all vertices that have the same terminal-
labelling and recursively solve the instance. For each solution of $G_{\tau}$
with at most $k$ crossing edges we collect said crossing edges in $E^{*}$.
That is, the set $E^{*}$ contains all edges that are crossing for an optimal
solution of _some_ labelling of $S_{1}$. Note that $|E^{*}|<\sigma$ by our
choice of $\sigma$. Since $G_{1}$ is connected, there is at least one edge in
$\hat{E}=E(G_{1})\setminus E^{*}$. Now, every solution $\lambda$ of $G$ that
has at most $k$ crossing edge can be modified to have only edges of $E^{*}$
and thus no edges of $\hat{E}$ crossing it; we simply observe what labelling
$\tau$ the solution $\lambda$ applies to $S_{1}$ and replace the colour
$\lambda$ applies to $V_{1}$ for the colours that the optimal solution of
$G_{\tau}$ applies to it.

Consequently, we can assume that the optimal solutions we are interested in
are not crossed by $\hat{E}$, therefore it is safe to contract $\hat{E}$ and
therefore reduce the size of $V_{1}$ to $\sigma$ (recall that $G[V_{1}]$ is
connected and the contraction of course preserves that property). We repeat
this procedure until the resulting graph is $(\sigma,k)$-connected
(alternatively, any of the recursive calls could tell us that no solution with
at most $k$ crossing edges exists in which case we return that the instance
has no solution). Then by Lemma 3.2, we can decide the problem in time
$O((|D|+2\sigma k+k)^{O(k)}(n+m)\log n)=O(|D|^{O(k^{2})}n^{2}\log n)$.

Let us now analyse the total running time $T(n)$; note that $k$ and $\sigma$
do not change with each recursive call. First, finding a good separation takes
time $O((\sigma+k)^{O(k)}n^{3}\log n)=O(|D|^{O(k^{2})}n^{3}\log n)$ and
constructing the instance $G_{\tau}$ at total of $O(|D|^{k}(n+m))$, which is
dominated by the former running time. The recursive call on $V_{1}$ with
$n_{1}:=|V_{1}|$ costs us $T(n_{1})$, after which we are left to work on an
instance of size at most $n-n_{1}+\sigma$ which will cost us
$T(n-n_{1}+\sigma)$. Note that, by the properties of $(\sigma,k)$-good
separations, it holds that $\sigma+1\leqslant n_{1}\leqslant n-\sigma-1$. We
therefore need to resolve the recurrence

$T(n)\leqslant\max_{\sigma+1\leqslant n_{1}\leqslant
n-\sigma-1}\Big{(}|D|^{O(k^{2})}n^{3}\log
n+T(n_{1})+T(n-n_{1}+\sigma)\Big{)}.$

As noted in [4], the maximum in this expression is attained at the extreme
values for $n_{1}$ and that the claimed running time is a bound on $T(n)$. ∎

##  4 General metrics: Pushing separators

We now consider the more restricted, but reasonable case that $\mu$ is a
metric, observing the triangle inequality. We find that this allows a ‘greedy’
operation of _pushing_ in a solution $\lambda$, which allows both the design
of a faster algorithm (Section 4.2) and the computation of a _metric
sparsifier_ (Section 4.3).

###  4.1 The pushing lemma

Let in the following $I=(G=(V,E),\tau,\mu,q)$ be an instance of Zero Extension
for an arbitrary metric $\mu$. Let $S\subseteq V$ be the range of $\tau$, and
let $D$ be the set of labels. We assume that the following reductions have
been performed on $G$: For every label $\ell$ used by $\tau$ there is a
terminal $t_{\ell}$, and every vertex $v$ such that $\tau(v)=\ell$ has been
identified with this terminal $t_{\ell}$.

Let $\lambda\colon V\to D$ be an extension of $\tau$, and let
$U=\lambda^{-1}(\ell)$ for some $\ell\in D$. By _pushing from $\ell$ in
$\lambda$_ we refer to the operation of relabelling vertices to grow the set
$U$ “as large as possible”, without increasing the number of crossing edges.
Formally, this refers to the following operation: Let $C$ be the furthest min-
cut between vertex sets $U$ and $S-t_{\ell}$ (respectively $S$ if there is no
terminal $t_{\ell}$), let $U^{\prime}$ be the vertices reachable from $U$ in
$G-C$, and let $\lambda^{\prime}$ be the labelling where
$\lambda^{\prime}(v)=\ell$ for $v\in U^{\prime}$ and
$\lambda^{\prime}(v)=\lambda(v)$ otherwise. Clearly, $\lambda^{\prime}$ is an
extension of $\tau$. The purpose of this section is to show that as long as
$\mu$ is a metric (in particular, observes the triangle inequality), this
operation does not increase the cost of the solution.

######  Lemma 4.1 (Pushing Lemma).

For any $\tau$-extension $\lambda$ and every label $\ell\in D$, pushing from
$\ell$ in $\lambda$ yields a $\tau$-extension $\lambda^{\prime}$ with
$\operatorname{\mathbf{cost}}_{\mu}(\lambda^{\prime},G)\leqslant\operatorname{\mathbf{cost}}_{\mu}(\lambda,G)$.

###### Proof.

Write $V_{\ell}=\lambda^{-1}(\ell)$, and for a set of vertices $U$ let
$\delta(U)$ denote the edges with one endpoint in $U$. Let $\mathcal{P}$ be a
max-flow from $V_{\ell}$ to the set $S-t_{\ell}$, let $C$ be a furthest
corresponding min-cut, and let $V_{\ell}^{+}\supseteq V_{\ell}$ be the set of
vertices reachable from $t_{\ell}$ in $G^{\prime}-C$. By Menger’s theorem,
$\mathcal{P}$ partitions the set of edges $\delta(V_{\ell}^{+})$. Finally, let
$\mathcal{P}^{-}$ consist of the prefixes of the paths $P\in\mathcal{P}$ up
until and including the edges of $C$. For $P\in\mathcal{P}^{-}$, let
$\lambda(P)$ be the label of its final edge. Let $\lambda^{\prime}$ be the
assignment resulting from letting $\lambda^{\prime}(v)=\ell$ for every $v\in
V_{\ell}^{+}$ and $\lambda^{\prime}(v)=\lambda(v)$ otherwise. We make two
quick observations.

######  Claim.

The cost incurred by $\lambda^{\prime}$ on every path $P\in\mathcal{P}^{-}$ is
precisely $\mu(\ell,\lambda(P))$, whereas for every edge $uv$ not on any such
path the cost is at most as high as for $\lambda$, i.e.,
$\mu(\lambda^{\prime}(u),\lambda^{\prime}(v))\leqslant\mu(\lambda(u),\lambda(v))$.

###### Proof.

For every path $P\in\mathcal{P}^{-}$ only the final vertex $v$ has a label
$\lambda^{\prime}(v)\neq\ell$, and the final edge has cost
$\mu(\ell,\lambda(v))$ where $\lambda(v)=\lambda(P)$. For the second part,
only edges with at least one end point in $V_{\ell}^{+}$ have changed cost
from $\lambda$ to $\lambda^{\prime}$, and among such edges only the edges of
$C$ have non-zero cost. Since $C$ is a min-cut, all such edges are covered by
paths $P\in\mathcal{P}^{-}$. ∎

######  Claim.

The cost incurred by $\lambda$ on a path $P\in\mathcal{P}^{-}$ is at least
$\mu(\ell,\lambda(P))$.

###### Proof.

Let $P=t_{\ell}v_{1}\ldots v_{r}$ where $v_{r}$ may be a terminal. This
describes a walk $\lambda(t_{\ell})=\ell$, …, $\lambda(v_{r})=\lambda(P)$ from
$\ell$ to $\lambda(P)$, and every edge $uv$ of $P$ where
$\lambda(u)\neq\lambda(v)$ incurs the corresponding cost. By the triangle
inequality for $\mu$, the sum of these costs is at least
$\mu(\ell,\lambda(P))$. ∎

The result follows immediately from the above two claims. ∎

An immediate consequence of the above lemma is the following reduction rule.

######  Corollary 4.2.

We can reduce to the case where for every label $\ell$ used by $\tau$, there
is a single terminal $t_{\ell}$ of value $\tau(t_{\ell})=\ell$ such that
$\delta(t_{\ell})$ is the unique isolating min-cut for $t_{\ell}$.

###### Proof.

The first part of the reduction (to terminals $t$) is trivial. Let $S$ be the
set of terminals. Let $t_{\ell}$ be a terminal with label $\ell$, let $C_{0}$
be a furthest isolating min-cut between $t_{\ell}$ and $S-t_{\ell}$, and let
$V_{\ell}^{0}$ be the vertices reachable from $t_{\ell}$ in $G-C_{0}$.

Now let $\lambda\colon V\to D$ be a $\tau$-extension and let
$V_{\ell}=\lambda^{-1}(\ell)$. Let $V_{\ell}^{+}\supseteq V_{\ell}$ be
produced by pushing from $\ell$ in $\lambda$. By Lemma 4.1, replacing $V_{i}$
by $V_{i}^{+}$ does not incur a larger cost.

To see that our reduction is valid, let $f\colon 2^{V}\to\mathbb{Z}$ be the
edge-cut function for $G$. Then, by submodularity,

$f(V_{\ell}^{0})+f(V_{\ell}^{+})\geqslant f(V_{\ell}^{0}\cap
V_{\ell}^{+})+f(V_{\ell}^{0}\cup V_{\ell}^{+})\geqslant
f(V_{\ell}^{0})+f(V_{\ell}^{0}\cup V_{\ell}^{+}),$

where the last step follows since $\delta(V_{\ell}^{0})$ is a minimum
isolating cut. Thus $V_{\ell}^{0}\cup V_{\ell}^{+}$ is a cut between
$t_{\ell}$ and $S-t_{\ell}$ of cost no more than $V_{\ell}^{+}$, which implies
that they are equal and $V_{\ell}^{0}\subseteq V_{\ell}^{+}$. Hence any
solution $\lambda$ can be modified to let $\lambda(V_{\ell}^{0})=\ell$, and we
may contract all vertices $V_{\ell}^{0}$ into $t_{\ell}$. Repeating this for
all vertices yields an instance as described. ∎

###  4.2 An FPT algorithm

Let $I=(G,\tau,\mu,q)$ be an instance of Zero Extension where $\mu$ is a
metric, a simple cost function observing the triangle inequality. Let $D$ be
the domain of $\mu$, and let $S$ be the terminals in $G$. We will show that
the problem is $\FPT$ parameterized by $k+|D|$ where $k$ is a bound on the
number of crossing edges in an optimum $\lambda$.

The algorithm uses the pushing lemma (Lemma 4.1) to guess a solution $\lambda$
using the technique of _important separators_. This is a classical ingredient
for $\FPT$ algorithms for cut problems, pioneered by Marx [23]. We focus on
the edge version. Let $G=(V,E)$ be a graph with disjoint vertex sets $S$ and
$T$, and let $C\subseteq E$ be a minimal $(S,T)$-cut which is not necessarily
minimum. Let $U$ be the set of vertices reachable from $S$ in $G-C$. Then $C$
is an _important separator_ if for every set $U^{\prime}\supset U$ with $T\cap
U^{\prime}=\emptyset$ we have $|\delta(U^{\prime})|>|C|$. In other words, $C$
represents a greedy “furthest cut” from $S$ for its size. The important
realization is that for every bound $k$ on $|C|$, there are at most
$f(k)=4^{k}$ important $(S,T)$-separators in $G$.

The algorithm we will use is inspired by the classical algorithm for Multiway
Cut of Chen, Liu and Lu [3], improving on Marx [23]. This algorithm works by
repeatedly selecting a terminal $t$, guessing an important separator around
$t$ (against the other terminals $S-t$), then deleting the chosen separator
and proceeding with the next terminal with a decreased budget $k$. The
important aspect to us is the process of enumerating important separators,
which for edge-cuts can be described as follows.

  1. 1.

Assume that we are enumerating important separators between sets $S$ and $T$,
which may be singleton sets (the process is the same regardless). Assume that
$k$ is our budget for the maximum separator size.

  2. 2.

Compute a furthest min-cut $C$ between $S$ and $T$. If $|C|>k$, abort.
Otherwise, contract edges so that $\delta(S)=C$. Initialise all edges as
unmarked.

  3. 3.

Select an unmarked edge $uv\in\delta(S)$ and branch recursively on two cases:

    1. (a)

Contract $uv$ into $S$, thereby increasing the max-flow

    2. (b)

Mark $uv$ as part of the final separator

Abort a branch whenever the resulting max-flow is more than $k$.

  4. 4.

Once all edges of $\delta(S)$ are marked, output $\delta(S)$ as an important
separator.

For the running time, we may analyse this in terms of the gap between $|C|$
and $k$. More precisely, consider an alternative lower bound where every
marked edge of $C$ counts for 1 point, but unmarked edges of $C$ are worth 1/2
point. Then it is clear that the lower bound increase by $1/2$ in both
branches of the recursive calls, and at most $2^{2k}$ important separators are
generated.

Compared to Edge Multiway Cut, there are two complications to an algorithm for
Zero Extension. First, if $C$ are the crossing edges on an optimal solution
$\lambda$, it may be that not every connected component of $G-C$ contains a
terminal; therefore the algorithm may need to branch on non-terminal vertices
as well. This is not an obstacle in itself, but it allows for only a weaker
running time analysis. Second, even after $C$ has been identified, it remains
to find an assignment $\lambda$ that minimizes cost. The complexity of this
may vary depending on the particular metric $\mu$.

For this reason, we describe the algorithm below as being composed of stages,
where the first stage identifies all crossing edges reachable from a terminal,
the second stage identifies the remaining crossing edges, and the third stage
finds an assignment $\lambda$. For specific metrics $\mu$, it may be possible
to skip or speed up the second and third stages; e.g., for a leaf metric it
can be checked that the algorithm is finished after the first stage.

In summary, we show the following.

See 1.2

We begin by proving the running time for the first stage. This is analysed in
terms of a lower bound $p$ on the crossing number of any labelling $\lambda$.
This bound is computed as follows. Let $S$ be the set of terminals. Observe
that for any $\tau$-extension $\lambda$, the crossing edges in $\lambda$ form
a multiway cut for $S$ in $G$. This can be lower-bounded as follows. For every
$t\in S$, let $f_{t}$ be the value of a max-flow between $t$ and $S-t$, and
let $p=\sum_{t\in S}f_{t}/2$. Then there is a half-integral packing of $p$
terminal-terminal paths in $G$ (i.e., a $\tau$-path-packing for the tree which
is a star with $S$ as leaves, as in Section 5.1) [31], hence there is no
solution $\lambda$ with crossing number less than $p$. Then the first phase
can be computed in time parameterized by the gap $k-p$. (We note that this is
a weaker lower bound, and hence a weaker gap parameter, compared to the
relaxation lower bound $\rho$ used later in this paper. However, it of course
applies to any metric.)

######  Lemma 4.3.

Let $p$ be the lower bound as above In $O(4^{k-p}km)$ time and $4^{k-p}$
guesses, we can reduce to the case where every edge of $\delta(t)$ is a
crossing edge in the optimal solution for every $t\in S$.

###### Proof.

This phase works almost exactly as Edge Multiway Cut. By Corollary 4.2, we
assume that for every $t\in S$, $\delta(t)$ is the unique ($t,S-t)$-min cut.
Since our parameter is a cardinality parameter, we implement this step by a
standard augmenting path algorithm, aborting whenever more than $k$ paths have
been found. More specifically, we proceed as follows. Let $f$ trace the number
of paths found in total across all terminals; initially $f=0$. Then for each
terminal $t\in S$ in turn, we pack $t-(S-t)$-paths in $G$, increasing $f$ at
each point, and aborting if $f>2k$ is reached. Assuming this does not happen,
we can in $O(m)$ time compute the furthest $(t,S-t)$-min cut $C$, and the set
$V_{t}$ of vertices reachable from $t$ in $G-C$, and finally the new graph $G$
resulting from contracting $V_{t}$ into $t$. In total, this process takes
$O(km)$ time and either aborts or produces a reduced graph. We assume in the
rest of the proof that the process has succeeded and proceed as follows.

Initialize all edges $tt^{\prime}$ for $t,t^{\prime}\in S$ as marked, all
other edges as unmarked. Compute a lower bound $p$ on $k$ by counting 1 for
every marked edge, and $1/2$ for every unmarked edge of $\delta(S)$. If $p>k$,
reject the instance. Otherwise, proceed as in the enumeration of important
separators, select an unmarked edge $tv$ incident with some $t\in S$ and
branch on two cases: Either contract $tv$ into $t$, and recompute the max-flow
and value of $p$; or mark $tv$ as part of the solution and select another
edge. Whenever $p>k$, abort the branch; whenever every edge of $\delta(S)$ is
marked, return the instance.

For the correctness, the value $p$ is a lower bound on the crossing number of
$\lambda$, as argued above. Hence if $p>k$, the current instance has no
solution. Otherwise, the branching is exhaustive, marking $tv$ as either
crossing or non-crossing, and in the latter case we are allowed to contract
out to the new furthest min-cut by the pushing lemma (Lemma 4.1). Hence,
assuming the instance has a solution at all, in at least one output instance
the marked edges correspond to the crossing edges of some optimal labelling
that are reachable from a terminal.

Regarding running time, Corollary 4.2 can be applied in $O(|S|km)$ time by an
augmenting path approach. For every further branching step, recomputing a new
max-flow can be done in $O(km)$ time. Throughout the branching process, the
value of $k-p$ decreases by at least $1/2$ in every branch (in particular, the
max-flow number increases in the contraction branch). Hence the branching
process produces at most $2^{2(k-p)}$ outputs. ∎

Next, we show a similar branching algorithm (without a lower bound) to mark
the remaining crossing edges of a solution.

######  Lemma 4.4.

Given an input from stage 1, with $p$ edges already marked, in $O(4^{2k-p}m)$
time and $4^{2k-p}$ guesses we can reduce to the case where every edge of $G$
is crossing in the optimal solution.

###### Proof.

We assume that the input from stage 1 has the property that an edge is marked
if and only if it is incident with a terminal. We proceed with a branching
process as follows. Let $v$ be an arbitrary non-terminal vertex incident with
at least one non-marked edge; if none exists, simply output the instance.
Compute a furthest min-cut $C$ between $v$ and $S$ in $G$, aborting if
$|C|>k$. Let $U$ be the vertices reachable from $v$ in $G-C$. If $U$ contains
any marked edge, abort the branch as being the result of inconsistent choices;
otherwise contract $U$ into $v$. If every edge of $\delta(v)$ is marked,
proceed with a different starting vertex $v$. Otherwise, as above select one
unmarked edge from $\delta(v)$ and branch on either marking it or contracting
it and recomputing the max-flow and min-cut. If at any point more than $k$
edges have become marked, abort the branch. Once only marked edges remain,
output the instance.

The correctness argument is similar as in stage 1. Assume that we are
currently working with a non-terminal vertex $v$, and that $\lambda(v)=i$ in
an optimal solution to the current instance; by Lemma 4.1, we may assume that
pushing from $i$ in $\lambda$ has no effect. Let $V_{i}=\lambda^{-1}(i)$ and
let $V_{v}$ be the vertices of the connected component of $G[V_{i}]$ that
contains $v$. Then $\delta(V_{i})$ is an important separator, and it follows
that the same holds for $\delta(V_{v})$ (as otherwise pushing would produce a
bigger set $V_{i}$). Thus contracting it to a furthest min-cut is allowed.
After this, the branching process is exhaustive as above.

For the running time, we view edges as being _double-marked_ , receiving one
mark from each endpoint. Edges marked in stage 1 are viewed as having received
a mark from each terminal side, at least $p$ marks have already been placed at
the start of the algorithm. We then view the branching around a vertex $v$ as
placing one such mark on the $v$-side of the solution edges connecting to
$V_{i}$ in $V_{v}$. Hence, both the packing of a path from $v$ and the final
marking of an edge represents the placing of half a mark, and in total at most
$2k-p$ such marks will be placed (ignoring the final leaf of an aborted branch
where $|C|$ grows too large). Hence the total number of branches in this stage
is at most $2^{2(2k-p)}$. Finally, for the polynomial part of the running
time, we consider the amount of work done in a single node, before branching.
As noted, every additional path added in the max-flow computation takes $O(m)$
time to find and counts as a half-mark against our budget, hence at most
$O(k)$ paths are found before aborting. Additionally, every contraction step
(out to a furthest min-cut) takes $O(m)$ time in total, and by the same
argument only $O(k)$ contraction steps are performed. Hence the local work per
node is bounded as $O(km)$. ∎

After stage 2, the remaining graph contains at most $k$ edges, hence at most
$O(k)$ vertices, and it only remains to find the min-cost labelling of the
non-terminal vertices. In the absence of any stronger structural properties of
the metric $\mu$, this last phase can be completed in $|D|^{O(k)}O(m)$ time.
Theorem 1.2 follows.

###  4.3 A kernel for any metric

We show that Zero Extension has a kernel of $O(k^{s+1})$ vertices for any
metric $\mu$, where $k$ is a bound on the crossing number of a solution and
$s$ is the number of labels of $\mu$. In fact, stronger than this, we show
that such a kernel can be computed without access to $\mu$: We can find a set
$Z$ of $O(k^{s+1})$ edges such that for every instance $I=(G,\tau,\mu,q)$ with
terminal set $S$, if $I$ admits any solution with at most $k$ crossing edges,
then $F$ contains all crossing edges of at least one optimal solution of this
type for $I$. By contracting all edges not in $Z$ this allows us to construct
a graph $G^{\prime}$ with $O(k^{s+1})$ edges such that $(G^{\prime},S)$ has
the ‘same behaviour’ as $(G,S)$, up to the values of $k$ and $s$. We refer to
this as a _metric sparsifier_. Let us make this more precise.

######  Definition 4.5.

For an instance $I=(G,\tau,\mu,q)$ of Zero Extension and an integer $k$, the
_$k$ -bounded cost_ $\operatorname{\mathbf{cost}}(I,k)$ of $I$ is the minimum
cost of a $\tau$-extension $\lambda$ with crossing number at most $k$, or
$\infty$ if no such $\tau$-extension exists. Let $G=(V,E)$ be a graph with a
set of terminals $S\subseteq V$, and let $k$ and $s$ be integers,
$s\geqslant|S|$. A _$k$ -bounded metric sparsifier for $(G,S)$ (for metrics
with up to $s$ labels)_ is a graph $G^{\prime}=(V^{\prime},E^{\prime})$ with
$S\subseteq V^{\prime}$, such that for any metric $\mu$ on a set $D$ of at
most $s$ labels, and for any injective labelling $\tau\colon S\to D$, we have
$\operatorname{\mathbf{cost}}((G,\tau,\mu,q),k)=\operatorname{\mathbf{cost}}((G^{\prime},\tau,\mu,q),k)$.

We show the following result, which implies the existence of a small metric
sparsifier.

######  Theorem 4.6.

Let $s\geqslant 3$ be a constant. For every graph $G=(V,E)$ with a set $S$ of
terminals, $|S|\leqslant s$, and integer $k$, there is a randomized
polynomial-time computable set $Z\subseteq E$ with $|Z|=O(k^{s+1})$ such that
for any instance $I=(G,\tau,\mu,q)$ of Zero Extension with $S$ being the set
of terminals in $I$ and $\mu$ having at most $s$ labels, if
$\operatorname{\mathbf{cost}}(I,k)<\infty$ then there is a $\tau$-extension
$\lambda$ with crossing number at most $k$ and cost
$\operatorname{\mathbf{cost}}(I,k)$ such that every crossing edge of $\lambda$
is contained in $Z$.

The kernel is an adaptation of the _irrelevant vertex_ strategy used in the
kernel of Multiway Cut for $s$ terminals of Kratsch and Wahlström [19]. In
that paper, a kernel is produced by first computing a set $Z_{0}$ of
$O(k^{s+1})$ vertices which contains all vertices $v$ which are contained in
_every_ minimum solution of size at most $k$. Then one _irrelevant vertex_
$v\notin Z_{0}$ is chosen and removed from the graph via a bypassing
operation, and the process is repeated until the computed set $Z_{0}$ covers
all non-terminal vertices, at which point $Z_{0}$ is the desired final set
$Z$. The set $Z_{0}$ is computed using a tool from matroid-theory called
_representative sets_. These same components will yield a kernel for our
present problem.

We give only a brief sketch of the technical background, and focus on the
kernelization result itself. For a complete description of the technical tools
involved, see Kratsch and Wahlström [19].

A _matroid_ is an “independence system” $M=(E,\mathcal{I})$,
$\mathcal{I}\subseteq 2^{V}$, subject to certain axioms. The sets
$S\in\mathcal{I}$ are the _independent sets_ of $M$. Matroids have broad
applications in combinatorics in general; see Oxley [28] and Schrijver [31]. A
_representation_ of a matroid is a matrix $A$ with columns labelled by $E$
such that for every $S\subseteq V$, $S\in\mathcal{I}$ if and only if the
corresponding columns of $A$ are linearly independent. A _gammoid_ is a
matroid corresponding to flows in a graph. Given a directed graph $G=(V,E)$
with a set of source vertices $S\subseteq V$, and a set $U\subseteq V$, the
gammoid defined from $G$, $S$ and $U$ is a matroid $M=(U,\mathcal{I})$ where
$T\subseteq U$ is independent if and only if the fully vertex-disjoint max-
flow from $S$ to $T$ is of size $|T|$; equivalently, there is no $(S,T)$-cut
in $G$ of fewer than $|T|$ vertices. A representation of a gammoid can be
computed in randomized polynomial time [28]. In our application, we need the
gammoid to represent edge cuts instead of vertex cuts; clearly this can be
done by subdividing edges of $E$ and multiplying every vertex $v$ of $G$ into
$d(v)$ copies. Undirected edges of $G$ can be implemented as a pair of
directed edges in opposite directions. Let $G^{\prime}$ be the directed graph
resulting from applying these modifications to $G$.

The main tool in our kernel is the following result. (See also Fomin et al.
[9] for a faster algorithm.)

######  Lemma 4.7 ([21, 24]).

Let $M=(E,\mathcal{I})$ be a linear matroid represented by a matrix $A$ of
rank $r+s$, and let $\mathcal{Y}$ be a collection of independent sets of $M$,
each of size $s$. Assume that $s$ is a constant. Then in polynomial time we
can compute a set $\mathcal{Y}^{*}\subseteq\mathcal{Y}$ of size at most
$\binom{r+s}{s}$ such that for every set $X\subseteq E$, there is a set
$Y\in\mathcal{Y}$ such that $X\cap Y=\emptyset$ and $X\cup Y\in\mathcal{I}$ if
and only if there is such a set $Y^{\prime}\in\mathcal{Y}^{*}$.

As shorthand, for an independent set $X$ we say that $Y$ _extends_ $X$ if
$X\cap Y=\emptyset$ and $X\cup Y\in\mathcal{I}$. The following is a useful
characterization of this notion in gammoids.

######  Proposition 4.8 (Prop. 1 of [19]).

Let $X$ be a independent set in a gammoid defined from $G$, $S$ and $U$. Let
$X^{\prime}$ be the minimum $(S,X)$-vertex cut closest to $S$ in $G$, which
may overlap $S$. Then for a vertex $v\in U$, the set $\\{v\\}$ extends $X$ in
the gammoid if and only if $v$ is reachable from $S$ in $G-X^{\prime}$.

For further terms from matroid theory used below, see [19], alternatively
Oxley [28] and Marx [24].

We are now ready to prove Theorem 4.6.

###### Proof.

Let a graph $G=(V,E)$ with a terminal set $S\subseteq V$, $|S|\leqslant s$,
and an integer $k$ be given. We apply Corollary 4.2 to $G$, then create a
digraph $G^{\prime}$ from $G$ as above. Additionally, for every edge $e=uv\in
E$ we introduce a _sink-copy_ $e^{\prime}$ of $e$ in $G^{\prime}$, with in-
arcs from all copies of vertices $u$ and $v$ in $G^{\prime}$, and no further
in- or out-arcs. Let $E_{S}=\bigcup_{t\in S}\delta(t)$. We first note that if
$|E_{S}|>2k$ then we may reject the input.

######  Claim.

If $\sum_{t\in S}d(t,G)>2k$, then every labelling $\lambda$ that is injective
on $S$ has more than $k$ crossing edges.

###### Proof.

The crossing edges of any such $\lambda$ form a multiway cut of $(G,S)$. It is
known that the cardinality of a multiway cut is at least $\sum_{t\in
S}d(t,G)/2$, as noted previously in Section 4.2. ∎

Hence if $|E_{S}|>2k$, then we reject the input (alternatively, simply produce
$Z=\emptyset$). Otherwise proceed as follows. Let an _instance over $(G,S)$_
be an instance $I(\tau,\mu,q)=(G,\tau,\mu,q)$ of Zero Extension where $\mu$ is
a metric over a set of labels $D$ with $|D|\leqslant s$ and $\tau$ is an
injective labelling $\tau\colon S\to D$. We first observe that the existence
of a $\tau$-extension $\lambda$ with crossing number at most $k$ for any
instance over $(G,S)$ is a property purely of $(G,S)$ and $k$, hence
independent of the metric; explicitly, it exists if and only if $(G,S)$ has a
multiway cut of at most $k$ edges. Since the theorem is vacuous otherwise, we
assume that such a multiway cut exists, hence that
$\operatorname{\mathbf{cost}}(I,k)<\infty$ for every instance $I$ over
$(G,S)$. Say that an edge $e$ is _essential_ in $G$ if there is some instance
$I=I(\tau,\mu,q)$ over $(G,S)$ such that there is at least one
$\tau$-extension $\lambda$ with crossing number at most $k$ and cost at most
$q$, and the edge $e$ is crossing in every such $\lambda$. We compute a set
$Z_{0}$ that contains all essential edges; any edge of $G$ not contained in
$Z_{0}\cup E_{S}$ is then _irrelevant_. The computation of $Z_{0}$ makes up
the major part of this proof.

Number the vertices of $S$ as $S=\\{t_{1},\ldots,t_{r}\\}$, $r=|S|$. We define
a matroid $M$ as the disjoint union of the following matroids: Matroids
$M_{1}$ through $M_{s}$ are disjoint copies of the gammoid defined from
$G^{\prime}$ with source set $E_{S}=\bigcup_{t\in S}\delta(t)$. Note that
$E_{S}$ is a vertex set in $G^{\prime}$. Finally, let $M_{0}$ be the uniform
matroid $U_{m,k}$ of rank $k$ on ground set $E(G)$. Since $M_{0}$ has a
representation over every sufficiently large field, we can compute a
representation of $M$ in randomized polynomial time with exponentially small
failure probability [24]. We refer to $M_{1}$, …, $M_{s}$ and $M_{0}$ as the
_layers_ of $M$. For an independent set $X$ of $M$, a set $Y$ extends $X$ in
$M$ if and only if the restriction of $Y$ to layer $i$ extends the restriction
of $Y$ to layer $i$ for every layer $i$. Since the rank of each gammoid is
$|E_{S}|\leqslant 2k$, the rank of $M$ is at most $(2s+1)k=O(k)$ since $s$ is
a constant. For an edge $e\in E(G)$, we let $e_{i}$ (respectively
$e_{i}^{\prime}$) refer to the copy of $e$ (of $e^{\prime}$) in $M_{i}$,
$i\in[s]$, and $e_{0}$ refers to the copy of $e$ in $M_{0}$.

We now define the collection $\mathcal{Y}$ of sets of size $s+1$. For an edge
$e\in E(G)$, let $Y(e)=(e_{1}^{\prime},\ldots e_{s}^{\prime},e_{0})$, and
define $\mathcal{Y}=\\{Y(e)\mid e\in E(G)\setminus E_{S}\\}$. Compute a
representative set $\mathcal{Y}^{*}\subseteq\mathcal{Y}$ in $M$, and let
$Z_{0}\subseteq E=\\{e\in E\mid Y(e)\in\mathcal{Y}^{*}\\}$. Then
$|Z_{0}|=O(k^{s+1})$ by Lemma 4.7. We show that $Z_{0}\cup E_{S}$ contains
every edge that is essential in $G$.

######  Claim.

If $e$ is essential in $G$ for some instance $I=I(\tau,\mu,q)$ over $(G,S)$,
then $e\in Z_{0}\cup E_{S}$.

###### Proof.

Let $D$ be the set of labels of $\mu$. Let $\lambda$ be an extension of $\tau$
with at most $k$ crossing edges, and of cost
$\operatorname{\mathbf{cost}}(I,k)$. Assume that among all such extensions,
$\lambda$ has the minimum crossing number. Let $C$ be the set of crossing
edges in $\lambda$, and for $i\in D$ let $V_{i}=\lambda^{-1}(i)$. Hence
$C=\bigcup_{i\in D}\delta(V_{i})$. Define a set $X$ in $M$ as follows: In
layers $i=1,\ldots,r$, $X$ contains the copy of edges
$\delta(V_{i})\cup\delta(t_{i})$; in layers $i=r+1,\ldots,s$, $X$ contains the
copy of edges $\delta(V_{i})$; and in the final layer (representing $M_{0}$),
$X$ contains the copy of $C-e$. It is clear that $X$ is independent in $M$, as
otherwise there is some label $i$ such that (by Lemma 4.1, the pushing lemma)
pushing from some label $i$ would yield a labelling $\lambda^{\prime}$ with
smaller crossing number and at most the same cost. The claim is now that
$Y(f)$ extends $X$ if and only if $f=e$.

In the one direction, assume that $Y(f)$ extends $X$. If $f\in C$, then $f=e$
by $M_{0}$. Otherwise, $f$ lies in some set $V_{i}$, $i\in D$. But then the
restriction of $X$ to layer $i$ separates $f$ from $E_{S}$, so $f^{\prime}$
cannot possibly extend $X$ in this layer. Hence $f\in C$, and $f=e$.

In the other direction, we show that $Y(e)$ indeed extends $X$. This is clear
in $M_{0}$, so we focus on a layer $i\in[s]$. Let $\lambda_{i}$ be the result
of pushing from $i$ in $\lambda$ and let $C_{i}$ be the set of crossing edges
in $\lambda_{i}$. Let $V_{i}^{\prime}=\lambda_{i}^{-1}(i)$. By Lemma 4.1,
$\lambda_{i}$ has a cost at most as high as $\lambda$, and clearly has at most
$k$ crossing edges, hence $\lambda_{i}$ is an optimal solution to $I$, and by
assumption $e\in C_{i}$. Let $v$ be an endpoint of $e$ such that
$\lambda_{i}(v)\neq i$; by assumption, $v$ exists. It follows from the pushing
operation that $v$ is reachable from $S-t_{i}$ (respectively from $S$ if
$i>r$) avoiding $\delta(V_{i}^{\prime})$. Thus, by Prop. 4.8, $e^{\prime}$
extends $\delta(V_{i})\cup\delta(t_{i})$ in $M_{i}$ (respectively
$\delta(V_{i})$ if $i>r$), which is the restriction of $X$ to layer $i$. Thus
$Y(e)$ extends $X$.

Since $\mathcal{Y}^{*}$ contains at least one set $Y(f)$ that extends $X$, we
conclude $e\in Z_{0}$. ∎

It only remains to show that sequentially contracting irrelevant edges (one at
a time, while recomputing $Z_{0}$ at every step) yields a final set $Z$ that
contains crossing edges of optimal solutions for all metrics as described.
This should be clear. The effect of contracting an edge $uv$ is precisely to
restrict the solution space to labellings $\lambda$ where $uv$ is non-
crossing. All other edges of the graph remain identifiable, and for every
instance $I$ over $(G,S)$ there still exists some optimal solution $\lambda$
after the contraction. That is, at every stage, for every instance $I$ over
$(G,S)$ there exists some solution $\lambda$ with crossing number at most $k$
and of cost $\operatorname{\mathbf{cost}}(I,k)$, such that the edge that is
about to be contracted is non-crossing in $\lambda$. Thus the final graph,
where $Z\cup E_{S}$ covers the entire edge set, also contains such a solution.
∎

######  Corollary 4.9.

For every graph $G$ with terminal set $S$, and integers $k$, $s$, there is a
$k$-bounded metric sparsifier $G^{\prime}$ for $(G,S)$, for metrics with up to
$s$ labels, with $O(k^{s+1})$ edges, which can be computed in randomized
polynomial time. Furthermore, for every metric $\mu$ on $s$ labels, Zero
Extension admits a randomized polynomial kernel with $O(q^{s+1})$ edges.

###### Proof.

The metric sparsifier is constructed by computing the $Z$ as above, then
contracting all edges not in $Z\cup E_{S}$. For the kernel, first assume that
$\mu$ has no distinct pair of labels at distance zero, as otherwise we can
compute a new metric $\mu^{\prime}$ and instance $I^{\prime}$ by identifying
labels and terminals at distance 0. Let $I=(G,\tau,\mu,q)$ be an instance. As
the metric is integer-valued, it follows that any $\tau$-extension $\lambda$
of cost at most $q$ has crossing number at most $q$. Hence we get a polynomial
kernel by computing a $q$-bounded metric sparsifier. ∎

##  5 Tree metrics: Discrete relaxations

We now give more powerful algorithms parameterized by the gap parameter for
problems where the metric embeds into a tree metric. We begin by a purely
combinatorial algorithm for Zero Extension on leaf metrics, then we move on to
the more general Zero Extension and Metric Labelling problems for general
induced tree metrics. The algorithms for the latter problems rely on the
_domain consistency_ property of the relaxation, which allows us to solve the
problem by simply branching on the value of a single variable at a time. This
property is shown by way of a detour into an analysis of properties of VCSP
instances whose cost functions are _weakly tree submodular_ , which is a
tractable problem class containing tree metrics. The algorithms for these
problems are then straight-forward.

At this point, we need to address a subtlety regarding the input cost function
$\mu$. So far, the cost function only had to obey basic properties that are
easily verifiable or could be seen as a ‘promise’. However, some of our
arguments below will explicitly need the tree $T$ that induces the metric.
Luckily this issue has been solved already: given a induced tree metric $\mu$
over $D$ in matrix form, one can in time $O(|D|^{2})$ compute a tree that
induces $\mu$ [6]. If $\mu$ is a leaf metric, the output will obviously have
$D$ as the leaves of $T$. In conclusion, we will tacitly assume that we have
access to the tree $T$ in the following.

###  5.1 Leaf metrics: A duality approach

The $\mu$-Edge Disjoint Packing problem asks, given a graph $G$ with a
terminal set $S\subseteq V(G)$, to find an edge-disjoint packing $\mathcal{P}$
of paths whose endpoints both lie in $S$ that maximizes
$\operatorname{pack}(\mu,G,S):=\sum_{P\in\mathcal{P}}\mu(s_{P},t_{P})$ (where
$s_{P},t_{P}$ denote the start- and endpoints of the path $P$). Hirai and Pap
[12], as part of a more general result, show that if $\mu$ is a tree metric,
then the problem is polynomial-time solvable and

$\operatorname{pack}(\mu,G,S)=\min_{\lambda}\max_{F\subseteq E}\sum_{uv\in
E\setminus F}\mu(\lambda(u),\lambda(v)),$

where $\lambda$ is precisely a zero-extension of the terminal-set $S$ and the
sets $F\subseteq E$ are so-called _inner odd-join_ , that is, a set of edges
whose deletion leaves every non-terminal vertex with an even degree. It
follows that the maximum value of a half-integral $\tau$-path packing is just
the minimum cost of a $\tau$-extension $\lambda$, since a half-integral path-
packing is just a path-packing in the graph where every edge of $G$ has been
duplicated, and such a graph has no vertices of odd degree.

Let in the following $I=(G,\tau,\mu,q)$ be an instance of Zero Leaf Extension,
where $\mu$ is a leaf metric over a tree $T$ with leaves $D$. Let
$\hat{\mu}=\operatorname{d}_{T}$ be the underlying tree metric. We define the
_relaxed instance_ $\hat{I}=(G,\tau,\hat{\mu},q)$. Let
$\operatorname{\mathbf{opt}}(I)$, $\operatorname{\mathbf{opt}}(\hat{I})$
denote the set of optimal solutions for the integral and the relaxed instance,
respectively. As mentioned in Section 2, it is known that the relaxed instance
can be solved optimally in polynomial time [30]. For convenience, we say that
a vertex $u$ is integral with respect to a solution $\lambda$ if
$\lambda(u)\in D$ and we say that an edge $uv\in G$ is integral with respect
to $\lambda$ if both endpoints are integral.

Using the above notation, we can summarize the duality between an minimum
relaxed labelling and a path packing as follows: Given a relaxed instance
$\hat{I}$, there exists a half-integral $\tau$-path-packing $\mathcal{P}$ of
cost precisely $\operatorname{\mathbf{cost}}(\hat{I})$. We will not explicitly
compute $\mathcal{P}$ in the final algorithm, instead we use its existence to
derive useful properties of the problem. In the following we will use $S$ to
denote the terminals of the instance, the vertices labelled by $\tau$. By the
usual identification argument, we can assume that $\tau$ is a bijection and a
$\tau$-path packing is equivalent to an $S$-path packing.

######  Lemma 5.1.

Let $\mathcal{P}$ be an half-integral $\tau$-path packing that satisfies

$\frac{1}{2}\sum_{P\in\mathcal{P}}\mu(\tau(s_{P}),\tau(t_{P}))=\operatorname{\mathbf{cost}}(\hat{I}).$

Let $\lambda\in\operatorname{\mathbf{opt}}(\hat{I})$ be a relaxed optimum and
let $P\in\mathcal{P}$ with endpoints $s,t$. Then

$\operatorname{\mathbf{cost}}_{\hat{\mu}}(\lambda,P)=\mu(\tau(s),\tau(t)).$

###### Proof.

First, consider _any_ $s$-$t$-path $P^{\prime}$ in $G$. Then

$\operatorname{\mathbf{cost}}_{\hat{\mu}}(\lambda,P)=\sum_{uv\in
P^{\prime}}\hat{\mu}(\lambda(u),\lambda(v))\geqslant\hat{\mu}(\tau(s),\tau(t)).$

We therefore find that the inequality

$\sum_{P\in\mathcal{P}}\hat{\mu}(\tau(s_{P}),\tau(t_{P}))\leqslant\sum_{P\in\mathcal{P}}\operatorname{\mathbf{cost}}_{\hat{\mu}}(\lambda,P)\leqslant
2\operatorname{\mathbf{cost}}_{\hat{\mu}}(\lambda,G)$

holds. But according to our assumption, the left-hand side and right-hand side
are equal and we conclude that

$\sum_{P\in\mathcal{P}}\hat{\mu}(\tau(s_{P}),\tau(t_{P}))=\sum_{P\in\mathcal{P}}\operatorname{\mathbf{cost}}_{\hat{\mu}}(\lambda,P).$

and therefore that for every $P\in\mathcal{P}$,
$\operatorname{\mathbf{cost}}_{\hat{\mu}}(\lambda,P)=\mu(\tau(s_{P}),\tau(t_{P}))$,
as claimed. ∎

A direct consequence is that if we trace an $s$-$t$-path $P\in\mathcal{P}$,
then the labels assigned by any relaxed optimum $\lambda$ to $P$ induce a
monotone sequence from $s$ to $t$ in $T$. That is, not only will we only
encounter those labels that lie on $T[s,t]$, we also will encounter them ‘in
order’. We further can conclude the following:

######  Corollary 5.2.

Let $e\in G$ be an edge that is _not_ part of the path-packing $\mathcal{P}$.
Then under every relaxed optimum
$\lambda\in\operatorname{\mathbf{opt}}(\hat{I})$ the edge $e$ has cost zero.

Consider an edge $xy\in E(T)$. Then, as a consequence of Lemma 5.1 the set of
edges $C_{xy}(\lambda)=\\{uv\in E(G)\mid\lambda(u)\in T_{x},\lambda(v)\in
T_{y}\\}$ between the vertex sets with labels in $T_{x}$ and $T_{y}$,
respectively, must be saturated by paths of the packing $\mathcal{P}$. For
cuts right above leafs of $T$, this implies the following.

######  Lemma 5.3.

Let $S$ be the vertices labelled by $\tau$ in $G$ and assume that $\tau$ is a
bijection. Let $C$ be any minimum $(x,S-x)$-cut for some terminal $x\in S$.
Then every optimal, half-integral $S$-path-packing in $G$ will saturate $C$.

###### Proof.

Let us first consider the closest minimal cut $\operatorname{C_{min}}(x)$ and
the furthest minimal cut $\operatorname{C_{max}}(x)$. Let $\mathcal{P}$ be a
max-value $\tau$-path-packing, and let $\lambda$ be the corresponding min-cost
extension of $S$. Let $y$ be the ancestor of $x$ in $T$ and consider
$C_{yx}(\lambda)$. By the above, $C_{yx}(\lambda)$ is saturated by
$\mathcal{P}$. Since every path of $\mathcal{P}$ induces a monotone sequence
in $T$ under $\lambda$, every path $P\in\mathcal{P}$ crossing $yx$ in $T$ must
have $x$ as an endpoint. But the total weight of such paths
$\mathcal{P}_{x}\subseteq\mathcal{P}$ is at most $\operatorname{C_{min}}(x)$.
Since $C$ is a $(x,S-x)$-cut, we must have
$C_{yx}(\lambda)=\operatorname{C_{min}}(x)$.

Now, since $\operatorname{C_{max}}(x)$ is a minimal $(x,S-x)$-cut as well,
$\mathcal{P}_{x}$ saturates $\operatorname{C_{max}}(x)$ as well. This in
particular means that every path in $\mathcal{P}$ that intersects
$\operatorname{C_{max}}(x)$ must end in $x$, those paths are exactly
$\mathcal{P}_{x}$. Consequently, every min-cut around $x$ is saturated by
$\mathcal{P}_{x}$, proving the statement. ∎

######  Lemma 5.4.

Let $\lambda$ be a not necessarily optimal solution for $\hat{I}$. Then

$\operatorname{\mathbf{cost}}_{\mu}(\lambda,G)=\sum_{xy\in
T}|C_{xy}(\lambda)|.$

###### Proof.

The claim is equivalent to proving that

$\sum_{uv\in G}\mu(\lambda(u),\lambda(v))=\sum_{xy\in T}|C_{xy}(\lambda)|.$

We proof the above equality by double-counting. Consider an edge $uv$, then
$\mu(\lambda(u),\lambda(v))$ is by definition $|T[\lambda(u),\lambda(v)]|$.
Note that $uv$ appears in exactly those cuts $C_{xy}$ with $xy\in
T[\lambda(u),\lambda(v)]$, hence we can charge the cost of
$\mu(\lambda(u),\lambda(v))$ on those cuts and the equation follows. ∎

######  Lemma 5.5.

Let $u\in G$ be such that $u\not\in\operatorname{C_{max}}(x)$ for all
terminals $x\in S$. Then $u$ does not receive any integral value by any
relaxed optimum.

###### Proof.

Assume otherwise: let $\lambda\in\operatorname{\mathbf{opt}}(\hat{I})$ be a
relaxed optimum that assigns $u$ some integral value $x\in T$. Let $y$ be the
parent of $x$ in $T$. Then we conclude that $C_{xy}(\lambda)$ cannot be a
minimum cut, since $u$ is part of $\lambda^{-1}(x)$, but $u$ is not in the
furthest min-cut $\operatorname{C_{max}}(x)$. But then $\sum_{xy\in
T}|C_{xy}(\lambda)|$ cannot be minimal, and by Lemma 5.4 therefore
$\operatorname{\mathbf{cost}}_{\mu}(\lambda,G)$ is not either, contradicting
our assumption. ∎

######  Lemma 5.6.

For every triple $x,y,z\in S$ of distinct terminals it holds that
$\operatorname{C_{max}}(x)\cap\operatorname{C_{max}}(y)\cap\operatorname{C_{max}}(z)=\emptyset$.

###### Proof.

Assume towards a contradiction that there exists
$u\in\operatorname{C_{max}}(x)\cap\operatorname{C_{max}}(y)\cap\operatorname{C_{max}}(z)$
and let us choose $u$ such that it is incident to edges that cross the cut
$\operatorname{C_{max}}(x)$.

Let $\mathcal{P}$ be an optimal half-integral $S$-path packing. By Lemma 5.3,
all paths of $\mathcal{P}$ that enter $\operatorname{C_{max}}(c)$ for $c\in S$
must have an endpoint in $c$; moreover, they saturated the cut
$\operatorname{C_{max}}(c)$. Since $x$ is incident to edges that cross the cut
$\operatorname{C_{max}}(x)$ it must therefore lie on at least one path $P$
that ends in $x$. Now, since $u$ also lies in $\operatorname{C_{max}}(y)$, the
path $P$ crosses $\operatorname{C_{max}}(y)$ and must therefore end in $y$.
However, the same argument holds for $z$ and we arrive at a contradiction. We
conclude that the intersection of the three cuts must indeed be empty. ∎

See 1.4

###### Proof.

Given the input graph $G$ we first construct for every edge $ij\in T$ a flow
network $H_{ij}$ from $G$ as follows: let $D_{i}$ be those leaves that lie in
the same component as $i$ in $T-ij$ and $D_{j}$ all others. Then $H_{ij}$ is
obtained from $G$ by identifying all terminals $\tau^{-1}(D_{i})$ into a
source $s$ and all terminals $\tau^{-1}(D_{j})$ into a sink $t$. For each
networks $H_{ij}$ we compute a maximum flow $f_{ij}$ in time $\phi(n,m)$. By
Lemma 5.4 we have that for every
$\lambda\in\operatorname{\mathbf{opt}}(\hat{I})$ it holds that

$\sum_{xy\in T}|f_{ij}|=\sum_{xy\in
T}|C_{xy}(\lambda)|=\operatorname{\mathbf{cost}}_{\mu}(\hat{I}).$

Note that we can also, in linear time, find the closest cuts
$\operatorname{C_{min}}(x)$ and furthest cuts $\operatorname{C_{max}}(x)$ for
terminals $x\in S$ using the residual network of $(H_{ij},f_{ij})$ with
$i=\tau(x)$ and $j$ the parent of $i$ in $T$.

Thus, in linear time, we can identify whether $G$ contains a vertex that is
not part of any furthest min-cut $\operatorname{C_{max}}(x)$ for all $x\in S$.
By Lemma 5.5, such a vertex cannot take an integral value in any relaxed
optimum. We therefore branch on the $|D|$ possible integral values it could
take: for $x\in S$ with $\tau(x)\in D$ being the chosen integral value, we
update the flow networks $(H_{ij},f_{ij})$ by adding an edge of infinite
capacity from $x$ to $u$ and then augment the flow $f_{ij}$ until it is
maximum again. Note that the number of augmentations necessary are at most
$k-p$, since each augmentation witnesses the increase of $p$ and thus the
decrease of the parameter by one. In our analysis we can therefore charge each
augmentation to a level of the search tree (treating each augmentation like a
descent to the next node) and thus spend only $O(m)$ time per flow $f_{ij}$,
for a total of $O(|T|m)$.

Otherwise, we find that every vertex of the current graph $G$ is contained in
at least one furthest min-cut. By Lemma 5.6, the intersection of three or more
such cuts is empty and we can partition the vertices of $G$ into sets
$\\{V_{x}\\}_{x\in S}\cup\\{U_{xy}\\}_{x,y\in S}$ where $V_{x}$ contains all
vertices that are only contained in $\operatorname{C_{max}}(x)$ while $U_{xy}$
contains those that live in the intersection
$\operatorname{C_{max}}(x)\cap\operatorname{C_{max}}(y)$. By Lemma 5.3 we have
that $U_{xy}$ only contains edges towards $V_{x}$ and $V_{y}$ (since these
edges are exactly saturated by a half-integral path-packing and the paths
saturating these edges have endpoints $x$ and $y$). Therefore we construct an
integral solution $\lambda$ as follows: every set $V_{x}$, $x\in S$ is
coloured $\tau(x)$ and for every non-empty set $U_{xy}$, $x,y\in S$ we choose
colour $\tau(x)$ or $\tau(y)$ arbitrarily. By Lemma 5.4, the cost of $\lambda$
is precisely

$\operatorname{\mathbf{cost}}_{\mu}(\lambda,G)=\sum_{xy\in
T}|C_{xy}(\lambda)|=\sum_{xy\in
T}|f_{ij}|=\operatorname{\mathbf{opt}}(\hat{I})$

and we conclude that $\lambda$ is an integral solution that matches the
relaxed optimum of the current instance. In this case, we return $\lambda$ as
a solution to the original instance. The claimed running time follows if we
prune every branch of the search tree in which the parameter drops below zero.
∎

###  5.2 VCSP toolkit

We now review some required terminology and tools for the proof of the
algebraic properties of distance problems on trees.

Given a set of cost functions $\Gamma$ over a domain $D$, an instance $I$ of
VCSP$(\Gamma)$ is defined by a set of variables $V$ and a sum of valued
constraints $f_{i}(\bar{v}_{i})$, where for each $i$, $f_{i}\in\Gamma$ and
$\bar{v}_{i}$ is a tuple of variables over $V$. We write $f_{i}(\bar{v})\in I$
to signify that $f_{i}(\bar{v})$ is a valued constraint in $I$.

It is known that the tractability of a VCSP is characterized by certain
algebraic properties of the set of cost functions. In full generality, such
conditions are known as _fractional polymorphisms_ for the finite-valued case
and more general _weighted polymorphisms_ in the general-valued case.
Dichotomies are known in these terms both for the finite-valued [33] and
general case of VCSP [18], i.e., characterizations of each VCSP as being
either in P or NP-hard. We will only need a less general term.

A _binary multimorphism_ $\langle\circ,\bullet\rangle$ of a language $\Gamma$
over a domain $D$ is a pair of binary operators that satisfy

$f(\bar{x})+f(\bar{y})\geqslant
f(\bar{x}\circ\bar{y})+f(\bar{x}\bullet\bar{y})\qquad\forall
f\in\Gamma,\bar{x},\bar{y}\in D^{\operatorname{\mathbf{ar}}(f)},$

where $\operatorname{\mathbf{ar}}(f)$ is the arity of $f$ and where we extend
the binary operators to vectors by applying them coordinate-wise. An operator
$\circ$ is _idempotent_ if $x\circ x=x$ for every $x\in D$, and _commutative_
if $x\circ y=y\circ x$. A (finite, finite-valued) language $\Gamma$ with a
binary multimorphism where both operators are idempotent and commutative is
solvable in polynomial time via an LP-relaxation [33]. The most basic example
is the Boolean domain $D=\\{0,1\\}$, in which case the multimorphism
$\langle\land,\lor\rangle$ corresponds to the well-known class of _submodular
functions_ , which is a tractable class that generalizes cut functions in
graphs.

The following is folklore, but will be important to our investigations. Again,
the corresponding statements apply for arbitrary fractional polymorphisms, but
we only give the version we need in the present paper.

######  Definition 5.7 (Preserved under equality).

Let $f$ be a function that admits a multimorphism
$\langle\circ,\bullet\rangle$. We say that two tuples $\bar{x},\bar{y}\in
D^{\operatorname{\mathbf{ar}}(f)}$ are _preserved under equality_ if

$f(\bar{x})+f(\bar{y})=f(\bar{x}\circ\bar{y})+f(\bar{x}\bullet\bar{y}).$

For a relation $R\subseteq D^{\operatorname{\mathbf{ar}}(r)}$, we say that $f$
is _preserved under equality in $R$_ if every pair of tuples
$\bar{x},\bar{y}\in R$ is preserved under equality and
$\bar{x}\circ\bar{y},\bar{x}\bullet\bar{y}\in R$.

######  Lemma 5.8.

Let $\Gamma$ be a language of cost functions that admit a multimorphism
$\langle\circ,\bullet\rangle$ and let
$\lambda_{1},\lambda_{2}\in\operatorname{\mathbf{opt}}(I)$ for some instance
$I$ of _VSCP_ $(\Gamma)$. Then for every valued constraint $f(\bar{v})\in I$
it holds that

$\displaystyle
f(\lambda_{1}(\bar{v}))+f(\lambda_{2}(\bar{v}))=f((\lambda_{1}\circ\lambda_{2})(\bar{v}))+f((\lambda_{1}\bullet\lambda_{2})(\bar{v})),$

where $f(\lambda(\bar{v}))=f(\lambda(v_{1}),\ldots,\lambda(v_{r}))$ for
$\bar{v}=v_{1},\ldots,v_{r}$ is the value of $f(\bar{v})$ under $\lambda$. In
other words, every valued constraint $f(\bar{v})\in I$ is preserved under
equality in $\operatorname{\mathbf{opt}}(I)$.

###### Proof.

Let $\operatorname{\mathbf{cost}}_{f}(\lambda)$ be the sum of all valued
constraints $f(\bar{v})\in I$ under $\lambda$. By the multimorphism, we have
that

$\operatorname{\mathbf{cost}}_{f}(\lambda_{1})+\operatorname{\mathbf{cost}}_{f}(\lambda_{2})\geqslant\operatorname{\mathbf{cost}}_{f}(\lambda_{1}\circ\lambda_{2})+\operatorname{\mathbf{cost}}_{f}(\lambda_{1}\bullet\lambda_{2})$

and since $\lambda_{1}$ and $\lambda_{2}$ are optimal we obtain that

$\operatorname{\mathbf{cost}}_{f}(\lambda_{1})+\operatorname{\mathbf{cost}}_{f}(\lambda_{2})=2\operatorname{\mathbf{opt}}(\hat{I})=\operatorname{\mathbf{cost}}_{f}(\lambda_{1}\circ\lambda_{2})+\operatorname{\mathbf{cost}}_{f}(\lambda_{1}\bullet\lambda_{2})$

and therefore that
$\operatorname{\mathbf{cost}}_{f}(\lambda_{1}\circ\lambda_{2})=\operatorname{\mathbf{cost}}_{f}(\lambda_{1}\bullet\lambda_{2})=\operatorname{\mathbf{opt}}(\hat{I})$.
For two variables $u,v$ that appear together in a valued constraint $f$ let us
define

$\Delta_{f}(\bar{v}):=f(\lambda_{1}(\bar{v}))+f(\lambda_{2}(\bar{v}))-f((\lambda_{1}\circ\lambda_{2})(\bar{v}))-f((\lambda_{1}\bullet\lambda_{2})(\bar{v})),$

then by the multimorphism property it follows that
$\Delta_{f}(\bar{v})\geqslant 0$. Since, by definition,

$\displaystyle\operatorname{\mathbf{cost}}_{f}(\lambda_{1})+\operatorname{\mathbf{cost}}_{f}(\lambda_{2})-\operatorname{\mathbf{cost}}_{f}(\lambda_{1}\circ\lambda_{2})-\operatorname{\mathbf{cost}}_{f}(\lambda_{1}\bullet\lambda_{2})=\sum_{f(\bar{v})\in
I}\Delta_{f}(\bar{v})$

and the left-hand side evaluates to zero, we conclude that $\sum_{uv\in
G}\Delta_{f}(u,v)=0$ and therefore that $\Delta_{f}(u,v)=0$ for every
constraint $f(u,v)\in I$. ∎

To illustrate, let us return again to the case of graph cut functions and
submodularity over the Boolean domain. Let $G=(V,E)$ be an undirected graph,
and define the cut function $f_{G}\colon 2^{V}\to\mathbb{Z}$ as
$f_{G}(S)=|\delta(S)|$. Then $f_{G}$ is the sum over binary valued constraints
$f(u,v)=[u\neq v]$ over all edges $uv\in E$, in Iverson bracket notation.
Since a single valued constraint $f(u,v)$ is submodular, the same holds for
the cut function as a whole. Then Lemma 5.8 specialises into the statement
that for two sets $A,B\subset V$ such that $\delta(A),\delta(B)$ are minimum
$s$-$t$-cuts in $G$ for some $s,t\in V$, there is no edge between $A\setminus
B$ and $B\setminus A$. This kind of observation is a common tool in, e.g.,
graph theory and approximation algorithms.

The above lemma will be very useful when reasoning about the structure of
$\operatorname{\mathbf{opt}}(I)$ subject to more complex multimorphisms, as we
will define next.

###  5.3 Submodularity on trees

Let $\preceq_{T}$ denote the ancestor relationship in a rooted tree $T$. For a
path $P[x,y]\subseteq T$, let $z_{1},z_{2}$ be the middle vertices of $P[x,y]$
(allowing $z_{1}=z_{2}$ in case $P[x,y]$ has odd length) such that
$z_{1}\preceq_{T}z_{2}$. Define the commutative operators
$\operatorname{\mathbin{\curvearrowleft}},\operatorname{\mathbin{\curvearrowright}}$
as returning exactly those two mid vertices,
$x\operatorname{\mathbin{\curvearrowleft}}y=y\operatorname{\mathbin{\curvearrowleft}}x=z_{1}$
and
$x\operatorname{\mathbin{\curvearrowright}}y=y\operatorname{\mathbin{\curvearrowright}}x=z_{2}$.
Languages admitting the multimorphism
$\langle\operatorname{\mathbin{\curvearrowleft}},\operatorname{\mathbin{\curvearrowright}}\rangle$
are called _strongly tree-submodular_.

Define the commutative operator $\operatorname{\mathbin{\uparrow}}$ to return
the common ancestor of two nodes $x,y$ in a rooted tree $T$. Define
$x\operatorname{\mathbin{\nearrow}}y$ to be the vertex $z$ on $P[x,y]$ which
satisfies
$\operatorname{d}_{T}(x,z)=\operatorname{d}_{T}(y,x\operatorname{\mathbin{\uparrow}}y)$.
In other words, to find $z=x\operatorname{\mathbin{\nearrow}}y$, we measure
the distance from $y$ to the common ancestor of $x$ and $y$ and walk the same
distance from $x$ along $P[x,y]$. Languages that admit
$\langle\operatorname{\mathbin{\uparrow}},\operatorname{\mathbin{\nearrow}}\rangle$
as a multimorphism are called _weakly tree-submodular_. In particular, all
strongly tree-submodular languages are weakly tree-submodular [17]. Tree-
metric are, not very surprisingly, strongly tree-submodular:

######  Lemma 5.9.

Every tree-metric is strongly tree-submodular for every rooted version of the
tree.

###### Proof.

Let $T$ be a rooted tree and let $a,b,x,y\in T$ not necessarily distinct
nodes. We let $\operatorname{d}$ be the distance-metric on $T$. We need to
show that

$\displaystyle\operatorname{d}(a,b)+\operatorname{d}(x,y)\geqslant\operatorname{d}(a\operatorname{\mathbin{\curvearrowleft}}x,b\operatorname{\mathbin{\curvearrowleft}}y)+\operatorname{d}(a\operatorname{\mathbin{\curvearrowright}}x,b\operatorname{\mathbin{\curvearrowright}}y).$
(1)

First, consider the case that $P[a,b]\cap P[x,y]=P[m_{1},m_{2}]$ is a non-
empty path. Assume that $P[a,x]$ and $P[b,y]$ are disjoint, Then the left-hand
side of (1) is equal to

$\displaystyle\operatorname{d}(a,b)+\operatorname{d}(x,y)=|P[a,b]|+|P[x,y]|=2|P[m_{1},m_{2}]|+|P[a,x]|+|P[b,y]|.$
(2)

Since the nodes $a\operatorname{\mathbin{\curvearrowleft}}x$,
$a\operatorname{\mathbin{\curvearrowright}}x$ both lie on $P[a,x]$ and the
nodes $b\operatorname{\mathbin{\curvearrowleft}}y$,
$b\operatorname{\mathbin{\curvearrowright}}y$ on $P[a,y]$, the right-hand side
of (1) cannot be larger than the right-hand side of (2), thus (1) holds in
this case. In the alternative case where $P[a,x]$ and $P[b,y]$ are non-
disjoint, we instead use the paths $P[a,y]$, $P[b,x]$. In this case, the nodes
$a\operatorname{\mathbin{\curvearrowleft}}x$,
$a\operatorname{\mathbin{\curvearrowright}}x$,
$b\operatorname{\mathbin{\curvearrowleft}}y$,
$b\operatorname{\mathbin{\curvearrowright}}y$ could now also lie on
$P[m_{1},m_{2}]$ but the argument remains the same.

Thus consider the second case: $P[a,b]$ and $P[x,y]$ do not intersect. Let now
$P[c,z]$ be the unique path connecting $P[a,b]$ and $P[x,y]$ with $c\in
P[a,b]$ and $z\in P[x,y]$. First, we simplify our lives by observing that the
right-hand side of (1) can be replaced using

$\operatorname{d}(a\operatorname{\mathbin{\curvearrowleft}}x,b\operatorname{\mathbin{\curvearrowleft}}y)+\operatorname{d}(a\operatorname{\mathbin{\curvearrowright}}x,b\operatorname{\mathbin{\curvearrowright}}y)=2\operatorname{d}(m_{ax},m_{by})$

where we allow the mid-points $m_{ax}$ of $P[a,x]$ and $m_{by}$ of $P[b,y]$ to
lie in the middle of an edge (by some abuse of notation we extend
$\operatorname{d}$ to such mid-points of edges and allow it to take half-
integral values). Consider the following re-writing of (1):

$\displaystyle\operatorname{d}(a,b)+\operatorname{d}(x,y)\geqslant
2\operatorname{d}(m_{ax},m_{by}).$ (3)

Clearly, it holds in the degenerate case of $a=b=c$ and $x=y=z$. We prove the
remainder by induction through the insertion of an arbitrary edge. First,
assume that an edge is inserted into $P[a,c]$. This increases the left-hand
side of (3) by one and moves $m_{ax}$ by half a unit, thus at most increasing
the right-hand by one as well. The same holds, by symmetry, for any edge
inserted into $P[b,c]$, $P[x,z]$, and $P[y,z]$. It remains to consider edges
inserted into $P[c,z]$ whose addition does not contribute to the left-hand
side. If such an edge additionally lies on the path between $m_{ax}$ and
$m_{by}$, the distance between these two mid-points decreases by one;
otherwise both midpoints are shifted in such a way that they remain
equidistant. In neither scenario does the right-hand side increase, proving
the claim. Finally, since $\operatorname{d}$ does not depend on the choice of
root in $T$, the result also holds for every root. ∎

######  Corollary 5.10.

Every tree-metric is weakly tree-submodular for every rooted version of the
tree.

We will need the following characterization of which value-pairs are preserved
under equality by strong tree submodularity for tree distance functions.

######  Lemma 5.11.

Two tuples $(a,b),(x,y)\in V(T)\times V(T)$ are preserved under equality by
$\operatorname{d}_{T}$ with multimorphism
$\langle\operatorname{\mathbin{\curvearrowleft}},\operatorname{\mathbin{\curvearrowright}}\rangle$
iff all four nodes lie on a single path $P$ in $T$ _and_ either
$a,b\leqslant_{P}x,y$ or $a,x\leqslant_{P}b,y$.

Below is a complete enumeration of all orders in which the nodes $a,b,x,y$
might appear on a path, where we removed all cases in which $b$ appears before
$a$ (to break mirror symmetry) and all cases derivable by exchanging $a$ with
$x$ and $b$ with $y$, or applying both operations. The cases on the right side
show how the nodes might all appear on a single path and yet not be preserved
under quality by
$\langle\operatorname{\mathbin{\curvearrowleft}},\operatorname{\mathbin{\curvearrowright}}\rangle$
(if they were, the sum of the magenta lines would match the sum of the cyan
lines)

###### Proof.

Let $m_{ax}$ and $m_{bx}$ denote the mid-points of $P[a,x]$ and $P[b,y]$, as
in the proof of Lemma 5.9 we allow these points to lie in the middle of an
edge in case these paths are of even length. We drop the subscript of
$\operatorname{d}_{T}$ in the following.

For the one direction, assume that $a,b,x,y$ all lie on some common path $P$.
We now need to show that

$\displaystyle\operatorname{d}(a,b)+\operatorname{d}(x,y)=2\operatorname{d}(m_{ax},m_{by}).$
(4)

It will be helpful to identify $P$ with the interval $I=[0,|P|]$. We
distinguish several cases depending on the order imposed on these nodes by
$P$, the two principal cases are depicted below. Since $a,b$ are exchangable,
we will assume that $a\leqslant_{P}b$ in all cases.

In both of these pictures we can easily verify that $m_{ax}$ lies at position
$\operatorname{d}(a,x)/2$ on $I$ and $m_{by}$ at
$\operatorname{d}(a,b)+\operatorname{d}(b,y)/2$, hence

$\displaystyle 2\operatorname{d}(m_{ax},m_{by})$
$\displaystyle=2\Big{|}\frac{\operatorname{d}(a,x)}{2}-\big{(}\operatorname{d}(a,b)+\frac{\operatorname{d}(b,y)}{2}\big{)}\Big{|}=\Big{|}\\!\operatorname{d}(a,x)-\operatorname{d}(b,y)-2\operatorname{d}(a,b)\Big{|}$
$\displaystyle=\operatorname{d}(a,b)+\operatorname{d}(x,y).$

Note that the case $axyb$ is equivalent to the case $axby$, since exchanging
$y$ and $b$ does not affect $m_{by}$ and thus none of the relevant distances.
This proves the first direction.

In the other direction, first assume that the nodes do all lie on a path $P$
but do no fulfil the second property. After removing symmetries we are left
with the four cases $aybx$, $ayxb$, $yaxb$. Consider $aybx$ first. We have
that

$\displaystyle 2\operatorname{d}(m_{ax},m_{by})$
$\displaystyle=2\Big{|}\frac{\operatorname{d}(a,x)}{2}-\big{(}\operatorname{d}(a,y)+\frac{\operatorname{d}(y,b)}{2}\big{)}\Big{|}=\Big{|}\\!\operatorname{d}(a,x)-\operatorname{d}(y,b)-2\operatorname{d}(a,y)\Big{|}$
$\displaystyle=\Big{|}\\!\operatorname{d}(a,y)+\operatorname{d}(b,x)-2\operatorname{d}(a,y)\Big{|}=\Big{|}\\!\operatorname{d}(b,x)-\operatorname{d}(a,y)\Big{|},$

which is smaller than either $\operatorname{d}(a,b)$ or
$\operatorname{d}(x,y)$. The calculation for $yaxb$ is essentially the same,
which leaves us with $ayxb$. In that case (skipping to the part where the
computation diverges) we obtain that

$\displaystyle 2\operatorname{d}(m_{ax},m_{by})$
$\displaystyle=\Big{|}\\!\operatorname{d}(a,x)-\operatorname{d}(y,b)-2\operatorname{d}(a,y)\Big{|}$
$\displaystyle=\Big{|}\\!\operatorname{d}(a,y)+\operatorname{d}(y,x)-\operatorname{d}(y,x)-\operatorname{d}(x,b)-2\operatorname{d}(a,y)\Big{|}$
$\displaystyle=\operatorname{d}(a,y)+\operatorname{d}(x,b),$

which is smaller than $\operatorname{d}(a,b)$ unless $x=y$.

This concludes the case in which the nodes all lie on a path, hence we are
left with cases in which the nodes $a,b,x,y$ do not lie on a single path in
$T$. First, consider the case $aybx$ (as in the above figure) and imagine
introducing edges to take $y$ and $b$ away from the path $P[a,x]$. Every edge
introduced in this manner will contribute exactly one the the left-hand side
of (4) and at most one to the right-hand side (since $m_{by}$ moves by half a
unit). Hence no tree derivable from $aybx$ can ever achieve equality. The same
argument holds for $ayxb$ (where we introduced edges to remove $y$ and $x$
from $P[a,b]$) and $yaxb$ (were we remove $a$ and $x$ from $P[y,b]$).

In the case of $axby$, removing $x$ or $b$ from $P[a,y]$ by introducing an
edge will contribute one to the left-hand side of (4) and decrease the right-
hand side (since $m_{ax}$ would move away from $a$ and $m_{by}$ away from
$y$), hence equality is broken. A similar argument works for $axyb$ and
$abxy$, in both cases the midpoints move in a way that decreases the right-
hand side of (4). This proves the claim. ∎

######  Corollary 5.12.

Let $d_{T}$ be preserved under equality in $R$ for some $R\subseteq
V_{T}\times V_{T}$, with at least one pair $(a,b)\in R$ with $a\neq b$. Then
there is a path $P$ in $T$ which can be oriented as a directed path such that
for every pair $(a,b)\in R$ the nodes $a$ and $b$ lie on $P$ with
$a\preceq_{P}b$.

###### Proof.

We first show that it holds for all pairs $(a,b)\in R$ with $a\neq b$. Let
$ij$ be an edge of $T$ and let $T_{i}$, $T_{j}$ be the trees of $T-ij$. By the
above lemma, there are no two pairs $(a,b),(x,y)\in R$ such that $a,y\in
T_{i}$ and $b,x\in T_{j}$. Hence we can define an oriented subforest
$T^{\prime}$ of $T$ by including a directed edge $ij$ whenever there is a pair
$(a,b)\in R$ with $a\in T_{i}$, $b\in T_{j}$. Then again by the above lemma,
there is no path $P$ in $T$ such that $T^{\prime}$ contains edges of $P$
oriented in conflicting directions. This implies that $T^{\prime}$ is a
subgraph of a directed path in $T$.

Next, let $P$ be a minimal directed path as above, i.e., $P=T[s,t]$ for some
$s,t$ such that $R$ contains pairs $(s,s^{\prime}),(t^{\prime},t)$ for some
$s^{\prime},t^{\prime}$, and all pairs of $R$ of non-zero length lie on $P$.
Let $(a,a)\in R$ be a point not on $P$ and let $b$ be the point on $P$ closest
to $a$. By Lemma 5.11, there is no pair $(x,y)\in R$ with $x\prec b\prec y$.
Let $(x,y)\in R$ with $x\neq y$, and assume that $x\prec y\prec b$. We claim
that by iterating the strong tree submodularity multimorphism, starting with
$(x,y)$ and $(a,a)$, we can generate new pairs $(x^{\prime},y^{\prime})\in R$
with $x^{\prime}\neq y^{\prime}$, such that $x^{\prime}$ and $y^{\prime}$ are
strictly closer to $a$ than $x$ and $y$. Indeed, let $m_{xa}$ and $m_{ya}$ be
the midpoints, which as above are allowed to lie on the middle of edges. Then
$m_{xa}$ and $m_{ya}$ are distinct, and if they are at distance at least 1 the
conclusion is clear. Otherwise one of the points is integral, and one of the
operations $\operatorname{\mathbin{\curvearrowleft}}$,
$\operatorname{\mathbin{\curvearrowright}}$ rounds the other point in the
other direction, generating a pair $(x^{\prime},y^{\prime})$ of non-zero
length. By iterating this, we eventually generate a pair $(b,b^{\prime})\in R$
where $b\neq b^{\prime}$ and $b^{\prime}$ does not lie on $P$, which is a
contradiction. ∎

###  5.4 The domain consistency property

Consider a problem VCSP$(\Gamma)$ over a domain $D_{I}$ and a discrete
relaxation VCSP$(\Gamma^{\prime})$ of VCSP$(\Gamma)$ over a domain $D\supseteq
D_{I}$. We say that the relaxation has the _domain consistency property_ if
the following holds: for any instance $I$ of VCSP$(\Gamma^{\prime})$, if for
every variable $v$ there is an optimal solution to $I$ where $v$ takes a value
in $D_{I}$, then there is an optimal solution where all variables take values
in $D_{I}$, an optimal solution to the original problem of the same cost. We
will use the results of the previous section to show that the relaxations we
are using for Zero Extension and Metric Labelling on induced tree metrics have
the domain consistency property (in the latter case with a suitable
restriction on the unary costs), allowing for $\FPT$ algorithms under the gap
parameter via simple branching algorithms.

The result will follow from a careful investigation of the binary constraints
that $\operatorname{\mathbf{opt}}(I)$ can induce on a pair of vertices $u,v\in
V$, also for cases when there is no edge $uv$ in $G$. The result builds on
Corollary 5.12.

For the rest of the section, let us fix a relaxed instance
$I=(G=(V,E),\tau,\mu,q)$ of Zero Extension where $\mu$ is a tree metric
defined by a tree $T$, and the original (non-relaxed) metric is the
restriction of $\mu$ to a set of nodes $D_{I}$. Note that $I$ can be expressed
as a VCSP instance using assignments and the valued constraint $\mu$. Let
$\operatorname{\mathbf{opt}}$ be the set of optimal labellings. For a vertex
$v\in V$, let $D(u)$ denote the set
$\\{\lambda(u)\mid\lambda\in\operatorname{\mathbf{opt}}\\}$, and let
$D_{I}(v)=D_{I}\cap D(v)$. Furthermore, for a pair of vertices $u,v\in V$, let
$R(u,v)=\\{(\lambda(u),\lambda(v))\mid\lambda\in\operatorname{\mathbf{opt}}\\}$
be the projection of $\operatorname{\mathbf{opt}}$ onto $(u,v)$, and
$R_{I}(u,v)=R(u,v)\cap(D_{I}\times D_{I})$ the integral part of this
projection. Let $F\subseteq E$ be the set of edges that are crossing in at
least one $\lambda\in\operatorname{\mathbf{opt}}$ and let $E_{0}=E\setminus
F$.

We begin by observing that the “path property” of Corollary 5.12 applies to
all vertices and edges in $\operatorname{\mathbf{opt}}$.

######  Lemma 5.13.

For every vertex $v$ that lies in a connected component of $G$ containing at
least one terminal, $D(v)$ is a path in $T$. Furthermore, for every edge
$uv\in E$, $R(u,v)$ embeds into the transitive closure of a directed path in
$T$.

###### Proof.

First note that $v$ has the same domain as any vertex $u$ reachable from $v$
via edges of $E_{0}$. Therefore we can focus on the case that $v$ is incident
with an edge $uv\in F$. In this case, the valued constraint
$\operatorname{d}_{T}(u,v)$ is present in $I$, and by Lemma 5.8 is preserved
under equality in $R(u,v)$. Since $D(v)$ is just the projection of $R(u,v)$ to
$v$, it follows from Corollary 5.12 that $D(v)$ is contained in a path.
Furthermore, $D(v)$ itself is closed under the
$\operatorname{\mathbin{\curvearrowleft}}$,
$\operatorname{\mathbin{\curvearrowright}}$ operations, which implies that
$D(v)$ covers the whole path. For the second part, if $uv\in F$ then the claim
is Corollary 5.12. Otherwise, $R(u,v)$ is a collection of pairs $(x,x)$ for
all $x\in D(v)$, which is equal to a path in $T$. ∎

Next, we show the main result of this section: if $u$ and $v$ is a pair of
variables, then whether or not there is an edge $uv$ in $E$, the constraint
$R(u,v)$ induced on $u$ and $v$ by $\operatorname{\mathbf{opt}}$ is only non-
trivial on values in $D(u)\cap D(v)$. Note that the proof only uses the
algebraic properties of weak tree submodularity, hence the only assumption
that is specific to Zero Extension is that $D(u)$ and $D(v)$ form paths in
$T$.

######  Lemma 5.14.

Let $u$ and $v$ be a pair of variables and $a\in D(u)$, $b\in D(v)$ a pair of
values. If $(a,b)\notin R(u,v)$, then $a,b\in D(u)\cap D(v)$ and $a\neq b$.

###### Proof.

Refer to the values of $D(u)\cap D(v)$ as _shared values_ , and other values
of $D(u)$ and $D(v)$ as _non-shared values_. Since $D(u)$ and $D(v)$ is each a
path in $T$, $R(u,v)$ is contained in the product of these paths, and the
shared values (if any) induce a common path. Let $P_{u}$ be the path on
vertices $D(u)$ and $P_{v}$ the path on vertices $D(v)$. Let $\omega_{d}$
denote the $d$-rooted weak tree submodularity multimorphism. Using the
operation $\operatorname{\mathbin{\uparrow}}$ rooted in $d$, we find for any
$d$ that $R(u,v)$ contains a pair $(a,b)$ where $a\in D(u)$ and $b\in D(v)$
are both chosen as the point closest to $d$. We refer to this as the _$d$
-closest pair_. We first handle the case that there are no shared values.

######  Claim.

If there are no shared values, then $R(u,v)=D(u)\times D(v)$.

###### Proof.

Let $p\in P_{u}$ and $q\in P_{v}$ be the points on the respective path closest
to the other path. By considering the $p$-closest pair in $R(u,v)$, we find
$(p,q)\in R(u,v)$. Now let $a\in D(u)$ and $b\in D(v)$ be arbitrary. By
considering the $a$-closest and $b$-closest pairs in $R(u,v)$, we find
$(a,q),(p,b)\in R(u,v)$. But then $\omega_{p}$ on this pair produces $(a,b)\in
R(u,v)$. ∎

Next, assume that there are shared values, and let $P_{I}$ be the path induced
on these values. Note that $(r,r)\in R(u,v)$ for every $r\in V(P_{I})$, by
considering the $r$-closest pair. We also have the following.

######  Claim.

Every vertex $r\in D(u)\cap D(v)$ is compatible with every vertex of
$D(u)\mathop{\vartriangle}D(v)$, i.e., $(a,r)\in R(u,v)$ for every $a\in
D(u)\setminus D(v)$, and $(r,b)\in R(u,v)$ for every $b\in D(v)\setminus
D(u)$.

###### Proof.

Let $r_{0}$ and $r_{n}$ be the endpoints of $P_{I}$. The vertices of
$D(u)\mathop{\vartriangle}D(v)$ are split into those closest to $r_{0}$ and
those closest to $r_{n}$. We first note that every vertex $a\in
D(u)\mathop{\vartriangle}D(v)$ is compatible with that endpoint it is closest
to, by considering the $a$-closest pair in $R(u,v)$. Next, let $a\in
D(u)\setminus D(v)$ be a point closer to $r_{0}$ than $r_{n}$, and write
$P_{I}=r_{0}r_{1}\ldots r_{n}$. We claim by induction that $(a,r_{i})\in
R(u,v)$ for every $i=0,\ldots,n$. As a base case, we already have
$(a,r_{0})\in R(u,v)$. The inductive step then goes as follows:

  1. 1.

Assume $(a,r_{i})\in R(u,v)$ for some $i<n$. Then $(a,r_{i})$ and
$(r_{i+1},r_{i+1})$ via $\omega_{r_{i}}$ produces $(a^{\prime},r_{i+1})$ where
$a^{\prime}$ is the vertex following $a$ on $P_{u}$ and may be
$a^{\prime}=r_{0}$

  2. 2.

$(a,r_{i}),(a^{\prime},r_{i+1})$ via $\omega_{r_{i}}$ produces $(a,r_{i+1})$

By induction we then get $(a,r)\in R(u,v)$ for every $r\in V(P_{I})$, and the
rest of the cases of the claim follow by symmetry. ∎

The rest of the proof is now easy. Let $a\in D(u)\setminus D(v)$ and $b\in
D(v)$; the other case is symmetric. If $b$ is a shared value, then $(a,b)\in
R(u,v)$ by the above. Otherwise, let $r$ be an arbitrary shared value; then
$(a,r),(r,b)\in R(u,v)$ and $\omega_{r}$ produces $(a,b)\in R(u,v)$. Hence the
only excluded pairs are on shared values. Finally, $(r,r)\in R(u,v)$ for every
shared value $r$ by considering the $r$-closest pair. ∎

We also need the following standard result.

######  Lemma 5.15.

Let $\lambda_{0}$ be a partial labelling on a set of vertices $U\subseteq V$.
Then there exists a labelling $\lambda\in\operatorname{\mathbf{opt}}$ that
extends $\lambda_{0}$ if and only if $(\lambda_{0}(u),\lambda_{0}(v))\in
R(u,v)$ for every pair $u,v\in U$.

###### Proof.

Define the operation
$m(a,b,c)=((a\operatorname{\mathbin{\uparrow}}b)\operatorname{\mathbin{\nearrow}}(a\operatorname{\mathbin{\uparrow}}c))\operatorname{\mathbin{\nearrow}}(b\operatorname{\mathbin{\uparrow}}c)$
(for an arbitrary choice of root). Then $m$ preserves
$\operatorname{\mathbf{opt}}$, and it is readily verified that $m$ is a
_majority operation_ , i.e., $m(x,x,y)=m(x,y,x)=m(y,x,x)x$. It follows that
$\operatorname{\mathbf{opt}}$ is characterized by its binary projections. ∎

This gives us the following algorithmic consequence.

######  Lemma 5.16.

There is a labelling $\lambda\in\operatorname{\mathbf{opt}}$ such that for
every variable $v$ with $D_{I}(v)$ non-empty, we have $\lambda(v)\in D_{I}$.

###### Proof.

Let $U=\\{v\in V\mid D_{I}(v)\neq\emptyset\\}$ be the set of vertices with at
least one integral value in the support. By Lemma 5.15, it suffices to produce
a partial labelling $\lambda_{0}:U\to D_{I}$ such that every binary projection
of $\lambda_{0}$ is supported by $\operatorname{\mathbf{opt}}$, i.e., for
every pair of distinct vertices $u,v\in U$ we have
$(\lambda_{0}(u),\lambda_{0}(v))\in R(u,v)$. For this, define an arbitrary
total order on $D_{I}$, and define $\lambda_{0}$ by selecting for every $v\in
U$ the value of $D_{I}(v)$ that is earliest according to this order. Then for
every pair $u,v\in U$ either $\lambda_{0}(u)=\lambda_{0}(v)$ or one of the
values $\lambda_{0}(u),\lambda_{0}(v)$ is not shared in $R(u,v)$. In both
cases, by Lemma 5.14 we have $(\lambda_{0}(u),\lambda_{0}(v))\in R(u,v)$. ∎

Let us for reusability spell out the explicit assumptions and requirements
made until now.

######  Theorem 5.17.

Let $I=(G=(V,E),\tau,\mu,q)$ be an instance of Zero Extension with no isolated
vertices and where every connected component of $G$ contains at least two
terminals, and where $\mu$ is an induced tree metric for some tree $T$ and
integral nodes $D_{I}\subseteq T$. Additionally, assume a collection of cost
functions ${\mathcal{F}}=(f_{i}(\bar{v}_{i}))_{i=1}^{m}$ has been given, where
for every $f_{i}$ the scope is contained in $V$ and where $f_{i}$ is weakly
tree submodular for every rooted version of $T$. Let $I^{\prime}$ be the VCSP
instance created from the sum of the cost functions of $I$ and $\mathcal{F}$.
Then $I^{\prime}$ has the domain consistency property, i.e., there is an
integral relaxed optimum if and only if every vertex $v$ is integral in at
least one relaxed optimum of $I^{\prime}$.

###### Proof.

As noted in Lemma 5.13, due to the instance $I$ every vertex $v$ is either
incident with at least one edge of $E$ that has non-zero length in at least
one optimum, or it holds that $u=v$ in every optimal assignment, where $u$ is
such a vertex. Hence $D(v)$ forms a path in $T$, and for every pair of
variables $u,v\in V$ the conclusion of Lemma 5.14 applies, even for the
projection $R(u,v)$ of $\operatorname{\mathbf{opt}}(I^{\prime})$ (as opposed
to just $\operatorname{\mathbf{opt}}(I)$). The result follows as in Lemma
5.16. ∎

###  5.5 Gap algorithms for general induced tree metrics

We now use the results of Theorem 5.17 to provide $\FPT$ algorithms
parameterized by the gap parameter $k-\rho$.

See 1.3

###### Proof.

This algorithm is similar to the algorithm for a leaf metric, except that we
are not as easily able to test whether every variable has an integral value in
$\operatorname{\mathbf{opt}}$. By the results of Section 5.1, the value of
$\operatorname{\mathbf{opt}}$ is witnessed by the collection of min-cuts for
edges in $T$; we will use this as a value oracle for $I$. We initially compute
a max-flow across every edge of $T$, then for every assignment made we can
compute the new value of $\operatorname{\mathbf{opt}}$ using $O(|T|)$ calls to
augmenting path algorithms. This allows us to test for optimality of an
assignment in $O(|T|m)$ time. The branching step then in general iterates over
at most $n$ variables, testing at most $|D|$ assigned values for each, and
testing for optimality each time. Hence the local work in a single node of the
branching tree is $O(|T||D|nm)$. This either produces a variable for branching
on or (by Theorem 5.17) produces an integral assignment, and in each branching
step the value of $\rho$ increases but $q$ does not. The time for the initial
max-flow computation is eaten by the factor $|T|nm$. The result follows. ∎

For Metric Labelling, we first need to restrict the unary cost functions to be
weakly tree-submodular.

######  Lemma 5.18.

Let $f\colon V(T)\to\mathbb{R}$ be a unary function on a tree $T$. Then $f$ is
weakly tree submodular on $T$ for every choice of root $r\in V_{T}$ if and
only if it observes the following _interpolation property_ : for any nodes
$u,v\in V(T)$, at distance $\operatorname{d}_{T}(u,v)=d$, and every
$i\in[d-1]$, let $w_{i}$ be the node on $T[u,v]$ satisfying
$d_{T}(u,w_{i})=i$. Then for any such choice of $u$, $v$ and $i$, it holds
that $f(w_{i})\leqslant((d-i)/d)f(u)+(i/d)f(v)$.

###### Proof.

On the one hand, assume that $f$ has the gradient property, and let $u,v\in
V(T)$ and let $r\in V(T)$ be a choice of root. We need to show that $f$ is
preserved by the $r$-rooted weakly tree submodular multimorphism. If $r$ does
not lie on $T[u,v]$, or $r\in\\{u,v\\}$, then this is vacuous. Otherwise, let
$\operatorname{\mathbin{\uparrow}}(u,v)$ be the $i$:th node of $T[u,v]$,
$i\in[d-1]$. Then we need to show

$f(u)+f(v)\geqslant f(w_{i})+f(w_{d-i}),$

which clearly holds. On the other hand, let $u,v\in V(T)$ and
$i\in[\operatorname{d}_{T}(u,v)-t]$ be such that the interpolation property
does not hold. Let $w_{a}$, $a<i$ be the last vertex before $w_{i}$ on
$T[u,v]$ such that the interpolation equality holds for $u$, $v$ and $a$, and
let $w_{b}$, $b>i$ be the first vertex after $w_{i}$ for which it holds. These
vertices clearly exist, possibly with choices $w_{a}=u$ and $w_{b}=v$. Then
$w_{a}$ and $w_{b}$ are a witness that the $w_{i}$-rooted weak tree
submodularity multimorphism is not a multimorphism of $f$. ∎

In particular, let $f_{0}\colon U\to\mathbb{Z}^{+}$ be a non-negative function
defined on a subset $U$ of the nodes of a tree $T$, and say that $f_{0}$
_admits an interpolation on $T$_ if there is an extension $f\colon
V(T)\to\mathbb{Z}^{+}$ with the interpolation property such that
$f(v)=f_{0}(v)$ for every $v\in U$. In particular, if $U$ is the set of leaves
of $T$, then every function $f_{0}$ admits an interpolation by simply padding
with zero values (although stronger interpolations are in general both
possible and desirable).

See 1.5

###### Proof.

Assume that $G$ is connected, or else repeat the below for every connected
component of $G$. Select two arbitrary vertices $u,v\in V$ and exhaustively
guess their labels; in the case that you guess them to have the same label,
identify the vertices in $I$ (adding up their costs in $\sigma$) and select a
new pair to guess on. Note that this takes at most $O(|D|^{2}n)$ time,
terminating whenever you have guessed more than one label in a branch or when
you have guessed that all vertices are to be identical. This guessing phase
can only increase the value of $\rho$. We may now treat $u$ and $v$ as
terminals, and the instance $I$ as the sum of a Zero Extension instance on
those two terminals and a collection of additional unary cost functions
$\sigma(v^{\prime},\cdot)$, as in Theorem 5.17. Note that the resulting VCSP
is tractable, i.e., the value of an optimal solution can be computed in
polynomial time. The running time from this point on consists of iterating
through all variables verifying whether each one has an integral value in some
optimal assignment, and branching exhaustively on its value if not. ∎

In particular, as noted, for a leaf metric $\mu$ the algorithm applies without
any assumptions on $\sigma$ (and without $T$ being explicitly provided).

##  6 Conclusions

We have given a range of algorithmic results for the Zero Extension and Metric
Labelling problems from a perspective of parameterized complexity.

Most generally, we showed that Zero Extension is $\FPT$ parameterized by the
number of _crossing edges_ of an optimal solution, the number of edges whose
endpoints receive distinct labels, for a very general class of cost functions
$\mu$ that need not even be metrics. This is a relatively straight-forward
application of the technique of recursive understanding [4].

For the more reasonable case that $\mu$ is a metric, observing the triangle
inequality, we gave two stronger results for the same parameter. First, we
showed a linear-time $\FPT$ algorithm, with a better parameter dependency,
using an important separators-based algorithm. Second, and highly
surprisingly, we show that every graph $G$ with a terminal set $S$ admits a
polynomial-time computable, polynomial-sized _metric sparsifier_ $G^{\prime}$,
with $O(k^{s+1})$ edges, such that $(G^{\prime},S)$ mimics the behaviour of
$(G,S)$ over _any_ metric on at most $s$ labels (up to solutions with crossing
number $k$). This is a direct and seemingly far-reaching generalization of the
polynomial kernel for $s$-Multiway Cut [19], which corresponds to the special
case of the uniform metric.

Finally, we further developed the toolkit of discrete relaxations to design
$\FPT$ algorithms under a _gap parameter_ for Zero Extension and Metric
Labelling where the metric is an induced tree metric (a restriction of a tree
metric to a subset of the values). This in particular involves a more general
$\FPT$ algorithm approach, supported by an applicability condition of _domain
consistency_ , relaxing the previously used persistence condition.

Let us highlight some questions. First, is there a lower bound on the size of
a metric sparsifier for $s$ labels for Zero Extension? This is particularly
relevant since the existence of a polynomial kernel for $s$-Multiway Cut whose
degree does not scale with $s$ is an important open problem, and since the
metric sparsifier is a more general result.

Second, can the $\FPT$ algorithms for induced tree metrics parameterized by
the relaxation gap be generalised to restrictions of other tractable metrics,
such as graph metrics for median graphs or the most general tractable class of
orientable modular graphs [11]? Complementing this, what are the strongest
possible gap parameters that allow $\FPT$ algorithms for metrics that are
either arbitrary, or do not explicitly provide their relaxation?

More broadly, we also ask how far the method of discrete relaxations stretches
in general. Let Subset VCSP be the class of problems defined by a (presumably
tractable) integer-valued language $\Gamma$ on a domain $D$, and a subset
$D_{I}\subseteq D$ of integral values in the domain, where the problem is
equivalent to the VCSP on $\Gamma$ restricted to the domain $D_{I}$, but where
we ask for an $\FPT$ algorithm parameterized by the corresponding relaxation
gap. Can it be characterized for which $\Gamma$ and $D_{I}$ this problem is
$\FPT$, and/or for which cases the domain consistency property holds?

## References

  * [1] J. Besag.  On the statistical analysis of dirty pictures.  J. Royal Stat. Soc. Ser. B, pages 259–302, 1986.
  * [2] S. Chakrabarti, B. Dom, and P. Indyk.  Enhanced hypertext categorization using hyperlinks.  In ACM SIGMOD Record, volume 27, pages 307–318. ACM, 1998.
  * [3] J. Chen, Y. Liu, and S. Lu.  An improved parameterized algorithm for the minimum node multiway cut problem.  Algorithmica, 55(1):1–13, 2009.
  * [4] R. Chitnis, M. Cygan, M. Hajiaghayi, M. Pilipczuk, and M. Pilipczuk.  Designing FPT algorithms for cut problems using randomized contractions.  SIAM J. Sci. Comput., 45(4):1171–1229, 2016.
  * [5] J. Chuzhoy and J. Naor.  The hardness of metric labeling.  SIAM J. Sci. Comput., 36(5):1376–1386, 2007.
  * [6] J. Culberson and P. Rudnicki.  A fast algorithm for constructing trees from distance matrices.  Inf. Process. Lett., 30(4):215–220, 1989.
  * [7] J. Fakcharoenphol, C. Harrelson, S. Rao, and K. Talwar.  An improved approximation algorithm for the 0-extension problem.  In Proc. of 14th SODA, pages 257–265. SIAM, 2003.
  * [8] J. Fakcharoenphol, S. Rao, and K. Talwar.  A tight bound on approximating arbitrary metrics by tree metrics.  J. Comput. Syst. Sci., 69(3):485–497, 2004.
  * [9] F. V. Fomin, D. Lokshtanov, F. Panolan, and S. Saurabh.  Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms.  J. ACM, 63(4):29:1–29:60, 2016.
  * [10] H. Hirai.  The maximum multiflow problems with bounded fractionality.  Math. Oper. Res., 39(1):60–104, 2014.
  * [11] H. Hirai.  Discrete convexity and polynomial solvability in minimum 0-extension problems.  Math. Program., 155(1-2):1–55, 2016.
  * [12] H. Hirai and G. Pap.  Tree metrics and edge-disjoint $S$-paths.  Math. Program., 147(1-2):81–123, 2014.
  * [13] Y. Iwata, M. Wahlström, and Y. Yoshida.  Half-integrality, LP-branching, and FPT algorithms.  SIAM J. Comput., 45(4):1377–1411, 2016.
  * [14] Y. Iwata, Y. Yamaguchi, and Y. Yoshida.  Linear-time FPT algorithms via half-integral non-returning A-path packing.  CoRR, abs/1704.02700, 2017.
  * [15] H. Karloff, S. Khot, A. Mehta, and Y. Rabani.  On earthmover distance, metric labeling, and 0-extension.  SIAM J. Sci. Comput., 39(2):371–387, 2009.
  * [16] A. Karzanov.  Minimum 0-extensions of graph metrics.  Eur. J. Comb., 19(1):71–101, 1998.
  * [17] V. Kolmogorov.  Submodularity on a tree: Unifying L♮natural-convex and bisubmodular functions.  In Proc. of 36th MFCS, pages 400–411. Springer, 2011.
  * [18] V. Kolmogorov, A. A. Krokhin, and M. Rolínek.  The complexity of general-valued CSPs.  SIAM J. Comput., 46(3):1087–1110, 2017.
  * [19] S. Kratsch and M. Wahlström.  Representative sets and irrelevant vertices: New tools for kernelization.  In Proc. of 53rd FOCS, pages 450–459. IEEE Computer Society, 2012.
  * [20] V. Kumar, J. Mukherjee, and S. Mandal.  Image inpainting through metric labeling via guided patch mixing.  IEEE Trans. Image Process., 25(11):5212–5226, 2016.
  * [21] L. Lovász.  Flats in matroids and geometric graphs.  In Proc. of 6th Br. Comb. Conf., Combinatorial Surveys, pages 45–86, 1977.
  * [22] R. Manokaran, J. Naor, P. Raghavendra, and R. Schwartz.  SDP gaps and UGC hardness for multiway cut, 0-extension, and metric labeling.  In Proc. of 40th STOC, pages 11–20, 2008.
  * [23] D. Marx.  Parameterized graph separation problems.  Theor. Comput. Sci., 351(3):394–406, 2006.
  * [24] D. Marx.  A parameterized view on matroid optimization problems.  Theor. Comput. Sci., 410(44):4471–4479, 2009.
  * [25] D. Marx and I. Razgon.  Fixed-parameter tractability of multicut parameterized by the size of the cutset.  SIAM J. Comput., 43(2):355–388, 2014.
  * [26] M. Naor, L.J.Schulman, and A. Srinivasan.  Splitters and near-optimal derandomization.  In Proc. of 36th FOCS, pages 182–191. IEEE, 1995.
  * [27] M. Óskarsdóttir, C. Bravo, W. Verbeke, C. Sarraute, B. Baesens, and J. Vanthienen.  A comparative study of social network classifiers for predicting churn in the telecommunication industry.  In Proc. of 8th ASONAM, pages 1151–1158. IEEE, 2016.
  * [28] J. Oxley.  Matroid Theory.  Oxford University Press, 2011.
  * [29] B. Pang and L. Lee.  Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales.  In Proc. of 43rd ACL, pages 115–124. Association for Computational Linguistics, 2005.
  * [30] J. Picard and H. Ratliff.  A cut approach to the rectilinear distance facility location problem.  Oper. Res., 26(3):422–433, 1978.
  * [31] A. Schrijver.  Combinatorial Optimization: Polyhedra and Efficiency.  Springer, 2003.
  * [32] J. Kleinberg and E. Tardos.  Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields.  J. ACM, 49(5):616–639, 2002.
  * [33] J. Thapper and S. Živný.  The complexity of finite-valued CSPs.  J. ACM, 63(4):37, 2016.
  * [34] N. Vikas.  A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results.  J. Comput. Syst. Sci., 71(4):406–439, 2005.
  * [35] M. Wahlström.  LP-branching algorithms based on biased graphs.  In Proc. of 28th SODA, pages 1559–1570. SIAM, 2017.