# Simulation Based Inference for Efficient Theory Space Sampling:
an Application to Supersymmetric Explanations of the Anomalous Muon (g-2)

Logan Morrison  Stefano Profumo  Nolan Smyth  John Tamanas<EMAIL_ADDRESS>Department of Physics and Santa Cruz Institute for Particle Physics University
of California, Santa Cruz, CA 95064, USA

###### Abstract

For the purpose of minimizing the number of sample model evaluations, we
propose and study algorithms that utilize (sequential) versions of likelihood-
to-evidence ratio neural estimation. We apply our algorithms to a
supersymmetric interpretation of the anomalous muon magnetic dipole moment in
the context of a phenomenological minimal supersymmetric extension of the
standard model, and recover non-trivial models in an experimentally-
constrained theory space. Finally we summarize further potential possible uses
of these algorithms in future studies.

##  I Introduction

The pursuit of understanding beyond the Standard Model (BSM) physics theories
in the context of experimental results is the cornerstone of much research in
high energy physics (HEP). However, despite the increasing accuracy of weak-
scale observables, it remains non-trivial to perform the inverse calculation,
i.e., to determine regions of parameter space yielding the observables.

Mapping out regions of parameter space that produce given observables is
especially difficult for theories with many free parameters – a famous example
being the minimal supersymmetric model (MSSM) (see, e.g., [1] for a review)
and down-sized versions thereof, in parameter space, such as the
phenomenological MSSM (pMSSM) [2, 3]. The exploration of the parameter space
of these theories is typically carried out, in the HEP literature, by defining
a search space in the space of pMSSM parameters, uniformly sampling it, and
then rejecting all samples which do not conform with theoretical or
experimental constraints (see, e.g., [4, 5, 6], albeit there is a very vast
literature on the topic). However, the number of required samples grows
exponentially with the dimension of the search space, so these methods are
extremely computationally intensive, if not intractable, when calculations of
the output predictions for a given set of input parameters are slow.

There has been a recent upsurge of developments in the broader scientific
literature regarding the inverse problem of restricting parameter spaces of a
forward model purely through sampling (i.e. calculating observables from model
parameters; see e.g. [7, 8, 9] for a few recent examples). The introduction of
neural networks to simulation-based inference (SBI) frameworks, in particular,
has lead to explosive improvements in accuracy and precision and ablation
studies comparing them all [10, 11, 12, 13].

In this work, we introduce the sequential neural ratio estimation (SNRE)
algorithm to the problem of sampling from an experimentally constrained
version of the pMSSM. Although not explicitly stated, recent work [14] has
used methods from the simulation-based inference literature – namely neural
likelihood estimation. We show how that method fits into the larger SBI
framework and discuss an alternative, though related, approach that uses
likelihood-to evidence ratio neural estimation. This fits in the context of
“likelihood-free” methods in which drawing samples from a forward model is
possible, but the likelihood is expensive or intractable to evaluate.
Additionally, we demonstrate sequential versions of two algorithms that can
significantly reduce the number of model evaluations required.

Specifically, here we are interested in the following example case study: we
perform sampling of the pMSSM parameter space, producing experimentally viable
predictions for (i) the relic density of dark matter ($\Omega_{\chi}h^{2}$) in
the form of the lightest neutralino, which has mass $M_{\chi}$, (ii) the Higgs
mass ($m_{h}$), (iii) the anomalous magnetic moment of the muon ($a_{\mu}$),
and (iv) WIMP-nucleon cross sections ($\sigma^{\textrm{SI}}$).

We organize the manuscript as follows: § II details the general SBI framework
and describes the SNRE algorithm in particular; § III details the search space
of the pMSSM to which we will be applying SNRE; in § IV we demonstrate the
improved sampling efficiency of sequential algorithms; we show an application
of SNRE to an experimentally constrained pMSSM parameter space in § V; and
finally, in § VI we summarize our findings and further discuss potential
future uses of SBI.

##  II Simulation-Based Inference

This work aims to use the simulation-based inference (SBI) framework to sample
from a large-dimensional parameter space while evaluating the model output as
few times as possible for computational efficiency. There are essentially four
overarching approaches to SBI: rejection sampling with approximate Bayesian
computation (ABC), posterior estimation (NPE), likelihood-to-evidence ratio
estimation (NRE), and likelihood estimation (NLE). For a full review of
simulation-based inference and other methods therein, we refer the Reader to
Ref. [15].

We begin by stating Bayes’ rule:

$P(\theta|X)=\frac{P(X|\theta)P(\theta)}{P(X)}$ (1)

where $P(X|\theta)$ is the likelihood of the data given the model parameters,
$P(\theta)$ is the prior probability of the model parameters, and $P(X)$ is
the evidence. In this work, $\theta$ refers to supersymmetric parameters, and
$X$ refers to various observables of our choosing, e.g., the Higgs mass, the
DM relic density, and the muon anomalous magnetic moment.

The NRE approach begins by approximating the likelihood-to-evidence ratio,
$r(X,\theta)=\frac{P(X|\theta)}{P(X)}$, and then using it to sample from the
posterior distribution of the model parameters with Hamiltonian Monte Carlo
(HMC). HMC can be thought of as a Markov Chain Monte Carlo (MCMC) [16, 17]
algorithm where a chain’s position and momentum are sampled from a joint
distribution and then evolved according to Hamilton’s equations. HMC makes use
of derivatives to calculate its transitions, which makes it not directly
applicable using the micrOMEGAs [18] package, but it can still be used on the
neural network side. For a full review of HMC, see [19].

###  II.1 Likelihood-to-Evidence Ratio Estimation

Here, we will follow the approach of Ref. [12] to approximate the likelihood-
to-evidence ratio: Assume we have two classes of simulations, $Y_{0}$ and
$Y_{1}$, each of which is composed of pairs of $\\{X,\theta\\}$. We define
$Y_{0}$ and $Y_{1}$ such that $Y_{0}=\\{X,\theta\\}\sim P(X)P(\theta)$ and
$Y_{1}=\\{X,\theta\\}\sim P(X|\theta)$. We use curly brackets to denote a set
of values. The optimal classifier (one which minimizes the binary cross-
entropy loss) between $Y_{0}$ and $Y_{1}$ is given by

$d^{*}(X,\theta)=\frac{P(X|\theta)}{P(X|\theta)+P(X)P(\theta)}$ (2)

which can, in turn, be used to express the likelihood-to-evidence ratio:

$r^{*}(X,\theta)=\frac{P(X|\theta)}{P(X)}=\frac{P(X,\theta)}{P(X)P(\theta)}=\frac{d^{*}(X,\theta)}{1-d^{*}(X,\theta)},$
(3)

where we used the fact that the joint distribution
$P(X,\theta)=P(X|\theta)P(\theta)$. Thus, approximating $r^{*}(X,\theta)$ is
equivalent to finding the optimal classifier $d^{*}(X,\theta)$, which we can
accomplish by training a classifier to distinguish between $Y_{0}$ and
$Y_{1}$. For the rest of this work, we shall use $r(X,\theta)$ to denote the
approximate likelihood-to-evidence ratio.

In practice, we produce samples of $Y_{1}$ by first drawing $\theta$ from the
prior, $P(\theta)$, and then passing it through our simulator (the micrOMEGAs
package) to generate $X$. We begin sampling from $Y_{0}$ in the same way: we
draw $\theta$ from the prior and plug it into our simulator to generate $X$.
After this, however, we re-sample $\theta^{\prime}\sim P(\theta)$ and use the
new value in its place, i.e. $(X,\theta^{\prime})\sim Y_{1}$.

We will use a neural network to model $r(X,\theta)$, which allows us to take
advantage of the vast literature and resources available for deep learning
applications. We will use an ensemble of multi-layer perceptrons (MLPs).
Ensembling models and taking their average was shown in [20] to produce more
accurate, conservative posteriors than would be obtained by simply training a
single model.

Although not applicable for this work, it is worth pointing out that the data
can be of virtually any format. For example, the authors of [12] have shown
the ability of this algorithm to ingest 128$\times$128 pixel images of
strongly-lensed galaxies and produce accurate posteriors of its Einstein
radius.

###  II.2 Sequential Neural Likelihood-to-Evidence Ratio Estimation

If the prior is not carefully crafted to be a good approximation of the
posterior to start with, we expect many of the samples to produce observables
far from the experimental values of interest. These can be seen as wasted
evaluations of the model, the very thing we are trying to limit. However, with
a trained NRE, we have a better approximation of the posterior available to
us. We therefore elect to iterate the training procedure outlined in the
previous section, but replace the sampling of $\theta$ from the prior with a
sampling from the intermediate posterior. The full algorithm is outlined in
Alg. (1).

Empirically, numerical experiments show that sequential versions of SBI tend
to converge to the true posteriors with fewer simulator evaluations than their
non-sequential counterparts [13]. Intuitively, this is because the approximate
posterior will be most accurate in the densest regions of the parameter space
as specified by the training data. However, when we are sampling from the
posterior, we are most interested in its regions of highest probability.
Therefore, we can reduce the number of model evaluations required by
iteratively closing in on the true posterior. We demonstrate this in Section
IV where we run trials to determine how efficient (the fraction of viable
simulations) naive, NRE, and SNRE sampling, respectively, are. Our results are
summarized in Fig. (1) and Fig. (2).

Finally, it is important to note that either version of SBI is not guaranteed
to converge to the true posterior and can often produce overconfident bounds
on parameter space with exceedingly high computational budgets required to
calibrate [20]. By using an ensemble of classifiers, which we do for all of
our applications, we partially alleviate this problem.

Algorithm 1 Sequential Neural Likelihood-to-Evidence Ratio Estimation (SNRE)

Let $p_{r}(\theta|X_{0})$ be the posterior in round $r$.

Let $p_{r=0}(\theta|X_{0})=P(\theta)$.

while $r<R$ do

set prior to $p_{r}(\theta|X_{0})$

while $n\leq N$ do

Sample $\theta_{n}\sim p_{r}(\theta|X_{0})$

Sample $X_{i}\sim P(X|\theta_{n})$

Add $\\{\theta_{n},X_{n}\\}$ to $\mathcal{D}$

end while

while $d\leq D$ do

Sample $\\{\theta_{A},X_{A}\\}_{d}\sim\mathcal{D}$

Sample $\\{\theta_{B},X_{B}\\}_{d}\sim\mathcal{D}$

Assign labels $y=1$ for $\\{\theta_{A},X_{A}\\}_{d}$ and
$\\{\theta_{B},X_{B}\\}_{d}$

Assign labels $y=0$ for $\\{\theta_{B},X_{A}\\}_{d}$ and
$\\{\theta_{A},X_{B}\\}_{d}$

end while

(re-)train $r(X,\theta)$ to classify $\\{\theta_{A},X_{A}\\}_{D}$,
$\\{\theta_{B},X_{B}\\}_{D}$, $\\{\theta_{B},X_{A}\\}_{D}$, and
$\\{\theta_{A},X_{B}\\}_{D}$ by minimizing the binary cross-entropy loss.

$p_{r}(\theta|X_{0})=r(X,\theta)P(\theta)$

end while

##  III Phenomenological Minimal Supersymmetric Model

The fully general, unconstrained minimal supersymmetric extension to the
Standard Model (MSSM) contains 105 free parameters [21], principally connected
with the soft supersymmetry breaking pattern. By enforcing no flavor changing
neutral currents, no new sources of CP violation, and first and second
generation universality, these parameters are restricted to a 19-dimensional
parameter space, known as the “phenomenological” MSSM (pMSSM) [22]. Here,
since we intend to illustrate the algorithms outlined above as applied to the
pMSSM in connection with supersymmetric contributions to the anomalous
magnetic moment of the muon, we entertain the possibility that the
supersymmetric scalar particles associated with second generation leptons,
smuons, be lighter than, and not as usually assumed degenerate with, their
first generation counterparts, selectrons. Therefore, we relax the
universality assumption in the slepton sector of the pMSSM, which adds two
more parameters to the parameter space of interest. To simplify, and since
they are largely irrelevant to quantities of interest, especially the muon
anomalous magnetic moment, we assume all squark masses to be degenerate at a
relatively large mass scale set to 4 TeV, large enough so that they have
negligible effects in our calculations.

Parameter | Domain |  | Description
---|---|---|---
$|\mu|$ | [100, 4000] |  | Higgs mixing parameter
$|M_{1}|$ | [50, 1000] |  | Bino mass parameter
$|M_{2}|$ | [100, 4000] |  | Wino mass parameter
$M_{3}$ | [400, 4000] |  | Higgsino mass parameter
$M_{L_{1}}$ | [100, 4000] |  | Left-handed selectron mass
$M_{L_{2}}$ | [100, 1000] |  | Left-handed smuon mass
$M_{L_{3}}$ | [100, 4000] |  | Left-handed stau mass
$M_{r_{1}}$ | [100, 4000] |  | Right-handed selectron mass
$M_{r_{2}}$ | [100, 1000] |  | Right-handed smuon mass
$M_{r_{3}}$ | [100, 4000] |  | Right-handed stau mass
$M_{A}$ | [400, 4000] |  | Pseudoscalar Higgs mass
$\tan\beta$ | [1, 60] |  | Ratio of Higgs VEVs $v_{u}/v_{d}$
$|A_{t}|$ | [0, 4000] |  | Trilinear Higgs-stop coupling
$|A_{b}|$ | [0, 4000] |  | Trilinear Higgs-sbottom coupling
$|A_{\tau}|$ | [0, 4000] |  | Trilinear Higgs-stau coupling
Table 1: Domains used for the pMSSM soft supersymmetry breaking parameters.
All parameters (aside from $\tan\beta$) are in units of GeV. We set all squark
mass parameters to 4 TeV.

To utilize the SBI framework, one must have a forward model of the likelihood,
i.e., a function which takes in a set of parameters, $\theta$, and produces an
observable, $X$, from some underlying distribution. The underlying
distribution need not be known explicitly, for our goal is to learn it from
the samples. Additionally, we must provide a prior distribution of the
parameters. For our applications, we will use a uniform prior for the
parameters, with bounds chosen to be consistent with the literature and listed
in Tab. (1).

