Utrecht University, The
Netherlandsh.l.bodlaender@uu.nlhttps://orcid.org/0000-0002-9297-3330 Utrecht
University, The
Netherlandsi.m.e.mannens@uu.nlhttps://orcid.org/0000-0003-2295-0827 Utrecht
University, The
Netherlandsj.j.oostveen@uu.nlhttps://orcid.org/0009-0009-4419-3143 Utrecht
University, The
Netherlandss.pandey1@uu.nlhttps://orcid.org/0000-0001-5728-1120 Utrecht
University, The
Netherlandse.j.vanleeuwen@uu.nlhttps://orcid.org/0000-0001-5240-7257
[500]Mathematics of computing Graph theory [500]Theory of computation Graph
algorithms analysis [500]Theory of computation Problems, reductions and
completeness

# The Parameterised Complexity of Integer Multicommodity Flow††thanks: The
research of Isja Mannens was supported by the project CRACKNP that has
received funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement No
853234). The research of Jelle Oostveen was supported by the NWO grant
OCENW.KLEIN.114 (PACAN).

Hans L. Bodlaender  Isja Mannens  Jelle J. Oostveen  Sukanya Pandey  Erik Jan
van Leeuwen

###### Abstract

The Integer Multicommodity Flow problem has been studied extensively in the
literature. However, from a parameterised perspective, mostly special cases,
such as the Disjoint Paths problem, have been considered. Therefore, we
investigate the parameterised complexity of the general Integer Multicommodity
Flow problem. We show that the decision version of this problem on directed
graphs for a constant number of commodities, when the capacities are given in
unary, is XNLP-complete with pathwidth as parameter and XALP-complete with
treewidth as parameter. When the capacities are given in binary, the problem
is NP-complete even for graphs of pathwidth at most $13$. We give related
results for undirected graphs. These results imply that the problem is
unlikely to be fixed-parameter tractable by these parameters.

In contrast, we show that the problem does become fixed-parameter tractable
when weighted tree partition width (a variant of tree partition width for edge
weighted graphs) is used as parameter.

###### keywords:

multicommodity flow; parameterised complexity; XNLP-completeness; XALP-
completeness

##  1 Introduction

The Multicommodity Flow problem is the generalisation of the textbook flow
problem where instead of just one commodity, multiple different commodities
have to be transported through a network. The problem models important
operations research questions (see e.g. [36]). Although several optimisation
variants of this problem exist [36], we consider only the variant where for
each commodity, a given amount of flow (the demand) has to be sent from the
commodity’s source to its sink, subject to a capacity constraint on the total
amount flow through each arc. The nature and computational complexity of the
problem is highly influenced by the graph (undirected or directed, its
underlying structure) and the capacities, demands, and flow value (integral or
not, represented in unary or binary). When the flow values are allowed to be
fractional, the problem can be trivially solved through a linear program (see
e.g. [26, 29]).

We focus on Integer Multicommodity Flow, where all the given capacities and
demands are integers, and the output flow must also be integral. The Integer
Multicommodity Flow problem is widely studied and well known to be NP-hard
even if all capacities are $1$, on both directed and undirected graphs, even
when there are only two commodities [13]. On directed graphs, it is NP-hard
even for two commodities of demand $1$ [16]. These strong hardness results
have led to a wide range of heuristic solution methods being investigated as
well as a substantial body of work on approximation algorithms. For surveys,
see e.g., [1, 36, 37].

An important special case of Integer Multicommodity Flow and the main source
of its computational hardness is the Edge Disjoint Paths problem. It can be
readily seen that Integer Multicommodity Flow is equivalent to Edge Disjoint
Paths when all capacities and demands are $1$. Indeed, all aforementioned
hardness results stem from this connection. The Edge Disjoint Paths problem
has been studied broadly in its own right (see e.g. the surveys by Frank [17]
and Vygen [35]), including a large literature on approximation algorithms.
See, amongst others [24, 34] for further hardness and inapproximability
results. On undirected graphs, Edge Disjoint Paths is fixed-parameter
tractable parameterised by the number of source-sink pairs [32, 28].

Investigation of the parameterised complexity of Edge Disjoint Paths has
recently been continued by considering structural parameterisations.
Unfortunately, the problem is NP-hard for graphs of treewidth $2$ [30] and
even for graphs with a vertex cover of size $3$ [15]. It is also W[1]-hard
parameterised by the size of a vertex set whose removal leaves an independent
set of vertices of degree $2$ [21]. From an algorithmic perspective, Ganian
and Ordyniak [21] showed that Edge Disjoint Paths is in XP parameterised by
tree-cut width. Zhou et al. [38] give two XP algorithms for Edge Disjoint
Paths for graphs of bounded treewidth: one for when the number of paths is
small, and one for when a specific condition holds on the pairs of terminals.
Ganian et al. [22] give an FPT algorithm parameterised by the treewidth and
degree of the graph. Friedrich et al. [19, 20] give approximation algorithms
for multicommodity flow on graphs of bounded treewidth.

These results naturally motivate the question:

> What can we say about the parameterised complexity of the general Integer
> Multicommodity Flow problem under structural parameterisations?

We are unaware of any explicit studies in this direction. We do note that the
result of Zhou et al. [38] implies an XP algorithm on graphs of bounded
treewidth for a bounded number of commodities if the capacities are given in
unary. We are particularly interested in whether this result can be improved
to an FPT algorithm, which is hitherto unknown.

###  1.1 Our Setting and Contributions

We consider the Integer Multicommodity Flow problem for a small, fixed number
of commodities. In particular, Integer $\ell$-Commodity Flow is the variant in
which there are $\ell$ commodities. Furthermore, we study the setting where
some well-known structural parameter of the input graph, particularly its
pathwidth or treewidth, is small.

Parameter | unary capacities | binary capacities
---|---|---
pathwidth | XNLP-complete | para-NP-complete
treewidth | XALP-complete | para-NP-complete
weighted tree partition width | FPT (1) | FPT (1)
vertex cover | (2); in XP | (2); open
Table 1: Overview of our results for Integer $2$-Commodity Flow. para-NP-
complete = NP-complete for fixed value of parameter. (1) = capacities of arcs
inside bags can be arbitrary, capacities of arcs between bags are bounded by
weighted tree partition width. (2) Approximation, see Theorem 1.11;
conjectured in FPT. For the undirected case, the same results hold, except
that for the para-NP-completeness for the parameters pathwidth and treewidth,
we need a third commodity.

Our main contribution is to show that Integer $2$-Commodity Flow is unlikely
to be fixed-parameter tractable parameterised by treewidth and or by
pathwidth. Instead of being satisfied with just a W[$t$]-hardness result for
some $t$ or any $t$, we seek stronger results using the recently defined
complexity classes XNLP and XALP. An overview of our results can be found in
Table 1.

XNLP is the class of parameterised problems that can be solved on a non-
deterministic Turing machine in $f(k)|x|^{O(1)}$ time and $f(k)\log|x|$ memory
for a computable function $f$, where $|x|$ is the size of the input $x$. The
class XNLP (under a different name) was first introduced by Elberfeld et al.
[11]. Bodlaender et al. [2, 5, 7] showed a number of problems to be XNLP-
complete with pathwidth as parameter. In particular, [2] gives XNLP-
completeness proofs for several flow problems with pathwidth as parameter.

In this work, we prove XNLP-completeness (and stronger) results for Integer
$\ell$-Commodity Flow. These give a broad new insight into the complexity
landscape of Integer Multicommodity Flow. We distinguish how the capacities of
arcs and edges are specified: these can be given in either unary or binary.
First, we consider the unary case:

######  Theorem 1.1.

Integer $2$-Commodity Flow with capacities given in unary, parameterised by
pathwidth, is XNLP-complete.

######  Theorem 1.2.

Undirected Integer $2$-Commodity Flow with capacities given in unary,
parameterised by pathwidth, is XNLP-complete.

These hardness results follow by reduction from the XNLP-complete Chained
Multicoloured Clique problem [6], a variant of the perhaps more familiar
Multicoloured Clique problem [14]. We follow a common strategy in such
reductions, using vertex selection and edge verification gadgets. However, a
major hurdle is to use flows to select vertices and verify the existence of
edges to form the sought-after cliques. To pass this hurdle, we construct
gadgets that use Sidon sets as flow values, combined with gadgets to check
that a flow value indeed belongs to such a Sidon set.

For the parameter treewidth, we are able to show a slightly stronger result.
Recently, Bodlaender et al. [6] introduced the complexity class XALP, which is
the class of parameterised problems that can be solved on a non-deterministic
Turing machine that has access to an additional stack, in $f(k)|x|^{O(1)}$
time and $f(k)\log|x|$ space (excluding the space used by the stack), for a
computable function $f$, where $|x|$ again denotes the size of the input $x$.
Many problems that are XNLP-complete with pathwidth as parameter are XALP-
complete with treewidth as parameter. We show that this phenomenon also holds
for the studied Integer Multicommodity Flow problem:

######  Theorem 1.3.

Integer $2$-Commodity Flow with capacities given in unary, parameterised by
treewidth, is XALP-complete.

The reduction is from the XALP-complete Tree-Chained Multicoloured Clique
problem [7] and follows similar ideas as the above reduction. Combining
techniques of the proofs of Theorems 1.2 and 1.3 gives the following result.

######  Theorem 1.4.

Undirected Integer $2$-Commodity Flow with capacities given in unary,
parameterised by treewidth, is XALP-complete.

Assuming the _Slice-wise Polynomial Space Conjecture_ [31, 5], these results
show that XP-algorithms for Integer $2$-Commodity Flow or Undirected Integer
$2$-Commodity Flow for graphs of small pathwidth or treewidth cannot use only
$f(k)|x|^{O(1)}$ memory. Moreover, the XNLP- and XALP-hardness implies these
problems are $W[t]$-hard for all positive integers $t$.

If the capacities are given in binary, then the problems become even harder.

######  Theorem 1.5.

Integer $2$-Commodity Flow with capacities given in binary is NP-complete for
graphs of pathwidth at most $13$.

######  Theorem 1.6.

Undirected Integer $3$-Commodity Flow with capacities given in binary is NP-
complete for graphs of pathwidth at most $18$.

Finally, we consider a variant of the Integer Multicommodity Flow problem
where the flow must be _monochrome_ , i.e. a flow is only valid when no edge
carries more than one type of commodity. Then, we obtain hardness even for
parameterisation by the vertex cover number of the graph, for both variants of
the problem.

######  Theorem 1.7.

Integer $2$-Commodity Flow with Monochrome Edges is NP-hard for binary weights
and vertex cover number $6$, and W[1]-hard for unary weights when
parameterised by the vertex cover number.

######  Theorem 1.8.

Undirected Integer $2$-Commodity Flow with Monochrome Edges is NP-hard for
binary weights and vertex cover number $6$, and W[1]-hard for unary weights
when parameterised by the vertex cover number.

To complement our hardness results, we prove two algorithmic results.
Bodlaender et al. [2] had given FPT algorithms for several flow problems,
using the recently defined notion of weighted tree partition width as
parameter (see [3, 2]). Weighted tree partition width can be seen as a variant
of the notion of _tree partition width_ for edge-weighted graphs, introduced
by Seese [33] in 1985 under the name _strong treewidth_. See Section 2 for
formal definitions of these parameters. We note that the known hardness for
the vertex cover number [15] implies that Edge Disjoint Paths is NP-hard even
for graphs of tree partition width $3$. Here, we prove the following:

######  Theorem 1.9.

The Integer $\ell$-Commodity Flow problem can be solved in time
$2^{2^{\operatorname{b}^{3\ell b}}}n^{O(1)}$, where $\operatorname{b}$ is the
breadth of a given tree partition of the input graph.

######  Theorem 1.10.

The Undirected Integer $\ell$-Commodity Flow problem can be solved in time
$2^{2^{\operatorname{b}^{3\ell b}}}n^{O(1)}$, where $\operatorname{b}$ is the
breadth of a given tree partition of the input graph.

For the standard Integer $2$-Commodity Flow problem with the vertex cover
number of the input graph as parameter, we conjecture that this problem is in
FPT. As a partial result, we can give the following approximation algorithms.
Let $\operatorname{vc}(G)$ denote the vertex cover number of a graph $G$.

######  Theorem 1.11.

There is a polynomial-time algorithm that, given an instance of Integer
$2$-Commodity Flow on a graph $G$ with demands $d_{1},d_{2}$, either outputs
that there is no flow that meets the demands or outputs a $2$-commodity flow
of value at least $d_{i}-O(\operatorname{vc}(G)^{3})$ for each commodity
$i\in[2]$.

######  Theorem 1.12.

There is a polynomial-time algorithm that, given an instance of Undirected
Integer $2$-Commodity Flow on a graph $G$ with demands $d_{1},d_{2}$, either
outputs that there is no flow that meets the demands or outputs a
$2$-commodity flow of value at least $d_{i}-O(\operatorname{vc}(G)^{3})$ for
commodity $i\in[2]$.

##  2 Preliminaries

In this paper, we consider both directed and undirected graphs. Graphs are
directed unless explicitly stated otherwise. Arcs and edges are denoted as
$vw$ (an arc from $v$ to $w$, or an edge with $v$ and $w$ as endpoints).

###  2.1 Integers

We use the interval notation for intervals of integers, e.g.,
$[-1,3]=\\{-1,0,1,2,3\\}$. We will simplify this notation for intervals that
start at $1$, i.e. $[k]=[1,k]$. Moreover, we use $\mathbb{N}=\\{1,2,\ldots\\}$
and $\mathbb{N}_{0}=\\{0,1,2,\ldots\\}$.

A _Sidon set_ is a set of positive integers $\\{a_{1},a_{2},\ldots,a_{n}\\}$
such that all pairs have a different sum, i.e., when
$a_{i}+a_{i^{\prime}}=a_{j}+a_{j^{\prime}}$ then
$\\{i,i^{\prime}\\}=\\{j,j^{\prime}\\}$. Sidon sets are also Golomb rulers and
vice versa — in a Golomb ruler, pairs of different elements have unequal
differences: if $i\neq i^{\prime}$ and $j\neq j^{\prime}$, then
$|a_{i}-a_{i^{\prime}}|=|a_{j}-a_{j^{\prime}}|$, then
$\\{i,i^{\prime}\\}=\\{j,j^{\prime}\\}$. A construction by Erdös and Turán
[12] for Sidon sets implies the following, cf. the discussion in [8].

######  Theorem 2.1.

A Sidon set of $n$ elements in $[4n^{2}]$ can be found in $O(n\sqrt{n})$ time
and logarithmic space.

###  2.2 Multicommodity Flow Problems

We now formally define our flow problems. A _flow network_ is a pair $(G,c)$
of a directed (undirected) graph $G=(V,E)$ and a function
$c:E\rightarrow\mathbb{N}_{0}$ that assigns to each arc (edge) a non-negative
integer _capacity_. We generally use $n=|V|$ and $m=|E|$.

For a positive integer $\ell$, an _$\ell$ -commodity flow_ in a flow network
with sources $s_{1},\ldots,s_{\ell}\in V$ and sinks $t_{1},\ldots,t_{\ell}\in
V$ is a $\ell$-tuple of functions
$f^{1},\ldots,f^{\ell}:E\rightarrow\mathbb{R}_{\geq 0}$, that fulfils the
following conditions:

  * •

Flow conservation. For all $i\in[\ell]$, $v\not\in\\{s_{i},t_{i}\\}$,
$\sum_{wv\in E}f^{i}(wv)=\sum_{vw\in E}f^{i}(vw)$.

  * •

Capacity. For all $vw\in E,\sum_{i\in[\ell]}f^{i}(vw)\leq c(vw)$.

An $\ell$-commodity flow is an _integer $\ell$-commodity flow_ if for all
$i\in[c]$, $vw\in E$, $f^{i}(vw)\in\mathbb{N}_{0}$. The _value for commodity
$i$_ of an $\ell$-commodity flow equals $\sum_{s_{i}w\in
E}f^{i}(s_{i}w)-\sum_{ws_{i}\in E}f^{i}(ws_{i})$. We shorten this to ‘flow’
when it is clear from context what the value of $\ell$ is and whether we are
referring to an integer or non-integer flow.

The main problem considered in the paper now is as follows:

Integer $\ell$-Commodity Flow Input: A flow network $G=(V,E)$ with capacities
$c$, sources $s_{1},\ldots,s_{\ell}\in V$, sinks $t_{1},\ldots,t_{\ell}\in V$,
and demands $d_{1},\ldots,d_{\ell}\in\mathbb{N}$. Question: Does there exist
an integer $\ell$-commodity flow in $G$ which has value $d_{i}$ for each
commodity $i\in[\ell]$?

The Integer Multicommodity Flow problem is the union of all Integer
$\ell$-Commodity Flow problems for all non-negative integers $\ell$.

For undirected graphs, flow still has direction, but the capacity constraint
changes to:

  * •

Capacity. For all $vw\in E,\sum_{i\in[\ell]}f^{i}(vw)+f^{i}(wv)\leq c(vw)$.

The undirected version of the Integer $\ell$-Commodity Flow problem then is as
follows:

Undirected Integer $\ell$-Commodity Flow Input: An _undirected_ flow network
$G=(V,E)$ with capacities $c$, sources $s_{1},\ldots,s_{\ell}\in V$, sinks
$t_{1},\ldots,t_{\ell}\in V$, and demands
$d_{1},\ldots,d_{\ell}\in\mathbb{N}$. Question: Does there exist an integer
$\ell$-commodity flow in $G$ which has value $d_{i}$ for each commodity
$i\in[\ell]$?