In the following applications, we aim to produce posterior distributions
conditioned on a combination of observables calculated by the micrOMEGAs
package [18]. Although not arbitrarily accurate, micrOMEGAs produces a
deterministic output, so we assume Gaussian error bars on these calculations.
Thus, our likelihood is given by
$\mathcal{N}\left(X(\theta),\sigma_{X}\right)$, where $\mathcal{N}$ is the
normal distribution and
$X(\theta)=(\Omega_{\textrm{DM}}(\theta),a_{\mu}(\theta),m_{h}(\theta),p_{\textrm{Xenon1T}})$
is the vector of calculated observables from micrOMEGAs. The variance of the
distribution is
$\sigma_{X}^{2}=\sigma_{\textrm{exp}}^{2}+\sigma_{\textrm{th}}^{2}$ with
theoretical Gaussian uncertainties are:

$\displaystyle\sigma_{X}$
$\displaystyle=(\sigma_{\Omega},\sigma_{a^{\mathrm{SUSY}}_{\mu}},\sigma_{m_{h}},\sigma_{p_{\textrm{Xenon1T}}})$
(4) $\displaystyle=(0.01,65\times 10^{-11},1.0\textrm{\ GeV},10^{-5}).$

pMSSM parameters, $\theta$ are sampled from a uniform prior, with bounds shown
in table 1. When sampling from our posterior, we set the observed values of
$X$ to their experimental results [23, 24, 25, 26, 27]

$\displaystyle X_{0}$
$\displaystyle=(\Omega_{\chi}h^{2},m_{h},a^{\mathrm{SUSY}}_{\mu},p_{\mathrm{Xenon1T}})$
(5) $\displaystyle=(0.12,125\ \textrm{GeV},251\times 10^{-11},0.0455).$

Here we are assuming that the discrepancy between the SM and experimentally
observed anomalous magnetic moment of the muon is solely due to supersymmetric
contributions
$a^{\mathrm{SUSY}}_{\mu}=a^{\mathrm{exp.}}_{\mu}-a_{\mu}^{\mathrm{SM}}$. As
Xenon1T has not yet observed WIMP dark matter, we set its p-value equal to
$\textrm{CDF}_{\mathcal{N}}(2\sigma)$ and treat all p-values greater than this
value identically via the pre-processing described in Eqn. (9)-Eqn. (12).

##  IV Benefits from Sequential Training

A key question in algorithm optimization is to seek the minimization of the
time required to obtain $N$ samples from a distribution. Here, we can
approximate the amount of time spent computing, $T$, via

$T=Ns+Rt+(R-1)v+w$ (6)

where $N$ is the total number of micrOMEGAs calculations performed, $s$ is the
time per micrOMEGAs evaluation, $R$ is the number of sequential rounds of
training, $t$ is the time to train the network in each sequential round, $v$
is the amount of time to sample from the intermediate posteriors during SNRE
training, and $w$ is the amount of time to sample from the final SNRE
posterior. In this application, we limit $R,t,v,w$, so that the majority of
the time is spent evaluating micrOMEGAs, i.e. $T\approx Ns$. $N$ is often
chosen to be large enough so that the number of samples surviving the
constraints is larger than some number, $M$. We can write

$N=M/\varepsilon+D,$ (7)

where $\varepsilon$ is the efficiency of our micrOMEGAs samples, and $D$ is
the number of samples used to train our models (for traditional methods,
$D=0$). If the efficiency is sufficiently small, the number of required
samples becomes prohibitively large, which is the typical case when sampling
$\theta$ from the prior. The goal of SBI is to minimize $N$ by maximizing
$\varepsilon$. We illustrate this effect by calculating the efficiency of over
a range of training sample sizes and SNRE training rounds.

###  IV.1 Setup

The benefits of the SBI framework become clear when looking at the efficiency
of sampling, i.e., the fraction of samples that satisfy the given constraints
of the problem. To illustrate this, we perform the pMSSM posterior
approximation exercise while enforcing observables to be within $3$-sigma of
their central values:

$\begin{split}0.09<\ &\Omega_{\chi}h^{2}<0.15\\\ 122\ \textrm{GeV}<\
&m_{h}<128\ \textrm{GeV}\\\ 56\times 10^{-11}<\
&a^{\mathrm{SUSY}}_{\mu}<445\times 10^{-11}\\\ 0.0455<\
&p_{\textrm{Xenon1T}}\end{split}$ (8)

where $a^{\mathrm{SUSY}}_{\mu}=(g^{\mathrm{SUSY}}_{\mu}-2)/2$ is the
supersymmetric contribution to the muon anomalous magnetic moment and
$p_{\textrm{Xenon1T}}$ is the p-value of the model as determined by Xenon1T.

We choose to run the SBI pipeline on three different choices of $R$.
Specifically we set $R=1$ for NRE, $R=3$ for SNRE3, and $R=5$ for SNRE5.

We compare each choice of $R$ with the “prior” baseline, which calculates
observables using samples from the prior, and then subjects them to the same
filtering as shown in Eqn. (8). We emphasize that samples from the prior do
not correspond to samples from the posterior, and we only use the samples as a
point of comparison.

We allot a budget of 150,000 micrOMEGAs calculations and split them into
training sets and inference sets. We use the training sets to train the
networks, and the inference sets are the evaluations from which our final
samples come. Ideally, the training sets will be as small as possible to
maximize the number of posterior samples in our inference set. However,
increasing the size of the training set could increase the efficiency of
posterior samples, thus enabling equal performance with the weaker algorithm
producing a larger inference set. For each method, we run a trial on a
training set of sizes 10,000, 31,000, and 100,000, with the remaining
calculations left for inference. For SNRER, we distribute the calculations
equally amongst the $R$ rounds.

###  IV.2 Results

Figure 1: The fraction of points sampled from the posterior that lie within
the ranges specified in Eqn. (8). The grey band indicates the efficiency of
sampling directly from the prior for comparison with standard MCMC based
approaches. Figure 2: The expected amount of time (minutes) needed to obtain
one sample in the ranges specified in Eqn. (8). Figure 3: Samples from the
posterior which lie within the experimental constraints specified in Eqn. (8)
obtained by running SNRE with hyperparameters listed in Tab. (2) are shown in
salmon. We note the overdensity of small smuon masses which affect $a_{\mu}$
and $\Omega_{\chi}$ by coannhiliations. See Fig. (5) and Fig. (4) for corner
plots with subsets of these parameters. Shown in blue are the filtered samples
from the posterior for the non-sequential NRE, again trained using the
hyperparameters in Tab. (2). We see the SNRE algorithm produces similar
coverage for most parameters while providing greater sampling efficiency.

The results demonstrate several notable features. First, in Fig. (1) we
observe the expected trend amongst the sequential algorithms; as the number of
points used to train increases, the number of points sampled from the
approximate posteriors which lie within the ranges specified in Eqn. (8) also
increases. However, this is not true for NRE, which performed worse for the
medium-sized training set. The absence of this scaling for NRE is likely due
to overfitting, which we did not prevent by early-stopping. Finally, as the
efficiency is highest for SNRE5, it is the preferred model in the event that
additional computational resources become available after the training phase,
e.g., in future follow-up analyses.

We determine the average amount of time from start to finish required to
generate a valid sample from the final posterior and display the results in
Fig. (2). Although slower overall, we determine that the efficiency of SNRER
gives it a factor of up to 3 times faster sampling than NRE, even when the
inference set is significantly smaller. Our results suggest sequential
algorithms are consistently the most efficient when they use
$\mathcal{O}(10\%)$ of the allotted calculations for training.

##  V Application to pMSSM

###  V.1 SBI Setup

We now examine the posteriors and experimental observables produced by an
application to the pMSSM. In this search, we are interested in finding the
regions of parameter space most likely to contain the correct relic density,
Higgs mass, provide a good fit to the observed anomalous magnetic moment of
the muon, and are not excluded by Xenon1T.

Inspired by the results of section IV, we run SNRE for a total of 10 rounds,
each with 20,000 new samples calculated with micrOMEGAs. Next, we assemble the
likelihood-to-evidence approximators with an ensemble of 5 binary classifiers
whose inputs are a concatenation of $X$ and $\theta$ and whose outputs are the
logit of the classification probability. Each network consists of three hidden
layers, each consisting of 256 units. Next, we train networks to minimize the
binary cross-entropy loss between samples from the likelihood, $p(X|\theta)$,
and the joint probability, $p(X)p(\theta)$. Finally, we average the ensemble
outputs during inference time to produce an approximate likelihood-to-evidence
ratio of a given sample. When we sample with HMC during intermediate training
steps, we use 20 chains with 2000 warmup steps and 32 chains with 2000 warmup
steps during the final inference time.

Figure 4: Corner plots of $\mu$ and gaugino mass parameters created from the
same samples as Fig. (3). Dotted lines correspond to $\mu=M_{1}$ and
$M_{2}-2=M_{1}$, respectively. We see a strong bias towards bino-like and
wino-like LSPs. Direct detection constraints force $\mu$ towards larger values
of its range. Additionally, we see a dependence on the relative signs of $\mu$
and $M_{2}$. Figure 5: Corner plots of smuon and dark matter masses calculated
from the same samples as Fig. (3). Shaded regions do not have a neutralino LSP
which, although not explicitly excluded, are not experimentally viable. We
note the large concentration of light right-handed smuons. Figure 6: Samples
from the approximate posterior which lie within the experimental constraints
specified in Eqn. (8). The color of each point corresponds to the p-value from
compressed spectra constraints reported by ATLAS. The background is shaded
according to a gaussian kernel density estimate in order to visualize the
concentration of points on these axes. We note the ability of ATLAS to probe
models which lie in the neutrino floor. Figure 7: Same as Fig. (6) but plotted
on ATLAS constraints with Xenon1T p-values, as calculated by micrOMEGAS. The
mass splitting is taken with respect to the lightest slepton mass, $M_{\ell}$.
Dotted lines correspond to $\pm 1\sigma$ constraints. We expect future
analyses to constrain much of the viable parameter space with small mass
splittings.

###  V.2 Results

In Fig. (3), we show samples from the approximate posterior as one-dimensional
histograms. The multi-modal and irregularly shaped distribution of points
demonstrates the ability of flexible neural methods to hone in on these
regions. The results exhibit several features previously found in the
literature despite not being enforced a priori in our search (outside of
choosing bounds on the prior.) Additionally, we plot two-dimensional
histograms for a subset of the dimensions in Fig. (4) and Fig. (5).

These results demonstrate, for example, the learned dependence on the relative
signs of $\mu$ and the gaugino parameters. In addition, we find that most
models have a bino-like LSP with light smuons whose masses are near the LSP
mass. Physically, these correspond to the bino coannihilation with smuons
driving thermal relic abundance. One expects these results as bino-like LSPs
have smaller WIMP-nucleon cross sections, and lighter sleptons contribute more
to $a_{\mu}$, while also suppressing the relic density. We note the generally
larger values of $M_{L_{2}}$ compared to $M_{r_{2}}$. This trend is mostly due
to the sneutrino requiring a larger value of $M_{L_{2}}$ because its mass is
typically lighter than the left-handed smuon. The right-handed smuon mass, on
the other hand, is generally equal to $M_{r_{2}}$.

Of the 96,000 samples generated from the approximated posterior, 179 survive
the cuts laid out in Eqn. (8), resulting in an efficiency of 0.00186, similar
to the results shown in Fig. (1). The surviving points are shown on top of
Xenon1T and ATLAS [28, 29] constraints in Fig. (6) and Fig. (7), respectively.
Interestingly, our results indicate that the experiments are complementary:
regions of low direct detection constraining power exist in high ATLAS
constraining power regions, and vice versa. We expect future analyses to probe
the majority of the surviving parameter space.

##  VI Conclusions

We introduced a simulation-based inference framework capable of analyzing
high-dimensional parameter spaces and applied the framework to supersymmetric
extensions to the Standard Model. We showed how equivalent amounts of
computational time result in orders of magnitude more pMSSM models of
experimental interest than naive sampling from the prior. Additionally, we
demonstrated how sequential sampling methods are even more efficient than
their non-sequential counterparts by performing a light scan over
hyperparameters.

Finally, we applied the framework to sample from regions of the pMSSM
parameter space yielding the correct thermal dark matter relic density, Higgs
mass, and the muon’s anomalous magnetic moment, which direct detection
experiments have not yet excluded. We found that the most likely regions of
this space are tantalizingly close to current ATLAS bounds and are likely to
be covered in future direct dark matter detection experiments.

Future exercises similar to the present one could make use of calibration
methods presented in Ref. [30] to avoid overly-confident constraints on the
approximated posterior and therefore avoid excluding potentially viable
regions of parameter space. Additionally, one can consider higher-dimensional
observables. Rather than summaries of observed weak-scale quantities, it is
potentially of interest to operate directly on the raw data obtained from
experiments.

###### Acknowledgements.

The authors would like to thank Michael Hance, Giordon Stark, Jeff Shahinian,
and Michael Holzbock. This work is partly supported by the U.S. Department of
Energy grant number de-sc0010107 and the National Science Foundation Graduate
Research Fellowship under Grant No. DGE-1842400 to NS.

##  Appendix A Training details

Prior to entering neural network, is data are pre-processed to restrict the
dynamic range of the inputs. For the relic density, we enforce the value to be
greater than $10^{-4}$, convert to log-space and rescale:

$\displaystyle\Omega_{\chi}h^{2}$ $\displaystyle\rightarrow
10\times\log_{10}\left(\textrm{clip}(\Omega_{\chi}h^{2},10^{-4},\infty)\right)$
(9)

The Higgs mass is restricted to be larger than $118$ GeV and made $\order{1}$
by subtracting off a value close to its know mass $123.864$ GeV and rescaling
to be $\order{1}$

$\displaystyle m_{h}$
$\displaystyle\to\frac{\mathrm{clip}(m_{h},118,\infty)-123.864}{2.2839}$ (10)

The SUSY contribution to the muon anomalous magnetic moment is restricted to
be within $10^{-11}$ and $10^{-8}$, converted to log-space and made
$\order{1}$

$\displaystyle a^{\mathrm{SUSY}}_{\mu}$
$\displaystyle\to\log_{10}\mathrm{clip}(a_{\mu},10^{-11},10^{-8})+9.5$ (11)

Lastly, we restrict the p-value from Xenon1T to be positive and less than
$0.0455$. We then rescale to be $\order{1}$:

$\displaystyle p_{\textrm{Xenon1T}}$ $\displaystyle\to
10\times\mathrm{clip}(p_{\textrm{Xenon1T}},0,0.0455)$ (12)

In the above, $\mathrm{clip}(x,x_{\mathrm{min}},x_{\mathrm{max}})$ is given
by:

$\mathrm{clip}(x,x_{\mathrm{min}},x_{\mathrm{max}})=\begin{cases}x_{\mathrm{min}}&\text{if
$x<x_{\mathrm{min}}$}\\\ x_{\mathrm{max}}&\text{if $x>x_{\mathrm{max}}$}\\\
x&\text{otherwise}\end{cases}$ (13)

The hyperparameters used in the networks are listed in Tab. (2).

Hyperparameter |  | Value
---|---|---
Hidden layers |  | 3
Hidden layer size |  | 256
Ensemble size |  | 5
Learning rate |  | 3 $\times 10^{-4}$
Weight decay |  | 0
Max gradient norm |  | $10^{-3}$
Validation interval |  | 50
Patience |  | 200
Batch size |  | 256
Training split |  | 0.95
Table 2: Hyperparameters common to all (S)NRE algorithms tested in all
applications.

We used the SaxBI package [31] with JAX [32] and Flax [33] backends to
initialize and fit the models to perform approximate Bayesian inference. We
used the optax-repository’s [34] implementation of the Adaptive Moment
Estimation (Adam) algorithm [35] to optimize our models. We used numpyro’s
implementation of Hamiltonian Monte Carlo (HMC) [36] [37] to sample from the
posterior distribution of the model parameters. We run our simulations using
microMEGAS v5.2.13 [18] with SOFTSUSY v.4.1.7 [38] backend. Our entire
codebase is open-source and can be found here:
https://www.github.com/jtamanas/MSSM . All computations were run on a machine
with an AMD Ryzen 7 3700X processor, 16 GB of RAM, and no GPU.

## References

  * Chung  _et al._ [2005] D. J. H. Chung, L. L. Everett, G. L. Kane, S. F. King, J. D. Lykken, and L.-T. Wang, Phys. Rept. 407, 1 (2005), arXiv:hep-ph/0312378 .
  * Berger  _et al._ [2009] C. F. Berger, J. S. Gainer, J. L. Hewett, and T. G. Rizzo, Journal of High Energy Physics 2009, 023 (2009).
  * AbdusSalam  _et al._ [2010] S. S. AbdusSalam, B. C. Allanach, F. Quevedo, F. Feroz, and M. Hobson, Phys. Rev. D 81, 095012 (2010), arXiv:0904.2548 [hep-ph] .
  * Roszkowski  _et al._ [2015] L. Roszkowski, E. M. Sessolo, and A. J. Williams, Journal of High Energy Physics 2015, 10.1007/jhep02(2015)014 (2015).
  * Bertone  _et al._ [2016] G. Bertone, F. Calore, S. Caron, R. Ruiz, J. S. Kim, R. Trotta, and C. Weniger, Journal of Cosmology and Astroparticle Physics 2016 (04), 037.
  * Van Beekveld  _et al._ [2021] M. Van Beekveld, W. Beenakker, M. Schutten, and J. De Wit, SciPost Phys. 11, 049 (2021), arXiv:2104.03245 [hep-ph] .
  * Alsing  _et al._ [2019] J. Alsing, T. Charnock, S. Feeney, and B. Wandelt, MNRAS 488, 4440 (2019), arXiv:1903.00007 [astro-ph.CO] .
  * Miller  _et al._ [2020] B. K. Miller, A. Cole, G. Louppe, and C. Weniger, arXiv e-prints , arXiv:2011.13951 (2020), arXiv:2011.13951 [astro-ph.IM] .
  * Cole  _et al._ [2021] A. Cole, B. K. Miller, S. J. Witte, M. X. Cai, M. W. Grootes, F. Nattino, and C. Weniger, Fast and credible likelihood-free cosmology with truncated marginal neural ratio estimation (2021).
  * Papamakarios  _et al._ [2018] G. Papamakarios, D. C. Sterratt, and I. Murray, arXiv e-prints , arXiv:1805.07226 (2018), arXiv:1805.07226 [stat.ML] .
  * Papamakarios and Murray [2016] G. Papamakarios and I. Murray, arXiv e-prints , arXiv:1605.06376 (2016), arXiv:1605.06376 [stat.ML] .
  * Hermans  _et al._ [2019] J. Hermans, V. Begy, and G. Louppe, arXiv e-prints , arXiv:1903.04057 (2019), arXiv:1903.04057 [stat.ML] .
  * Lueckmann  _et al._ [2021] J.-M. Lueckmann, J. Boelts, D. S. Greenberg, P. J. Gonçalves, and J. H. Macke, arXiv e-prints , arXiv:2101.04653 (2021), arXiv:2101.04653 [stat.ML] .
  * Hollingsworth  _et al._ [2021] J. Hollingsworth, M. Ratz, P. Tanedo, and D. Whiteson, The European Physical Journal C 81, 10.1140/epjc/s10052-021-09941-9 (2021).
  * Cranmer  _et al._ [2019] K. Cranmer, J. Brehmer, and G. Louppe, arXiv e-prints , arXiv:1911.01429 (2019), arXiv:1911.01429 [stat.ML] .
  * Metropolis  _et al._ [1953] N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, J. Chem. Phys. 21, 1087 (1953).
  * Hastings [1970] W. K. Hastings, Biometrika 57, 97 (1970), https://academic.oup.com/biomet/article-pdf/57/1/97/23940249/57-1-97.pdf .
  * Bélanger  _et al._ [2010] G. Bélanger, F. Boudjema, A. Pukhov, and A. Semenov, Nuovo Cimento C Geophysics Space Physics C 33, 111 (2010), arXiv:1005.4133 [hep-ph] .
  * Neal [2011] R. Neal, in  _Handbook of Markov Chain Monte Carlo_, edited by S. Brooks, A. Gelman, G. Jones, and X.-L. Meng (Chapman and Hall/CRC, 2011) pp. 113–162.
  * Hermans  _et al._ [2021] J. Hermans, A. Delaunoy, F. Rozet, A. Wehenkel, and G. Louppe, arXiv e-prints , arXiv:2110.06581 (2021), arXiv:2110.06581 [stat.ML] .
  * MARTIN [1998] S. P. MARTIN, in  _Perspectives on Supersymmetry_ (WORLD SCIENTIFIC, 1998) pp. 1–98.
  * Djouadi  _et al._ [1999] A. Djouadi, S. Rosier-Lees, M. Bezouh, M. A. Bizouard, C. Boehm, F. Borzumati, C. Briot, J. Carr, M. B. Causse, F. Charles, X. Chereau, P. Colas, L. Duflot, A. Dupperin, A. Ealet, H. El-Mamouni, N. Ghodbane, F. Gieres, B. Gonzalez-Pineiro, S. Gourmelen, G. Grenier, P. Gris, J. F. Grivaz, C. Hebrard, B. Ille, J. L. Kneur, N. Kostantinidis, J. Layssac, P. Lebrun, R. Ledu, M. C. Lemaire, C. LeMouel, L. Lugnier, Y. Mambrini, J. P. Martin, G. Montarou, G. Moultaka, S. Muanza, E. Nuss, E. Perez, F. M. Renard, D. Reynaud, L. Serin, C. Thevenet, A. Trabelsi, F. Zach, and D. Zerwas, arXiv e-prints , hep-ph/9901246 (1999), arXiv:hep-ph/9901246 [hep-ph] .
  * Planck Collaboration  _et al._ [2020] Planck Collaboration, N. Aghanim, Y. Akrami, M. Ashdown, J. Aumont, C. Baccigalupi, M. Ballardini, A. J. Banday, R. B. Barreiro, N. Bartolo, S. Basak, R. Battye, K. Benabed, J. P. Bernard, M. Bersanelli, P. Bielewicz, J. J. Bock, J. R. Bond, J. Borrill, F. R. Bouchet, F. Boulanger, M. Bucher, C. Burigana, R. C. Butler, E. Calabrese, J. F. Cardoso, J. Carron, A. Challinor, H. C. Chiang, J. Chluba, L. P. L. Colombo, C. Combet, D. Contreras, B. P. Crill, F. Cuttaia, P. de Bernardis, G. de Zotti, J. Delabrouille, J. M. Delouis, E. Di Valentino, J. M. Diego, O. Doré, M. Douspis, A. Ducout, X. Dupac, S. Dusini, G. Efstathiou, F. Elsner, T. A. Enßlin, H. K. Eriksen, Y. Fantaye, M. Farhang, J. Fergusson, R. Fernandez-Cobos, F. Finelli, F. Forastieri, M. Frailis, A. A. Fraisse, E. Franceschi, A. Frolov, S. Galeotta, S. Galli, K. Ganga, R. T. Génova-Santos, M. Gerbino, T. Ghosh, J. González-Nuevo, K. M. Górski, S. Gratton, A. Gruppuso, J. E. Gudmundsson, J. Hamann, W. Handley, F. K. Hansen, D. Herranz, S. R. Hildebrandt, E. Hivon, Z. Huang, A. H. Jaffe, W. C. Jones, A. Karakci, E. Keihänen, R. Keskitalo, K. Kiiveri, J. Kim, T. S. Kisner, L. Knox, N. Krachmalnicoff, M. Kunz, H. Kurki-Suonio, G. Lagache, J. M. Lamarre, A. Lasenby, M. Lattanzi, C. R. Lawrence, M. Le Jeune, P. Lemos, J. Lesgourgues, F. Levrier, A. Lewis, M. Liguori, P. B. Lilje, M. Lilley, V. Lindholm, M. López-Caniego, P. M. Lubin, Y. Z. Ma, J. F. Macías-Pérez, G. Maggio, D. Maino, N. Mandolesi, A. Mangilli, A. Marcos-Caballero, M. Maris, P. G. Martin, M. Martinelli, E. Martínez-González, S. Matarrese, N. Mauri, J. D. McEwen, P. R. Meinhold, A. Melchiorri, A. Mennella, M. Migliaccio, M. Millea, S. Mitra, M. A. Miville-Deschênes, D. Molinari, L. Montier, G. Morgante, A. Moss, P. Natoli, H. U. Nørgaard-Nielsen, L. Pagano, D. Paoletti, B. Partridge, G. Patanchon, H. V. Peiris, F. Perrotta, V. Pettorino, F. Piacentini, L. Polastri, G. Polenta, J. L. Puget, J. P. Rachen, M. Reinecke, M. Remazeilles, A. Renzi, G. Rocha, C. Rosset, G. Roudier, J. A. Rubiño-Martín, B. Ruiz-Granados, L. Salvati, M. Sandri, M. Savelainen, D. Scott, E. P. S. Shellard, C. Sirignano, G. Sirri, L. D. Spencer, R. Sunyaev, A. S. Suur-Uski, J. A. Tauber, D. Tavagnacco, M. Tenti, L. Toffolatti, M. Tomasi, T. Trombetti, L. Valenziano, J. Valiviita, B. Van Tent, L. Vibert, P. Vielva, F. Villa, N. Vittorio, B. D. Wandelt, I. K. Wehus, M. White, S. D. M. White, A. Zacchei, and A. Zonca, A&A 641, A6 (2020), arXiv:1807.06209 [astro-ph.CO] .
  * Aad  _et al._ [2012] G. Aad, T. Abajyan, B. Abbott, J. Abdallah, S. Abdel Khalek, A. Abdelalim, O. Abdinov, R. Aben, B. Abi, M. Abolins, _et al._ , Physics Letters B 716, 1 (2012).
  * Chatrchyan  _et al._ [2012] S. Chatrchyan, V. Khachatryan, A. Sirunyan, A. Tumasyan, W. Adam, E. Aguilo, T. Bergauer, M. Dragicevic, J. Erö, C. Fabjan, _et al._ , Physics Letters B 716, 30 (2012).
  * Abi  _et al._ [2021] B. Abi, T. Albahri, S. Al-Kilani, D. Allspach, L. P. Alonzi, A. Anastasi, A. Anisenkov, F. Azfar, K. Badgley, S. Baeßler, I. Bailey, V. A. Baranov, E. Barlas-Yucel, T. Barrett, E. Barzi, A. Basti, F. Bedeschi, A. Behnke, M. Berz, M. Bhattacharya, H. P. Binney, R. Bjorkquist, P. Bloom, J. Bono, E. Bottalico, T. Bowcock, D. Boyden, G. Cantatore, R. M. Carey, J. Carroll, B. C. K. Casey, D. Cauz, S. Ceravolo, R. Chakraborty, S. P. Chang, A. Chapelain, S. Chappa, S. Charity, R. Chislett, J. Choi, Z. Chu, T. E. Chupp, M. E. Convery, A. Conway, G. Corradi, S. Corrodi, L. Cotrozzi, J. D. Crnkovic, S. Dabagov, P. M. De Lurgio, P. T. Debevec, S. Di Falco, P. Di Meo, G. Di Sciascio, R. Di Stefano, B. Drendel, A. Driutti, V. N. Duginov, M. Eads, N. Eggert, A. Epps, J. Esquivel, M. Farooq, R. Fatemi, C. Ferrari, M. Fertl, A. Fiedler, A. T. Fienberg, A. Fioretti, D. Flay, S. B. Foster, H. Friedsam, E. Frlež, N. S. Froemming, J. Fry, C. Fu, C. Gabbanini, M. D. Galati, S. Ganguly, A. Garcia, D. E. Gastler, J. George, L. K. Gibbons, A. Gioiosa, K. L. Giovanetti, P. Girotti, W. Gohn, T. Gorringe, J. Grange, S. Grant, F. Gray, S. Haciomeroglu, D. Hahn, T. Halewood-Leagas, D. Hampai, F. Han, E. Hazen, J. Hempstead, S. Henry, A. T. Herrod, D. W. Hertzog, G. Hesketh, A. Hibbert, Z. Hodge, J. L. Holzbauer, K. W. Hong, R. Hong, M. Iacovacci, M. Incagli, C. Johnstone, J. A. Johnstone, P. Kammel, M. Kargiantoulakis, M. Karuza, J. Kaspar, D. Kawall, L. Kelton, A. Keshavarzi, D. Kessler, K. S. Khaw, Z. Khechadoorian, N. V. Khomutov, B. Kiburg, M. Kiburg, O. Kim, S. C. Kim, Y. I. Kim, B. King, N. Kinnaird, M. Korostelev, I. Kourbanis, E. Kraegeloh, V. A. Krylov, A. Kuchibhotla, N. A. Kuchinskiy, K. R. Labe, J. LaBounty, M. Lancaster, M. J. Lee, S. Lee, S. Leo, B. Li, D. Li, L. Li, I. Logashenko, A. Lorente Campos, A. Lucà, G. Lukicov, G. Luo, A. Lusiani, A. L. Lyon, B. MacCoy, R. Madrak, K. Makino, F. Marignetti, S. Mastroianni, S. Maxfield, M. McEvoy, W. Merritt, A. A. Mikhailichenko, J. P. Miller, S. Miozzi, J. P. Morgan, W. M. Morse, J. Mott, E. Motuk, A. Nath, D. Newton, H. Nguyen, M. Oberling, R. Osofsky, J.-F. Ostiguy, S. Park, G. Pauletta, G. M. Piacentino, R. N. Pilato, K. T. Pitts, B. Plaster, D. Počanić, N. Pohlman, C. C. Polly, M. Popovic, J. Price, B. Quinn, N. Raha, S. Ramachandran, E. Ramberg, N. T. Rider, J. L. Ritchie, B. L. Roberts, D. L. Rubin, L. Santi, D. Sathyan, H. Schellman, C. Schlesier, A. Schreckenberger, Y. K. Semertzidis, Y. M. Shatunov, D. Shemyakin, M. Shenk, D. Sim, M. W. Smith, A. Smith, A. K. Soha, M. Sorbara, D. Stöckinger, J. Stapleton, D. Still, C. Stoughton, D. Stratakis, C. Strohman, T. Stuttard, H. E. Swanson, G. Sweetmore, D. A. Sweigart, M. J. Syphers, D. A. Tarazona, T. Teubner, A. E. Tewsley-Booth, K. Thomson, V. Tishchenko, N. H. Tran, W. Turner, E. Valetov, D. Vasilkova, G. Venanzoni, V. P. Volnykh, T. Walton, M. Warren, A. Weisskopf, L. Welty-Rieger, M. Whitley, P. Winter, A. Wolski, M. Wormald, W. Wu, and C. Yoshikawa (Muon $g-2$ Collaboration), Phys. Rev. Lett. 126, 141801 (2021).
  * Bennett  _et al._ [2006] G. W. Bennett, B. Bousquet, H. N. Brown, G. Bunce, R. M. Carey, P. Cushman, G. T. Danby, P. T. Debevec, M. Deile, H. Deng, W. Deninger, S. K. Dhawan, V. P. Druzhinin, L. Duong, E. Efstathiadis, F. J. M. Farley, G. V. Fedotovich, S. Giron, F. E. Gray, D. Grigoriev, M. Grosse-Perdekamp, A. Grossmann, M. F. Hare, D. W. Hertzog, X. Huang, V. W. Hughes, M. Iwasaki, K. Jungmann, D. Kawall, M. Kawamura, B. I. Khazin, J. Kindem, F. Krienen, I. Kronkvist, A. Lam, R. Larsen, Y. Y. Lee, I. Logashenko, R. McNabb, W. Meng, J. Mi, J. P. Miller, Y. Mizumachi, W. M. Morse, D. Nikas, C. J. G. Onderwater, Y. Orlov, C. S. Özben, J. M. Paley, Q. Peng, C. C. Polly, J. Pretz, R. Prigl, G. zu Putlitz, T. Qian, S. I. Redin, O. Rind, B. L. Roberts, N. Ryskulov, S. Sedykh, Y. K. Semertzidis, P. Shagin, Y. M. Shatunov, E. P. Sichtermann, E. Solodov, M. Sossong, A. Steinmetz, L. R. Sulak, C. Timmermans, A. Trofimov, D. Urner, P. von Walter, D. Warburton, D. Winn, A. Yamamoto, and D. Zimmerman (Muon g-2 Collaboration), Phys. Rev. D 73, 072003 (2006).
  * ATLAS Collaboration [2020] ATLAS Collaboration, European Physical Journal C 80, 123 (2020), arXiv:1908.08215 [hep-ex] .
  * ATLAS Collaboration [2019] ATLAS Collaboration, arXiv e-prints , arXiv:1911.12606 (2019), arXiv:1911.12606 [hep-ex] .
  * Cranmer  _et al._ [2015] K. Cranmer, J. Pavez, and G. Louppe, arXiv e-prints , arXiv:1506.02169 (2015), arXiv:1506.02169 [stat.AP] .
  * Tamanas [2022] J. Tamanas, SaxBI: Likelihood-based Inference with JAX (2022), available at https://github.com/jtamanas/SaxBI, version 1.0.0.
  * Bradbury  _et al._ [2018] J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, and Q. Zhang, JAX: composable transformations of Python+NumPy programs (2018).
  * Heek  _et al._ [2020] J. Heek, A. Levskaya, A. Oliver, M. Ritter, B. Rondepierre, A. Steiner, and M. van Zee, Flax: A neural network library and ecosystem for JAX (2020).
  * Hessel  _et al._ [2020] M. Hessel, D. Budden, F. Viola, M. Rosca, E. Sezener, and T. Hennigan, Optax: composable gradient transformation and optimisation, in jax! (2020).
  * Kingma and Ba [2014] D. P. Kingma and J. Ba, arXiv e-prints , arXiv:1412.6980 (2014), arXiv:1412.6980 [cs.LG] .
  * Phan  _et al._ [2019] D. Phan, N. Pradhan, and M. Jankowiak, arXiv preprint arXiv:1912.11554 (2019).
  * Bingham  _et al._ [2019] E. Bingham, J. P. Chen, M. Jankowiak, F. Obermeyer, N. Pradhan, T. Karaletsos, R. Singh, P. A. Szerlip, P. Horsfall, and N. D. Goodman, J. Mach. Learn. Res. 20, 28:1 (2019).
  * Allanach [2002] B. Allanach, Computer Physics Communications 143, 305–331 (2002).


# Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth

<EMAIL_ADDRESS>
Hasso Plattner Institute
University of Potsdam
Potsdam, Germany  Tobias Friedrich<EMAIL_ADDRESS>
Hasso Plattner Institute
University of Potsdam
Potsdam, Germany  Davis Issac<EMAIL_ADDRESS>
Hasso Plattner Institute
University of Potsdam
Potsdam, Germany  Nikhil Kumar<EMAIL_ADDRESS>
Hasso Plattner Institute
University of Potsdam
Potsdam, Germany  Nadym Mallek<EMAIL_ADDRESS>
Hasso Plattner Institute
University of Potsdam
Potsdam, Germany  Ziena Zeif<EMAIL_ADDRESS>
Hasso Plattner Institute
University of Potsdam
Potsdam, Germany

(November 2022)

###### Abstract

We prove an approximate max-multiflow min-multicut theorem for bounded
treewidth graphs. In particular, we show the following: Given a treewidth-$r$
graph, there exists a (fractional) multicommodity flow of value $f$, and a
multicut of capacity $c$ such that $f\leq c\leq\mathcal{O}(\ln(r+1))\cdot f$.
It is well known that the multiflow-multicut gap on an $r$-vertex (constant
degree) expander graph can be $\Omega(\ln r)$, and hence our result is tight
up to constant factors. Our proof is constructive, and we also obtain a
polynomial time $\mathcal{O}(\ln(r+1))$-approximation algorithm for the
minimum multicut problem on treewidth-$r$ graphs. Our algorithm proceeds by
rounding the optimal fractional solution to the natural linear programming
relaxation of the multicut problem. We introduce novel modifications to the
well-known region growing algorithm to facilitate the rounding while
guaranteeing at most a logarithmic factor loss in the treewidth.

##  1 Introduction

Given an undirected graph with edge capacities and $k$ source-sink pairs, the
_maximum multicommodity flow problem_ asks for the maximum amount of
(fractional) flow that can be routed between the source-sink pairs.
Multicommodity flow problems (and its variants) have been studied extensively
over the last five decades and find extensive applications in VLSI design,
routing and wavelength assignment etc. [ZJM+00].

A natural dual to the maximum multicommodity flow problem is the _minimum
multicut problem_. Given an edge-capacitated graph with $k$ source-sink pairs,
a multicut is a set of edges whose removal disconnects all the source-sink
pairs, and the capacity (or value) of the cut is the sum of capacities of the
edges in it. The value of any feasible multicommodity flow is at most the
capacity of any feasible multicut. The ratio of the values of the minimum
multicut and maximum multicommodity flow is called the _multiflow-multicut
gap_. Minimum multicut is NP-Hard to compute, even in very restricted settings
such as trees [GVY97]. More precisely, it is known to be equivalent to the
vertex cover problem in stars with unit weights [GVY97], which implies that it
is APX-Hard.

There is a rich literature on proving bounds on the multiflow-multicut gap.
Perhaps the most famous of them is the max-flow min-cut theorem of Ford and
Fulkerson [FF09], which states that the value of the minimum multicut is equal
to the maximum (integral) flow when $k=1$. Hu [Hu63] extended the result of
Ford and Fulkerson to show that the multiflow-multicut gap is 1 even when
$k=2$. There are many other special cases where the multiflow-multicut gap is
1, for example when $G$ is a path, but in general it can be arbitrarily large.
Garg, Vazirani, and Yannakakis [GVY96] proved a tight bound of
$\Theta(\ln(k+1))$ on the multiflow-multicut gap for any graph $G$. If $G$ is
a tree, then the multiflow-multicut gap is exactly 2 [GVY97].

For $K_{r}$ minor-free graphs, Tardos and Vazirani [TV93] used the
decomposition theorem of Klein Plotkin and Rao [KPR93] to prove a bound of
$\mathcal{O}(r^{3})$ on the multiflow-multicut gap. This bound was
subsequently improved to $\mathcal{O}(r^{2})$ by Fakcharoenphol and Talwar
[FT03], and then to $\mathcal{O}(r)$ by [AGG+14]. Given any natural number
$n$, there exist graphs on $n$ vertices such that the multiflow-multicut gap
on them is $\Omega(\ln(n+1))$ [GVY96]. This also implies a lower bound of
$\Omega(\ln(r+1))$ for graphs which do not contain $K_{r}$ as a minor. It is
conjectured by [AGG+14] that this lower bound is tight (in fact they state
their conjecture in terms of small diameter padded-decompostion and is
slightly more general):

######  Conjecture 1.

Multiflow-multicut gap for $K_{r}$-minor free graphs is $\Theta(\ln(r+1))$.

Since treewidth $r$ graphs do not contain $K_{r+2}$ as a minor, the above
mentioned results also imply an upper bound of $\mathcal{O}(r)$ for treewidth
$r$ graphs. In fact, [AGG+14] show that their techniques can be extended to
prove a bound of $\mathcal{O}(\log r+\log\log n)$ for treewidth-$r$ graphs. A
lower bound of $\Omega(\ln(r+1))$ on the multiflow-multicut gap for graphs of
treewidth $r$ follows form the discussion above. In this work, we show that
Conjecture 1 is true for graphs of bounded treewidth, which forms an important
subclass of minor-free graphs. In particular, we show that the multiflow-
multicut gap for graphs of treewidth $r$ is $\Theta(\ln(r+1))$. Our proof is
constructive, and we also obtain a polynomial time $\mathcal{O}(\ln(r+1))$
approximation algorithm for the minimum multicut problem on graphs of
treewidth-$r$.

######  Theorem 2.

Let $G=(V,E)$ be a treewidth-$r$ graph with edge capacity
$c:E\rightarrow\mathcal{R}_{\geq 0}$ and $(s_{i},t_{i}),1\leq i\leq k$ be a
set of source-sink pairs. Then there exists a polynomial time computable
multicommodity flow of value $f$ and a multicut of value $c$ such that $f\leq
c\leq\mathcal{O}(\ln(r+1))\cdot f$.

##  2 Preliminaries

Let $G=(V,E)$ be a simple undirected graph with edge capacities $c\colon
E\rightarrow\mathds{Z}_{\geq 0}$. Let $(s_{i},t_{i})$ be the source-sink
pairs. Let $\mathcal{P}$ be the set of all paths in $G$ between a source and
its corresponding sink. A multiflow
$f\colon\mathcal{P}\rightarrow\mathds{R}_{\geq 0}$ is feasible if for every
edge $e\in E$, the total flow on all paths containing the edge,
$\sum_{P:e\in\mathcal{P}}f_{P}$, is at most the capacity of the edge, $c(e)$.
For a path $P\in\mathcal{P}$, we refer to $f_{P}$ as the value of flow on $P$.
A maximum multiflow is a feasible flow $f$ which maximises
$\sum_{P\in\mathcal{P}}f_{P}$. A multicut is a set of edges
$E^{\prime}\subseteq E$ such that every $P\in\mathcal{P}$ contains at least
one edge in $E^{\prime}$. Equivalently, a multicut is a set of edges whose
removal disconnects every source-sink pair. Since a multicut contains an edge
of every path in $\mathcal{P}$, the value of any feasible multicut is at least
the value of any feasible multiflow. The ratio of the minimum multicut to the
maximum multiflow is called the multiflow-multicut gap.