Finally, we say that an $\ell$-commodity flow $f^{1},\ldots,f^{\ell}$ is
_monochrome_ if no arc (edge) has positive flow of more than one commodity.
That is, if $f^{i}(e)>0$ for some arc (or edge) $e$, then
$f^{i^{\prime}}(e)=0$ for all $i^{\prime}\in[\ell]\setminus\\{i\\}$. We can
then immediately define monochrome versions of Integer $\ell$-Commodity Flow
and Undirected Integer $\ell$-Commodity Flow in the expected way.

###  2.3 Parameters

We now define the various parameters and graph decompositions that we use in
our paper. A _tree decomposition_ of a graph $G=(V,E)$ is a pair
$(\\{X_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ i\in I\\},T)$, with
$\\{X_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ i\in I\\}$ a family of
subsets (called _bags_) of $V$, and $T=(I,F)$ a tree, such that:
$\bigcup_{i\in I}X_{i}=V$; for all $vw\in E$, there is a bag $X_{i}$ with
$v,w\in X_{i}$; and for all $v\in V$, the nodes $i$ with $v\in X_{i}$ form a
(connected) subtree of $T$. The _width_ of a tree decomposition
$(\\{X_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ i\in I\\},T)$ equals
$\max_{i\in I}|X_{i}|-1$, and the _treewidth_ $\operatorname{tw}(G)$ of $G$ is
the minimum width of a tree decomposition of $G$.

A tree decomposition $(\\{X_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ i\in
I\\},T)$ is a _path decomposition_ , if $T$ is a path, and the _pathwidth_
$\operatorname{pw}(G)$ of a graph $G$ is the minimum width of a path
decomposition of $G$.

A _tree partition_ of a graph $G=(V,E)$ is a pair
$(\\{B_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ i\in I\\},T)$, with
$\\{B_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ i\in I\\}$ a family of
subsets (called _bags_) of $V$, and $T=(I,F)$ a tree, such that

  1. 1.

For each vertex $v\in V$, there is exactly one $i\in I$ with $v\in B_{i}$.
(I.e., $\\{B_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ i\in I\\}$ forms a
partition of $V$, except that we allow that some bags are empty.)

  2. 2.

For each edge $vw\in E$, if $v\in B_{i}$ and $w\in B_{i^{\prime}}$ then
$i=i^{\prime}$ or $ii^{\prime}\in F$.

The _width_ of a tree partition $(\\{B_{i}\leavevmode\nobreak\
|\leavevmode\nobreak\ i\in I\\},T)$ equals $\max_{i\in I}|B_{i}|$, and the
_tree partition width_ of a graph $G$ is the minimum width of a tree partition
of $G$.

The notion of weighted tree partition width is defined for edge-weighted
graphs and originates in the work of Bodleander et al. [2] (see also [3]). Let
$G=(V,E)$ be a graph and suppose $c:E\rightarrow\mathbb{N}$ is an edge-weight
function. The _breadth_ 111This notion of breadth should not be confused with
the breadth of a tree decomposition and the related notion of treebreadth
[10]. The breadth of a tree decomposition is defined as the maximum radius of
any bag of a tree decomposition. of a tree partition
$(\\{B_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ i\in I\\},T)$ of $G$
equals the maximum of $\max_{i\in I}|B_{i}|$ and $\max_{ii^{\prime}\in
F}c(B_{i},B_{i^{\prime}})$ with $c(B_{i},B_{i^{\prime}})=\sum_{e=vw,v\in
B_{i},w\in B_{i^{\prime}}}c(e)$, i.e., the maximum sum of edge weights of
edges between the bags of $T$. Then the _weighted tree partition width_
$\operatorname{wtpw}(G)$ of $G$ is the minimum breadth of any tree partition
of $G$. For our application, we interpret the capacity function as the weight
function for weighted tree partition width.

Finally, a _vertex cover_ of a graph $G$ is a set $X\subseteq V(G)$ such that
$X\cap\\{u,v\\}\not=\emptyset$ for every edge $uv\in V(G)$. Then the _vertex
cover number_ $\operatorname{vc}(G)$ of $G$ is the size of the smallest vertex
cover of $G$.

We also use these parameters for directed graphs. In that case, the direction
of edges is ignored, i.e., the treewidth, pathwidth, tree partition width, or
vertex cover number of a directed graph equals that parameter for the
underlying undirected graph.

###  2.4 XNLP and XALP

The class XNLP is the class of parameterised problems that can be solved on a
non-deterministic Turing machine in $f(k)|x|^{O(1)}$ time and $f(k)\log|x|$
memory for a computable function $f$, where $|x|$ is the size of the input
$x$. The class XALP is the class of parameterised problems that can be solved
on a non-deterministic Turing machine that has access to an additional stack,
in $f(k)|x|^{O(1)}$ time and $f(k)\log|x|$ space (excluding the space used by
the stack) for a computable function $f$, where $|x|$ is the size of the input
$x$.

A parameterized logspace reduction or pl-reduction from a parameterized
problem $A\subseteq\Sigma^{\ast}\times\mathbb{N}$ to a parameterized problem
$B\subseteq\Sigma^{\ast}\times\mathbb{N}$ is a function
$f:\Sigma^{\ast}\times\mathbb{N}\rightarrow\Sigma^{\ast}\times\mathbb{N}$,
such that

  * •

there is an algorithm that computes $f((x,k))$ in space $O(g(k)+\log n)$, with
$g$ a computable function and $n=|x|$ the number of bits to denote $x$;

  * •

for all $(x,k)\in\Sigma_{1}^{\ast}\times\mathbb{N}$, $(x,k)\in A$ if and only
if $f((x,k))\in B$.

  * •

there is a computable function $g$, such that for all
$(x,k)\in\Sigma_{1}^{\ast}\times\mathbb{N}$, if
$f(x,k)=(x^{\prime},k^{\prime})$, then $k^{\prime}\leq g(k)$.

XNLP-hardness and XALP-hardness are defined with respect to pl-reductions. The
main difference with the more standard parameterized reductions is that the
computation of the reduction must be done with logarithmic space. In most
cases, existing parameterized reductions are also pl-reductions; logarithmic
space is achieved by not storing intermediate results but recomputing these
when needed.

Hardness for XNLP (and XALP) has a number of consequences. One is the
following conjecture due to Pilipczuk and Wrochna [31] that states that XP-
algorithms for XNLP-hard problems are likely to use much memory.

######  Conjecture 2.2 (Slice-wise Polynomial Space Conjecture [31]).

If parameterized problem $A$ is XNLP-hard, then there is no algorithm that
solves $A$ in $|x^{\prime}|^{f(k)}$ time and $f(k)|x|^{O(1)}$ space, for
instances $(x,k)$, with $f$ a computable function, and $|x|$ the size of
instance $x$.

One can easily observe from the definitions that for all $t\in\mathbb{N}$,
$W[t]\subseteq$ XNLP. Thus, we have the following lemma.

######  Lemma 2.3.

If problem $A$ is XNLP-hard, that $A$ is hard for all classes $W[t]$,
$t\in\mathbb{N}$.

Our hardness proofs start from two variations of the well-known Multicoloured
Clique problem (see [14]).

Chained Multicoloured Clique Input: A graph $G=(V,E)$, a partition of $V$ into
$V_{1},\ldots,V_{r}$, such that $|i-j|\leq 1$ for each edge $uv\in E(G)$ with
$u\in V_{i}$ and $v\in V_{j}$, and a function $c\colon V\to[k]$. Parameter:
$k$. Question: Is there a set of vertices $W\subseteq V$ such that for all
$i\in[r-1]$, $W\cap(V_{i}\cup V_{i+1})$ is a clique, and for each $i\in[r]$
and $j\in[k]$, there is a vertex $v\in W\cap V_{i}$ with $c(v)=j$?

Tree-Chained Multicoloured Clique Input: A graph $G=(V,E)$, a tree partition
$(\\{V_{i}\mid i\in I\\},T=(I,F))$ with $T$ a tree of maximum degree $3$, and
a function $c\colon V\to[k]$. Parameter: $k$. Question: Is there a set of
vertices $W\subseteq V$ such that for all $ii^{\prime}\in F$, $W\cap(V_{i}\cup
V_{i^{\prime}})$ is a clique, and for each $i\in I$ and $j\in[k]$, there is a
vertex $v\in W\cap V_{i}$ with $c(v)=j$?

######  Theorem 2.4 (From [6] and [7]).

Chained Multicoloured Clique is XNLP-complete, and Tree-Chained Multicoloured
Clique is XALP-complete.

##  3 Hardness results

In this section, we give the proofs of our hardness results. The section is
partitioned into three parts. We start by giving the results for the case of
unary capacities, parameterised by pathwidth and parameterised by treewidth,
both for the directed and undirected cases. This is followed by our results
for binary capacities in these settings. Finally, we give the results for
graphs of bounded vertex cover, for both the unary and binary case.

###  3.1 Unary Capacities

We prove our hardness results for Integer Multicommodity Flow with unary
capacities, parameterised by pathwidth and parameterised by treewidth. We aim
to reduce from Chained Multicoloured Clique (for the parameter pathwidth) and
Tree-Chained Multicoloured Clique (for the parameter treewidth). We first
introduce a number of gadgets: subgraphs that fulfil certain properties and
that are used in the hardness constructions. After that, we give the hardness
results for directed graphs, followed by reductions from the directed case to
the undirected case.

Before we start describing the gadgets, it is good to know that all
constructions will have disjoint sources and sinks for the different
commodities. We will set the demands for each commodity equal to the total
capacity of the outgoing arcs from the sources, which is equal to the total
capacity of the incoming arcs to the sinks. Thus, the flow over such arcs will
be equal to their capacity.

Furthermore, throughout this section, our constructions will have two
commodities. We name the commodities 1 and 2, with sources $s_{1},s_{2}$ and
sinks $t_{1},t_{2}$, respectively.

####  3.1.1 Gadgets

We define two different types of (directed) gadgets. Given an integer $a$, the
_$a$ -Gate gadget_ either can move $1$ unit of flow from one commodity from
left to right, or at most $a$ units of flow from the other commodity from top
to bottom, but not both. Hence, it models a form of choice. This gadget will
grow in size with $a$, and thus will only be useful if the input values are
given in unary. Given a set $S$ of integers and a large integer $L$ (larger
than any number in $S$), the _$(S,L)$ -Verifier_ is used to check if the flow
over an arc belongs to a number in $S$. The $a$-Gate gadget is used as a sub-
gadget in this construction. In our reduction, later, we will use
appropriately constructed sets $S$ to select vertices or to check for the
existence of edges. Both types of gadget have constant pathwidth, and thus
constant treewidth.

When describing the gadgets and proving that their tree- or pathwidth is
bounded, it is often convenient to think of them as puzzle pieces being placed
in a bigger mold. Formally, a _(puzzle) piece_ is a directed (multi-)graph $H$
given with a set $B^{-}\subseteq V(H)$ of vertices that have in total $a$
incoming arcs without tail (_entry arcs_) and a set $B^{+}\subseteq V(H)$ of
vertices that have in total $b$ outgoing arcs without head (_exit arcs_). The
sets $B^{-}$ and $B^{+}$ are disjoint and we call the vertices of $B^{-}$ and
$B^{+}$ the _boundary vertices_ of $H$. It is a _path piece_ if $H$ has a path
decomposition such that all vertices of $B^{-}$ are (also) in the first bag
and all vertices of $B^{+}$ are (also) in the last bag.

Now let $G$ be any directed graph or piece. We say that the piece
$(H,B^{-},B^{+},a,b)$ is a _valid_ piece for $v\in V(G)$ if the in-degree of
$v$ is $a$ and the out-degree of $v$ is $b$. Then the _placement_ of the valid
piece for $v$ in $G$ replaces $v$ by $H$ such that the original incoming and
outcoming arcs of $v$ are identified with the entry and exit arcs
(respectively) of $H$ in any way that forms a bijection. This terminology
enables the following convenient lemmas:

######  Lemma 3.1.

Let $G$ be a path piece with boundary vertices $B^{-},B^{+}$. Let $S\subseteq
V(G)$. Suppose that the assumed path decomposition $(\\{X_{i}\mid i\in
I\\},T=(I,F))$ of $G$ has width $w$ and, for every $v\in S$, all in-neighbors
of $v$ also appear in the first bag containing $v$. Moreover, for every $v\in
S$, let $(H_{v},B^{-}_{v},B^{+}_{v},a_{v},b_{v})$ be a valid path piece for
$v$ such that the assumed path decomposition of $H_{v}$ has width $w_{v}$. Let
$G^{\prime}$ be obtained from $G$ by the placement of the pieces of $H_{v}$ in
$G$ for all $v\in S$. Then $G^{\prime}$ is a path piece such that the required
path decomposition has width at most the maximum over all $i\in I$ of:

$|X_{i}\setminus S|+\max_{v\in S\cap
X_{i}}\left\\{w_{v}+1+\sum_{v^{\prime}\in(S\cap
X_{i})\setminus\\{v\\}}\max\\{|B^{-}_{v^{\prime}}|,|B^{+}_{v^{\prime}}|\\}\right\\}-1.$

######  Proof 3.2.

We modify the path decomposition for $G$. We may assume that the path
decomposition is such that for two consecutive bags $X_{i},X_{i^{\prime}}$, it
holds that $|X_{i}\triangle X_{i^{\prime}}|=1$. For every $v\in S$, let
$X_{v}$ be the first bag containing $v$ (note that $X_{v}$ will be the same
for all $v$ in the first bag of the path decomposition of $G$, but will
otherwise be unique). Then, for each $v\in S$, iteratively, replace $v$ in
$X_{v}$ by $B^{-}_{v}$. Then, create a number of copies of the $i\in I$
corresponding to $X_{v}$, where the number of copies is equal to the number of
nodes of the assumed path decomposition of $H_{v}$. To each of these new bags,
add the vertices in the bags of the assumed path decomposition of $H_{v}$ in
the natural order. We need special care again for the first bag of the path
decomposition: here we expand the decomposition for one vertex after the
other. Finally, we add $B^{+}_{v}$ to all further bags containing $v$. The
claimed bound immediately follows from this construction.

We consider the following strengthening of Lemma 3.1.

######  Lemma 3.3.

Let $G$ be a path piece with boundary vertices $B^{-}$ and $B^{+}$. Let
$S\subseteq V(G)$. Suppose that $G$ has a path decomposition $(\\{X_{i}\mid
i\in I\\},T=(I,F))$ of width $w$, the first bag contains at most one vertex
from $S$, no bag contains more than two vertices from $S$, and, for every
$v\in S$, every in-neighbor $u$ of $v$ is contained in the first bag
containing $v$ and if $u\in S$, not in any subsequent bags. Moreover, for
every $v\in S$, let $(H_{v},B^{-}_{v},B^{+}_{v},a_{v},b_{v})$ be a valid path
piece for $v$ such that the assumed path decomposition of $H_{v}$ has width
$w_{v}$. Let $G^{\prime}$ be obtained from $G$ by the placement of the pieces
of $H_{v}$ in $G$ for all $v\in S$. Then $G^{\prime}$ is a path piece such
that the required path decomposition has width at most the maximum over all
$i\in I$ of:

$|X_{i}\setminus S|+\max\left\\{\max_{v\in S\cap
X_{i}}\left\\{w_{v}+1\right\\},\sum_{v\in S\cap
X_{i}}\max\\{|B^{-}_{v^{\prime}}|,|B^{+}_{v^{\prime}}|\\}\right\\}-1.$

######  Proof 3.4.

We modify the path decomposition for $G$. We may assume that the path
decomposition is such that for two consecutive bags $X_{i},X_{i^{\prime}}$, it
holds that $|X_{i^{\prime}}\setminus X_{i}|\leq 1$. For every $v\in S$, let
$X_{v}$ be the first bag containing $v$ (note that $X_{v}$ is unique by the
previous assumption and the assumption that the first bag contains at most one
vertex from $S$). Treat the bags of the path decomposition in the path order
on $T$. Consider the vertex $v\in S$ for which $X_{v}$ comes first in this
order. Replace $v$ by $B^{-}_{v}$ in this bag. Then, create a number of copies
of this bag equal to the number of bags of the assumed path decomposition of
$H_{v}$, and insert these bags (joined with the vertices of
$X_{v}\setminus\\{v\\}$) into the path decomposition after $X_{v}$. At the
end, we have a bag containing $(X_{v}\setminus\\{v\\})\cup B^{+}_{v}$, because
$(H_{v},B^{+}_{v},B^{-}_{v},a_{v},b_{v})$ is a path piece. We now continue
along the path order of $T$ and replace $v$ by $B^{+}_{v}$ in every bag we
encounter, until the first bag we encounter containing a vertex $v^{\prime}\in
S\setminus\\{v\\}$. In this bag, we still replace $v$ by $B^{+}_{v}$, then
replace $v^{\prime}$ by $B^{-}_{v^{\prime}}$ and create a new subsequent bag
where we remove $B^{+}_{v}$. This yields a bag containing
$(X_{v^{\prime}}\setminus\\{v,v^{\prime}\\})\cup B^{-}_{v}$. Since $v$ will
not appear in any further bags by the assumptions of the lemma, this is safe.
Then, we continue with the same treatment for $v^{\prime}$ as we did before
with $v$, etc., all thew way until we reach the end of $T$. The claimed bound
immediately follows from this construction.