A cut $S\subseteq V$ is a partition of the vertex set $(S,V\setminus S)$. Let
$\delta_{E}(S)$ denote the edges in $E$ with exactly one endpoint in $S$. We
will usually drop the subscript $E$ if it is clear from the context. We may
also subscript by the graph and say $\delta_{G}(S)$. For a subset
$E^{\prime}\subseteq E$ let $c(E^{\prime})$ be the total capacity of edges in
$E^{\prime}$. Given a graph $G=(V,E)$ with edge-length
$l:E\rightarrow\mathds{R}_{\geq 0}$, we denote the length of the shortest
$u,v$ path in $G$ (w.r.t $l$) by $d_{G}(u,v)$, where we may omit the subscript
$G$ if it is clear from the context. Similarly for a set $S$ we use
$d_{G}(u,S)$ or $d(u,S)$ to denote the shortest path between $u$ and $S$.
Whenever we say distance between two vertices we mean the distance $d$ ie. the
shortest path distance w.r.t to $l$. For graph $G=(V,E)$ and
$V^{\prime}\subseteq V$ we will use $G-V^{\prime}$ to denote the graph induced
in $G$ by $V\setminus V^{\prime}$. For a vertex $s$ and value $\alpha$, we use
$\mathcal{B}_{G}(s,\alpha)$ to denote the set of vertices that are a distance
of at most $\alpha$ from $s$. Also, for a vertex set $S$ we use
$\mathcal{B}_{G}(S,\alpha)$ to denote the set of vertices that are a distance
of at most $\alpha$ from $S$. We call $\mathcal{B}_{G}(S,\alpha)$ as the ball
of radius $\alpha$ centered around $S$ in $G$. We will omit the subscript $G$
when it is clear.

A graph $G=(V,E)$ is said to have treewidth at most $r$ if there exist subsets
$S_{1},S_{2},\ldots,S_{m}$ of the vertex set $V$ called bags and a tree $T$
with $S_{1},S_{2},\ldots,S_{m}$ as vertices such that (i) $|S_{i}|\leq r+1$
for $i\in[1,m]$ (ii) for each $(u,v)\in E$, there exists a $j\in[1,m]$ such
that $u,v\in S_{j}$ (iii) for each $v\in V$, the subgraph induced by
$T_{v}=\\{S_{j}\mid v\in S_{j}\\}$ on $T$ is connected. It follows from the
definition that trees have treewidth-1 and any graph on $n$ vertices has
treewidth at most $n$. [FHL05] gave a polynomial time algorithm that computes
a bag decomposition of width $\mathcal{O}(r\cdot\sqrt{\ln(r+1)})$, if $G$ has
a treewidth of at most $r$. We use the above algorithm to compute a bag-
decomposition of size $\mathcal{O}(r\cdot\sqrt{\ln(r+1)})$. Since all our
guarantees are a logarithmic function of the bag-decomposition size, this
approximation does not have any asymptotic effect on our guarantees. For the
sake of presentation, from now on we assume that the tree decomposition of the
graph is given to us.

##  3 Linear Programming Formulation for Mulicut

We first describe an integer programming formulation for the minimum multicut
problem. For every edge $e\in E$, we have a variable $x(e)$, which indicates
if the edge is picked in the cut. We want to disconnect every path between the
source-sink pairs, therefore we have a constraint saying that at least one
edge must be picked on every path between a source-sink pair. Let $d(u,v)$
denote the distance between the vertices $u$ and $v$ by setting the length of
each edge $e\in E$ to be equal to $x(e)$. We drop the integrality constraints
to obtain a linear programming (LP) relaxation for the multicut problem. The
dual of the multicut LP is exactly the maximum multicommodity flow problem
[GVY96]. In particular, we have a non-negative flow variable $f_{P}$ for each
$P\in\mathcal{P}$, and capacity constraints for each edge.

$\displaystyle\min\displaystyle\sum_{e\in E}$ $\displaystyle c(e)x(e)$
$\displaystyle d(s_{i},t_{i})\geq 1$ $\displaystyle\text{ for }1\leq i\leq k$
$\displaystyle 0\leq x(e)$ $\displaystyle\leq 1\text{ for }e\in E$

$\displaystyle\max\displaystyle\sum_{P\in\mathcal{P}}$ $\displaystyle f_{P}$
$\displaystyle\displaystyle\sum_{P:e\in P}f_{P}\leq c(e)$ $\displaystyle\text{
for }e\in E$ $\displaystyle f_{P}\geq 0\text{ for }$ $\displaystyle
P\in\mathcal{P}$

Even though there are an exponential number of constraints, it is well known
that the optimal solution to the above LPs can be computed in polynomial time
[GVY96]. We refer to the optimum solution to the above LP as the minimum
fractional multicut and maximum (fractional) multicommodity-flow. By the
strong duality theorem, the minimum fractional multicut is exactly equal to
the maximum multicommodity flow that can be routed between the source-sink
pairs. If we can construct a multicut with value at most $\alpha\geq 1$ times
the minimum fractional solution, we obtain an $\alpha$-approximation algorithm
for the minimum multicut problem. Furthermore, since the value of any feasible
multicut is at least the value of the minimum fractional multicut, we also
obtain the following approximate max-flow min-cut theorem:

$\text{max-multicommodity-flow}\leq\text{min-
multicut}\leq\alpha\cdot\text{max-multicommodity-flow}$

Garg, Vazirani and Yannakakis [GVY96] gave a region growing algorithm to
obtain a multicut of value at most $\mathcal{O}(\ln(k+1))$ times the minimum
fractional solution. The region growing algorithm was first introduced by
Leighton and Rao [LR99] in the context of sparsest-cut problem. Our algorithm
also builds upon this idea. We next describe the algorithm by [GVY96] in more
detail.

##  4 Region Growing Algorithm

As before, suppose we are given a graph $G=(V,E)$ with edge capacities
$c:E\rightarrow\mathds{R}_{\geq 0}$. Furthermore, we also have a length
function on the edges $l:E\rightarrow\mathds{R}_{\geq 0}$. Recall that for
$S\subseteq V$, $\mathcal{B}(S,t)$ denotes the set of vertices whose distance
from $S$ is at most $t$. We call $\mathcal{B}(S,t)$ the _ball of radius $t$
centred around $S$_. Let $\texttt{Vol}_{G}(S,t)$ be the _volume_ of the edges
contained inside the ball $\mathcal{B}(S,t)$, defined as follows

$\texttt{Vol}_{G}(S,t)=\texttt{Vol}(S,0)+\displaystyle\sum_{\begin{subarray}{c}(u,v)\in
E,\\\ u,v\in\mathcal{B}(S,t)\end{subarray}}c(u,v)\cdot
l(u,v)+\displaystyle\sum_{\begin{subarray}{c}(u,v)\in E,\\\
u\in\mathcal{B}(S,t),v\notin\mathcal{B}(S,t)\end{subarray}}c(u,v)\cdot(t-d(S,u))$
(1)

Here, $\texttt{Vol}(S,0)$ is the _initial volume_ at $S$ and can be chosen to
be any positive real number. We also define $\texttt{Vol}^{\prime}$ to be the
volume without the initial volume ie.,

$\displaystyle\texttt{Vol}^{\prime}_{G}(S,t)=\texttt{Vol}_{G}(S,t)-\texttt{Vol}(S,0).$

Let $C_{G}(S,t)$ be the total capacity of the cut edges going across the set
$\mathcal{B}(s,t)$. More formally,

$C_{G}(S,t)=\displaystyle\sum_{(u,v)\in\delta(\mathcal{B}(s,t))}c(u,v)$

In the above definitions, the subscript $G$ may be omitted when the graph is
clear from context. Given $a,b\in\mathds{R}_{\geq 0}$, we will use
$r\sim\mathds{U}(a,b)$ to denote the fact that $t$ is chosen uniformly at
random in the interval $(a,b)$. [GVY96] showed that if $t\sim\mathds{U}(a,b)$,
then the expected value of $C(S,t)$ can be bounded in terms of
$\texttt{Vol}(S,t)$.

######  Lemma 3.

$\displaystyle\mathop{\mathds{E}}_{t\sim\mathds{U}(a,b)}\left(\dfrac{C(S,t)}{\texttt{Vol}(S,t)}\right)\leq\dfrac{1}{b-a}\cdot\ln\left(\dfrac{\texttt{Vol}(S,b)}{\texttt{Vol}(S,a)}\right)$.

Since there are at most $n$ distinct balls $\mathcal{B}(S,t)$ for any
$S\subseteq V$, the above also implies the existence of a polynomial time
computable $t_{0}\in[a,b)$ such that

$C(S,t_{0})\leq\dfrac{1}{b-a}\cdot\ln\left(\dfrac{\texttt{Vol}(S,b)}{\texttt{Vol}(S,a)}\right)\cdot\texttt{Vol}(S,t_{0})$
(2)

We will refer to this as the region growing lemma 111we follow the
presentation in Section 8.3 of the book by Williamson-Shmoys [WS11]. [GVY96]
use the region growing lemma to construct a multicut as follows. First they
find an optimal solution to the linear programming relaxation for the
multicut, say $\\{x_{e}^{*}\\}_{e\in E}$, and set $l(e)=x^{*}(e)$. The
algorithm picks edges into the multicut as follows: if there exists a
component containing an $(s_{i},t_{i})$ pair, then choose $t\in[0,1/2)$ as
guaranteed by the region growing lemma and include the edges in
$\delta(\mathcal{B}(s_{i},t))$ into the multicut. Since the diameter of the
graph induced by vertices in $\mathcal{B}(s_{i},t)$ is at most $1$, it does
not contain any source-sink pair. Hence, we can safely remove the vertices in
$\delta(\mathcal{B}(s_{i},t))$ from the graph and iterate on the rest of the
graph. The algorithm terminates when no connected component contains an
$(s_{i},t_{i})$ pair. Note that the algorithm picks at most $k$ cuts using
region growing. They set the initial volumes $\texttt{Vol}(s_{i},0)=V^{*}/k$
for $i=1,2,\ldots,k$, where $V^{*}=\sum_{e\in E}c(e)\cdot x^{*}(e)$. Using the
region growing lemma, the cost of the solution can then be bounded by
$\mathcal{O}(\ln(k+1))\cdot V^{*}$.

##  5 Multicuts and Small Diameter Decomposition

Let $G=(V,E)$ be a graph with edge capacities $c:E\rightarrow\mathds{R}_{\geq
0}$ and edge lengths $l:E\rightarrow\mathds{R}_{\geq 0}$. A subset of edges
$E^{\prime}\subseteq E$ is called a small diameter decomposition of $G$ if all
the components of $G^{\prime}=(V,E\setminus E^{\prime})$ have diameter
strictly less than 1 with respect to the distance $d_{G}$ (notice that the
distance is not in $G^{\prime}$)222this is also known as the weak-diameter
decomposition. The cost of the decomposition is the sum of all the edge
capacities in $E^{\prime}$, ie. $c(E^{\prime})$. Note that the small diameter
decomposition corresponds to a feasible multicut when the length of edges
correspond to a feasible (fractional) solution to the linear programming
relaxation of the multicut. If $G$ has treewidth at most $r$, then we will
give a polynomial time algorithm to find a small diameter decomposition whose
cost is $\mathcal{O}\left(\ln(r+1)\right)\cdot\sum_{e\in E}c(e)\cdot l(e)$.
This will give us an $\mathcal{O}\left(\ln(r+1)\right)$-approximation
algorithm for the minimum multicut problem, and also imply a bound of
$\mathcal{O}\left(\ln(r+1)\right)$ on the multiflow-multicut gap for graphs
with treewidth at most $r$. We first show that if there exists a set
$S\subseteq V$ of at most $r$ vertices such that for every vertex $v\in V$,
there exists a $u\in S$ such that $d(u,v)\leq 1/4$, then there exists a small
diameter decomposition with cost $\mathcal{O}(\ln(r+1))\cdot\sum_{e\in
E}c(e)\cdot l(e)$. This lemma will serve as an important building block in our
algorithm for graphs of bounded treewidth.

######  Lemma 4.

Let $G=(V,E)$ be a graph with edge capacities $c:E\rightarrow\mathds{R}_{\geq
0}$ and edge lengths $l:E\rightarrow\mathds{R}_{\geq 0}$. Let $S\subseteq V$
be such that $|S|\leq r$ and for all $u\in V$, $d(u,S)\leq 1/4$. Then there
exists a small diameter decomposition of $G$ with cost at most
$1/8\cdot\ln(r+1)\cdot F$, where $F=\sum_{e\in E}c(e)\cdot l(e)$.

###### Proof.

We may assume w.l.o.g. that $S$ has size exactly $r$. Let
$S=\\{s_{1},s_{2},\ldots,s_{r}\\}$. We will use the region growing lemma to
give such a decomposition. We will have $r$ iterations, and after each
iteration, we will construct a new graph $G_{i}=(V_{i},E_{i})$ and a set of
vertices $S_{i}$. The vertices in $S_{i}$ will have the property that
$d_{G}(u,S_{i})\leq 1/4$ for each vertex $u\in V_{i}$ and $|S_{i}|=r-i$.
Initially, we set $G_{1}=G$ and $S_{1}=S$. In iteration $i$, we use the region
growing lemma in the graph $G_{i}$ to pick a ball centered at $s_{i}\in S_{i}$
with radius $t_{i}\in[1/4,1/2)$ such that:

$C(s_{i},t_{i})\leq
4\cdot\ln\left(\dfrac{\texttt{Vol}(s_{i},1/2)}{\texttt{Vol}(s_{i},1/4)}\right)\cdot\texttt{Vol}(s_{i},t_{i})$

We set $\texttt{Vol}(s_{i},0)=F/r$ and let
$F_{i}=\texttt{Vol}(s_{i},t_{i})-\texttt{Vol}(s_{i},0)$. Since
$\texttt{Vol}(s_{i},1/2)\leq F+\texttt{Vol}(s_{i},0)=F+F/r$ and
$\texttt{Vol}(s_{i},1/4)\geq\texttt{Vol}(s_{i},0)\geq F/r$, we have

$C(s_{i},t_{i})\leq 4\cdot\ln(r+1)\cdot\texttt{Vol}(s_{i},t_{i})\leq
4\cdot\ln(r+1)\cdot(F_{i}+F/r).$

We include all the edges in $\delta(\mathcal{B}(s_{i},t_{i}))\cap E$ in our
small diameter decomposition. We then go on to construct a new graph
$G_{i+1}=(V_{i+1},E_{i+1})$ by first removing the vertices in
$\mathcal{B}(s_{i},t_{i})$ from $G_{i}$. If some $s_{j}\in
S_{i}\setminus\\{s_{i}\\}$ is contained in the set $\mathcal{B}(s_{i},t_{i})$,
then we (re-)introduce the vertex $s_{j}$ to $G_{i+1}$ and connect it to every
other vertex $u\in V_{i}\setminus\mathcal{B}(s_{i},t_{i})$ by an edge of
capacity $0$ and length $d_{G}(s_{j},u)$. It is easy to observe that in
$G_{i+1}$, we have a set $S_{i+1}=\\{s_{i+1},\ldots,s_{r}\\}$ of $r-i$
vertices such that $d_{G}(u,S_{i+1})\leq 1/4$ for all $u\in V_{i+1}$.

We run the above procedure on all the vertices in $S$. Since every vertex of
$G$ is at a distance of at most 1/4 from at least one of the vertices in $S$,
and we pick a ball of radius at least 1/4 from each of the vertices in $S$,
each vertex of $G$ is a part of at least one of the
$\mathcal{B}(s_{j},t_{j})$. Also, each vertex in $\mathcal{B}(s_{j},t_{j})$ is
at a distance of strictly less than $1/2$ from $s_{j}$ and hence any pair of
vertices in $\mathcal{B}(s_{j},t_{j})$ has a distance less than one. Hence,
each vertex is contained in a connected component with diameter at most one
(w.r.t. $d_{G}$), and we have a feasible small diameter decomposition. Using
the fact that $\sum_{i=1}^{r}F_{i}\leq F$, the total cost of the small
diameter decomposition can be bounded by:

$\displaystyle\sum_{i=1}^{r}C(s_{i},t_{i})\leq
4\cdot\ln(r+1)\cdot\displaystyle\sum_{i=1}^{r}\left(F_{i}+\frac{F}{r}\right)=4\cdot\ln(r+1)\cdot\left(F+\displaystyle\sum_{i=1}^{r}F_{i}\right)\leq
8\cdot\ln(r+1)\cdot F$

∎

##  6 Graphs of Width $r$

To simplify the presentation, we will work with a class of graphs that is
slightly more general than graphs of treewidth $r$.

######  Definition 5.

Graphs of width $r$: A graph $G=(V,E)$ is said to have width $r$ if there
exists a partition $\mathcal{S}=\\{S_{1},S_{2},\ldots,S_{m}\\}$ of $V$ and a
rooted tree $T$ with $S_{1},S_{2},\ldots,S_{m}$ as its vertices such that
$|S_{i}|\leq r$ for each $S_{i}\in\mathcal{S}$ and for each $(u,v)\in E$,
there exists a $S_{i},S_{j}\in\mathcal{S}$ such that $S_{j}$ is a parent of
$S_{i}$ and $u,v\in S_{i}\cup S_{j}$. The tree $T$ is called the width-$r$
decomposition of $G$.

Notice that unlike in a tree decomposition, here the bags $S_{i}$ are disjoint
from each other. As before, let $G=(V,E)$ be a graph with edge capacity
$c:E\rightarrow\mathds{R}_{\geq 0}$, edge-length
$l:E\rightarrow\mathds{R}_{\geq 0}$ and $F=\sum_{e\in E}c(e)\cdot l(e)$. It is
easy to see that if $G$ has treewidth $r$, then we can construct an equivalent
graph $G^{\prime}=(V^{\prime},E^{\prime})$ with width $r+1$ as follows: for
each $u\in V$, if $u$ appears in bags $B_{1},B_{2},\ldots,B_{k}$ in the tree
decomposition of $G$, then we replace each appearance of $u$ in the bags by a
new (distinct) vertex, ie. $u_{1},u_{2},\ldots,u_{k}$ respectively.
Furthermore, we connect $u_{i}\in B_{i},u_{j}\in B_{j}$ by an edge of
sufficiently high capacity and zero length if the bags $B_{i},B_{j}$ are
adjacent in the tree decomposition of $G$. For each $(u,v)\in E$, there exists
at least one bag $B_{j}$ of the tree decomposition of $G$ such that $u,v\in
B_{j}$. We add the edge $(u_{j},v_{j})$ to $E^{\prime}$. If there are multiple
bags with the edge, we add only one of the edges. It is straight forward to
verify that $G^{\prime}$ has width at most $r+1$ and $F=\sum_{e\in E}c(e)\cdot
l(e)=\sum_{e\in E^{\prime}}c(e)\cdot l(e)$. An illustration of the transition
from a tree decomposition to a width decomposition can be found in Fig. 1.

Figure 1: Transition from a tree decomposition to a width decomposition. The
red edges are the original edges in $G$ and the blue edges are the added edges
with length zero and high capacity.

Any small diameter decomposition of $G^{\prime}$ does not split copies of the
same vertex in $G$ (as they are connected with edges of very high capacity),
and hence, also corresponds to a small diameter decomposition for $G$ with the
same cost. In the next section, we give an algorithm for computing a small
diameter decomposition for a graph of width $r$.

##  7 Overview of The Algorithm

Our algorithm has three phases. In phase one, we build a collection of sets,
called the cores. The cores form a cover of the vertices in $G$. Furthermore,
for every core $R$, we have a set $Y$ of at most $r$ vertices such that each
vertex of $R$ is close to at least one of the vertices in $Y$. We refer to $Y$
as the center of the core. In phase two, we process the cores in a top down
order w.r.t the width-$r$ decomposition. When processing a core, we use the
region growing algorithm of [GVY96] to pick a set of cut edges and remove
these edges from the graph. Each connected component obtained at the end of
phase two has an associated core and center. Each vertex in the connected
component is close in the original graph $G$ to one of the at most $r$
vertices of its center (though center might not be contained in the
component). Finally, in phase three, we use the algorithm described in Section
5 for each connected component to find a small diameter decomposition. We
prove the following, from which Theorem 2 follows as well.

######  Theorem 6.

Let $G=(V,E)$ be a graph of width at most $r$ with edge capacities
$c:E\rightarrow\mathds{R}_{\geq 0}$ and edge lengths
$l:E\rightarrow\mathds{R}_{\geq 0}$. Then there exists a small diameter
decomposition of $G$ with cost $\mathcal{O}(\ln(r+1))\cdot F$, where
$F=\sum_{e\in E}c(e)\cdot l(e)$. Moreover, such a decomposition can be
constructed in polynomial time.

##  8 The Algorithm

Figure 2: An illustration of the terms used in the algorithm and its analysis.

Let $G=(V,E)$ be a graph with edge-capacity $c:E\rightarrow\mathds{R}_{\geq
0}$ and edge-length $l:E\rightarrow\mathds{R}_{\geq 0}$. We also have two
parameters $a,b\in\mathbb{R}_{\geq 0}$ with $b>a$ for the algorithm. They will
in fact be fixed to $a=1/8$ and $b=1/4$ later.

Let $T(G)$ be the width-$r$ decomposition of $G$. We may omit the brackets and
use just $T$. We define the level of a bag in $T(G)$ to be its hop-distance
from the root of $T(G)$. For a bag $B$ of a subtree $T^{\prime}$ of $T(G)$, we
define $T^{\prime}_{B}$ to be the subtree of $T^{\prime}$ rooted at $B$. For a
subtree $T^{\prime}$ of $T(G)$, we define $V[T^{\prime}]$ to be the union of
all bags in $T^{\prime}$.

Phase 1. Growing Cores: The first phase of the algorithm outputs a set
$\mathcal{R}$ of subsets of the vertex set $V$ whose union covers $V$. Each
set in $\mathcal{R}$ is called a _core_.

During the algorithm, we say that a vertex is _covered_ if it is part of at
least one core constructed so far. For a $V^{\prime}\subseteq V$, we use
$\mathtt{Uncov}(V^{\prime})$ to denote the set of uncovered vertices of
$V^{\prime}$. Also, we say that a bag of $T(G)$ is _covered_ if all the
vertices in the bag are covered. Similarly, a bag is uncovered if one of its
vertices is uncovered.

We associate with each bag $B$ of $T(G)$ an attachment $A(B)\subseteq V$. For
a subtree $T^{\prime}$ of $T(G)$ we use $A[T^{\prime}]$ to denote the union of
attachments of all bags of $T^{\prime}$.

_Initialization:_ We initialize the set of cores $\mathcal{R}$ to $\emptyset$.
The attachment of each bag of $T(G)$ is initialized to $\emptyset$.

We proceed in _iterations_ during Phase 1 until all vertices are covered.
During each iteration we process one by one each connected component
$T^{\prime}$ of the forest induced on $T(G)$ by the uncovered bags of $T(G)$
(note that $T^{\prime}$ gives a rooted subtree of $T(G)$). We process each
such $T^{\prime}$ in a top-down manner as follows (see Fig. 3):

  1. 1.

Mark all bags of $T^{\prime}$ as _unvisited_.

  2. 2.

While there is an unvisited bag in $T^{\prime}$:

    1. (a)

Pick an unvisited bag $B$ of $T^{\prime}$ of the smallest level (breaking ties
arbitrarily).

    2. (b)

In the graph induced in $G$ by $\mathtt{Uncov}(V[T^{\prime}_{B}])\cup
A[T^{\prime}_{B}]$ we pick the ball $\mathcal{B}(\mathtt{Uncov}(B),a)$ as a
new _core_ $R$ into $\mathcal{R}$.

    3. (c)

Mark all the bags of $T^{\prime}$ that intersects $R$ as _visited_.

    4. (d)

If $B$ is not the root of $T^{\prime}$ then add $R$ to the attachment of the
parent bag of $B$.

This finishes the Phase 1 algorithm. The _center_ of a core is defined as the
center from which the ball defining the core was picked during Phase 1. The
following lemmas follow directly from the construction.

######  Lemma 7.

Every vertex $v$ of $G$ is in at least one core in $\mathcal{R}$.

######  Lemma 8.

The center of each core is contained in some bag of $T(G)$. Also, each bag
contains the center of at most one core.

######  Lemma 9.

The cores constructed in the same iteration are vertex disjoint.

We call the bag containing the center of a core to be its _center-bag_. We now
bound the number of iterations of Phase 1.

(a)

(b)

Figure 3: An illustration of two iterations of Phase 1. Note that the
attachment links allow a core of iteration 2 to grow within a core of
iteration 1.

######  Lemma 10.

The Phase 1 of the algorithm has at most r iterations.

###### Proof.

At each iteration of the Phase 1, at least one vertex per bag of each
uncovered bag of $T(G)$ gets $covered$. Since each bag has no more than $r$
elements, the algorithm can not have more than $r$ iterations. ∎

Phase 2. Growing Components: The goal of the second phase is to partition the
graph $G$ into components $\mathcal{S}$ such that each component
$S\in\mathcal{S}$ has a set $Y$ of $r$ vertices in the original graph (not
necessarily in $S$) called its center such that each vertex in $S$ is at a
distance of at most $b$ in $G$ from $Y$. The components will be such that the
capacity of edges going across the components is small.

We will process the cores in $\mathcal{R}$ in a specific top-down order. While
processing a core, we will grow a ball with the core as center, and pick this
as one component. The center of each component will be in fact the center of
the core from which it was grown. The capacity of the edges going across the
components can be bounded as we will pick the radius of the ball as given by
the region growing lemma.

During the second phase algorithm, we will process the cores in a top-down
manner. That is, out of all the unprocessed cores we pick the one whose
center-bag is in the smallest level in $T(G)$ (breaking ties arbitrarily) to
be processed next. Let $\mathcal{R}=\\{R_{1},\ldots,R_{p}\\}$ be the cores in
this top-down order. Each core $R_{i}$ is processed as follows:

We pick a new component $S_{i}$ grown from $R_{i}$ as follows: let
$G_{i}:=G_{i-1}-S_{i-1}$ where $G_{1}=G$. Also, let $R^{\prime}_{i}$ be
defined as $R_{i}-S_{1}-\ldots-S_{i-1}$. If $R^{\prime}_{i}$ is isolated in
$G_{i}$ then take $S_{i}:=R^{\prime}_{i}$. Otherwise take $S_{i}$ as the ball
$\mathcal{B}_{G_{i}}(R^{\prime}_{i},t_{i})$ where $t_{i}\in[0,b-a)$ is given
by the region growing lemma (see Eq. 2) such that

$\displaystyle
C_{G_{i}}(R^{\prime}_{i},t_{i})\leq\dfrac{1}{b-a}\cdot\ln\left(\dfrac{\texttt{Vol}_{G_{i}}(R^{\prime}_{i},b-a)}{\texttt{Vol}(R^{\prime}_{i},0)}\right)\cdot\texttt{Vol}_{G_{i}}(R^{\prime}_{i},t_{i}),$
(3)

where the initial volume $\texttt{Vol}(R^{\prime}_{i},0)$ is set to be
$\texttt{Vol}^{\prime}_{G_{i}}(R^{\prime}_{i},b-a)/h$ where $h=2r^{3}+2r$.

That concludes the processing of a core and also concludes the Phase 2
algorithm. Let $\mathcal{S}=\\{S_{1},\ldots,S_{p}\\}$ denote the set of
components. Let $X_{2}$ be the set of edges of $G$ going across the components
in $\mathcal{S}$. We say that $X_{2}$ is the set of cut-edges picked in Phase
2. In Section 10, we will bound their total capacity to be logarithmic in the
width of the graph. An important property that is used for this is that if
$b=2a$ each edge contributes to the volume
$\texttt{Vol}^{\prime}_{G_{i}}(R^{\prime}_{i},b-a)$ of at most
$\mathcal{O}\left(r^{3}\right)$ many cores. This property will be proved in
Section 9. We now state the required _near to center_ property of components,
which follows just by construction.

######  Lemma 11.