We can prove a similar lemma with respect to tree decompositions. A piece
$(H,B^{-},B^{+},a,b)$ is a _tree piece_ if $H$ has a tree decomposition that
has a bag containing $B^{-}\cup B^{+}$.

######  Remark 3.5.

Any path piece $(H,B^{-},B^{+},a,b)$ with an assumed path decomposition of
width $w$ is also a tree piece with a tree decomposition of width at most
$w+|B^{+}|$ by adding $B^{+}$ to every bag.

######  Lemma 3.6.

Let $G$ be a tree piece with boundary vertices $B^{-},B^{+}$ such that the
assumed tree decomposition $(\\{X_{i}\mid i\in I\\},T=(I,F))$ has width $w$.
Let $S\subseteq V(G)$. For every $v\in S$, let
$(H_{v},B^{-}_{v},B^{+}_{v},a_{v},b_{v})$ be a valid path piece for $v$ such
that the assumed tree decomposition of $H_{v}$ has width $w_{v}$. Let
$G^{\prime}$ be obtained from $G$ by the placement of the pieces of $H_{v}$ in
$G$ for all $v\in S$. Then $G^{\prime}$ is a tree piece such that the required
tree decomposition has width at most:

$\max\left\\{\max_{v\in S}\\{w_{v}\\},\max_{i\in I}\left\\{|X_{i}\setminus
S|+\max_{v\in S\cap X_{i}}\\{|B^{-}_{v^{\prime}}\cup
B^{+}_{v^{\prime}}|\\}\right\\}-1\right\\}.$

######  Proof 3.7.

We modify the tree decomposition for $G$. For each $v\in S$, replace $v$ in
all bags containing $v$ by $B^{-}_{v}\cup B^{+}_{v}$. For each $v\in S$, add
the assumed tree decomposition of $H_{v}$ to $T$ by adding an edge between any
node of this tree decomposition and any node $i\in I$ for which $v$ used to be
in $X_{i}$. The claimed bound immediately follows from this construction.

######  Remark 3.8.

The same lemmas hold (with simple modifications) in the case of directed or
undirected graphs instead of (directed) path/tree pieces.

We now describe both gadgets in detail.

#####  $a$-Gate Gadget

Let $a$ be a positive integer. The _$a$ -Gate gadget_ gadget will allow $a$
units of flow of commodity 2 through one direction, unless $1$ unit of flow of
commodity 1 flows through the other direction.

Figure 1: The $a$-Gate gadget. Left: the schematic representation of the
gadget, with its entry and exit arcs. Right: the full construction for $a=4$,
with arcs labelled by their capacities.

The gadget is constructed as follows. See Figure 1 for its schematic
representation and for an example with $a=4$. We build a directed path $P$
with $2\cdot a$ vertices. We add two additional vertices $v$ and $w$. The
vertex $v$ has arcs towards the first, third, fifth, etc. vertices of the
path, and $w$ has arcs from the second, fourth, sixth, etc. vertices of the
path. All these arcs and the arcs of the path have capacity $1$. We add an
incoming arc of capacity $1$ to the leftmost vertex $x$ of the path and an
incoming arc of capacity $a$ to $v$. We call these the _entry arcs_ of the
gadget. We add an outgoing arc of capacity $1$ at the rightmost vertex $y$ of
the path and an outgoing arc with capacity $a$ to $w$. We call these the _exit
arcs_ of the gadget.

We call $v,w,x,y$ the _boundary vertices_ of the gadget. Note that all arcs
incoming to or outgoing from the gadget are incident on boundary vertices.

Observe that this gadget can be constructed in time polynomial in the given
value of $a$ if $a$ is given in unary, as the gadget has size linear in $a$.
We capture the functioning of the gadget in the following lemma.

######  Lemma 3.9.

Consider the $a$-Gate gadget for some integer $a$. Let $f$ be some
$2$-commodity flow such that the entry arc at $x$ and the exit arc at $y$ only
carry flow of commodity $1$ and such that the entry arc at $v$ and the exit
arc at $w$ only carry flow of commodity $2$. Then:

  * •

If $v$ receives $a$ units of commodity $2$, then $x$ receives no flow of
commodity $1$.

  * •

If $x$ receives $1$ unit of commodity $1$, then $v$ receives no flow of
commodity $2$.

######  Proof 3.10.

Suppose that $v$ receives $a$ units of commodity $2$. Then, every arc leaving
$v$ is used to capacity by commodity $2$. Since the exit arc at $y$ can only
have flow of commodity $1$, the flow of commodity $2$ can only exit the gadget
at $w$. This means that the arc leaving $x$ is used to capacity by commodity
$2$. As such, $x$ cannot receive any flow of commodity $1$.

Suppose that $x$ receives $1$ unit of commodity $1$. Since $w$ can only
receive flow of commodity $2$, the flow of commodity $1$ can only exit the
gadget at $y$. This means that all the arcs in the path $P$ are used to
capacity by commodity $1$. As such, $w$ cannot receive any flow of commodity
$2$.

######  Lemma 3.11.

For any integer $a$, the $a$-Gate gadget is a path piece such that the
required path decomposition has width $3$.

######  Proof 3.12.

The gadget is a piece by construction, with $B^{-}=\\{v,x\\}$,
$B^{+}=\\{w,y\\}$, and $a=b=2$. To construct the path decomposition, begin
with a path decomposition where the endpoints of each edge on the path from
$x$ to $y$ are in a consecutive bags together. Add $v,w$ to every bag. This is
a valid path decomposition of width $3$.

##### Verifier Gadget

Let $L$ be a (typically large) integer. Let $S\subseteq[L-1]$ be a set of
integers, where $S=\\{a_{1},\ldots,a_{|S|}\\}$. An _$(S,L)$ -Verifier_ gadget
is used to verify that the amount of flow through an edge is in $S$.

Figure 2: The $(S,L)$-Verifier gadget. Left: a schematic representation of the
gadget, with its entry and exit arcs. The value on the bottom-right of the
schematic representation denotes the sum of the incoming flows to the gadget.
Right: the graph that realises the gadget for $S=\\{a_{1},a_{2},a_{3}\\}$,
with arcs labelled by their capacities (the unlabelled arcs have capacities
$a_{2}$ and $L-a_{2}$ respectively; their labels are omitted for clarity).

The gadget is constructed as follows. See Figure 2 its schematic
representation and for an example with $S=\\{a_{1},a_{2},a_{3}\\}$. We add six
vertices $u$, $v$, $w$, $x$, $y$, $z$; these are the _boundary vertices_ of
this gadget. We add arcs $s_{1}u$ and $zt_{1}$ of capacity $r-1$. Then, $v$
and $w$ have incoming arcs of capacity $L-1$ (the _entry arcs_ of this gadget)
and $x$ and $y$ have outgoing arcs of capacity $L-1$ (the _exit arcs_ of this
gadget). Finally, we have $r$ rows of two Gate gadgets each. The $i$th row has
two $a_{i}$-Gate gadgets with the following arcs:

  * •

an arc of capacity $1$ from $u$ to the first Gate gadget,

  * •

an arc of capacity $a_{i}$ from $v$ to the first Gate gadget,

  * •

an arc of capacity $a_{i}$ from the first Gate gadget to $x$,

  * •

an arc of capacity $1$ from the first to the second Gate gadget,

  * •

an arc of capacity $L-a_{i}$ from $w$ to the second Gate gadget,

  * •

an arc of capacity $L-a_{i}$ from the second Gate gadget to $y$,

  * •

an arc of capacity $1$ from the second Gate gadget to $z$.

Observe that this gadget can be constructed in time polynomial in the values
of $a_{1},\ldots,a_{|S|}$ if they are given in unary, as the Gate gadgets have
size linear in the given value. We capture the functioning of the gadget in
the following lemma.

######  Lemma 3.13.

Consider the $(S,L)$-Verifier gadget for some integer $L$ and some
$S\subseteq[L-1]$. Let $f$ be some $2$-commodity flow such that $s_{1}$ sends
${|S|}-1$ units of flow of commodity 1 to $u$, $t_{1}$ receives ${|S|}-1$
units of flow of commodity 1 from $z$. Suppose there is an integer
$\alpha\in[L-1]$ such that $v$ receives $\alpha$ units of flow of commodity 2
over its entry arc, $w$ receives $L-\alpha$ units of flow of commodity 2 over
its entry arc, and neither entry arc receives flow of commodity 1. Then:

  * •

$\alpha\in S$,

  * •

$x$ sends $\alpha$ units of flow of commodity 2 over its exit arc,

  * •

$y$ sends $L-\alpha$ units of flow of commodity 2 over its exit arc.

Conversely, if $\alpha\in S$, then there exists a $2$-commodity flow that
fulfills the conditions of the lemma.

######  Proof 3.14.

Since $u$ receives ${|S|}-1$ units of flow of commodity 1 and has ${|S|}$
outgoing arcs, $u$ sends $1$ unit of flow of commodity 1 over all but one of
its outgoing arcs. Recall that $v$ and $w$ do not receive flow of commodity 1.
If $1$ unit of flow of commodity 1 is sent over say the $i$th outgoing arc of
$u$, in order to arrive at $z$, it must go through the $a_{i}$-Gate gadget and
the corresponding $(L-a_{i})$-Gate gadget. The same amount of flow must also
leave these gadgets and thus by Lemma 3.9, these gadgets cannot transfer flow
of commodity 2. Thus, the flow of commodity 2 that $v$ and $w$ receive must go
through the Gate gadgets of the row where $u$ has not sent any flow to, say
this is row $j$. $x$ and $y$ must send flow through arcs of capacity $a_{j}$
and $L-a_{j}$, respectively. The capacities of the arcs and the gadgets
enforce that $\alpha\leq a_{j}$ and $L-\alpha\leq L-a_{j}$, respectively.
Thus, $\alpha=a_{j}$, and so $\alpha\in S$.

All the flow that the $(L-a_{j})$-Gate gadget receives (which is only of
commodity 2) must be sent to $y$, since $t_{1}$ is a sink. Hence, $y$ sends
$L-\alpha$ flow through its exit arc. The flow that the $a_{j}$-Gate gadget
receives (which is only of commodity 2) must all be sent to $x$: we cannot
send even $1$ unit of flow over the horizontal arc to the second gadget, as
the second gadget would then receive $L-\alpha+1$ units of flow of commodity
2. However, it cannot send flow of commodity 2 to $z$ (as $z$ only has an arc
to $t_{1}$) and can send out at most $L-\alpha$ flow to $y$. Thus, $x$ sends
$\alpha$ units of flow over its exit arc.

For the converse, $u$ sends $1$ unit of flow of commodity 1 through all Gate
gadgets of the values unequal to $\alpha$, and $\alpha$ and $L-\alpha$ flow
through the two other Gate gadgets.

We note that in the later proofs, for a particular choice of $L$, we may also
use Verifier gadgets with capacities $2L-1$, and incoming and outgoing flows
adding up to $2L$ instead of $L$. We will explicitly indicate that, also in
the schematic representation.

######  Lemma 3.15.

For any integer $L$ and any $S\subseteq[L-1]$, the $(S,L)$-Verifier gadget is
a path piece such that the required path decomposition (ignoring $s_{1}$ and
$t_{1}$) has width $9$.

######  Proof 3.16.

The gadget is a piece by construction, with $B^{-}=\\{u,v,w\\}$ and
$B^{+}=\\{x,y,z\\}$. If we treat the Gate gadgets as vertices, then we can
immediately construct a path decomposition of width $7$, by putting $u$, $v$,
$w$, $x$, $y$, $z$ in all bags and adding the two vertices corresponding to
each row of Gate gadgets in successive bags. Since the Gate gadgets are each
path pieces with a decomposition of width $3$ by Lemma 3.11 and each have two
entry and exit arcs, we obtain a path decomposition of the whole Verifier of
width $9$ by Lemma 3.3.

####  3.1.2 Reductions for Directed Graphs

Using the gadgets we just proposed, we show our hardness results for Integer
$2$-Commodity Flow (i.e. the case of directed graphs) with pathwidth and with
treewidth as parameter.

We note that our hardness construction will be built using only Verifier
gadgets as subgadgets. The entry arcs and exit arcs of this gadget are meant
to transport solely flow of commodity 2 per Lemma 3.13. Hence, in the
remainder, it helps to think of only commodity 2 being transported along the
edges, so that we may focus on the exact value of that flow to indicate which
vertex is selected or whether two selected vertices are adjacent. We later
make this more formal when we prove the correctness of the reduction.

See 1.1

######  Proof 3.17.

Membership in XNLP can be seen as follows. Take a path decomposition of $G$,
say with successive bags $(X_{1},\ldots,X_{r})$. One can build a dynamic
programming table, where each entry is indexed by a node $j$ with associated
bag $X_{j}$ and a function $f^{i}_{j}:X_{j}\rightarrow[-C,C]$, where $C$ is
some upper bound on the maximum value of the flow of any commodity (note that
$C$ is linear in the input size), $i=1,2$ and $1\leq j\leq r$. One should
interpret $f^{i}_{j}$ as mapping each vertex $v\in X_{j}$ to the net
difference of flow of commodity $i$ in- or outgoing on that vertex in a
partial solution up to bag $X_{j}$. The content of the table is a Boolean
representing whether there is a partial flow satisfying the requirements that
$f^{i}_{j}$ sets. Basic application of dynamic programming on (nice) path
decompositions can solve the Integer $2$-Commodity Flow problem with this
table. This dynamic programming algorithm can be transformed to a non-
deterministic algorithm by not building entire tables, but instead guessing
one element for each table with positive Boolean. The guessed element of the
table can be represented by $O(\operatorname{pw}(G)\log C)$ bits; in addition,
we need $O(\log n)$ bits to know which bag of the path decomposition we are
handling, and to look up relevant information of the graph. This yields an
non-deterministic algorithm with $O(\operatorname{pw}(G)\log C+\log n)$
memory.

For the hardness, we use a reduction from Chained Multicolour Clique (see
Theorem 2.4). Suppose we have an instance of Chained Multicolour Clique, with
a graph $G=(V,E)$, colouring $c:V\rightarrow[k]$, and partition
$V_{1},\ldots,V_{r}$ of $V$.

Build a Sidon set with $|V|$ numbers by applying the algorithm of Theorem 2.1.
Following the same theorem, the numbers are in $[4|V|^{2}]$. Set
$L=4|V|^{2}+1$ to be a ‘large’ integer. To each vertex $v\in V$, we assign a
unique element of the set $S$, denoted by $S(v)$. For any subset
$V^{\prime}\subseteq V$, let $S(V^{\prime})=\\{S(v)\mid v\in W\\}$. For any
subset $E^{\prime}\subseteq E$, let $S(E^{\prime})=\\{S(u)+S(v)\mid uv\in
E^{\prime}\\}$.

Figure 3: Vertex selector gadget used in the proof Theorem 1.1. The flow sent
through the $(V_{i,\gamma},L)$-Verifier will correspond to selecting a vertex
from the class $V_{i,\gamma}$.

We now describe several (further) gadgets that we use to build the full
construction. Let $V_{i,\gamma}$ be the vertices in $V_{i}$ with colour
$\gamma$. Each set $V_{i,\gamma}$ is called a class. For each class
$V_{i,\gamma}$, we use a _Vertex selector gadget_ to select the vertex from
$V_{i,\gamma}$ that should be in the solution to the Chained Multicoloured
Clique instance. This gadget (see Figure 3) consists of a single
$(V_{i,\gamma},L)$-Verifier gadget, where its entry arcs jointly start in a
single vertex that in turn has a single arc from $s_{2}$ of capacity $L$.
Intuitively, we select some $v\in V_{i,\gamma}$ if and only if the left branch
receives $S(v)$ flow and the right branch receives $L-S(v)$ flow.

Figure 4: Edge check gadget for the combination $V_{i,\gamma}$ and
$V_{i^{\prime},\gamma^{\prime}}$. Left: the schematic representation of the
gadget. The flow corresponding to the $V_{i,\gamma}$ vertex enters on the left
and exits on the right. The flow corresponding to the
$V_{i^{\prime},\gamma^{\prime}}$ vertex enters from the top and exits at the
bottom. Right: the realisation of the gadget. The flow sent through the
$(S(E),2L)$-Verifier must correspond to a unique sum of two incident vertices
from the classes $V_{i,\gamma}$ and $V_{i^{\prime},\gamma^{\prime}}$. The
$(S(V_{i,\gamma}),L)$-Verifiers and
$(S(V_{i^{\prime},\gamma^{\prime}}),L)$-Verifiers ensure the right combination
is checked, and the outgoing flow is the same as the incoming flow. Chaining
Edge check gadgets makes some $(S(V_{i,\gamma}),L)$-Verifiers redundant, but
this does not matter for the argument.

For each pair of incident classes, we construct an _Edge check gadget_. That
is, we have an Edge check gadget for all classes $V_{i,\gamma}$ and
$V_{i^{\prime},\gamma^{\prime}}$ with $|i-i^{\prime}|\leq 1$, and
$\\{i,\gamma\\}\neq\\{i^{\prime},\gamma^{\prime}\\}$. Let
$E^{i^{\prime},\gamma^{\prime}}_{i,\gamma}\subseteq E$ denote the set of edges
between $V_{i,\gamma}$ and $V_{i^{\prime},\gamma^{\prime}}$. An Edge check
gadget will check if two incident classes have vertices selected that are
adjacent. The gadget (see Figure 4) consists of a central $(S(E),2L)$-Verifier
gadget (note that we could also use an
$(S(E^{i^{\prime},\gamma^{\prime}}_{i,\gamma}),2L)$-Verifier gadget instead,
but this is not necessary). Its entry arcs originate from two vertices that
have as incoming arcs the exit arcs of an $(S(V_{i,\gamma}),L)$\- and
$(S(V_{i^{\prime},\gamma^{\prime}}),L)$-Verifier gadget. Its exit arcs head to
two vertices that have as outgoing arcs the entry arcs of a different
$(S(V_{i,\gamma}),L)$\- and $(S(V_{i^{\prime},\gamma^{\prime}}),L)$-Verifier
gadget. The gadget thus has four entry arcs and four exit arcs, corresponding
to the entry arcs of the first two Verifier gadgets and the exit arcs of the
last two Verifier gadgets.

Intuitively, if the entry arcs have flow (of commodity 2) of value $S(v)$,
$L-S(v)$, $S(w)$, and $L-S(w)$ consecutively (refer to Figure 4), then there
is a valid flow if and only if $vw\in
E^{i^{\prime},\gamma^{\prime}}_{i,\gamma}$. Note that the sum $S(v)+S(w)$ is
unique, because $S$ is a Sidon set, and thus so is $2L-(S(v)+S(w))$. Hence,
the only way for the flow to split up again and leave via the exit arcs is to
split into $S(v)$, $S(w)$, $L-S(v)$, and $L-S(w)$; otherwise, it cannot pass
the $(S(V_{i,\gamma}),L)$-Verifier or the
$(S(V_{i^{\prime},\gamma^{\prime}}),L)$-Verifier at the bottom of the Edge
check gadget. Hence, the exit arcs again have flow of values $S(v)$, $L-S(v)$,
$S(w)$, and $L-S(w)$ consecutively, just like the entry arcs.

With these gadgets in hand, we now describe the global structure of the
reduction. Throughout, it will be more helpful to look at the provided figures
than to follow the formal description. For each class $V_{i,\gamma}$, we first
create a Vertex selector gadget (as in Figure 3).

Figure 5: Illustration of the structure of Vertex selector and Edge check
gadgets to enforce that the selected vertices from $V_{1}$ form a clique. In
this example, $k=4$. The $\alpha_{i,\gamma}$’s denote the amount of flow,
having a value of $S(v)$ for some $v\in V_{i,\gamma}$, selected in the
corresponding $(S(V_{i,\gamma}),L)$-Verifiers of the Vertex selector gadgets.

We then create Edge check gadgets to check, for any $i\in[r]$, that the
selected vertices in $V_{i,\gamma}$ for all $\gamma\in[k]$ are adjacent in
$G$. We create $k$ rows of gadgets. Row $\gamma\in[k]$ has $k-\gamma$ Edge
check gadgets, which correspond to checking that the vertices selected in
$V_{i,\gamma}$ and $V_{i,\gamma^{\prime}}$ are indeed adjacent (via edges in
$E^{i,\gamma^{\prime}}_{i,\gamma}$) for each $\gamma^{\prime}\in[\gamma+1,k]$.
The construction is as follows (see Figure 5). For any
$\gamma\in[k],\gamma^{\prime}\in[\gamma+1,k]$, the Edge check gadget for
$E^{i,\gamma^{\prime}}_{i,\gamma}$ has its left entry arcs unified with the
bottom exit arcs of the Edge check gadget for
$E^{i,\gamma^{\prime}-1}_{i,\gamma-1}$ if $\gamma>1$ and
$\gamma^{\prime}=\gamma+1$ and with the exit arcs of the Edge check gadget for
$E^{i,\gamma^{\prime}-1}_{i,\gamma}$ if $\gamma>1$ and
$\gamma^{\prime}>\gamma+1$. The Edge check gadget for
$E^{i,\gamma^{\prime}}_{i,\gamma}$ has its top entry arcs unified with the
bottom exit arcs of the Edge check gadget for
$E^{i,\gamma^{\prime}}_{i,\gamma-1}$ if $\gamma>1$.

We call this the _Triangle gadget_ for $V_{i}$. Note that it has $2k$ entry
arcs and $2k$ exit arcs. The former can be interpreted to be partitioned into
$k$ columns, while the latter can be seen to be partitioned into $k$ rows (see
Figure 5).

Note that chaining Edge check gadgets makes some
$(S(V_{i,\gamma}),L)$-Verifiers redundant, as two such verifiers of the same
type will follow each other. However, for the sake of clarity and as it does
not matter for the overall, we leave such redundancies in place.

Figure 6: Illustration of the structure of the Edge check gadgets to enforce
that the selected vertices from $V_{1}$ and from $V_{2}$ are complete to each
other. In this example, $k=4$. The $\alpha_{i,\gamma}$’s denote the amount of
flow, having a value of $S(v)$ for some $v\in V_{i,\gamma}$, selected in the
corresponding $(S(V_{i,\gamma}),L)$-Verifiers.

Next, we create Edge check gadgets to check, for any $i\in[r-1]$, that the
selected vertices in $V_{i,\gamma}$ and $V_{i+1,\gamma^{\prime}}$ for all
$\gamma,\gamma^{\prime}\in[k]$ are indeed adjacent in $G$. We create a grid
with $k$ rows and $k$ columns of gadgets, where each row corresponds to a
combination of $\gamma$ and $\gamma^{\prime}$. The construction is as follows
(see Figure 6). For each $\gamma,\gamma^{\prime}\in[k]$, the Edge check gadget
for $E^{i+1,\gamma^{\prime}}_{i,\gamma}$ has its left entry arcs identified
with the right exit arcs of the Edge check gadget for
$E^{i+1,\gamma^{\prime}-1}_{i,\gamma}$ if $\gamma^{\prime}>1$ and it has its
top entry arcs identified with the bottom exit arcs of the Edge check gadget
for $E^{i+1,\gamma^{\prime}}_{i,\gamma-1}$ if $\gamma>1$.

We call this the _Square gadget_ for $V_{i}$ and $V_{i+1}$. Note that it has
$4k$ entry arcs and $4k$ exit arcs. The horizontal entry and exit arcs (see
Figure 6) correspond to $V_{i}$, whereas the vertical entry and exit arcs
correspond to $V_{i+1}$.

Then, we connect the Vertex selector and Triangle gadgets. For each $V_{i}$,
we connect the Vertex selector gadget for $V_{i}$ to the Triangle gadget for
$V_{i}$ as follows (see Figure 5). The Edge check gadget for $E^{i,2}_{i,1}$
of the Triangle gadget has its left entry arcs unified with the exit arcs of
the Vertex selector gadget of $V_{i,1}$. For all $\gamma\in[1,k]$, the Edge
check gadget for $E^{i,\gamma}_{i,\gamma-1}$ has its top entry arcs unified
with the exit arcs of the Vertex selector gadget of $V_{i,\gamma}$.

Finally, we connect the Triangle and Square gadgets (see Figure 7). The Square
gadget for $V_{1}$ and $V_{2}$ has its horizontal entry arcs identified with
the exit arcs of the Triangle gadget for $V_{1}$. Then, for the Square gadget
for $V_{i}$ and $V_{i+1}$ for any $i\in[r-1]$, it has its vertical entry arcs
identified with the exit arcs of the Triangle gadget for $V_{i+1}$. Its $2k$
horizontal exit arcs are paired (one pair per colour class) and directed to a
vertex; these $k$ vertices are then each connected by a single arc of capacity
$L$ to $t_{2}$ (cf. Figure 6). Finally, we also do the latter for the vertical
exit arcs of the Square gadget for $V_{r-1}$ and $V_{r}$.

We now set the demand for commodity 1 to the sum of the capacities of the
outgoing arcs of $s_{1}$ (which is equal to the sum of the capacities of the
incoming arcs of $t_{1}$). We set the demand for commodity 2 to the sum of the
capacities of the outgoing arcs of $s_{2}$ (which is equal to the sum of the
capacities of the incoming arcs of $t_{2}$). This completes the construction.
We now prove the bound on the pathwidth, followed by the correctness of the
reduction and a discussion of the time and space needed to produce it. To
prove the pathwidth bound, we note that all constructed gadgets are path
pieces, and thus we can apply Lemma 3.1.

Figure 7: Overview of the complete structure of the reduction for $r=4$.
Triangles represent a structure as in Figure 5, and squares a structure as in
Figure 6. Directions are not drawn, but clear from Figure 5 and 6. The labels
inside each block (say $V_{i}$ or $V_{i},V_{i+1}$) denote that flow
corresponding to vertices of this set (i.e. $V_{i}$ or $V_{i}$ and $V_{i+1}$)
is flowing in a block. Note that all points labelled $s_{2},t_{2}$ are indeed
the same vertex.

######  Claim 1.

The constructed graph has pathwidth at most $8k+O(1)$.

We construct a path decomposition as follows. First, we will ensure that
$s_{1},t_{1},s_{2},t_{2}$ are in every bag. Then, we make the following
observations about the gadgets we construct. Notice that Vertex selector
gadgets and Edge check gadgets have pathwidth $O(1)$, which directly follows
from Lemma 3.1 and the fact that Verifier gadgets have pathwidth $O(1)$, as
proven in Lemma 3.15. Note that Vertex selector gadgets have two exit arcs,
whereas Edge check gadgets have four entry arcs and four exit arcs.

The Triangle gadget is a subgraph of a $k\times k$ grid, while the Square
gadget is a $k\times k$ grid. Note that a standard path decomposition of the
grid has width $k$ and satisfies the conditions of Lemma 3.1. Hence, following
Lemma 3.1 and the above bounds for the Vertex selector and Edge check gadgets,
the pathwidth of the Triangle gadget and the Square gadget is at most
$4k+O(1)$. The Triangle gadget has $2k$ entry arcs and $2k$ exit arcs, whereas
the Square gadget has $4k$ entry arcs and $4k$ exit arcs.

Finally, the full construction (treating Triangle and Square gadgets as
vertices) has a path decomposition of width $2$, as it is a caterpillar (see
Figure 7), with at most two vertices corresponding to Triangle or Square
gadgets per bag. Applying Lemma 3.1, we obtain a bound of $8k+O(1)$. We note
that a slightly stronger bound of $4k+O(1)$ seems possible with a more refined
analysis, but this bound will be sufficient for our purposes.

######  Claim 2.

The given Chained Multicolour Clique instance has a solution if and only if
the constructed instance of Integer $2$-Commodity Flow has a solution.

For the forward direction, assume there exists a chained multicolour clique
$W$ in $G$. We construct a flow. We first consider commodity 2. Recall that
one vertex is picked per $V_{i,\gamma}$ class by definition and thus $W$ has
size $rk$. If $v\in V_{i,\gamma}\cap W$ for some $i\in[r],\gamma\in[k]$, then
in the Vertex selector gadget of $V_{i,\gamma}$, we send $S(v)$ units of flow
of commodity 2 to the left and $L-S(v)$ units of flow to the right into the
Verifier gadget (see Figure 3). In any Verifier gadget, we route the flow so
that it takes the path with capacity equal to the flow (see Lemma 3.13). This
flow is then routed through all Edge check gadgets of the Triangle and Square
gadgets, in the manner presented above in the description of Edge check
gadgets. Since $W$ is a chained multicolour clique, the corresponding edge
exist in $E$ and the flow can indeed pass through the $(S(E),2L)$-Verifier
gadget of each Edge check gadget (again, see Lemma 2). For any $i\in[r-1]$,
after passing through the Square gadget for $V_{i}$ and $V_{i+1}$, the flow
originating in the Vertex selector gadget corresponding to $V_{i}$ is sent to
$t_{2}$ through the horizontal exit arcs of the Square gadget (see Figure 6).
Finally, the flow originating in the Vertex selector gadget corresponding to
$V_{r}$ is sent to $t_{2}$ through the vertical exit arcs of the Square
gadget. Since $W$ has size equal to $rk$ and we send $L$ units of flow through
each Vertex selector gadget, all arcs from $s_{2}$ and to $t_{2}$ are used to
capacity.

Next, we consider commodity 1. All flow of commodity 1 is routed through the
unused gates in the Verifier gadgets, which is possible as we only use one
vertical path per gadget for the flow corresponding to a vertex or edge (see
Figure 2). It follows that we use all arcs from $s_{1}$ and to $t_{1}$ to
capacity.

For the other direction, suppose we have an integer $2$-commodity flow $f$
that meets the demands. Hence, there is a $2$-commodity flow in the
constructed graph with all arcs from $s_{1}$ and $s_{2}$ and to $t_{1}$ and
$t_{2}$ used to capacity, meaning that their total flow is equal to their
total capacity, with flow with the corresponding commodity: commodity 1 for
$s_{1}$ and $t_{1}$, and commodity 2 for $s_{2}$ and $t_{2}$.

We first reason that the flow of commodity 1 behaves as expected in the
Verifier gadgets. Notice that the constructed graph is a directed acyclic
graph. Abstractly, it can also be seen as a directed acyclic graph where the
vertices are Verifier gadgets. Hence, there exists a topological ordering on
the Verifier gadgets. We refer to Figure 2 to recall the naming of the
vertices $u$ and $z$ of a Verifier gadget. We prove by induction on the
topological ordering that the flow of commodity 1 in $f$ that enters over the
arc $s_{1}u$ leaves over the arc $zt_{1}$, while staying in the gadget for the
entirety of its flow path. As the base case, consider the last Verifier gadget
$H$ in the ordering. The bottom of this gadget (refer to Figure 2) has arcs
only going to $t_{2}$, by construction and the fact that it is the last
Verifier gadget in the ordering. Hence, flow from $u\in H$ must all go to
$z\in H$ and the flow on the arcs $s_{1}u$ and $zt_{1}$ fully fills the
capacities. Then, indeed, flow of commodity 1 behaves as in the precondition
of Lemma 3.13, and this flow does not leave the gadget downwards. For the
induction step, consider some Verifier gadget $H$ in the ordering. By the
induction hypothesis, all Verifier gadgets later in the ordering have the arcs
to $t_{1}$ fully filled. But then the flow of commodity 1 in $H$ can only go
to $z\in H$ to go to $t_{1}$. We get that the flow on the arcs $s_{1}u$ and
$zt_{1}$ in $H$ fully fills the capacities, and does not leave the gadget
downwards. Hence, flow of commodity 1 behaves as in the precondition of Lemma
3.13. By induction, all flow of commodity 1 behaves ‘properly’ for Lemma 3.13.

By applying Lemma 3.13 to every Verifier gadget, we get that the amount flow
of commodity 2 always corresponds to some $\alpha\in S$ for the associated set
$S$ of the gadget, and the left and right exit arcs carry $\alpha$ and
$L-\alpha$ units of flow of commodity 2 respectively. Now, the arc from
$s_{2}$ in a Vertex selector gadget for $V_{i,\gamma}$ must have $L$ flow of
commodity 2 and this must be split in $\alpha$ and $L-\alpha$, with $\alpha\in
S(V_{i,\gamma})$. Thus, there is a $v\in V_{i,\gamma}$ with $\alpha=S(v)$,
which corresponds to placing $v$ in the chained multicoloured clique. In any
Edge check gadget, the flow of $\alpha\in S(V_{i,\gamma})$, $L-\alpha$ and
$\beta\in S(V_{i^{\prime},\gamma^{\prime}})$,$L-\beta$ combines to a unique
sum $\alpha+\beta$ and $2L-(\alpha+\beta)$, and assures that the edge between
the corresponding vertices is present. As reasoned before, the flow must split
back up into $\alpha$, $L-\alpha$ and $\beta,L-\beta$ by the unique sum due to
the fact that $S$ is a Sidon set. We get that the chosen vertices indeed form
a chained multicolour clique, as the Edge check gadgets in the Triangle and
Square gadgets enforce that all edges between selected vertices are present as
should be.

Finally, we claim that the constructed graph with its capacities can be built
using $O(f(k)+\log n)$ space, for some computable function $f$. First, Sidon
sets can be built in logarithmic space (cf. Theorem 2.1). Second, we use the
(for log-space reductions standard) technique of not storing intermediate
results, but recomputing parts whenever needed. E.g., each time we need the
$i$th number of the Sidon set, we recompute the set and keep the $i$th number.
Viewing the computation as a recursive program, we have constant recursion
depth, while each level uses $O(f(k)+\log n)$ space, for some computable
function $f$. The result now follows.

To show the XALP-hardness of the Integer $2$-Commodity Flow parameterised by
treewidth, we reduce from Tree-Chained Multicolour Clique in a similar, but
more involved manner.

See 1.3

######  Proof 3.18.

Membership in XALP can be seen as follows. Take a tree decomposition of $G$,
say $(\\{X_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\ i\in I\\},T)$; assume
that $T$ is binary. One can build a dynamic programming table, where each
entry is indexed by a node $j\in I$ with associated bag $X_{j}$ and a function
$f^{i}_{j}:X_{j}\rightarrow[-C,C]$, where $C$ is some upper bound on the
maximum flow (note that $C$ is linear in the input size), $i=1,2$ and $1\leq
j\leq r$. One should interpret $f^{i}_{j}$ as mapping each vertex $v\in X_{j}$
to the net difference of flow of commodity $i$ in- or outgoing on that vertex
in a partial solution in the subtree with bag $X_{j}$ as root. The content of
the table is a boolean representing when there is a partial flow satisfying
the requirements that $f^{i}_{j}$ sets. Basic application of dynamic
programming on (nice) tree decompositions can solve the Integer $2$-Commodity
Flow problem with this table.