Let $S$ be the component constructed during the processing of core $R$. Let
$Y$ be the center of $R$. All vertices in $S$ are at a distance of at most $b$
from $Y$ in $G$.

Also, we prove that the components indeed give a partition of the vertex set.

######  Lemma 12.

Each vertex $v$ of $G$ is in exactly one component in $\mathcal{S}$.

###### Proof.

Since the vertices in $G_{i}$ does not intersect any component of
$S_{1},\ldots,S_{i-1}$, we have that $v$ cannot be in more than one component.
To see that $v$ should be in a component, recall that it should be in at least
one core $R$. When this core $R$ is processed, $v$ will be picked into the
resulting component, if it has not been picked in any component so far. ∎

Phase 3. Decomposing Components: Each component $S\in\mathcal{S}$ output by
the second phase has the property that there is a set $Y\subseteq V$ called
the center of $S$ containing at most $r$ vertices (not necessarily in $S$)
such that each vertex in $S$ is at most a distance of $b$ away from $Y$. In
the third phase for each component $S$ we make an auxillary graph $G(S)$ on
which we apply Lemma 4. The graph $G(S)$ is obtained by taking the induced
graph of the component $G[S]$ and adding the vertices $Y$ to it. In addition,
for each $y\in Y$ and each $s\in S$, we add edges of capacity $0$ and length
equal to $d_{G}(y,s)$ to $G(S)$. In this auxillary graph we find a small
diameter decomposition of small cost by using Lemma 4. We satisfy the pre-
condition of Lemma 4, if we set $b=1/4$, by using Lemma 11. Note that this
means we should set $a=1/8$ as the condition $b=2a$ is required for bounding
the cost of cut-edges. Let $X^{\prime}(S)$ be the cut-edges of the small
diameter decomposition of $G(S)$ given by Lemma 4, and let $X(S)$ be
$X^{\prime}(S)$ minus the auxilliary edges from $Y$ to $S$. Note that the cost
of $X(S)$ is same as the cost of $X^{\prime}(S)$ and $X(S)$ gives a small
diameter decomposition of $G[S]$ with respect to the distance $d_{G}$. Our
final set of cut-edges giving a small diameter decomposition of $G$ is given
by the union of $X_{2}$ (the cut-edges from Phase 2) and
$X_{3}:=\bigcup_{S\in\mathcal{S}}X(S)$.

######  Lemma 13.

The set of cut-edges $X_{2}\cup X_{3}$ gives a small diameter decomposition of
$G$.

###### Proof.

Once we remove $X_{2}$ there are no edges going across the components in
$\mathcal{S}$ output by Phase 2. Within each of those components Lemma 4
guarantees that after removing $X(S)$ the remaining connected components have
a diameter strictly less than one with respect to the distance $d_{G}$. Thus
we have a small diameter decomposition of $G$. ∎

We will bound the cost of $X_{2}\cup X_{3}$ in the next two sections.

##  9 Bounding the Volume Contributions of an Edge

We want to upper bound the capacity of edges going across components produced
by Phase 2. For this, it is clearly sufficient to bound the capacity of
$\delta(S_{i})$ in the graph $G_{i}$, for each core $R_{i}$, because when we
process a core $R_{i}$ in Phase 2, we consider only the graph $G_{i}$. Thus we
want to bound the capacity of
$\delta_{G_{i}}(\mathcal{B}_{G_{i}}(R^{\prime}_{i},t_{i}))$, where $t_{i}<b-a$
is the radius that satisfies Eq. 3. In Eq. 3, notice that to bound the
capacity, we use the volume of the ball
$\mathcal{B}_{G_{i}}(R^{\prime}_{i},b-a)$, whereas we remove only
$S_{i}=\mathcal{B}_{G_{i}}(R^{\prime}_{i},t_{i})$ afterwards. Thus, it is
possible that the edges of the graph
$G[\mathcal{B}_{G_{i}}(R^{\prime}_{i},b-a)\setminus\mathcal{B}_{G_{i}}(R^{\prime}_{i},t_{i})]$
are used to pay for certain cut edges for components arising in the processing
of subsequent cores. Our goal in this section is to bound the number of times
an edge can be used to pay for the cut-edges of a component with respect to
the width of the graph, as described in the following lemma.

######  Lemma 14.

Let $e$ be an edge of $G$. The number of cores $R_{i}$ for which $e$ appears
(even partially) in $\mathcal{B}_{G_{i}}(R^{\prime}_{i},b-a)$ during the
processing of $R_{i}$ in Phase 2 is at most $2r^{3}+2r$.

The rest of this section is devoted to proving the above lemma. We begin by
introducing some definitions. We say that a core has _rank_ $i$ if it was
constructed in the $i$-th iteration of phase 1. We define the rank of a vertex
to be the lowest rank among all the cores containing it. For each core we
define its _center-bag_ to be the bag of $T(G)$ that contains its center. We
say that a core $R_{1}$ is an ancestor (descendant resp.) of $R_{2}$ if the
center-bag of $R_{1}$ is an ancestor (descendant resp.) of $R_{2}$. For any
bag of $T(G)$ we define its _level_ to be the hop distance from the root in
$T(G)$. Also, we define the _graph rooted at $B$_ to be the subgraph of $G$
induced by the subtree of $T(G)$ rooted at $B$. For any core $R$ we denote by
$G_{T}[R]$ to be the graph rooted at the center-bag of $R$. Let $H(R)$ denote
the set of cores that are ancestors of $R$ and have rank strictly less than
$R$. We define the _shadow-domain_ of a core $R$ to be the graph obtained from
$G_{T}[R]$ by removing the vertices that are contained in at least one core in
$H(R)$. Note that the shadow domain of a core $R_{i}$ in phase $2$ is a super-
graph of the graph $G_{i}$. The _shadow_ $Q$ of a core $R$ is defined as the
ball of radius $b-a$ centered around $R$ in the shadow-domain of $R$. Note
that the shadow of of a core $R_{i}$ in phase 2 contains
$\mathcal{B}_{G_{i}}(R^{\prime}_{i},b-a)$. The _strict shadow_ of $R$ is
defined as its shadow minus itself, ie. $Q\setminus R$.

(a)

(b)

Figure 4: An illustration of the graph $G_{T}[R]$, shadow-domain, and shadow.

Next, we will prove some lemmas useful for proving the main lemma of this
section. The following two statements bounds the number of intersecting cores.

######  Lemma 15.

The number of cores intersecting any bag is at most $r^{2}$.

###### Proof.

First, let us determine an upper bound for the number of cores of the same
rank that can be intersecting a given bag $B\in T(G)$. The cores of the same
rank are disjoint by Lemma 9. Hence there can at most be $r$ of them
intersecting $B$ because $|B|\leq r$. Then, since the rank of each core is in
$[r]$ by Lemma 10 we have that the total number of cores intersecting any bag
is at most $r^{2}$. ∎

The following also follows from the Phase 1 algorithm.

######  Lemma 16.

If $B$ is a bag containing the center $Y$ of a core that has rank $i$ then all
the vertices in $B\setminus Y$ have a rank strictly lower than $i$.

###### Proof.

In case a bag $B$ contains a center $Y$ that does not contain all vertices of
$B$, ie. $B\setminus Y\neq\emptyset$, then as explained above $B\setminus Y$
have to be covered by the previously constructed cores. Those cores must have
been constructed in previous iterations, by construction. This implies that
the vertices in $B\setminus Y$ have a strictly lower rank than the vertices in
$Y$. ∎

The use of Lemma 16 allows to prove a relation between ranks and shadow-
domains.

######  Lemma 17.

Let $R_{1}$ and $R_{2}$ be two cores such that the rank of $R_{1}$ is greater
than or equal to that of $R_{2}$ and $R_{1}$ is an ancestor of $R_{2}$. Let
$B$ be the center-bag of $R_{2}$ and let $Y$ be the center of $R_{2}$. If the
shadow-domain of $R_{1}$ intersects $B\setminus Y$ then there is a core
$R_{3}$ that is an ancestor of $R_{2}$ and descendant of $R_{1}$ and has rank
strictly smaller than the rank of $R_{2}$ .

###### Proof.

Let $x$ be a vertex in the intersection of the shadow-domain of $R_{1}$ and
$B\setminus Y$. By Lemma 16 it follows that $x$ has a rank strictly lower than
the rank of $R_{2}$. Thus $x$ is contained in a core $R_{3}$ that has rank
strictly lower than $R_{2}$. Also, $R_{3}$ is a descendant of $R_{1}$ as
otherwise none of the vertices in $R_{3}$ and in particular $x$ is not in the
shadow-domain of $R_{1}$. Finally, $R_{3}$ is an ancestor of $R_{2}$ as the
center-bag of $R_{2}$ contains vertices of $R_{3}$. ∎

The next observation will also help towards proving the main lemma of the
section.

######  Lemma 18.

Let $R_{1}$ and $R_{2}$ be two cores such that the rank of $R_{1}$ is strictly
greater than that of $R_{2}$, and $R_{1}$ is an ancestor of $R_{2}$.
Furthermore, suppose that there are no cores of rank smaller than $R_{2}$
whose center-bag is in the path between the center-bags of $R_{1}$ and
$R_{2}$. In $G_{T}[R_{2}]$, every vertex in the shadow-domain of $R_{1}$ is in
the shadow-domain of $R_{2}$.

###### Proof.

Let $x$ be a vertex in $G_{T}[R_{2}]$ that is not in the shadow-domain of
$R_{2}$. It suffices to prove that $x$ is not in the shadow-domain of $R_{1}$.
Since $x$ is not in the shadow-domain of $R_{2}$ there should be an ancestor
core $R_{3}$ of $R_{2}$ having rank smaller than $R_{2}$ containing $x$. By
the precondition of the lemma, the core $R_{3}$ has to be an ancestor of also
$R_{1}$. This means that $x$ cannot be in the shadow-domain of $R_{1}$. ∎

We use all the above properties to prove the following lemma, from which the
main lemma of the section follows rather directly.

######  Lemma 19.

If $b=2a$ in our algorithm, then for any vertex $u$, the number of cores whose
strict shadow contains $u$ is at most $r^{3}$.

###### Proof.

Consider a vertex $u$. Let $\mathfrak{C}$ be the set of cores whose strict
shadow contains $u$. So, our goal is to prove that $|\mathfrak{C}|\leq r^{3}$.

Let $P$ be the path in $T(G)$ from the root bag to the bag containing $u$. The
center-bags of the cores in $\mathfrak{C}$ are all on $P$. This comes from the
fact that the shadow-domain of a core is a subgraph of the graph rooted at its
center-bag.

Let $r_{1}$ be the lowest rank among all cores in $\mathfrak{C}$. We will show
that there is only one core in $\mathfrak{C}$ having rank $r_{1}$ in 20. Let
this unique core in $\mathfrak{C}$ with rank $r_{1}$ be $P_{1}$. Let
$\mathfrak{C}_{1}$ be the set of all cores in $\mathfrak{C}$ (including
$P_{1}$) that are ancestors of $P_{1}$. We will show that each core in
$\mathfrak{C}_{1}$ intersects the center of $P_{1}$ in 21. Since the center is
contained in a bag, by Lemma 15 this implies that $|\mathfrak{C}_{1}|\leq
r^{2}$.

Now, let $\bar{\mathfrak{C}}_{1}=\mathfrak{C}\setminus\mathfrak{C}_{1}$. If
$\bar{\mathfrak{C}}_{1}$ is non-empty, define $r_{2}$ be the lowest rank among
cores in $\bar{\mathfrak{C}_{1}}$. Note that $r_{2}>r_{1}$. We show that there
is only one core in $\bar{\mathfrak{C}}_{1}$ having rank $r_{2}$ in 20. Let
this unique core in $\bar{\mathfrak{C}}_{1}$ with rank $r_{2}$ be $P_{2}$. Let
$\mathfrak{C}_{2}$ be the set of all ancestor cores $P_{2}$ in
$\bar{\mathfrak{C}}_{1}$ including $P_{2}$. We show that each core in
$\mathfrak{C}_{2}$ intersects the center of $P_{2}$ in 21. Since the center is
contained in a bag, by Lemma 15 this implies that $|\mathfrak{C}_{2}|\leq
r^{2}$.

We repeat the procedure and define the sequences
$\mathfrak{C}_{1},\mathfrak{C}_{2},\mathfrak{C}_{3},\dots,\mathfrak{C}_{\ell}$
and $r_{1}<r_{2}<\dots<r_{\ell}$ until
$\bar{\mathfrak{C}}_{\ell}=\bar{\mathfrak{C}}_{\ell-1}\setminus\mathfrak{C}_{\ell}$
is empty, where $\bar{\mathfrak{C}}_{0}=\mathfrak{C}$. Here, $r_{j}$ is
defined as the lowest rank among cores in $\bar{\mathfrak{C}}_{j-1}$. For each
$j\in[\ell]$, we show that there is a unique core $P_{j}$ in
$\bar{\mathfrak{C}}_{j-1}$ with rank $r_{j}$ in 20. Let $\mathfrak{C}_{j}$ be
the set of all cores in $\bar{\mathfrak{C}}_{j}$ that are ancestors of $P_{j}$
(including $P_{j}$). Also, we show that all cores in $\mathfrak{C}_{j}$
intersects the center of $P_{j}$ in 21, implying that $|\mathfrak{C}_{j}|\leq
r^{2}$ for each $j\in[\ell]$. Since $r_{1}<r_{2}<\dots<r_{\ell}\leq r$, this
implies that $|\mathfrak{C}|\leq r^{3}$.

Thus, the proof of the lemma concludes by proving the following claims.

######  Claim 20.

There is only one core in $\bar{\mathfrak{C}}_{j-1}$ having rank $r_{j}$ for
each $j\in[\ell]$.

###### Proof.

Suppose this is not true. Then there are two cores $R_{1}$ and $R_{2}$ in
$\bar{\mathfrak{C}}_{j-1}$ having rank $r_{j}$. Assume without loss of
generality that $R_{1}$ is an ancestor of $R_{2}$. Note that $R_{1}$ and
$R_{2}$ are disjoint as they have the same rank. Also, since
$R_{1},R_{2}\in\mathfrak{C}$, the center-bags of $R_{1}$ and $R_{2}$ lie on
the path $P$.