Now, we transform this to a non-deterministic algorithm with a stack as
follows. We basically guess an entry of each table, similar to the path
decomposition case of Theorem 1.1, and use the stack to handle nodes with two
children. Recursively, we traverse the tree $T$. For a leaf bag, guess an
entry of the table. For a bag with one child, guess an entry of the table
given the guessed entry of the child. For a bag with two children, recursively
get a guessed entry of the table of the left child. Put that entry on the
stack. Then, recursively get a guessed entry of the table of the right child.
Get the top element of the stack, and combine the two guessed entries. We need
$O(\log n)$ bits to store the position in $T$ we currently are and to look up
information on $G$. We need $O(f(k)\log C)$ bits to denote a table entry and
at each point, we have $O(1)$ such table entries in memory. This shows
membership in XALP.

For the hardness, we use a reduction from Tree Chained Multicolour Clique (see
Theorem 2.4). Suppose we have an instance of Tree Chained Multicolour Clique,
with a graph $G=(V,E)$, a tree partition $(\\{V_{i}\mid i\in I\\},T=(I,F))$
with $T$ a tree of maximum degree $3$, and a function $c\colon V\to[k]$.

As in the proof of Theorem 1.1, we build a Sidon set $S$ of $|V|$ integers in
the interval $[4|V|^{2}]$ using Theorem 2.1. To each vertex $v\in V$, we
assign a unique element of the set $S$, denoted by $S(v)$. For any subset
$W\subseteq V$, let $S(W)=\\{S(v)\mid v\in W\\}$ and for any subset
$E^{\prime}\subseteq E$, let $S(E^{\prime})=\\{S(u)+S(v)\mid uv\in
E^{\prime}\\}$. Also, let $L=4|V|^{2}+1$ be a ‘large’ integer.

We now create a flow network, similar to the network in the proof of Theorem
1.1. In particular, we recall the different gadgets that we created in that
construction: the Vertex selector gadget (see Figure 3), the Edge check gadget
(see Figure 4), the Triangle gadget (see Figure 5), and the Square gadget (see
Figure 6). Their structure, functionalities, and properties will be exactly
the same as before.

Root the tree $T$ at an arbitrary leaf $r$. We may assume that $T$ has at
least two nodes. We now create gadgets in the following manner, essentially
mimicking the structure of $T$ (see Figure 8). Start with $r$. Let
$r^{\prime}$ be its child in $T$. Create a Triangle gadget for $V_{r}$ and a
Square gadget for $V_{r}$ and $V_{r^{\prime}}$. Identify the exit arcs of the
Triangle gadget with the horizontal entry arcs of the Square gadget.

Figure 8: Overview of the complete structure of the reduction for $|I|=7$.
Left: the structure of the input tree partition. Right: the structure of the
reduction. Triangles represent a structure as in Figure 5, and squares a
structure as in Figure 6. Directions are not drawn, but clear from Figure 5
and 6. The labels inside each block (say $V_{i}$ or $V_{i},V_{i+1}$) denote
that flow corresponding to vertices of this set (i.e. $V_{i}$ or $V_{i}$ and
$V_{i+1}$) is flowing in a block. Note that all points labelled $s_{2},t_{2}$
are indeed the same vertex. Flow paths corresponding to a selected vertex in
$V_{2}$ (orange) and one in $V_{5}$ (purple) are drawn as an example.

Now, for every node $i$ of $T$, starting with $r^{\prime}$ and traversing the
tree down in DFS order, do the following. Let $p$ be the parent of $i$.
Suppose the depth of $p$ is odd. Create a Triangle gadget for $V_{i}$.
Identify the exit arcs of this new Triangle gadget with the horizontal entry
arcs of the (already constructed) Square gadget for $V_{p}$ and $V_{i}$. If
$i$ has a child in $T$, let $d$ be the first child of $i$ in DFS order. Create
a Square gadget for $V_{i}$ and $V_{d}$ and identify the horizontal exit arcs
of the Square gadget of $V_{p}$ and $V_{i}$ with the horizontal entry arcs of
the Square gadget of $V_{i}$ and $V_{d}$. If $i$ does not have a second child,
then the $2k$ horizontal exit arcs of the Square gadget of $V_{i}$ and $V_{d}$
are paired (one pair per colour class) and directed to a vertex; these $k$
vertices are then each connected by a single arc of capacity $L$ to $t_{2}$
(cf. Figure 6). If $i$ has a second child $d^{\prime}$, create a Square gadget
for $V_{i}$ and $V_{d^{\prime}}$, identify the horizontal exit arcs of the
Square gadget of $V_{i}$ and $V_{d}$ with the horizontal entry arcs of the
Square gadget of $V_{i}$ and $V_{d^{\prime}}$. Then the $2k$ horizontal exit
arcs of the Square gadget of $V_{i}$ and $V_{d^{\prime}}$ are paired (one pair
per colour class) and directed to a vertex; these $k$ vertices are then each
connected by a single arc of capacity $L$ to $t_{2}$ (cf. Figure 6).

If the depth of $p$ is even, then we do the same as above, but with vertical
entry and exit arcs instead of the horizontal ones.

We now set the demand for commodity 1 to the sum of the capacities of the
outgoing arcs of $s_{1}$ (which is equal to the sum of the capacities of the
incoming arcs of $t_{1}$). We set the demand for commodity 2 to the sum of the
capacities of the outgoing arcs of $s_{2}$ (which is equal to the sum of the
capacities of the incoming arcs of $t_{2}$). This completes the construction.
We now prove the bound on the pathwidth, followed by the correctness of the
reduction and a discussion of the time and space needed to produce it. To
prove the pathwidth bound, we note that all constructed gadgets are pieces,
and thus we can apply Lemma 3.6.

######  Claim 3.

The constructed graph has treewidth at most $16k+O(1)$.

We construct a tree decomposition as follows. First, we will ensure that
$s_{1},t_{1},s_{2},t_{2}$ are in every bag. Following the proof of Claim 1,
the pathwidth (and thus the treewidth) of the Triangle gadget and the Square
gadget is at most $4k+O(1)$. Recall that the Triangle gadget has $2k$ entry
arcs and $2k$ exit arcs, whereas the Square gadget has $4k$ entry arcs and
$4k$ exit arcs. The full construction (treating the Triangle and Square
gadgets as vertices) has a tree decomposition of width $1$, since it is tree
(see also Figure 8). Applying Lemma 3.6 and Remark 3.5, we obtain a bound of
$16k+O(1)$. We note that a slightly stronger bound of $4k+O(1)$ seems possible
with a more refined analysis, but this bound will be sufficient for our
purposes.

######  Claim 4.

The given Tree Chained Multicolour Clique instance has a solution if and only
if the constructed instance of Integer $2$-Commodity Flow has a solution.

If $G$ is a YES-instance of Tree Chained Multicolour Clique, then using a
similar construction of flows as in Theorem 1.1, we can see that the
constructed graph has a flow with all arcs from $s_{1}$ and $s_{2}$ and to
$t_{1}$ and $t_{2}$ are used to capacity. Minor modifications are needed to
route the flow corresponding through the tree structure of the Square gadgets
in the constructed instance here. Examples of such flow paths are illustrated
in Figure 8 for the orange and purple vertices.

Conversely, suppose we have an integer $2$-commodity flow that meets the
demands. Hence, there is a $2$-commodity flow in the constructed graph with
all arcs from $s_{1}$ and $s_{2}$ and to $t_{1}$ and $t_{2}$ used to capacity;
that is, their total flow is equal to their total capacity, with flow with the
corresponding commodity: commodity 1 for $s_{1}$ and $t_{1}$, and commodity 2
for $s_{2}$ and $t_{2}$. Like in Theorem 1.1, all flow of commodity 1 does not
leave the Verifier gadget it enters, as the constructed graph again is a
acyclic. Then, $s_{2}$ sends $L$ units of flow of commodity $2$ to each Vertex
selector gadget. This flow now splits into $\alpha$ and $L-\alpha$, where
$\alpha\in S(V_{i,l})$, as Lemma 3.13 can be applied. Therefore, there is some
$v\in V_{i,l}$ such that $\alpha=S(v)$. We select $v$ into the multicoulored
clique. Each Vertex selector gadget in turn sends $\alpha$ and $L-\alpha$ flow
respectively through the two input arcs of the edge check gadget incident on
it. Since there is a flow passing through each Edge check gadget, we know that
there exists an edge between the pair of the selected vertices. From the
construction, we then see that the selected vertex form a tree chained
multicolour clique. Therefore, $G$ is a YES-instance of Tree Chained
Multicolour Clique. As the constructed graph with its capacities can be built
using $O(f(k)+\log|V|)$ space for some computable function $f$, the result
follows. (See also the discussion at the end of the proof of Theorem 1.1.)

####  3.1.3 Reductions for Undirected Graphs

We now reduce from the case of directed graphs to the case of undirected
graphs in a general manner, by modification of a transformation by Even et al.
[13, Theorem 4]. In this way, both our hardness results (for parameter
pathwidth and for parameter treewidth) can be translated to undirected graphs.

######  Lemma 3.19.

Let $G$ be a directed graph of an Integer $2$-Commodity Flow instance with
capacities given in unary. Then in logarithmic space, we can construct an
equivalent instance of Undirected Integer $2$-Commodity Flow with an
undirected graph $G^{\prime}$ with
$\operatorname{pw}(G^{\prime})\leq\operatorname{pw}(G)+O(1)$,
$\operatorname{tw}(G^{\prime})\leq\operatorname{tw}(G)+O(1)$, and unit
capacities.

######  Proof 3.20.

We consider the transformation given by Even et al. [13, Theorem 4] that shows
the NP-completeness of Undirected Integer $2$-Commodity Flow and argue that we
can modify it to obtain a parameterised transformation from Integer
$2$-Commodity Flow to Undirected Integer $2$-Commodity Flow with capacities
given in unary, and with path- or treewidth as parameter. In particular, the
transformation increases the path- or treewidth of a graph by at most a
constant.

Figure 9: The transformation of Lemma 3.19 from directed to undirected graphs.
Every arc $uv$ with capacity $c$ is replaced by $c$ parallel copies of gadget
(a), where
$\overline{t_{1}},\overline{s_{1}},\overline{t_{2}},\overline{s_{2}}$ are the
same for every gadget, for all arcs. All capacities are 1. The remaining
figures illustrate that the gadget either transports no flow (b), a flow of
commodity 1 (c), or a flow of commodity 2 (d).

Given a directed graph $G=(V,E)$, demands $d_{1}$ and $d_{2}$, and capacity
function $c:E\to\mathbb{N}_{0}$, we construct the instance $G^{\prime}$,
$d^{\prime}_{1}$ and $d^{\prime}_{2}$, and
$c^{\prime}:E(G^{\prime})\to\\{0,1\\}$ as follows. To the graph $G$, we add
four new vertices
$\overline{s_{1}},\overline{s_{2}},\overline{t_{1}},\overline{t_{2}}$ as new
sources and sinks. We connect $\overline{s_{i}}$ to $s_{i}$ and
$\overline{t_{i}}$ to $t_{i}$ by $d_{i}$ parallel undirected edges of capacity
$1$, for each $i\in\\{1,2\\}$. Next, for each arc $uv\in E$ of capacity $p$,
we create $p$ parallel undirected edges between $u$ and $v$ of capacity $1$
each. Then, we replace each of these $p$ undirected edges by the following
Diamond gadget. We create a cycle $C$ on six vertices
$x^{uv}_{1},\ldots,x^{uv}_{6}$, numbered in cyclic order, which we make
adjacent to $u$, $\overline{t_{1}}$, $\overline{s_{1}}$, $v$,
$\overline{s_{2}}$, and $\overline{t_{2}}$ respectively by an edge of capacity
$1$ (see Figure 9(a)).

This is the graph $G^{\prime}$ and $c^{\prime}$ is as just described. In
$G^{\prime}$, the demands on the two commodities are
$d^{\prime}_{1}=d_{1}+e^{*}$ and $d^{\prime}_{2}=d_{2}+e^{*}$, where $e^{*}$
is the number of edge gadgets in $G^{\prime}$ (i.e. the sum of all capacities
in $c$). While $G^{\prime}$ is technically a multi-graph, any parallel edges
$e$ can be subdivided once, and the resulting edges $e_{1}$ and $e_{2}$ given
the same capacity as $e$. By abuse of notation, we still call this graph
$G^{\prime}$.

######  Claim 5.

The pathwidth of $G^{\prime}$ is $\operatorname{pw}(G)+O(1)$ and the treewidth
is $\operatorname{tw}(G)+O(1)$.

We note that each of the Diamond gadgets has pathwidth and treewidth $2$ and
forms a path piece and a tree piece. We add
$\overline{s_{1}},\overline{s_{2}},\overline{t_{1}},\overline{t_{2}}$ as well
as $s_{1}$, $s_{2}$, $t_{1}$, $t_{2}$ to every bag. Hence, using Lemma 3.1 and
3.6 and the above description, the claim follows.

######  Claim 6.

The demands $d_{1}$ and $d_{2}$ are met in $G$ if and only if the demands
$d^{\prime}_{1}$ and $d^{\prime}_{2}$ are met in $G^{\prime}$.

Suppose that the demands in the directed graph $G$ are met by some flow. Then,
first we send one unit of flow of each commodity in each edge gadget as shown
in Figure 9(b). If $uv$ is used to flow one unit of commodity 1 in $G$, then
we change the direction of flow in the edge gadget as in Figure 9(c). If one
unit of commodity 2 flows through $uv$, we change the flow through the edge
gadget as in Figure 9(d). Hence, in addition to the $d_{1}$ units of flow of
commodity 1 and $d_{2}$ units of flow of commodity 2, $e^{*}$ units of flow of
each type of commodity flows through $G^{\prime}$. Therefore, the demands
$d^{\prime}_{1}$ and $d^{\prime}_{2}$ are met.

Conversely, suppose that the demands of each commodity are met in the
undirected graph $G^{\prime}$ by some flow. The pattern of flow through each
edge gadget could be as in one of the three flows in Figure 9. If the flow
pattern is as in Figure 9(b), then the corresponding flows through the arc
$uv$ in $G$ are set as $f^{1}(uv)=f^{2}(uv)=0$. If it is in accordance with
Figure 9(c), then the corresponding flows in $G$ are set as $f^{1}(uv)=1$ and
$f^{2}(uv)=0$. If the flow pattern is as in Figure 9(d), then the
corresponding flows in $G$ are set as $f^{1}(uv)=0$ and $f^{2}(uv)=1$. There
are no other options, as every edge incident to any of
$\overline{s_{1}},\overline{s_{2}},\overline{t_{1}},\overline{t_{2}}$ must
have $1$ unit of flow of that commodity, otherwise the demands cannot be met.
Since the capacity of each edge of the Diamond gadget is $1$, the three
options (b), (c), (d) in Figure 9 model exactly the possibilities of sending
$1$ unit of flow over each edge incident to one of
$\overline{s_{1}},\overline{s_{2}},\overline{t_{1}},\overline{t_{2}}$.
Therefore, the flow through $G$ is at least $d_{1}+d_{2}$ and the demands of
each commodity are met.

The construction can be done in logarithmic space: while scanning $G$, we can
output $G^{\prime}$. This completes the proof.

See 1.2

######  Proof 3.21.

The proof of membership in XNLP follows in the same way as the membership of
Integer $2$-Commodity Flow as described in the proof of Theorem 1.1. For the
hardness, apply the reduction of Lemma 3.19 to the construction of Theorem
1.1.

See 1.4

######  Proof 3.22.

The proof of membership in XALP follows in the same way as the membership of
Integer $2$-Commodity Flow as described in the proof of Theorem 1.3. For the
hardness, apply the reduction of Lemma 3.19 to the construction of Theorem
1.3.

###  3.2 Binary Capacities

We prove our hardness results for Integer Multicommodity Flow with binary
capacities, parameterised by pathwidth. This immediately implies the same
results for the parameter treewidth; we do not obtain separate (stronger)
results for this case here. Our previous reduction strategy relied heavily on
$a$-Gate gadgets, which have size linear in $a$, and thus only work in the
case a unary representation of the capacities is given.

For the case of binary capacities, we can prove stronger results by reducing
from Partition. However, we need a completely new chain of gadgets and
constructions. Therefore, we first introduce a number of new gadgets. After
that, we give the hardness results for directed graphs, followed by reductions
from the directed case to the undirected case.

As before, throughout the section, all constructions will have disjoint
sources and sinks for the different commodities. We will set the demands for
each commodity equal to the total capacity of the outgoing arcs from the
sources, which is equal to the total capacity of the incoming arcs to the
sinks. Thus, the flow over such arcs will be equal to their capacity.

In contrast to the previous, our constructions will have two or three
commodities. We name the commodities 1, 2, and 3, with sources
$s_{1},s_{2},s_{3}$ and sinks $t_{1},t_{2},t_{3}$, respectively. We only need
the third commodity for the undirected case.

####  3.2.1 Gadgets