Since $u$ is in the shadow of $R_{1}$ there is a path $Z$ of length at most
$b$ that goes from the center of $R_{1}$ to $u$ in the shadow-domain of
$R_{1}$. This path $Z$ has to intersect the center-bag of $R_{2}$ to get to
$u$.

Suppose this intersection occurs at a vertex in the center of $R_{2}$. Then
the path $Z$ goes from the center of $R_{1}$ to outside $R_{1}$ and then into
the center of $R_{2}$ and then to outside of $R_{2}$. It has to go outside of
$R_{2}$ as $u$ is in the strict shadow of $R_{2}$. Also, it has to go outside
of $R_{1}$ before entering $R_{2}$ as $R_{1}$ and $R_{2}$ are disjoint
(however, it is possible that there is an edge from $R_{1}$ to $R_{2}$). This
means $Z$ has a length of more than $a+a=2a=b$, a contradiction.

Now, suppose this intersection occurs at a vertex in the center-bag of $R_{2}$
that is not in the center of $R_{2}$. Then by Lemma 17 it follows that there
is at least one core that is ancestor of $R_{2}$ and descendant of $R_{1}$,
and having rank lower than $r_{j}$. Let $R_{3}$ be the one among such cores
whose center-bag has the smallest level.

We claim that the path $Z$ intersects the center of $R_{3}$. Suppose
otherwise. However, the path has to intersect the center-bag of $R_{3}$ to get
to $u$. Then, by Lemma 17 it follows that there is a core that is ancestor of
$R_{3}$ and descendant of $R_{1}$, and having rank lower than $r_{j}$, a
contradiction to the selection of $R_{3}$.

Note that $u$ is not in $R_{3}$ as $R_{3}$ is disjoint from the shadow-domain
of $R_{2}$ by definition of shadow-domain. However, $u$ is contained in the
shadow of $R_{3}$ as the part of the path $Z$ from the center of $R_{3}$ to
$u$ is contained in the shadow-domain of $R_{3}$ (by Lemma 18) and has length
at most $b$. Thus, $u$ is contained in the strict shadow of $R_{3}$. Since
$R_{3}$ is a descendant of $R_{1}$, we have that
$R_{3}\notin\mathfrak{C}_{1}\cup\mathfrak{C}_{2}\cup\dots\cup\mathfrak{C}_{j-1}$
and hence $R_{3}\in\bar{\mathfrak{C}}_{j-1}$. Thus, there is a core in
$\bar{\mathfrak{C}}_{j-1}$ that has rank lower than $r_{j}$, a contradiction
to the choice of $r_{j}$. ∎

######  Claim 21.

Each core in $\mathfrak{C}_{j}$ intersects the center of $P_{j}$ for each
$j\in[\ell]$.

###### Proof.

Suppose this is not true. Then there is a core $R\in\mathfrak{C}_{j}$ that is
disjoint from the center of $P_{j}$. Note that $P_{j}$ is a descendant of $R$
by definition of $\mathfrak{C}_{j}$ and the rank of $P_{j}$ is less than the
rank of $R$ by the definition of $P_{j}$. Since $u$ is in the shadow of $R$
there is a path $Z$ of length at most $b$ that goes from the center of $R$ to
$u$ in the shadow-domain of $R$. This path $Z$ has to intersect the center-bag
of $P_{j}$ to get to $u$.

Suppose this intersection occurs at a vertex in the center of $P_{j}$. Then
the path $Z$ goes from the center of $R$ outside $R$ and then into the center
of $P_{j}$ and then to outside of $P_{j}$. It has to go outside of $P_{j}$ as
$u$ is in the strict shadow of $P_{j}$. Also, it has to go outside of $R$
before entering $P_{j}$ as $R$ and the center of $P_{j}$ are disjoint. This
means $Z$ has a length of more than $a+a=2a=b$, a contradiction.

Now, suppose this intersection occurs at a vertex in the center-bag of $P_{j}$
that is not in the center of $P_{j}$. Then, by Lemma 17, there exist at least
one core that is an ancestor of $P_{j}$ and a descendant of $R$ and having
rank lower than $r_{j}$. Let $R^{\prime}$ be the one among such cores whose
center-bag has the smallest level. The path $Z$ has to intersect the center of
$R^{\prime}$ as otherwise there is a core that is an ancestor of $R^{\prime}$
and a descendant of $R$ and having rank lower than $r_{j}$, contradicting the
selection of $R^{\prime}$.

Note that $u$ is not in $R^{\prime}$ as $R^{\prime}$ is disjoint from the
shadow-domain of $R$ by definition of shadow-domain. However, $u$ is contained
in the shadow of $R^{\prime}$ as the the part of the path $Z$ from center of
$R^{\prime}$ to $u$ is contained in the shadow-domain of $R^{\prime}$ (by
Lemma 18) and has length at most $b$. Thus, $u$ is contained in the strict
shadow of $R^{\prime}$. This implies that $R^{\prime}\in\mathfrak{C}_{j}$.
Thus we have a core in $\mathfrak{C}_{j}$ having rank strictly smaller than
$r_{j}$, a contradiction. ∎

∎

###### Proof of Lemma 14.

Each vertex $u$ appears in the strict shadow of at most $r^{3}$ cores by Lemma
19. Also, any vertex can only intersect one core of a fixed rank, and hence
the total number of cores intersecting a vertex $u$ is at most $r$. Thus, each
vertex $u$ appears in the shadow of at most $r^{3}+r$ cores. This implies that
for any edge $(u,v)$, the number of cores such that at least one of $u$ or $v$
appear in the shadow is at most $2r^{3}+2r$. Observe that by construction, the
shadow of a core $R_{i}$ contains the ball
$\mathcal{B}_{G_{i}}(R^{\prime}_{i},b-a)$. This implies the lemma. ∎

##  10 Bounding the Total Weight of Cut Edges

######  Lemma 22.

If $b=2a>0$ in our algorithm, then the total capacity of the cut edges $X_{2}$
picked in the second phase is at most $\dfrac{16}{a}\cdot\ln(r+1)\cdot F^{*}$,
where $F^{*}=\sum_{e\in E}c(e)\cdot l(e)$.

###### Proof.

Let $R_{i},S_{i},G_{i},R^{\prime}_{i},t_{i}$ be as in Phase 2 description.
Note that the set of cut-edges $X_{2}$ in Phase $2$ is equal to
$\bigcup\delta_{G_{i}}(S_{i})$. Thus the cost of $X_{2}$ can be bounded by
$\sum_{i\in[p]}C_{G_{i}}(R^{\prime}_{i},t_{i})$. Recall that we selected
$t_{i}$ in Phase 2 algorithm such that

$\displaystyle C_{G_{i}}(R^{\prime}_{i},t_{i})$
$\displaystyle\leq\dfrac{1}{b-a}\cdot\ln\left(\dfrac{\texttt{Vol}_{G_{i}}(R^{\prime}_{i},b-a)}{\texttt{Vol}(R^{\prime}_{i},0)}\right)\cdot\texttt{Vol}_{G_{i}}(R_{i}^{\prime},t_{i})$

Also, recall that for a core $R_{i}$, the initial volume
$\texttt{Vol}(R^{\prime}_{i},0)$ was chosen to be
$\texttt{Vol}^{\prime}_{G_{i}}(R^{\prime}_{i},b-a)/h$ where $h=2r^{3}+2r$. By
Lemma 14, any edge $(u,v)$ contributes at most $h$ times to the sum
$\sum_{i\in[p]}\texttt{Vol}^{\prime}_{G_{i}}\left(R^{\prime}_{i},b-a\right)$
and we obtain the following:

######  Claim 23.

$\sum_{i\in[p]}\dfrac{\texttt{Vol}^{\prime}_{G_{i}}\left(R^{\prime}_{i},b-a\right)}{h}\leq\sum_{e\in
E}c(e)\cdot l(e)=F^{*}$

Thus,

$\displaystyle C_{G_{i}}(R^{\prime}_{i},t_{i})$
$\displaystyle\leq\dfrac{1}{b-a}\cdot\ln\left(\dfrac{\texttt{Vol}_{G_{i}}(R^{\prime}_{i},b-a)}{\texttt{Vol}(R^{\prime}_{i},0)}\right)\cdot\texttt{Vol}_{G_{i}}(R_{i}^{\prime},t_{i})$
$\displaystyle=\dfrac{1}{b-a}\cdot\ln\left(\dfrac{\texttt{Vol}(R^{\prime}_{i},0)+\texttt{Vol}^{\prime}_{G_{i}}(R^{\prime}_{i},b-a)}{\texttt{Vol}(R^{\prime}_{i},0)}\right)\cdot\texttt{Vol}_{G_{i}}(R_{i}^{\prime},t_{i})$
$\displaystyle=\dfrac{1}{b-a}\cdot\ln\left(1+\dfrac{\texttt{Vol}^{\prime}_{G_{i}}(R^{\prime}_{i},b-a)}{\texttt{Vol}^{\prime}_{G_{i}}(R^{\prime}_{i},b-a)/h}\right)\cdot\texttt{Vol}_{G_{i}}(R_{i}^{\prime},t_{i})$
$\displaystyle=\dfrac{1}{b-a}\cdot\ln\left(1+h\right)\cdot\texttt{Vol}_{G_{i}}(R_{i}^{\prime},t_{i})$

Summing now up over all coresets yields:

$\displaystyle\sum_{i\in[p]}C_{G_{i}}(R^{\prime}_{i},t_{i})$
$\displaystyle\leq\sum_{i\in[p]}\dfrac{1}{b-a}\cdot\ln\left(1+h\right)\cdot\texttt{Vol}_{G_{i}}(R_{i}^{\prime},t_{i})$
$\displaystyle=\dfrac{1}{a}\cdot\ln\left(2r^{3}+2r+1\right)\cdot\sum_{i\in[p]}\texttt{Vol}_{G_{i}}(R_{i}^{\prime},t_{i})$
$\displaystyle\leq\dfrac{8\cdot\ln(r+1)}{a}\cdot\sum_{i\in[p]}\left(\dfrac{\texttt{Vol}^{\prime}_{G_{i}}(R_{i}^{\prime},b-a)}{h}+\texttt{Vol}^{\prime}_{G_{i}}(R_{i}^{\prime},t_{i})\right)$
$\displaystyle\leq\dfrac{8\cdot\ln(r+1)}{a}\cdot(F^{*}+F^{*})=\dfrac{16\cdot\ln(r+1)}{a}\cdot
F^{*}$

The last inequality follows from Claim 23 and the fact that any edge
contributes to at most one term in
$\texttt{Vol}^{\prime}_{G_{i}}\left(R_{i}^{\prime},t_{i})\right)$. ∎

Proof of Theorem 6 : We showed in Lemma 13 that $X_{2}\cup X_{3}$ gives a
small diameter decomposition. It only remains to bound the cost of $X_{2}\cup
X_{3}$. Lemma 22 gives a bound on the total capacity of edges in $X_{2}$. It
follows directly from Lemma 4 the capacity of $X_{3}$ used in Phase 3 is at
most $8\cdot\ln(r+1)\cdot F^{*}$. Hence the total cost of the small diameter
decomposition is at most $8\cdot\ln(r+1)\cdot F^{*}+128\cdot\ln(r+1)\cdot
F^{*}=136\cdot\ln(r+1)\cdot F^{*}$. This completes the proof of Theorem 6.

##  11 Concluding Remarks

In this paper, we give an algorithm for finding low diameter decomposition of
small cost for bounded treewidth graphs, more specifically with a cost
logarithmic in treewidth. Our result also imples a multiflow-multicut gap and
an approximation ratio for multicut that is logarithmic in treewidth. These
results are tight asymptotically. We believe that our techniques could provide
useful insights for proving such a (tight) result for the class of
$K_{r}$-minor-free graphs. We also believe that it should be possible to
extend our techniques for constructing low-diameter padded decomposition for
bounded treewidth graphs (see [AGG+14] for the definition of padded
decomposition).

## References

  * [AGG+14] Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar.  Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 79–88, 2014.
  * [FF09] Lester Randolph Ford and Delbert R Fulkerson.  Maximal flow through a network.  In Classic papers in combinatorics, pages 243–248. Springer, 2009\.
  * [FHL05] Uriel Feige, MohammadTaghi Hajiaghayi, and James R Lee.  Improved approximation algorithms for minimum-weight vertex separators.  In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 563–572, 2005.
  * [FT03] Jittat Fakcharoenphol and Kunal Talwar.  An improved decomposition theorem for graphs excluding a fixed minor.  In Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques, pages 36–46. Springer, 2003.
  * [GVY96] Naveen Garg, Vijay V Vazirani, and Mihalis Yannakakis.  Approximate max-flow min-(multi) cut theorems and their applications.  SIAM Journal on Computing, 25(2):235–251, 1996.
  * [GVY97] Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis.  Primal-dual approximation algorithms for integral flow and multicut in trees.  Algorithmica, 18(1):3–20, 1997.
  * [Hu63] T Chiang Hu.  Multi-commodity network flows.  Operations research, 11(3):344–360, 1963.
  * [KPR93] Philip Klein, Serge A Plotkin, and Satish Rao.  Excluded minors, network decomposition, and multicommodity flow.  In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 682–690. ACM, 1993.
  * [LR99] Tom Leighton and Satish Rao.  Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.  Journal of the ACM (JACM), 46(6):787–832, 1999.
  * [TV93] Eva Tardos and Vijay V Vazirani.  Improved bounds for the max-flow min-multicut ratio for planar and $K_{r,r}$-free graphs.  Information Processing Letters, 47(2):77–80, 1993.
  * [WS11] David P Williamson and David B Shmoys.  The design of approximation algorithms.  Cambridge university press, 2011.
  * [ZJM+00] Hui Zang, Jason P Jue, Biswanath Mukherjee, et al.  A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks.  Optical networks magazine, 1(1):47–60, 2000.