We define three different types of (directed) gadgets. Since we use binary
capacities, our goal is to double flow in an effective manner. For a given
integer $a$, the _$a$ -Doubler gadget_ receives $a$ flow and sends out $2a$
flow of the same commodity. This gadget is obtained by combining two other
gadgets: the $a$-Switch and the Doubling $a$-Switch. The _$a$ -Switch gadget_
changes the type of flow; that is, it receives $a$ flow from one commodity,
but sends out $a$ flow from the other commodity. The _Doubling $a$-Switch_ is
similar, but sends out $2a$ flow. All three types of gadgets have constant
size, even in the binary setting.

We now describe the three gadgets in detail.

#####  $a$-Switch Gadget

Let $a$ be any positive integer. The first gadget is called an _$a$ -Switch_.
This gadget turns $a$ units of flow of one type of commodity (in the
remainder, of commodity 2) into an equal amount of flow of the other commodity
(in the remainder, of commodity 1).

The gadget is constructed as follows (see Figure 10). We create six vertices
$v_{1},\dots,v_{6}$. We add an entry arc incoming to $v_{2}$ (the left entry
arc) and an entry arc incoming to $v_{3}$ (the right entry arc). We add an
exit arc outgoing from $v_{4}$ (the bottom exit arc) and an exit arc outgoing
from $v_{5}$ (the top exit arc). We add arcs along the paths
$v_{2}v_{4}v_{6}t_{2}$, $x_{2}v_{3}v_{5}v_{6}$, $s_{1}v_{1}v_{2}$, and
$v_{1}v_{3}$. All arcs have capacity $a$. We call $v_{2},v_{3},v_{4},v_{5}$
the boundary vertices of the gadget.

We note that, technically, we could also count the arc incoming on $v_{1}$ and
the arc outgoing from $v_{6}$ as entry and exit arcs, but since they are
coming from $s_{1}$ and going to $t_{2}$ respectively, we ignore this aspect.

Figure 10: The $a$-Switch gadget. Left: the schematic representation of the
gadget, with its entry and exit arcs. Right: the graph that realises the
gadget. All arcs have capacity $a$.

######  Lemma 3.23.

Consider the $a$-Switch gadget for some integer $a$. Let $f$ be some
$2$-commodity flow such that the arc outgoing from $s_{1}$ carries $a$ units
of flow commodity 1 and the arc incoming to $t_{2}$ carries $a$ units of flow
of commodity 2.

  1. 1.

If the left entry arc carries $a$ units of flow of commodity 2 and the right
entry arc carries $0$ units of flow of commodity 2, then the top exit arc
carries $a$ units of flow commodity 1 and the bottom exit arc carries $0$
units of flow.

  2. 2.

If left entry arc carries $0$ units of flow of commodity 2 and the right entry
arc carries $a$ units of flow of commodity 2, then the top exit arc carries
$0$ units of flow and the bottom exit arc carries $a$ units of flow of
commodity 1.

######  Proof 3.24.

Suppose the left entry arc carries $a$ units of flow of commodity 2 and the
right entry arc carries $0$ units of flow of commodity 2. We must send $a$
units of commodity 2 over the path $v_{2}v_{4}v_{6}t_{2}$, as this is the only
way $a$ units of commodity 2 can be sent over the arc $v_{6}t_{2}$ (recall
that this arc must be used to capacity and this flow cannot come from
$s_{1}$). Then all arcs along the path have been used to capacity. By a
similar argument, the $a$ units of flow of commodity 1 from $s_{1}$ to $v_{1}$
must go to $v_{3}$, and then via $v_{5}$ through the top exit arc.

The other case is symmetric.

######  Lemma 3.25.

For any integer $a$, the $a$-Switch is a path piece such that the required
path decomposition (ignoring the sources and sinks) has width $2$.

######  Proof 3.26.

The gadget is a piece by construction, with $B^{-}=\\{v_{2},v_{3}\\}$ and
$B^{+}=\\{v_{4},v_{5}\\}$. To construct the path decomposition, start with a
bag containing $v_{2},v_{3}$. We can now add $v_{1}$, and in the next bag
remove $v_{1}$ and add $v_{4}$. Then remove $v_{2}$ and add $v_{5}$. In the
final bag, remove $v_{3}$ and add $v_{6}$. Each bag contains at most 3
vertices.

##### Doubling $a$-Switch Gadget

Let $a$ be any positive integer. The second gadget is called a _Doubling
$a$-Switch_. This gadget turns $a$ units of flow of one type of commodity (in
the remainder, of commodity 1) into a $2a$ units of flow of the other
commodity (in the remainder, of commodity 2).

The gadget is constructed as follows (see Figure 11). We create fourteen
vertices $v_{1},\dots,v_{14}$. We add an entry arc incoming to $v_{4}$ (the
left entry arc) and an entry arc incoming to $v_{9}$ (the right entry arc),
each of capacity $a$. We add an exit arc outgoing from $v_{13}$ (the bottom
exit arc) and an exit arc outgoing from $v_{14}$ (the top exit arc), each of
capacity $2a$. We add arcs with capacity $a$ along the paths
$v_{4}v_{5}v_{6}v_{7}v_{8}t_{1}$, $v_{9}v_{10}v_{11}v_{12}v_{8}$. We also add
arcs $v_{2}v_{4}$, $v_{2}v_{6}$, $v_{3}v_{9}$, $v_{3}v_{11}$, $v_{5}v_{13}$,
$v_{7}v_{13}$, $v_{10}v_{14}$ and $v_{12}v_{14}$ with capacity $a$. Finally,
we add the arcs $s_{2}v_{1}$, $v_{1}v_{2}$, $v_{1}v_{3}$ with capacity $2a$.
The vertices $v_{4}$, $v_{9}$, $v_{13}$, $v_{14}$ are the boundary vertices of
the gadget.

Figure 11: The Doubling $a$-Switch gadget. Left: the schematic representation
of the gadget, with its entry and exit arcs. Right: the graph that realises
the gadget. The arcs are labelled with their capacities; all unlabelled arcs
have capacity $a$.

######  Lemma 3.27.

Consider the Doubling $a$-Switch gadget for some integer $a$. Let $f$ be some
$2$-commodity flow such that the arc outgoing from $s_{2}$ carries $2a$ units
of flow of commodity 1 and the arc incoming to $t_{1}$ carries $a$ units of
flow of commodity 2 .

  1. 1.

If the left entry arc carries $a$ units of flow of commodity 1 and the right
entry arc from carries $0$ units of flow of commodity 1, then the top exit arc
carries $2a$ units of flow of commodity 2, and the bottom exit arc carries $0$
units of flow of commodity 2.

  2. 2.

If the left entry arc carries $0$ units of flow of commodity 1 and the right
entry arc carries $a$ units of flow of commodity 1, then the top exit arc
carries $0$ units of flow of commodity 2 and the bottom exit arc carries $2a$
units of flow of commodity 2.

######  Proof 3.28.

Suppose the left entry arc carries $a$ units of flow of commodity 1 and the
right entry arc carries $0$ units of flow of commodity 1. We must send $a$
units of flow of commodity 1 over the path $v_{4}v_{5}v_{6}v_{7}v_{8}t_{1}$,
as this is the only way $a$ units of commodity 1 can be sent over the arc
$v_{8}t_{1}$. Then all arcs along the path have been used to capacity. This
implies that the flow from $s_{2}$ to $v_{1}$ must go to $v_{3}$, and then via
$v_{9}v_{10}$ and $v_{11}v_{12}$ to $v_{14}$ after which it must go through
the top exit arc.

The other case is symmetric.

######  Lemma 3.29.

For any integer $a$, the Doubling $a$-Switch is a path piece such that the
required path decomposition (ignoring sources and sinks) has width $5$.

######  Proof 3.30.

The gadget is a piece by construction, with $B^{-}=\\{v_{4},v_{9}\\}$ and
$B^{+}=\\{v_{13},v_{14}\\}$. To construct the path decomposition, start with a
bag containing $v_{4},v_{9},v_{1},v_{2},v_{3}$, followed by a bag containing
$v_{4},v_{9},v_{2},v_{3}$. From there, we create bags where we subsequently
add $v_{5}$, remove $v_{4}$, add $v_{6}$ and $v_{13}$, remove $v_{5}$, add
$v_{7}$, remove $v_{2}$ and $v_{6}$, and add $v_{8}$. The bag then contains
$v_{3},v_{8},v_{9},v_{13}$. Then we create bags where we subsequently add
$v_{10}$, remove $v_{9}$, add $v_{11}$ and $v_{14}$, remove $v_{10}$, and add
$v_{12}$. This forms the required path decomposition. All bags contain at most
six vertices.

#####  $a$-Doubler Gadget

Let $a$ be any positive integer. We can combine an $a$-Switch gadget with a
Doubling $a$-Switch gadget to get an $a$-Doubler gadget. The first gadget
changes the commodity of the flow, where the second gadget changes the
commodity back with double the amount of flow.

We construct this gadget as follows (see Figure 12). Create an $a$-Switch
gadget and an Doubling $a$-Switch gadget (refer to Figure 10 and 11). Identify
the top exit arc of the $a$-Switch gadget with the left entry arc of the
Doubling $a$-Switch gadget. Then identify the bottom exit arc of the
$a$-Switch gadget with the right entry arc of the Doubling $a$-Switch gadget.

Figure 12: The $a$-Doubler gadget. Left: the schematic representation of the
gadget, with its entry and exit arcs. Right: the graph that realises the
gadget. The arcs are labelled by their capacities.

Note that the $a$-Doubler gadget has two entry arcs (the left and right entry
arcs) and two exit arcs (the left and right exit arcs), corresponding to the
left and right entry arcs of the $a$-Switch gadget and the top and bottom exit
arcs of the Doubling $a$-Switch gadget respectively.

######  Lemma 3.31.

Consider the $a$-Doubler gadget for some integer $a$. Let $f$ be some
$2$-commodity flow. Then:

  1. 1.

If the left entry arc carries $a$ units of flow of commodity 2 and the right
entry arc carries $0$ units of flow of commodity 2, then the left exit arc
carries $2a$ units of flow of commodity 2 and the right exit arc carries $0$
units of flow of commodity 2.

  2. 2.

If the left entry arc carries $0$ units of flow of commodity 2 and the right
entry arc carries $a$ units of flow of commodity 2, then the left exit arc
carries $0$ units of flow of commodity 2 and the right exit arc carries $2a$
units of flow of commodity 2.

######  Proof 3.32.

The lemma follows immediately by combining Lemma 3.23 and 3.27.

######  Lemma 3.33.

For any integer $a$, the $a$-Doubler is a path piece such that the required
path decomposition (ignoring sources and sinks) has width $5$.

######  Proof 3.34.

Recall from Lemma 3.25 that the $a$-Switch is a path piece of pathwidth at
most $2$ with two entry arcs and two exit arcs. Recall from Lemma 3.29 that
the Doubling $a$-Switch is a path piece of pathwidth at most $5$ with two
entry arcs and two exit arcs. Note that the structure of the $a$-Doubler
gadget trivially satisfies the preconditions of Lemma 3.3. Hence, the lemma
then follows by applying Lemma 3.3.

####  3.2.2 Reduction for Directed Graphs

With the gadgets in hand, we can prove our hardness result for Integer
Multicommodity Flow (i.e. the case of directed graphs) for parameter
pathwidth.

See 1.5

######  Proof 3.35.

Membership in NP is trivial. To show NP-hardness, we transform from Partition.
Recall Partition problem asks, given positive integers $a_{1},\ldots,a_{n}$,
to decide if there is a subset $S\subseteq[n]$ with $\sum_{i\in S}a_{i}=B$,
where $B=\sum_{i=1}^{n}a_{i}/2$. This problem is well known to be NP-complete
[27].

So consider an instance of Partition with given integers $a_{1},\ldots,a_{n}$.
Create the sources $s_{1},s_{2}$ and the sinks $t_{1},t_{2}$. Create two
vertices $b_{1},b_{2}$, both with an arc of capacity $B$ to $t_{2}$.

For each $a_{i}$, we build a Binary gadget that either sends $a_{i}$ units of
flow to $b_{1}$ or $a_{i}$ units of flow to a vertex $b_{2}$, in each case of
commodity 2. This will indicate whether or not $a_{i}$ is in the solution set
to the Partition instance. This gadget is constructed as follows (see Figure
13 for the case when $a_{i}=13$). Consider the binary representation
$a_{i}^{p},\ldots,a_{i}^{0}$ of $a_{i}$. That is,
$a_{i}=\sum_{j=0}^{p}2^{j}a_{i}^{j}$. For each $j\in[p]$ such that
$a_{i}^{j}=1$, we create a column of chained Doubler gadgets. For each
$j^{\prime}<j$, create a $2^{j^{\prime}}$-Doubler gadget and identify its
entry arcs with the exit arcs of the $2^{j^{\prime}-1}$-Doubler gadget (see
Figure 13). Then the left exit arc of the (final) $2^{j-1}$-Doubler gadget is
directed to $b_{1}$, while the right exit arc is directed to $b_{2}$.

Note that the Binary gadget for $a_{i}$ still has $2\sum_{j=0}^{p}a_{i}^{j}$
open entry arcs (of the $1$-Doubler gadget of each column). These naturally
partition into $\sum_{j=0}^{p}a_{i}^{j}$ left entry arcs and
$\sum_{j=0}^{p}a_{i}^{j}$ right entry arcs. These all have capacity $1$. We
now connect these arcs. All further arcs in the construction will have
capacity $1$.

Create two directed paths $P_{i}^{1},P_{i}^{2}$ of $2\sum_{j=0}^{p}a_{i}^{j}$
vertices each (see Figure 13). We consider the vertices of each of these paths
in consecutive pairs, one pair for each $a_{i}^{j}$ that is equal to $1$. For
each $j\in[p]$ such that $a_{i}^{j}=1$, create a vertex $v_{i}^{j}$ with an
arc from $s_{2}$, an arc to the first vertex of the pair on $P_{i}^{1}$
corresponding to $a_{i}^{j}$, and an arc to the first vertex of the pair on
$P_{i}^{2}$ corresponding to $a_{i}^{j}$. Then, add an arc from the second
vertex of the pair on $P_{i}^{1}$ corresponding to $a_{i}^{j}$ to the left
entry arc of the $1$-Doubler gadget of the $j$th column of gadgets and an arc
from the second vertex of the pair on $P_{i}^{2}$ corresponding to $a_{i}^{j}$
to the right entry arc of the $1$-Doubler gadget of the $j$th column of
gadgets. Finally, create a vertex $u_{i}$ with an arc to the first vertex of
$P_{i}^{1}$ and to the first vertex of $P_{i}^{2}$ and create a vertex $w_{i}$
with an arc from the last vertex of $P_{i}^{1}$ and the last vertex of
$P_{i}^{2}$. This completes the description of the Binary gadget.

We now chain the Binary gadgets. For each $i\in[n-1]$, add an arc from $w_{i}$
to $u_{i+1}$. Add an arc from $s_{1}$ to $u_{1}$ and from $w_{n}$ to $t_{1}$.
These arcs all have capacity $1$.

We now set the demand for commodity 1 to the sum of the capacities of the
outgoing arcs of $s_{1}$ (which is equal to the sum of the capacities of the
incoming arcs of $t_{1}$). We set the demand for commodity 2 to the sum of the
capacities of the outgoing arcs of $s_{2}$ (which is equal to the sum of the
capacities of the incoming arcs of $t_{2}$). This completes the construction.

Figure 13: Example of the Binary gadget for $a_{i}=13$ and its associated
paths $P_{i}^{1}$ and $P_{i}^{2}$ and the ends $u_{i}$ and $w_{i}$. Since
$13=2^{3}+2^{2}+2^{0}$, we have a column with three Doubler gadgets, a column
with two Doubler gadgets, and one with no Doubler gadgets. The vertices
$v_{i}^{3}$, $v_{i}^{2}$ and $v_{i}^{0}$ are also drawn. Arcs are labelled by
their capacities, but unlabelled arcs have capacity $1$. If $1$ unit of flow
of commodity 1 is sent from $s_{1}$ to $t_{1}$, then it must pick one of
$P_{i}^{1},P_{i}^{2}$ to go through. Hence, the gadget ensures that either
$a_{i}$ units of flow of commodity 2 are sent to $b_{1}$ through the left
entry and exit arcs of the Doubler gadgets, or $a_{i}$ units of flow of
commodity 2 are sent to $b_{2}$ through the left entry and exit arcs of the
Doubler gadgets.

######  Claim 7.

The constructed graph has pathwidth at most $13$.

We construct a path decomposition as follows. Add
$s_{1},s_{2},t_{1},t_{2},b_{1}$ and $b_{2}$ to every bag. Then, we construct a
path decomposition for the Binary gadget and its associated paths $P_{i}^{1}$
and $P_{i}^{2}$. We create the trivial path decompositions for $P_{i}^{1}$ and
$P_{i}^{2}$ and union each of their bags, so that we ‘move’ through the two
paths simultaneously. When the first vertex of the pair corresponding to
$a_{i}^{j}$ (where $a_{i}^{j}=1$) is introduced in a bag, we add a subsequent
copy of the bag to which we add $v_{i}^{j}$ and another subsequent copy
without it. Then, when the second vertex of the pair corresponding to
$a_{i}^{j}$ (where $a_{i}^{j}=1$) is introduced in a bag, we add bags for the
Doubler gadgets of the column corresponding to $a_{i}^{j}$. Since each Doubler
gadget has two entry and exit arcs and is a path piece with a path
decomposition of width $5$ by Lemma 3.33, it follows from Lemma 3.3 (recalling
Remark 3.8) that each column has pathwidth $5$. Combining this with the other
vertices we add to each bag ($s_{1},s_{2},t_{1},t_{2},b_{1}$ and $b_{2}$) and
to each bag for each column (both second vertices of the pair corresponding to
the column), the total width of the path decomposition is $13$.

######  Claim 8.

The given Partition instance has a solution if and only if the constructed
instance of Integer $2$-Commodity Flow has a solution.

Let $S\subseteq[n]$ be a solution to the Partition instance. We will find a
corresponding solution to the constructed Integer $2$-Commodity Flow instance.
For each $i\in[n]$, we do the following. If $i\in S$, then we send flow of
commodity 2 from $s_{2}$ to $b_{1}$, through left entry and exit arcs of the
Doubler gadgets in the Binary gadget corresponding to $a_{i}$. To reach this
left side of the Doubler gadgets, the flow passes through vertices and arcs of
$P_{i}^{1}$. We can thus send flow of commodity 1 from $u_{i}$ to $w_{i}$ via
$P_{i}^{2}$. Otherwise, if $i\not\in S$, we send flow of commodity 2 from
$s_{2}$ to $b_{2}$, through right entry and exit arcs of the Doubler gadgets
in the Binary gadget corresponding to $a_{i}$. To reach this right side of the
Doubler gadgets, the flow passes through vertices and arcs of $P_{i}^{2}$. We
can thus send flow of commodity 1 from $u_{i}$ to $w_{i}$ via $P_{i}^{1}$.

Now note that by the properties of the Doubler gadget, proved in Lemma 3.31,
$b_{1}$ will receive $a_{i}$ units of flow of commodity 2 if $i\in S$ and
$b_{2}$ will receive $a_{i}$ units of flow of commodity 2 if $i\not\in S$.
Since $S$ is a solution to Partition, both $b_{1}$ and $b_{2}$ receive $B$
units of flow of commodity 2, which they can then pass on to $t_{2}$.
Moreover, we observe that we can send $1$ unit of flow from $s_{1}$ to $t_{1}$
via the paths $P_{i}^{1}$ and $P_{i}^{2}$, using $i\notin S$ and $i\in S$
respectively.

In the other direction, suppose we have an integer $2$-commodity flow that
meets the demands. That is, there is a $2$-commodity flow in the constructed
graph with all arcs from $s_{1}$ and $s_{2}$ and to $t_{1}$ and $t_{2}$ used
to capacity; that is, their total flow is equal to their total capacity, with
flow with the corresponding commodity: commodity 1 for $s_{1}$ and $t_{1}$,
and commodity 2 for $s_{2}$ and $t_{2}$. Hence, the arc $w_{n}t_{1}$ is used
to capacity, so $1$ unit flow of commodity 1 flows over this arc. Because of
the direction of the arcs, this flow can only come from $u_{n}$, and so from
$w_{n-1}$. By induction, this flow must come over the arc $s_{1}u_{1}$. We see
that the flow of commodity 1 starting at $u_{1}$ takes a path which is a union
of $P_{i}^{j_{i}}$ paths, for $i\in[n]$ and $j_{i}\in\\{1,2\\}$. In
particular, this flow does not ‘leak’ into any Doubler gadget, uses all the
arcs $w_{i}u_{i+1}$ for all $i\in[n-1]$ to capacity, and uses a complete path
$P_{i}^{j_{i}}$ up to capacity for each $i\in[n]$, $j_{i}\in\\{1,2\\}$.
Consider the Binary gadget corresponding to $a_{i}$. By the above argument, we
must have an $1$ unit of flow of commodity 1 going through one of the two
paths $P_{i}^{1}$ or $P_{i}^{2}$, also using the arc $w_{i}u_{i+1}$ to
capacity. Suppose this is $P_{i}^{1}$. This means that any flow from $s_{2}$
to $t_{2}$, in this Binary gadget, has to utilise $P_{i}^{2}$, the right side
of the Doubler gadgets, and end up at $b_{2}$. We can apply Lemma 3.31 to
every Doubler gadget. As flow of commodity 2 is carried over the right entry
and exit arcs and no flow flows over the left entry and arcs, the total flow
value reaching $b_{2}$ has to be equal to $a_{i}$. The same argument holds
with respect to $P_{i}^{2}$ and $b_{1}$. Let $S\subseteq[n]$ be the set of
indices $i$ for which the flow of commodity 2 through the Binary gadget
corresponding to $a_{i}$ arrives at $b_{1}$. Since the edge $b_{1}t_{2}$ has
capacity $B$ and since $b_{1}$ has received $\sum_{i\in S}a_{i}$ units of flow
of commodity 2, we find that $\sum_{i\in S}a_{i}\leq B$. Similarly,
$\sum_{i\notin S}a_{i}\leq B$. Since $\sum_{i\in[n]}a_{i}=2B$, we conclude
that $S$ is a valid solution to the Partition instance.

Finally, as each $a$-Doubler has constant size, the gadget for some $a_{i}$
has size $O(\log^{2}(a_{i}))$, which is polynomial in the input size. Hence,
the construction as a whole has size polynomial in the input size. Moreover,
it can clearly be computed in polynomial time.

####  3.2.3 Reduction for Undirected Graphs

We now reduce from the case of directed graphs to the case of undirected
graphs in a general manner. We define a new gadget that is similar to the
gadget we used in Section 3.1.3. However, we note that there we required $a$
copies of the gadget if the capacity of an arc is $a$, which is not feasible
in the case of binary capacities. Also note that increasing the capacities of
the gadget by Even et al. [13, Theorem 4], here Figure 9, invalidates the
gadget, as any under-capacity edge would allow flow in the other direction.
Hence, we need a different gadget, before we can give our hardness result for
undirected graphs.

We first define a subgadget called a _Directed twin flow edge_ gadget, seen in
Figure 14, which we construct as follows. Given two vertices $u$ and $v$, two
commodities $i_{1}$ and $i_{2}$, and an integer (capacity) $c$, we add
vertices $w_{1},w_{2},w_{3}$, and $w_{4}$. We then add edges $uw_{1}$,
$w_{1}w_{2}$, $w_{2}w_{3}$, $w_{3}w_{4}$, $w_{4}v$, $t_{i_{1}}w_{1}$,
$s_{i_{1}}w_{2}$, $t_{i_{2}}w_{3}$ and $s_{i_{2}}w_{4}$, all with capacity
$2c$. We will refer to the vertex $u$ as the _tail-vertex_ of the gadget and
to $v$ as the _head-vertex_. Furthermore, we say that the gadget is _labelled_
by the two commodities whose source and sink are attached in the gadget.

Figure 14: The Directed twin flow edge gadget of capacity $c$. Left: the
schematic representation of the gadget. Right: the gadget itself. The arcs are
labelled by their capacities. The colours are used to indicate the respective
commodities.

The gadget only allows flow of the two given commodities through, in only one
direction and only in equal amounts. The following lemma captures this
behaviour.

######  Lemma 3.36.

Let $G$ be an undirected graph is part of an instance of Undirected Integer
$\ell$-Commodity Flow for some $\ell\geq 2$. Let $u,v\in V(G)$ and suppose
there is a a Directed twin flow edge gadget $H$ in $G$ for commodities $i_{1}$
and $i_{2}$ with $u$ as the tail-vertex of $H$ and $v$ the head-vertex of $H$.
Let $f$ be an $\ell$-flow in $G$ that fills all edges incident on each source
and sink to capacity with flow of the corresponding commodity. Then:

  * •

no flow of any commodity other than $i_{1}$ or $i_{2}$ can travel from $u$ to
$v$, through $H$,

  * •

the amount of flow of commodities $i_{1}$ and $i_{2}$ travelling from $u$ to
$v$ through $H$ is equal,

  * •

no flow can travel through $H$ from $v$ to $u$.

######  Proof 3.37.

For simplicity, we will assume that the flow $f$ does not go back on itself,
i.e. no edge has nonzero flow of the same commodity in both directions.

If in total $x$ units of flow of any commodity other than $i_{1}$ or $i_{2}$
travel from $u$ to $w_{3}$ through $H$, then by the capacity of $w_{1}w_{2}$
and the fact that $2c$ units of flow of commodity $i_{1}$ enter the gadget at
$w_{2}$, at least $x$ units of flow of commodity $i_{1}$ must travel from
$w_{2}$ via $w_{3}$ to $w_{4}$. Hence, by a similar argument, at least $2x$
units of flow of commodity $i_{2}$ leave the gadget at $w_{4}$. Therefore, the
flow of commodity $i_{2}$ travelling from $u$ to $w_{3}$ must be at least $2x$
units, a contradiction.

We then note that if we have $a_{1}$ units of flow of commodity $i_{1}$
entering the gadget at $w_{1}$, we can only have at most a total of $a_{1}$
units of the other commodities flowing from $w_{1}$ to $w_{2}$. Indeed, note
that $2c$ units of flow of commodity $i_{1}$ must enter the gadget from
$s_{i_{1}}$ to $w_{2}$ and leave the gadget via $w_{1}$ to $t_{i_{1}}$. Hence,
$2c-a_{1}$ units of flow of commodity $i_{1}$ would travel from $w_{2}$ to
$w_{1}$. Similarly, if we have $a_{2}$ units of flow of commodity $i_{2}$
leaving the gadget at $w_{4}$, we can only have at most a total of $a_{2}$
units of the other commodities flowing from $w_{3}$ to $w_{4}$. Hence, the
amount of flow of commodities $i_{1}$ and $i_{2}$ travelling from $u$ to $v$
through $H$ is equal.

We also find that the edges $w_{1}w_{2}$ and $w_{3}w_{4}$ are always used to
capacity and thus we cannot send any flow from $v$ to $u$ through $H$, which
proves the last item of the lemma.

We now create a _Directed edge gadget_ that effectively functions as a
directed edge. To enable this gadget, we need an additional commodity to
activate the gadget. So suppose we have $\ell+1$ commodities, with commodity
$\ell+1$ being this extra commodity. The gadget is constructed as follows (see
Figure 15). Given two vertices $u$ and $v$ and an integer (capacity) $c$, we
wish to simulate the arc $e=uv$. Create a new vertex $v_{e}$. For each
$i\in[\ell]$, we then attach a Directed twin flow edge gadget from $u$ to
$v_{e}$ for commodities $i$ and $\ell+1$, with capacity $c$. Finally, we add
an edge $v_{e}v$ with capacity $2c$. Again, we will refer to the vertex $u$ as
the _tail-vertex_ of the gadget and to $v$ as the _head-vertex_ of the gadget.

Figure 15: Directed edge gadget, for $\ell=2$ and capacity $c$.

######  Lemma 3.38.

Let $G$ be an undirected graph that is part of an instance of Undirected
Integer $\ell+1$-Commodity Flow for some $\ell\geq 2$. Let $u,v\in V(G)$ and
suppose there is a a Directed edge gadget $H$ in $G$ with $u$ as the tail-
vertex of $H$ and $v$ the head-vertex of $H$. Let $f$ be an $(\ell+1)$-flow in
$G$. Then:

  * •

in total, no more than $c$ units of flow of commodities $1,\dots,\ell$ can
travel from $u$ to $v$, through $H$,

  * •

the amount of flow of commodity $\ell+1$ travelling from $u$ to $v$ through
$H$ is equal to the sum of all other commodities travelling from $u$ to $v$
through $H$,

  * •

no flow can travel through $H$ from $v$ to $u$.

######  Proof 3.39.

Recall that $H_{1},\dots,H_{\ell}$ are the Directed twin flow edge gadgets in
the Directed edge gadget and let $v_{e}$ be the ‘middle vertex’ of the gadget.
By the last item of Lemma 3.36, no flow can travel from $v_{e}$ to $u$ through
any of the $H_{i}$ and thus no flow can travel from $v$ to $u$ through $H$.

By the first two items of Lemma 3.36, the amount of flow travelling from $u$
to $v_{e}$ through $H_{i}$ is equal to some $a_{i}$ for commodities $i$ and
$\ell+1$, and $0$ for any other commodities. We find that the amount of flow
travelling from $u$ to $v_{e}$ of commodity $\ell+1$ is equal to the sum the
other commodities and thus the amount of flow of commodity $\ell+1$ travelling
from $u$ to $v$ through $H$ is equal to the sum of all other commodities
travelling from $u$ to $v$ through $H$.

The first item now holds trivially, since the edge $v_{e}v$ has capacity $2c$.

This construction now allows us to extend any reductions from some problem to
Integer $\ell$-Commodity Flow to a reduction from the problem to Undirected
Integer $\ell+1$-Commodity Flow. We now show such an extension only increases
the pathwidth by a constant.

######  Lemma 3.40.

Let $G$ be a directed graph of an Integer $\ell$-Commodity Flow instance with
a path decomposition of width $w$, such that each bag contains the sources and
sinks of commodities $1,\ldots,\ell$. Then in polynomial time, we can
construct an equivalent instance of Undirected Integer $\ell+1$-Commodity Flow
of pathwidth at most $w+5$.

######  Proof 3.41.

For each $i\in[\ell]$, let $d_{i}$ denote the demand for commodity $i$ for the
given instance of Integer $\ell$-Commodity Flow. To start, we create a source
$s_{\ell+1}$ and sink $t_{\ell+1}$ for the extra commodity, with demand
$d^{\prime}_{\ell+1}=\sum_{i=1}^{\ell}d_{i}$. Then, for $i\in[\ell]$, we
connect $s_{\ell+1}$ to $s_{i}$ by an edge with capacity $d_{i}$, and connect
$t_{i}$ to $t_{\ell+1}$ by an edge with capacity $d_{i}$. Then, replace each
arc $uv$ in $G$ by a Directed edge gadget. Call the resulting graph
$G^{\prime}$. Set the remaining demands $d_{i}^{\prime}=d_{i}$ for $i\in\ell$.
This completes the construction.

We note that $G^{\prime}$ can be constructed in polynomial time from $G$. The
fact that the given instance of Integer $\ell$-Commodity Flow and the
constructed instance of Undirected Integer $\ell+1$-Commodity Flow are
equivalent follows immediately from Lemma 3.38 and the construction of
$G^{\prime}$. Indeed, by the setting of the demand $d^{\prime}_{\ell+1}$ and
the capacities of the edges incident on $s_{\ell+1}$, every source $s_{i}$ of
$G$ receives $d_{i}$ units of flow of commodity $\ell+1$. Hence, every flow of
commodity $i$ is and can be accompanied by an equal amount of flow of
commodity $\ell+1$. Then, following Lemma 3.38, the direction of $uv$ is
maintained by the transformation.

To prove the upper bound on the pathwidth of $G^{\prime}$, consider some arc
$e=uv$ in the directed graph $G$. In the path decomposition of $G$, there must
be some bag $X$ that contains both $u$ and $v$. Create $3\ell$ copies of the
bag $X$ that we insert after $X$. To each of these copies, add the vertex
$v_{e}$ of the Directed edge gadget (this covers in particular the edge
$v_{e}v$ of the gadget). For each commodity $i\in[\ell]$, add to consecutive
bags the pairs $(w_{1},w_{2})$, $(w_{2},w_{3})$, and $(w_{3},w_{4})$ of the
Directed twin flow edge gadget $H_{i}$ in the Directed edge gadget. These
three bags for each $i\in[\ell]$ handle the path decomposition for the
Directed twin flow edge of commodity $i$. So, in total, the $3\ell$ bags
handle the path decomposition for the entire gadget.

We do this for every arc in $G$, where the copies we make of bags are copies
only of bags in the path decomposition of $G$. After we have done this for
every arc, we add the source and sink of the ‘extra’ commodity $\ell+1$ to
every bag. We see that the maximum number of vertices in any bag increases by
at most $5$.

By combining Lemma 3.40 and Theorem 1.5, we obtain the following.

See 1.6

######  Proof 3.42.

By Theorem 1.5, Integer $2$-Commodity Flow with capacities given in binary is
NP-complete for graphs of pathwidth at most $13$. By inspection of the proof,
we see that it has a path decomposition of width $13$ such that each bag
contains both sources and both sinks. Then the reduction of Lemma 3.40
immediately implies the theorem.

###  3.3 Parameterisation by Vertex Cover — At Most One Commodity Per Edge

Our last hardness result concerns a parameterisation by vertex cover. In this
case, we will add the additional constraint that the edges must be
_monochrome_ , that is, for each edge, only one commodity can have positive
flow. Later, in Section 4.2, we will see that it is possible to approximately
solve the problem without this constraint, in polynomial time.

Figure 16: Construction for the reduction from Bin Packing to 2-Commodity
Flow.

See 1.8

######  Proof 3.43.

We reduce from Bin Packing. Recall that in Bin Packing, we are given integers
$a_{1},\ldots,a_{n}$, an integer $B$, and an integer $k$. We are asked to
decide whether the integers $a_{1},\ldots,a_{n}$ can be partitioned into at
most $k$ bins, such that the sum of the numbers assigned to each bin does not
exceed $B$. Bin Packing is NP-hard for binary weights and $k=2$ [23] and
W[1]-hard for unary weights when parameterised by $k$ [25]. In both cases, we
may assume that $\sum_{j=1}^{n}a_{j}=kB$: if $k=2$, we have the Subset Sum
problem, and in the unary case, we can add $kB-\sum_{j=1}^{n}a_{j}$ additional
integers that are all equal to $1$.

We first describe our construction. Suppose we are given an instance
$((a_{j})_{1}^{n},B,k)$ of Bin Packing. Without loss of generality, we may
assume that $\sum_{j=1}^{n}a_{j}=kB$. We construct an equivalent instance of
Undirected Integer $2$-Commodity Flow with Monochrome Edges that has a vertex
cover of size $k+4$ (see also Figure 16). We create a graph $G$ with the
following vertices and edges:

$\displaystyle V(G)$ $\displaystyle=\\{s_{1},s_{2},t_{1},t_{2},v_{1},\dots
v_{n},w_{1},\dots,w_{k}\\}$ $\displaystyle E(G)$
$\displaystyle=\\{s_{i}v_{j}:i\in\\{1,2\\},j\in[n]\\}\cup\\{w_{i}v_{j}:i\in[k],j\in[n]\\}\cup\\{w_{i}t_{j}:i\in[k],j\in\\{1,2\\}\\}.$

We set the capacities of the edges as follows:

$\displaystyle c(s_{1}v_{j})$ $\displaystyle=a_{j}$ $\displaystyle\forall
j\in[n]$ $\displaystyle c(s_{2}v_{j})$ $\displaystyle=(k-1)a_{j}$
$\displaystyle\forall j\in[n]$ $\displaystyle c(w_{i}v_{j})$
$\displaystyle=a_{j}$ $\displaystyle\forall i\in[k],j\in[n]$ $\displaystyle
c(w_{i}t_{1})$ $\displaystyle=B$ $\displaystyle\forall i\in[k]$ $\displaystyle
c(w_{i}t_{2})$ $\displaystyle=(k-1)B$ $\displaystyle\forall i\in[k].$

We set the demands as $d_{1}=kB$ and $d_{2}=(k-1)kB$. This completes the
reduction.

Suppose that the instance of Bin Packing is a YES-instance. Thus, there is a
partition $I_{1},\ldots,I_{k}$ of $\\{1,\ldots,n\\}$ such that $\sum_{j\in
I_{i}}a_{j}\leq B$ for each $i\in[k]$. As $\sum_{j=1}^{n}a_{j}=kB$, actually
$\sum_{j\in I_{i}}a_{j}=B$ for each $i\in[k]$. For each $i\in[k]$ and each
$j\in I_{i}$, route $a_{j}$ units of flow of commodity 1 from $s_{1}$ to
$v_{j}$ to $w_{i}$ to $t_{1}$. Hence, edges incident on $s_{1}$ and $t_{1}$
only transport flow of commodity 1. For $i\in[k]$, since $\sum_{j\in
I_{i}}a_{j}=B$, the flow over each edge $w_{i}t_{1}$ does not exceed $B$.
Also, route $(k-1)a_{j}$ units of flow of commodity 2 from $s_{2}$ to $v_{j}$.
Then, split this flow into $k-1$ units of flow to each vertex in
$\\{w_{1},\ldots,w_{k}\\}\setminus\\{w_{i}\\}$ and from these vertices to
$t_{2}$. Hence, edges incident on $s_{2}$ and $t_{2}$ only transport flow of
commodity 2. For $i\in[k]$, $\sum_{i\in[k]\setminus\\{i\\}}\sum_{j\in
I_{i^{\prime}}}\leq(k-1)B$ since $\sum_{j\in I_{i}}a_{j}=B$, and thus the flow
over each each edge $w_{i}t_{2}$ does not exceed $(k-1)B$. Finally, note that
edges between $\\{v_{1},\ldots,v_{n}\\}$ and $\\{w_{1},\ldots,w_{k}\\}$ only
transport flow of a single commodity, because $I_{1},\ldots,I_{k}$ is a
partition of $\\{1,\ldots,n\\}$. Hence, the instance of Undirected Integer
$2$-Commodity Flow with Monochrome Edges is a YES-instance.

Conversely, suppose that the instance of Undirected Integer $2$-Commodity Flow
with Monochrome Edges is a YES-instance and consider a valid flow. We analyse
the structure of this flow. The cut $(\\{s_{1}\\},V(G)\setminus\\{s_{1}\\})$
has capacity $\sum_{i=1}^{n}a_{i}=kB=d_{1}$. Hence, for each $j\in[n]$, we
must have $a_{j}$ units of flow of commodity 1 from $s_{1}$ to $v_{j}$.
Similarly, the cut $(\\{s_{2}\\},V(G)\setminus\\{s_{2}\\})$ has capacity
$\sum_{i=1}^{n}(k-1)a_{i}=kB=d_{2}$. Hence, for each $j\in[n]$, we must have
$(k-1)a_{j}$ units of flow of commodity 2 from $s_{2}$ to $v_{j}$. Since the
total capacity of the remaining edges connected to $v_{j}$ (the edges
$v_{j}w_{i}$) is equal to $ka_{j}$ and since each edge can only be used by one
commodity, we find that exactly one of these edges transports $a_{j}$ units of
flow of commodity 1 to some $w_{i}$ and the other $k-1$ edges each transport
$a_{j}$ units of flow of commodity 2 to the other $w_{i^{\prime}}$ with
$i^{\prime}\not=i$. Finally, any unit of commodity 1 in $w_{i}$ must be sent
to $t_{1}$ and any unit of commodity 2 must be set to $t_{2}$, since by
construction the total capacity of the cut
$(V(G)\setminus\\{t_{1},t_{2}\\},\\{t_{1},t_{2}\\})$ is
$k\sum_{j=1}^{n}a_{j}=d_{1}+d_{2}$, so we cannot have any flow going in the
reverse direction.

We now construct sets $I_{1},\ldots,I_{k}$. Now observe that each $v_{j}$
sends $a_{j}$ units of flow of commodity 1 to exactly one neighbour $w_{i}$.
Then add $j$ to $I_{i}$. Then $I_{1},\ldots,I_{k}$ forms a partition of
$\\{1,\ldots,n\\}$. Moreover, each $w_{i}$ can send at most $B$ units of flow
of commodity 1 to $t_{1}$ and $t_{1}$ does not receive units of flow of
commodity 1 from vertices outside the set $\\{v_{1},\dots,v_{n}\\}$. Hence,
$\sum_{j\in I_{i}}a_{j}\leq B$ for all $i\in[k]$. Hence, the instance of Bin
Packing is a YES-instance.

Finally, note that $|V(G)|=O(n)$, that $V(G)\setminus\\{v_{1},\dots,v_{n}\\}$
forms a vertex cover of size $k+4$, and that we can construct the instance in
time $n^{O(1)}$. We conclude that since Bin Packing is NP-hard for binary
weights and $k=2$ [23], Undirected Integer $2$-Commodity Flow with Monochrome
Edges is NP-hard for binary weights and vertex cover size 6. We also conclude
that since Bin Packing is W[1]-hard for unary weights when parameterised by
$k$ [25], Undirected Integer $2$-Commodity Flow with Monochrome Edges is
W[1]-hard for unary weights, when parameterised by the vertex cover size.

The reduction to the directed case can be readily seen.

See 1.7

######  Proof 3.44.

The proof immediately follows from the proof of Theorem 1.8, by directing each
edge from left to right (direction as in Figure 16).

##  4 Algorithms

In this section, we complement our hardness results with two algorithmic
results.

###  4.1 Parameterisation by Weighted Tree Partition Width

We first give an FPT-algorithm for Integer $\ell$-Commodity Flow parameterised
by weighted tree partition width. This algorithm assumes that a tree partition
of the input graph is given. There is an algorithm by Bodlaender et al. [4]
that for any graph $G$ and integer $w$, runs in time $\mathrm{poly}(w)\cdot
n^{2}$ and either outputs a tree partition of $G$ of width $\mathrm{poly}(w)$
or outputs that $G$ has no tree partition of width at most $w$. By some simple
tricks, this can be expanded to approximate weighted tree partition width as
well, at the expense of a slightly worse polynomial in $w$. An approximately
optimal tree partition of this form would be sufficient as input to our
algorithm.

See 1.9

######  Proof 4.1.

We will describe a dynamic-programming algorithm on a given tree partition
$(T,(B_{x})_{x\in V(T)})$. Let $r\in V(T)$ be some node, that we will
designate as the root of the tree $T$. For convenience, we first attach a node
to every leaf, with an empty bag.

We will create a table $\tau$, where every entry is indexed by a node $x$ of
the tree partition and a collection $\mathbf{f}_{x}$ of functions $f^{i}_{x}$,
one function for every commodity $i\in[\ell]$. We will refer to
$\mathbf{f}_{x}$ as a flow profile and use the superscript $i$ to refer to the
flow function for commodity $i$ in the profile. The function

$f^{i}_{x}:B_{p(x)}\to[-\operatorname{b},\operatorname{b}],$

where $p(x)$ the parent node of $x$, indicates for every $v\in B_{p(x)}$ the
net difference between the amount of flow of commodity $i$ that $v$ receives
from (indicated by a positive value) or sends to (indicated by a negative
value) the vertices in the bag $B_{x}$, in the current partial solution. That
is, $f^{i}_{x}(v)$ models the value of $\sum_{u\in
B_{x}}(f^{i}(uv)-f^{i}(vu))$, where $f$ denotes the current partial solution.
Notice that this sum has value in $[-\operatorname{b},\operatorname{b}]$, as
the sum over all capacities of edges between bags $B_{x}$ and $B_{p(x)}$ is at
most $\operatorname{b}$. The content of each table entry will be a boolean
that indicates whether there exists a partial flow on the graph considered up
to $x$ that is consistent with the indices of the table entry.

We will build the table $\tau$, starting at the leaves of the tree, for which
we assumed the corresponding bags to be empty sets, and working towards the
root. If $x$ is a leaf in the tree partition, we set
$\tau[x,\\{\emptyset,\dots,\emptyset\\}]=\text{True}$, where we denote by
$\emptyset$, the unique function with the empty set as domain. Otherwise, $x$
is some node with children $y_{1},\dots,y_{t}$. We will group these children
$y_{i}$ in equivalence classes $\xi$, defined by the equivalence relation
$y\sim y^{\prime}$ if and only if
$\tau[y,\mathbf{f}_{x}]=\tau[y^{\prime},\mathbf{f}]$ for every flow profile
$\mathbf{f}$. Note that there are at most
$2^{\operatorname{b}^{\ell(2\operatorname{b}+1)}}$ such equivalence classes,
with at most $\operatorname{b}^{\ell(2\operatorname{b}+1)}$ possible flow
profiles $\mathbf{f}_{y_{j}}=(f^{1}_{y_{j}},\dots,f^{\ell}_{y_{j}})$ for every
child $y_{j}$ of $x$.

We will now describe an integer linear program that determines the value of
$\tau[x,\mathbf{f}_{x}]$ for a given flow profile $\mathbf{f}_{x}$. We define
a variable $X_{\xi,\mathbf{g}}$ as the number of sets in class $\xi$ whose in-
and outflow we choose to match flow profile $\mathbf{g}$222Throughout the
proof, if we sum over pairs $\xi,\mathbf{g}$, we only sum over flow profiles
that are valid for bags in $\xi$. Alternatively, we can set any invalid
$X_{\xi,\mathbf{g}}$ to $0$ beforehand.. We also define a variable $Y_{e}^{i}$
for each edge inside the bag $B_{x}$ or between $B_{x}$ and its parent bag,
which indicates the flow of commodity $i$ on this edge. We will denote by
$N^{in}(v)$ and $N^{out}(v)$ the set of in-neighbours and out-neighbours of
$v$, respectively, restricted to $B_{x}\cup B_{p(x)}$. We now add constraints
for the following properties, for every commodity $i\in[\ell]$. Flow
conservation for all vertices $v$ in the bag $B_{x}$, that are not a
sink/source for commodity $i$:

$\sum\limits_{u\in
N^{in}(v)}Y_{uv}+\sum\limits_{\xi,\mathbf{g}}X_{\xi,\mathbf{g}}\cdot
g^{i}(v)=\sum\limits_{u\in N^{out}(v)}Y_{uv}.$

The flow of commodity $i$ from a source $s_{i}$ (if $s_{i}\in B_{x}$):

$-\sum_{u\in N^{in}(s_{i})}Y_{us_{i}}+\sum_{u\in
N^{out}(s_{i})}Y_{us_{i}}-\sum\limits_{\xi,\mathbf{g}}X_{\xi,\mathbf{g}}\cdot
g^{i}(s_{i})=d_{i}$

The flow of commodity $i$ to a sink $t_{i}$ (if $t_{i}\in B_{x}$):

$\sum_{u\in N^{in}(t_{i})}Y_{ut_{i}}-\sum_{u\in
N^{out}(t_{i})}Y_{ut_{i}}+\sum\limits_{\xi,\mathbf{g}}X_{\xi,\mathbf{g}}\cdot
g^{i}(t_{i})=d_{i}$

The desired flow to a vertex $v$ in the parent bag:

$\sum_{u\in N^{in}(v)\setminus B_{p(x)}}Y_{uv}-\sum_{u\in N^{out}(v)\setminus
B_{p(x)}}Y_{uv}=f_{x}^{i}(v).$

Edge capacities and non-negative flow:

$0\leq\sum_{i=1}^{\ell}Y_{e}^{i}\leq c(e)$

The number of flow profiles of each type from each class matches the number of
bags in that class:

$\sum\limits_{g:B_{x}\to[-\operatorname{b},\operatorname{b}]}X_{\xi,\mathbf{g}}=|\xi|.$

$X_{\xi,\mathbf{g}}$ must be a non-negative integer:

$X_{\xi,\mathbf{g}}\in\mathbb{N}_{0}$

We then use an algorithm of Frank and Tardos [18, Theorem 5.3] to solve the
ILP in time $N^{2.5N+o(N)}$, where $N$ is the number of variables in the ILP.
This number is dominated by the number of variables $X_{\xi,\mathbf{g}}$, of
which there are $O(2^{\operatorname{b}^{\ell(2\operatorname{b}+2)}})$. We thus
find a running time of
$2^{\operatorname{b}^{\ell(2\operatorname{b}+2)}(2.5\cdot
2^{\operatorname{b}^{\ell(2\operatorname{b}+2)}}+o(2^{\operatorname{b}^{\ell(2\operatorname{b}+2)}}))}$.
If the ILP has a feasible solution, we set
$\tau[x,\mathbf{f}_{x}]=\text{True}$; otherwise, we set
$\tau[x,\mathbf{f}_{x}]=\text{False}$. We solve
$\operatorname{b}^{\ell(2\operatorname{b}+1)}$ such ILP’s per bag in the
decomposition and thus find a total running time of
$O(2^{2^{\operatorname{b}^{3\ell b}}})$

Once we reach the root bag, we use a similar ILP to compute the flow on the
root bag, finding a final solution. We find a total running time of
$2^{2^{\operatorname{b}^{3\ell b}}}n^{O(1)}$.

Note that with some minor changes to the ILP (flow variables can be negative
and there is no distinction between in/out edges), this proof also works in
the undirected case. Thus, we also find the following result.

See 1.10

######  Proof 4.2.

Adjusting the ILP so that flow variables can be negative and there is no
distinction between in/out edges, we can see the proof of Theorem 1.9 extends
to the undirected case.

###  4.2 Parameterisation by Vertex Cover

In this section, we give an approximation algorithm for the Integer
$2$-Commodity Flow problem, parameterised by the vertex cover number of a
graph. Since we consider a decision problem, the use of the term
‘approximation’ requires some explanation, since technically the output of an
exact algorithm is simply ‘true’ or ‘false’. In our case, we still give a
Boolean output, but for the question of whether there is a flow with values in
some range around the demands. We make this more precise with the following
theorem:

See 1.11

######  Proof 4.3.

Let $X$ be a vertex cover of the graph $G$. We can assume that one of size
$\operatorname{vc}(G)$ is given as part of the input or we can compute a
$2$-approximation in polynomial time by the folklore algorithm (attributed to
Gavril and to Yannakakis; see e.g. [9]). In the latter case, the proof still
holds, but the (hidden) constant is worse by a factor $8$. Write $Y=V\setminus
X$.

We first compute, in polynomial time, a solution to the LP relaxation of the
problem. This gives us a fractional flow $f$. If this flow does not meet the
demands, then we can immediately answer that there exists no integral flow
that meets the demands. We will now argue that we can transform this flow such
that the total value remains the same, but the number of arcs that is assigned
a non-integral value is $O(|X|^{3})$.

We say that an arc $e$ is a _mono-fractional arc_ if there is exactly one
commodity $i\in[2]$ such that $f^{i}(e)\not\in\mathbb{N}_{0}$. We say that arc
$e$ is an _bi-fractional arc_ if for both commodities $i\in[2]$, we have
$f^{i}(e)\not\in\mathbb{N}_{0}$. An arc is _fractional_ if it is mono-
fractional or bi-fractional. An arc that is not fractional is called
_integral_.

We will show that a fractional flow $f$ can be transformed to a flow with the
same values for both commodities, such that there are at most $O(|X|^{3})$
fractional arcs. The case analysis is tedious, with many cases that are
similar but handled slightly differently. In each case, small changes are made
to the flow, but all vertices in $X$ will have the same inflow and outflow.

Note that if $v$ is incident to an arc with fractional flow for commodity $i$,
then there must be another arc with $v$ as endpoint with fractional flow for