Improved Upper Bounds on Multiflow-Multicut Gaps in Cactus Graphs

Kalantarzadeh, Sina; Kumar, Nikhil

doi:10.4230/LIPIcs.FSTTCS.2025.40

Improved Upper Bounds on Multiflow-Multicut Gaps in Cactus Graphs

Sina Kalantarzadeh

University of Waterloo, Waterloo, Canada Nikhil Kumar

Tata Institute of Fundamental Research, Mumbai, India

Abstract

Given a set of source-sink pairs, the maximum multiflow problem asks for the largest total amount of flow that can be feasibly routed between them. The minimum multicut problem, which is dual to multiflow, seeks the lowest-cost set of edges whose removal disconnects all source-sink pairs. It is straightforward to see that the value of a minimum multicut is at least that of the corresponding maximum multiflow. The ratio between the two is known as the multiflow-multicut gap. The classical max-flow min-cut theorem tells us that this gap is exactly one when there is only a single source-sink pair. However, for multiple source-sink pairs, the gap can be arbitrarily large. In this work, we investigate the multiflow-multicut gap in cactus graphs, and establish the following results (i) tight upper bound of 1.5 for cycle (ii) an upper bound of $2+\frac{2}{\ln 2}<3.45$ for general cactus graph (iii) tight upper bound of 2 for unicyclic graphs, where the graph contains exactly one cycle (iv) tight upper bound of 2 for path cactus graphs, where cycles are arranged along a single path. We develop novel generalizations of the classical rounding algorithm to establish our results.

Keywords and phrases:

Approximation Algorithms, Randomized Algorithms, Linear Programming, Graph Algorithms, Multicut, Multicommodity flow

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Approximation algorithms analysis ; Mathematics of computing

\rightarrow

Approximation algorithms

Acknowledgements:

We thank Joseph Cheriyan for many helpful discussions throughout this project. We are also grateful to Hadas Barabash and Tom Iagovet for their work and insights during Summer 2024, which contributed to these results.

Funding:

The work was done while the second author was a postdoctoral researcher at the University of Waterloo and was supported in part by J. Cheriyan’s NSERC Discovery Grant RGPIN-2024-04473 and C. Swamy’s NSERC Discovery Grant RGPIN-2024-04532.

DOI:

10.4230/LIPIcs.FSTTCS.2025.40

Event:

45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Editors:

C. Aiswarya, Ruta Mehta, and Subhajit Roy

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Given an edge-weighted graph with $k$ source-sink pairs, a multicut is a set of edges whose removal separates each source from its corresponding sink. The minimum multicut problem aims to find such a multicut with the smallest possible total edge weight. This problem generalizes the classical minimum $s$ - $t$ cut problem and has been extensively studied. Notably, computing the minimum multicut is NP-hard, even on simple graph classes such as trees [10].

Closely related to the multicut problem is the multicommodity flow problem (or multiflow), where the objective is to maximize the total flow that can be simultaneously routed between the source-sink pairs. When the flow is required to be integral, the problem becomes the maximum integer multiflow problem, a generalization of the well-known edge-disjoint paths problem. Since every source-sink path must cross some edge in any feasible multicut, the value of any multicut provides an upper bound on the value of any feasible multiflow.

In fact, the natural linear programming (LP) relaxation of the multicut problem is the dual of the LP formulation of the multiflow problem. The ratio between the cost of the minimum multicut and the value of the maximum multicommodity flow is known as the multiflow–multicut gap. By LP strong duality, this ratio also bounds the integrality gap of the LP relaxation of the multicut problem, and vice versa.
The celebrated max-flow min-cut theorem [7] states that the multiflow–multicut gap is exactly 1 when $k=1$ , i.e., for a single source-sink pair. A classic result by Hu [11] extends this and shows that the gap remains 1 when $k=2$ . However, the equality fails when $k\geq 3$ , even on very simple graphs (see [10] for an example).
Garg, Vazirani, and Yannakakis [9] established a tight bound of $\Theta(\log k)$ on the multiflow–multicut gap in general graphs. For trees, the gap is exactly 2 [10]. For $K_{r}$ -minor-free graphs, Tardos and Vazirani [16] used the decomposition theorem of Klein, Plotkin, and Rao [15] to obtain an upper bound of $\mathcal{O}(r^{3})$ . Building on a long sequence of results [5, 1, 8, 6], Conroy and Filtser [3] recently proved an asymptotically tight bound of $\Theta(\log r)$ on the multiflow–multicut gap for $K_{r}$ -minor-free graphs.

The primary motivation behind the aforementioned works was to establish asymptotic bounds on the integrality gap (as a function of $r$ ), without focusing on optimizing the constants involved. However, for specific graph families, such as planar graphs – the constants obtained from these results are quite large (close to 100). As a result, determining the exact integrality gap remains an intriguing open question. Tighter upper and lower bounds are still elusive and serve as the central motivation for this paper.

While the multiflow–multicut gap is well understood for trees, in this work we study a broader class of graphs, namely cactus graphs. Recall that in a cactus graph, any two simple cycles are either vertex-disjoint or share exactly one vertex. Recently, [14] showed that the multiflow–multicut gap for cactus graphs is at least $\frac{16}{7}$ . We complement their result by proving improved upper bounds. In particular, we show that the multiflow–multicut gap is at most $3.45$ for cactus graphs, improving upon the bound of 4 by Bentz [2]. Our approach involves a novel modification of the well-known algorithm for trees. Moreover, we demonstrate that adding structural constraints to cactus graphs can yield even tighter bounds. Specifically, we prove a tight upper bound of 2 for unicyclic graphs, graphs with exactly one cycle, which we refer to as the central cycle, and also a tight upper bound of 2 for path cactus graphs, where cycles are arranged along a single path. For completeness, we also include a tight integrality gap of $\frac{3}{2}$ for simple cycles – likely known in the community, although we could not find an explicit reference.
All our results are derived using the fact that the natural linear programming relaxations of the multicut and multiflow problems are dual to each other. We introduce new algorithmic ideas to round the linear programming relaxation to the multicut problem, and then use strong duality to obtain our bounds.

2 Preliminaries

Given a connected graph $G$ , we denote its vertex and edge sets by $V(G)$ and $E(G)$ , respectively. We will use $K_{r}$ to denote the complete graph on $r$ vertices. In this paper, we will only be concerned with cactus graphs. Graphs in which every edge is contained in at most one cycle are called cactus graphs. Cactus graphs are a subclass of series-parallel and planar graphs, and are arguably the simplest family of planar graphs after trees and cycles. Cactus and series-parallel graphs do not contain $K_{4}$ as a minor.

Let $G$ be a simple undirected graph with edge costs $c\colon E(G)\rightarrow\mathbb{R}_{\geq 0}$ , and let $\{(s_{i},t_{i})\}_{i=1}^{k}$ be the set of source-sink pairs. Let $\mathcal{P}_{i}$ denote the set of all paths between $s_{i}$ and $t_{i}$ in $G$ , and let $\mathcal{P}=\bigcup_{i=1}^{k}\mathcal{P}_{i}$ . A multicut is a set of edges $F\subseteq E(G)$ such that every $P\in\mathcal{P}$ contains at least one edge in $F$ . Equivalently, a multicut is a set of edges whose removal disconnects every source-sink pair.

Given two arbitrary vertices $u,v\in V(G)$ , we use $d_{G}(u,v)$ to denote the shortest path distance between $u$ and $v$ in $G$ . The diameter of $G$ is the maximum distance between a pair of vertices in $G$ , i.e., $\text{diam}(G)=\max_{u,v\in V(G)}d_{G}(u,v)$ . We use $d_{G}(v,e)$ to denote the distance of a vertex $v$ from an edge $e=(x,y)$ , i.e., $d_{G}(v,e)=\min\{d_{G}(v,x),d_{G}(v,y)\}$ .

For $F\subseteq E(G)$ , we use $G\setminus F$ to denote the graph obtained after the removal of $F$ from $G$ . For any $v\in V(G)$ , we use $C_{F}(v)$ to denote the connected component of $G\setminus F$ containing $v$ . We overload notation and also use $C_{F}(v)$ to denote the set of vertices in the connected component containing $v$ . We define the radius of $v$ with respect to $F$ as the distance of the farthest vertex from $v$ in $C_{F}(v)$ , i.e., $\text{rad}_{F}(v)=\max_{u\in C_{F}(v)}d_{G}(v,u)$ . In addition, the diameter of $F$ is the maximum diameter of a connected component after the removal of $F$ from $G$ , i.e., $\text{diam}(F)=\max_{v\in V(G)}\text{diam}(C_{F}(v))$ . Given $t\in\mathbb{R}_{\geq 0}$ as a parameter, we say that $F$ forms a $t$ -diameter decomposition if $\text{diam}(F)<t$ . We denote the set of all $t$ -diameter decompositions of $G$ by $\mathcal{F}_{t}(G)$ . Note that when referring to the distance between two vertices $u, v$ in a component $C$ , $d_{G}(u,v)$ denotes their distance in $G$ , rather than in the subgraph induced by $C$ , i.e., $G[C]$ . Given a cycle $C$ and a path $P$ , we denote by $\text{len}(C)$ and $\text{len}(P)$ the number of edges in $C$ and $P$ , respectively.

Definition 1.

Let $P=(v_{1},\ldots,v_{n})$ be a path on $n$ vertices. For any $i\neq j$ , we denote by $P[v_{i},v_{j}]$ the induced subpath of $P$ between $v_{i}$ and $v_{j}$ (inclusive).

Definition 2.

Let $P=(v_{1},\ldots,v_{n})$ and $Q=(v_{n},\ldots,v_{n+m})$ be two distinct paths such that they share the vertex $v_{n}$ . We denote by $P\oplus Q$ the path from $v_{1}$ to $v_{n+m}$ obtained by concatenating $P$ and $Q$ .

2.1 Graphs Classes

We recall a few definitions from the graph theory textbook by Diestel [4]. A block is a maximal connected subgraph without a cut-vertex (of that subgraph). Thus, every block is either a maximal 2-connected subgraph, or a cut-edge (with its ends), or an isolated vertex. The block graph of a graph $G$ is a bipartite graph on $A\cup{B}$ , where $A$ is the set of cut-vertices of $G$ and B is the set of blocks of $G$ , and the block graph has an edge $a b$ (where $a\in{A},\,b\in{B}$ ) iff $a\in V(B)$ .
A cactus is a connected graph in which every block is either a cycle or a cut-edge (with its ends). A path-cactus is a cactus whose block graph is a path and that has no cut-edges. A unicyclic graph is a connected graph with exactly one cycle. We denote these families by CACTUS, PATH CACTUS, UNICYCLIC, and CYCLE (the last being the family of all simple cycles).

2.2 Linear Programming Relaxation for the Minimum Multicut Problem

We begin by describing an integer programming (IP) formulation for the minimum multicut problem. For each edge $e\in E(G)$ , we introduce an integer variable $x(e)\in\{0,1\}$ , which indicates whether the edge is selected in the multicut. For a given path $P$ , we define $x(P)=\sum_{e\in E(P)}x(e)$ . A feasible multicut must include at least one edge from each source-sink path, so we impose the constraint $x(P)\geq 1$ for all $P\in\mathcal{P}$ , ensuring that each path is cut by at least one edge. We relax the integrality constraints to obtain the linear programming (LP) relaxation (1) of the multicut problem, which is formulated as follows:

	$\displaystyle\min\sum_{e\in E(G)}c(e)\cdot x(e)$	(1)
subject to
	$\displaystyle x(P)\geq 1\quad\forall P\in\mathcal{P}$
	$\displaystyle x(e)\geq 0\quad\forall e\in E(G).$

Even though there are an exponential number of constraints, it is well known that the optimal solution to this LP can be computed in polynomial time [9]. We denote the optimal solutions of the integer and linear programs as $\textsc{OPT}_{IP}$ and $\textsc{OPT}_{LP}$ , respectively. We refer to $\textsc{OPT}_{LP}$ as the minimum fractional multicut. We know that the value of the maximum multiflow is equal to the minimum fractional multicut. Furthermore, a bound on the integrality gap of the LP relaxation for the multicut problem provides the same bound for the multiflow-multicut gap. Therefore, from this point onward, we will focus solely on the integrality gap of the multicut LP.

Definition 3.

Let $\mathcal{G}$ be a family of graphs, and let $\mathcal{M}(\mathcal{G})$ be the family of all instances of the minimum multicut problem on $\mathcal{G}$ , obtained by assigning arbitrary capacities to the edges and selecting a set of source-sink pairs. The integrality gap $\alpha_{\mathcal{M}(\mathcal{G})}$ of the minimum multicut problem on $\mathcal{M}(\mathcal{G})$ is defined as follows:

\alpha_{\mathcal{M}(\mathcal{G})}:=\max_{M\in\mathcal{M}(\mathcal{G})}\frac{% \textsc{OPT}_{IP}(M)}{\textsc{OPT}_{LP}(M)}.

From the discussion above, we know that $\alpha_{\mathcal{M}(\textsc{tree})}=2$ [10], where tree denotes the family of all trees, and $\alpha_{\mathcal{M}(\textsc{planar})}=\mathcal{O}(1)$ [15], where planar refers to the family of all planar graphs. In this paper, we focus on cactus graphs.

2.3 Transition from the Minimum Multicut Problem to the Small Diameter Decomposition Problem

For all of our upper bounds, we reduce the analysis of the multicut LP to a Small Diameter Decomposition (SDD) guarantee. We first define SDD formally.

Definition 4 (Small Diameter Decomposition (SDD)).

Given an unweighted graph $G$ , an integer $k\in\mathbb{N}$ , and a parameter $p\in(0,1)$ , an SDD for $(G,k,p)$ is a probability distribution $\mathcal{D}=\{y_{F}\}_{F\in\mathcal{F}_{k}(G)}$ over the family $\mathcal{F}_{k}(G)$ of $k$ -diameter decompositions of $G$ such that every edge $e\in E(G)$ is included in a random $k$ -diameter decomposition sampled from $\mathcal{D}$ with probability at most $p$ :

\sum_{\begin{subarray}{c}F\in\mathcal{F}_{k}(G)\\ e\in F\end{subarray}}y_{F}\;\leq\;p\qquad\text{for all }e\in E(G).

If such a distribution exists, we write $SDD(G,k,p)$ .

We use the connection between SDDs and the multicut integrality gap established in [14]. We only need the “backward” direction for upper bounds on the integrality gap (the “forward” direction was used in [14] to derive the lower bound $16/7$ for the family CACTUS).

Theorem 5 (Theorem 2 of [14]).

Let $\mathcal{G}$ be a family of graphs closed under taking minors and under edge subdivisions, and let $\alpha>0$ . Then

\alpha_{\mathcal{M}(\mathcal{G})}\leq\alpha\quad\iff\quad\forall\,G\in\mathcal% {G},\ \forall\,w\in\mathbb{N},\ \exists\,SDD\!\left(G,2w,\tfrac{\alpha}{2w}% \right).

Transitioning to the SDD framework removes any dependence on the placement of source–sink pairs and edge costs, and replaces it with a uniform, metric-style requirement.
All graph families we consider (cycles, unicyclic graphs, path-cactus graphs, and cactus graphs) are closed under minors and edge subdivisions. It is convenient to work with instances in which every cycle of the graph has even length. More generally, for any $k\in\mathbb{N}$ , Lemma 6 shows that establishing an SDD with parameters $(4kw,\alpha/(4kw))$ for the normalized instances (where each cycle length is divisible by $2k$ ) suffices to obtain an SDD with parameters $(2w,\alpha/(2w))$ for the original family.

Lemma 6 (see Appendix B for the proof in the appendix).

Fix $k\in\mathbb{N}$ and $\alpha>0$ . Let $\mathcal{G}$ be a subfamily of cactus graphs closed under minors and edge subdivisions, and let

\mathcal{G}^{\prime}\;=\;\{\,G^{\prime}\in\mathcal{G}\ :\ \text{every cycle of% $G^{\prime}$ has length divisible by }2k\,\}.

Then

\Big[\forall\,G^{\prime}\in\mathcal{G}^{\prime},\,\forall\,w\in\mathbb{N},\,% \exists\,SDD\!\left(G^{\prime},4kw,\tfrac{\alpha}{4kw}\right)\Big]\;% \Longrightarrow\;\Big[\forall\,G\in\mathcal{G},\,\forall\,w\in\mathbb{N},\,% \exists\,SDD\!\left(G,2w,\tfrac{\alpha}{2w}\right)\Big].

In what follows, we apply Theorem 5 together with Lemma 6 to obtain the stated upper bounds for the families CYCLE, UNICYCLIC, PATH CACTUS, and CACTUS. By Lemma 6, we may assume that every cycle in $G$ has even length (the case $k=1$ of the normalization). For such graphs, it suffices to show that for any $w\in\mathbb{N}$ there exists an $SDD(G,2w,\tfrac{\alpha}{2w})$ .

Throughout, the setting is as follows: given a graph $G$ from the relevant subfamily with all cycles even (by Lemma 6) and a parameter $w\in\mathbb{N}$ , we construct an $SDD(G,2w,\tfrac{\alpha}{2w})$ . This certifies the required SDD and, by Theorem 5, yields the upper bound $\alpha$ on the integrality gap. To prove existence, we design randomized algorithms that output a $2w$ -diameter decomposition while controlling the marginal probability that any edge is cut. We fix $w$ and present four algorithms, each tailored to one graph class. Given $G$ , an algorithm samples a set $F\subseteq E(G)$ such that every component of $G\setminus F$ has diameter at most $2w-1$ (i.e., $F\in\mathcal{F}_{2w}(G)$ ) and we bound $\Pr[e\in F]$ for each edge. We will use Theorems 5 and 6 repeatedly in what follows.

$\blacksquare$

Algorithm 1: For a cycle $C\in\textsc{CYCLE}$ of even length, each edge $e\in E(C)$ is removed with probability at most $\tfrac{3}{4}\cdot\tfrac{1}{w}$ . By Theorem 5, this yields $\alpha_{\textsc{CYCLE}}\leq 2\cdot\tfrac{3}{4}=\tfrac{3}{2}$ . A matching lower bound (see Appendix A in the appendix) shows that $\alpha_{\textsc{CYCLE}}=\tfrac{3}{2}$ .
$\blacksquare$

Algorithm 2: For a cactus graph $G\in\textsc{CACTUS}$ in which every cycle has even length, each edge $e\in E(G)$ is removed with probability at most $\bigl(1+\tfrac{1}{2\ln 2}\bigr)\cdot\tfrac{1}{w}\approx 1.721\cdot\tfrac{1}{w}$ . Hence there exists an $SDD(G,2w,1.721\cdot\tfrac{1}{w})$ , and Theorem 5 together with Lemma 6 implies

$\alpha_{\textsc{CACTUS}}\leq 2\!\left(1+\tfrac{1}{2\ln 2}\right)=2+\tfrac{1}{% \ln 2}\approx 3.443\;<\;3.45.$
$\blacksquare$

Algorithm 3: For a unicyclic graph $G\in\textsc{UNICYCLIC}$ , each edge $e\in E(G)$ is removed with probability at most $\tfrac{2}{2w-1}$ . If this were $\tfrac{2}{2w}$ we would immediately get $\alpha_{\textsc{UNICYCLIC}}\leq 2$ ; since it is slightly larger, we apply Lemma 6 to obtain $\alpha_{\textsc{UNICYCLIC}}\leq 2$ (see Corollary 25). Because unicyclic graphs contain trees as subgraphs (for which the gap is $2$ [10]), we conclude $\alpha_{\textsc{UNICYCLIC}}=2$ .
$\blacksquare$

Algorithm 4: For a path-cactus graph $G\in\textsc{PATH\text{-}CACTUS}$ in which all cycles have even length, each edge $e\in E(G)$ is removed with probability at most $\tfrac{1}{w}$ . Hence there exists an $SDD(G,2w,\tfrac{1}{w})$ , and Theorems 5 and 6 yield $\alpha_{\textsc{PATH\text{-}CACTUS}}\leq 2$ .

In the appendix (see Appendix C in the appendix), we give an explicit instance with gap at least $2$ , and therefore $\alpha_{\textsc{PATH\text{-}CACTUS}}=2$ .

2.4 Small Diameter Decomposition for Trees

As mentioned earlier, $\alpha_{\mathcal{M}(\textsc{tree})}=2$ . By Theorem 5, this implies that for any tree $T$ and any $w\in\mathbb{N}$ ,

SDD\!\left(T,2w,\tfrac{2}{2w}\right)=SDD\!\left(T,2w,\tfrac{1}{w}\right).

Here we give an explicit construction of $SDD(T,2w,\tfrac{1}{w})$ without invoking Theorem 5. This construction will be reused in Section 5 to obtain an appropriate SDD for unicyclic graphs.

Theorem 7.

Let $T$ be a tree. Then for every integer $w\in\mathbb{N}$ , there exists $SDD\!\left(T,2w,\tfrac{1}{w}\right)$ . Equivalently, there exists a probability distribution $\mathcal{D}=\{y_{F}\}_{F\in\mathcal{F}_{2w}(T)}$ over $\mathcal{F}_{2w}(T)$ such that

\displaystyle\sum_{\begin{subarray}{c}F\in\mathcal{F}_{2w}(T)\\ e\in F\end{subarray}}y_{F}\;\leq\;\frac{1}{w}\quad\forall e\in E(T).

(2)

Proof.

Root the tree $T$ at an arbitrary vertex $r\in V(T)$ . For $i=0,\ldots,w-1$ , define

F_{i}=\{\,e\in E(T)\mid d(r,e)=i+kw\text{ for some }k\in\mathbb{Z}_{\geq 0}\,\}.

Set $y_{F_{i}}=\tfrac{1}{w}$ for each $i=0,\ldots,w-1$ , and $y_{F}=0$ otherwise. Note that the sets $F_{i}$ partition $E(T)$ : we have $E(T)=\bigcup_{i=0}^{w-1}F_{i}$ and $F_{i}\cap F_{j}=\emptyset$ for $i\neq j$ . Thus,

\sum_{\begin{subarray}{c}F\in\mathcal{F}_{2w}(T)\\ e\in F\end{subarray}}y_{F}=\sum_{\begin{subarray}{c}i=0\\ e\in F_{i}\end{subarray}}^{w-1}y_{F_{i}}=\tfrac{1}{w},\quad\forall e\in E(T).

It remains to show that each $F_{i}$ is a valid $2w$ -diameter decomposition. Fix $F_{i}$ , and consider a pair of vertices $(u,v)$ with $d(u,v)\geq 2w$ . Let $q$ be the lowest common ancestor of $u$ and $v$ . The unique $u$ – $v$ path consists of the $u$ – $q$ path and the $q$ – $v$ path. Since $d(u,v)\geq 2w$ , one of these subpaths has length at least $w$ . Without loss of generality, suppose $d(q,v)\geq w$ , and denote this path by $Q=e_{0},e_{1},\dots,e_{p}$ . Because $q$ is an ancestor of $v$ , we have $d(r,e_{i})=d(r,e_{i-1})+1$ for $i=1,\dots,p$ . Hence there exists some $e_{j}\in Q$ such that $d(r,e_{j})\equiv i\pmod{w}$ , i.e., $e_{j}\in F_{i}$ . Removing $F_{i}$ therefore separates $u$ and $v$ , as required. This shows that $F_{i}$ defines a $2w$ -diameter decomposition, and hence $\mathcal{D}$ is a valid $SDD(T,2w,1/w)$ . $\hfill\blacktriangleleft$ The $2w$ -diameter decompositions $F_{0},\ldots,F_{w-1}$ described in the proof of Theorem 7 will be useful in the Algorithm 3 in Section 5, so we record a formal definition:

Definition 8.

Let $w\in\mathbb{N}$ , and let $T$ be a tree with a distinguished root vertex $r\in V(T)$ . For each $i=0,1,\ldots,w-1$ , define

F^{i}_{w}(T,r):=\left\{e\in E(T)\;\middle|\;d_{T}(r,e)\equiv i\pmod{w}\right\},

where $d_{T}(r,e)$ denotes the distance from $r$ to the closer endpoint of $e$ . Then $\{F^{i}_{w}(T,r)\}_{i=0}^{w-1}$ forms a partition of $E(T)$ . Moreover, each $F^{i}_{w}(T,r)$ defines a $2w$ -diameter decomposition of $T$ , and the connected component containing the root $r$ has radius at most $i$ from $r$ , that is,

rad_{F^{i}_{w}(T,r)}(r)\leq i\leq w-1.

3 Cycle

Let $w\in\mathbb{N}$ and let $C$ be a cycle of even length. If $len(C)\leq 4w-1$ , then $\text{diam}(C)\leq 2w-1$ and no edges need be removed (set $F=\emptyset$ ). Otherwise ( $len(C)\geq 4w$ ), Algorithm 1 outputs a random $2w$ -diameter decomposition $F\in\mathcal{F}_{2w}(C)$ such that, for every edge $e\in E(C)$ , $\Pr[e\in F]\;\leq\;\tfrac{3}{4}\cdot\tfrac{1}{w}$ .

Algorithm 1 Cycle Algorithm.

$\blacktriangleright$ Remark 9.

The choice of $\rho$ in the line 4 is independent of the choice of the edges in the line 2 of Algorithm 1.

Lemma 10.

$F\in\mathcal{F}_{2w}(C)$ .

Proof.

Let $P$ be the path referenced in line 3 of Algorithm 1, and let $r$ denote its starting point. For all $i=1,\ldots,2w-1$ , observe that $F_{2w}^{i}(P,r)$ is a $2w$ -diameter decomposition of $P$ . Therefore, $F$ is a $2w$ -diameter decomposition of $C$ . $\hfill\blacktriangleleft$ Each edge $e\in E(C)$ is added to $F$ either in the line 2, or the line 5. The first case occurs with probability $\frac{1}{len(C)}\leq\frac{1}{4w}$ , and the second case occurs with probability $\frac{1}{2w}$ . Thus, using the union bound, the probability of $e$ being removed by Algorithm 1 is at most $\frac{1}{4w}+\frac{1}{2w}=\frac{3}{4}\cdot\frac{1}{w}$ . Theorem 5 implies that $\alpha_{CYCLE}\leq 2\times\frac{3}{4}=\frac{3}{2}$ .

4 Cactus

Let $w\in\mathbb{N}$ and $G$ be a cactus with distinct cycles $C_{1},\ldots,C_{k}$ such that $len(C_{i})$ is an even number for $i=1,\ldots,k$ . For simplicity, we denote the distance function $d_{G}$ as $d$ throughout this section. Let $r\in V(G)$ be an arbitrary vertex, which we denote as the root. For any cycle $C_{i}$ , let $r_{C_{i}}\in V(C_{i})$ be the unique vertex such that $d(r,r_{C_{i}})=\min_{v\in V(C_{i})}d(r,v)$ , and let

\beta_{i}=2\cdot\sum_{j=1}^{len(C_{i})/2}\frac{1}{len(C_{i})-j},

and let $\mathcal{D}_{i}$ be the probability distribution on $E(C_{i})$ defined by

\Pr_{\mathcal{D}_{i}}(e)=\frac{1}{\beta_{i}}\cdot\frac{1}{len(C_{i})-d(r_{C_{i% }},e)-1},\quad\forall e\in E(C_{i}),

where $\beta_{i}$ is the normalizing constant ensuring that the total probability sums to 1. To see this note that for each $j=1,\ldots,\frac{len(C_{i})}{2}$ , we have $|\{e\in E(C_{i})\;|\;d(r_{C_{i}},e)=j-1\}|=2$ . The algorithm is described in detail in Algorithm 2.

Algorithm 2 Cactus Algorithm.

Lemma 11.

$F\in\mathcal{F}_{2w}(G)$ .

Proof.

Let $F^{\prime}$ denote the set of edges in $F$ immediately before the execution of the line 8 of Algorithm 2. At that point, we have $F^{\prime}=(E(G)\setminus E(T))\cup F_{w}^{\rho}(T,r)$ , which means that $F^{\prime}\in\mathcal{F}_{2w}(G)$ , as $F_{w}^{\rho}(T,r)\in\mathcal{F}_{2w}(T)$ mentioned in Definition 8. During the execution of the lines 8 to 12 of Algorithm 2, each edge $e_{i}$ is removed from $F^{\prime}$ only if its endpoints are still connected in $G\setminus F^{\prime}$ . This means that no two previously disconnected components become reconnected. Thus, $F\in\mathcal{F}_{2w}(G)$ . $\hfill\blacktriangleleft$ Now, we show that each edge $e\in E(G)$ is removed by Algorithm 2 with probability at most $(1+\frac{1}{2\ln{2}})\cdot\frac{1}{w}$ .

$\blacktriangleright$ Remark 12.

The choice of $\rho$ in the line 6 is independent of the choice of the edges in the lines 2 to 4 of Algorithm 2.

Remark 12 implies that each cut-edge $e\in E(G)$ is removed by Algorithm 2 with probability $\frac{1}{w}$ . For edges that lie within cycles, we have the following Lemma 13.

Lemma 13.

Let $e\in E(C_{i})$ for some $i=1,\ldots,k$ . $\Pr[e\in F]=(1+\frac{1}{\beta_{i}})\cdot\frac{1}{w}$ .

Proof.

Let $A$ be the event that $e\in F$ , and let $B$ be the event that $e$ is chosen as $e_{i}$ in line 3 of Algorithm 2. Then,

\displaystyle\Pr[A]=\Pr[A\mid B]\cdot\Pr[B]+\Pr[A\mid\bar{B}]\cdot\Pr[\bar{B}].

By Remark 12, we have

\Pr[A\mid\bar{B}]\cdot\Pr[\bar{B}]\leq\frac{1}{w}\cdot 1=\frac{1}{w}.

To compute $\Pr[A\mid B]$ , let $P_{1}$ and $P_{2}$ denote the shorter and longer paths, respectively, between $r_{C_{i}}$ and $e$ in $C_{i}$ (see Figure 1). Note that

\text{len}(P_{1})=d(r_{C_{i}},e)<\text{len}(P_{2})=\text{len}(C_{i})-d(r_{C_{i% }},e)-1.

Since $r_{C_{i}}$ is the least common ancestor (LCA) of $P_{1}$ and $P_{2}$ in the tree $T$ rooted at $r$ (as defined in line 5), it follows that if $E(P_{1})\cap F_{w}^{\rho}(T,r)\neq\varnothing$ , then $E(P_{2})\cap F_{w}^{\rho}(T,r)\neq\varnothing$ as well. Each edge in $E(P_{2})$ is removed independently with probability $\frac{1}{w}$ . Therefore, by the union bound, $\Pr[A\mid B]\leq\frac{\text{len}(P_{2})}{w}$ .

Now, observe that

\Pr[A\mid B]\cdot\Pr[B]=\frac{\text{len}(C_{i})-d(r_{C_{i}},e)-1}{w}\cdot\frac% {1}{\beta_{i}}\cdot\frac{1}{\text{len}(C_{i})-d(r_{C_{i}},e)-1}=\frac{1}{\beta% _{i}w}.

Combining both parts, we conclude:

\displaystyle\Pr[A]=\frac{1}{\beta_{i}w}+\frac{1}{w}=\left(1+\frac{1}{\beta_{i% }}\right)\cdot\frac{1}{w}.

Figure 1:

P_{1},P_{2},e

in

C_{i}

.

$\hfill\blacktriangleleft$

Lemma 14.

$\beta_{i}\geq 2\ln{2}$ for all $i=1,\ldots,k$ .

Proof.

It is sufficient to prove $f(k)=\frac{1}{k}+\cdots+\frac{1}{2k-1}\geq\ln{2}$ for any $k\in\mathbb{N}$ . $f(k)$ is decreasing in $\mathbb{N}$ . We have

\displaystyle\sum_{i=k}^{2k-1}\frac{1}{i}\geq\int_{k}^{2k}\frac{1}{x}\,dx=\ln(% 2k)-\ln(k)=\ln\left(\frac{2k}{k}\right)=\ln 2.

$\hfill\blacktriangleleft$ Thus, the probability that any edge is removed by Algorithm 2 is at most $\left(1+\tfrac{1}{2\ln{2}}\right)\cdot\tfrac{1}{w}$ . By Theorem 5 together with the lower bound established in [14], we obtain

2.285\;\approx\;\tfrac{16}{7}\;\leq\;\alpha_{\text{CACTUS}}\;\leq\;2\cdot\left% (1+\tfrac{1}{2\ln{2}}\right)\;\leq\;3.442.

5 Unicyclic Graphs

Let $w\in\mathbb{N}$ and let $G$ be a unicyclic graph with central cycle $C$ of even length. For each $u\in V(C)$ , let $T(u)$ denote the tree attached to $v_{j}$ . See the following figure for an illustration:

Algorithm 3 returns a (random) subset of edges $F\in\mathcal{F}_{2w}(G)$ such that $\Pr[e\in F]\leq\frac{2}{2w-1}$ for all $e\in E(G)$ .
The algorithm involves two sources of randomness. First, the algorithm selects an edge $e\in E(C)$ uniformly at random and temporarily removes it, transforming the cycle $C$ into a path $P:=C\setminus e$ . The path $P$ is then extended at both ends, which we refer to as the extended path $P^{\prime}$ . Next, the algorithm selects a sequence of roots $R$ along $P^{\prime}$ such that consecutive roots are spaced at distance exactly $2w-1$ from each other. For each pair of consecutive roots $r_{1},r_{2}\in R$ , the algorithm removes the middle edge of the subpath $P^{\prime}[r_{1},r_{2}]$ . Then, for each vertex $u\in V(P)$ , it removes the set $F_{w}^{l(u)}(T(u),u)$ from the tree $T(u)$ attached at $u$ , where $0\leq l(u)\leq w-1$ is chosen appropriately. Finally, if the algorithm ends up removing an additional edge from $P$ (other than the initially chosen edge $e$ ), then $e$ is permanently removed. Otherwise, if no other edge from $P$ is removed, the edge $e$ is retained.

Algorithm 3 Unicyclic Algorithm.

Let $F^{\prime}$ denote the set of edges in $F$ immediately before the execution of the line 12 of the Algorithm 3.

$\blacktriangleright$ Remark 15.

Each two consecutive roots in $R$ are at distance $2w-1$ of each other, and the middle edge of the path between each two consecutive roots is contained in $F^{\prime}$ . This means that on $P^{\prime}$ , any two consecutive edges in $F^{\prime}$ are at distance $2w-2$ of each other, meaning there are exactly $2w-2$ number of edges of $P^{\prime}$ between them. Since $len(P_{\textit{left}}),len(P_{\textit{right}})=2w-1$ , then $|F^{\prime}\cap E(P_{\textit{left}})|=|F^{\prime}\cap E(P_{\textit{right}})|=1$ . This means that any vertex $v\in V(P)$ is between two consecutive edges in $F^{\prime}\cap E(P^{\prime})$ . Moreover, there are exactly $2w-2$ edges of the path $P^{\prime}$ between these two edges, which creates the path $Q$ . The middle vertex of this sub-path $Q$ of $P^{\prime}$ is the unique root $r(v)\in R$ denoted in the line 10 of the Algorithm 3. So, it can be derived that $0\leq d_{G^{\prime}(r(v),v)}\leq w-1$ . Also, since each two consecutive roots of $R$ are at distance $2w-1$ of each other, then $r(v)$ is the unique closest root to $v$ in $G^{\prime}$ .

Figure 2: The left figure shows the random chosen edge

e\in E(C)

, and the right figure shows the graph

H=G\setminus e

.

Figure 3: The extended graph

G^{\prime}

and the extended path

P^{\prime}=P_{\textit{left}}\oplus P\oplus P_{\textit{right}}

.

Lemma 16.

$F\in F_{2w}(G)$ .

Proof.

It suffices to prove $F^{\prime}\in\mathcal{F}_{2w}(G^{\prime})$ : adding (or not adding) $e$ cannot increase component diameters, and removing $P_{\textit{left}}$ and $P_{\textit{right}}$ affects only auxiliary edges outside $E(G)$ .

Claim 17.

If $F^{\prime}\in\mathcal{F}_{2w}(G^{\prime})$ , then $F\in\mathcal{F}_{2w}(G)$ .

Proof.

Assume $F^{\prime}\in\mathcal{F}_{2w}(G^{\prime})$ . Note that $G^{\prime}+e$ is a super graph of $G$ , i.e., $G$ is an induced sub-graph of $G+e$ . So, we have $F^{\prime}\cup\{e\}\in\mathcal{F}_{2w}(G^{\prime}+e)$ . Based on the if condition in the line 12 of the Algorithm 3, there are two cases to consider:

1.

The endpoints of $e$ are within different connected component in $G^{\prime}\setminus F^{\prime}$ ; then the line 13 is executed by the Algorithm 3, which means that $F=F^{\prime}\cap\{e\}$ right after the execution of the line 14.
2.

The endpoints of $e$ are within the same connected component in $G^{\prime}\setminus F^{\prime}$ ; then the line 13 is not executed by the Algorithm 3, which means that $F=F^{\prime}$ right after the execution of the line 14, and $F^{\prime}\in\mathcal{F}_{2w}(G^{\prime}+e)$ .

Thus, in both cases, $F\in\mathcal{F}_{2w}(G^{\prime})$ right after the execution of the line 14. In the line 15 the edges of $P_{\textit{left}},P_{\textit{right}}$ are being excluded from $F$ . Thus, $F\in\mathcal{F}_{2w}(G)$ after the execution of the Algorithm 3. $\hfill\vartriangleleft$ We prove $F^{\prime}\in\mathcal{F}_{2w}(G^{\prime})$ in the remaining. As stated in the Remark 15, $|F^{\prime}\cap E(P_{\textit{left}})|=|F^{\prime}\cap E(P_{\textit{right}})|=1$ , which means that the connected components containing the endpoints of $P^{\prime}$ in $G^{\prime}\setminus F^{\prime}$ are simple paths with length at most $2w-2$ . Now, consider the other connected components in $G^{\prime}\setminus F^{\prime}$ . Let $D$ be a connected component not containing the endpoints of $P^{\prime}$ . If $D$ is a subgraph of $T(u)$ for some $u\in V(C)$ , then $diam(D)\leq 2w-1$ , since $F_{w}^{l(u)}(T(u),u)\subseteq F^{\prime}$ , and $F_{w}^{l(u)}(T(u),u)$ is a $2w$ -diameter decomposition for $T(u)$ , as stated in the Definition 8.
Thus, assume that $D$ is not a sub-graph of any $T(u)$ . This means that $V(D)\cap V(P^{\prime})\neq\varnothing$ . Since $F^{\prime}\cap E(P^{\prime})$ must consists of edges along $P^{\prime}$ spaced exactly $2w-2$ apart using Remark 15, and $D$ does not contain the endpoints of $P^{\prime}$ , then the sub-graph induced by $D$ on the vertices $V(P^{\prime})$ , denoted $D[V(P^{\prime})]$ , forms a contiguous sub-path $Q$ of $P^{\prime}$ of length $2w-2$ . Moreover, the unique middle vertex of $Q$ is a root $r^{\prime}\in R$ . Note that the only vertex in $V(D)$ that belongs to the root set $R$ is this single, central vertex $r^{\prime}$ .

Claim 18.

$d_{G^{\prime}}(r^{\prime},u)\leq w-1$ for all $u\in V(D)$ .

Proof.

If $u\in V(Q)$ , then since $len(Q)=2w-2$ , and $r^{\prime}$ is the middle vertex of $Q$ , then $d_{G^{\prime}}(r^{\prime},u)\leq w-1$ . So, assume $u\notin V(Q)$ . This means that there exists a vertex $v\in V(Q)$ such that $u\in V(T_{v})$ . We have $l(v)=w-1-d_{G^{\prime}}(r^{\prime},v)$ . As stated in the Definition 8, $rad_{F_{w}^{l(v)}(T(u),u)}(v)\leq l(v)$ , which means that $d_{G^{\prime}}(v,u)\leq l(v)$ . The triangle inequality implies that

d_{G^{\prime}}(r^{\prime},u)\leq d_{G^{\prime}}(r^{\prime},v)+d_{G^{\prime}}(v% ,u)\leq w-1-l(v)+l(v)=w-1.\

$\hfill\vartriangleleft$ This shows that $diam(D)\leq 2w-2$ . Thus, $F^{\prime}\in\mathcal{F}_{2w}(G^{\prime})$ . $\hfill\blacktriangleleft$ Now, we are going to show that each edge $e\in E(G)$ is removed by the Algorithm 3 with probability at most $\frac{2}{2w-1}$ .

Definition 19.

For any $z\in\mathbb{Z}$ , let $m_{w}(z)\in\{-(w-1),\ldots,0,\ldots,w-1\}$ be the unique integer such that $z=m_{w}(z)\mod 2w-1$ . Note that $0\leq|m_{w}(z)|\leq w-1$ , and $m_{w}(-z)=-m_{w}(z)$ .

Lemma 20.

Fix the random edge $e\in E(C)$ in the line 2, and let $G^{\prime}$ and $P_{\textit{left}}=(v_{0},\ldots,v_{2w-1})$ be as stated in the line 3 and $\rho$ stated in the line 4 of the Algorithm 3. For any $v\in V(C)=V(P)$ , we have $d_{G^{\prime}}(r(v),v)=|m_{w}(d_{G^{\prime}}(v_{0},v)-\rho)|$ .

Proof.

We have $d_{G^{\prime}}(v_{0},r_{v})=d_{G^{\prime}}(v_{0},v_{\rho})+d_{G^{\prime}}(v_{% \rho},r(v))=\rho+d_{G^{\prime}}(v_{\rho},r(v))$ , which implies $d_{G^{\prime}}(v_{0},r_{v})=\rho\mod 2w-1$ . There are two cases to consider:

1.

$r(v)\in V(P^{\prime}[v_{0},v])$ ; this means that

$\displaystyle d_{G^{\prime}}(r(v),v)=d_{G^{\prime}}(v_{0},v)-d_{G^{\prime}}(v_% {0},r(v)),$

which implies

$\displaystyle d_{G^{\prime}}(r(v),v)=d_{G^{\prime}}(v_{0},v)-\rho\mod 2w-1.$

Since $0\leq d_{G^{\prime}}(r(v),v)\leq w-1$ , then $0\leq m_{w}(d_{G^{\prime}}(v_{0},v)-\rho)$ , which implies

$\displaystyle d_{G^{\prime}}(r(v),v)=m_{w}(d_{G^{\prime}}(v_{0},v)-\rho)=|m_{w% }(d_{G^{\prime}}(v_{0},v)-\rho)|.$
2.

$v\in V(P^{\prime}[v_{0},r(v)])$ ; this means that

$\displaystyle d_{G^{\prime}}(r(v),v)=d_{G^{\prime}}(v_{0},r(v))-d_{G^{\prime}}% (v_{0},v),$

which implies

$\displaystyle d_{G^{\prime}}(r(v),v)=-(d_{G^{\prime}}(v_{0},v)-\rho)\mod 2w-1.$

Since $0\leq d_{G^{\prime}}(r(v),v)\leq w-1$ , then $0\leq m_{w}(-(d_{G^{\prime}}(v_{0},v)-\rho))=-m_{w}(d_{G^{\prime}}(v_{0},v)-\rho)$ , which implies

$\displaystyle d_{G^{\prime}}(r(v),v)=-m_{w}(d_{G^{\prime}}(v_{0},v)-\rho)=|m_{% w}(d_{G^{\prime}}(v_{0},v)-\rho)|.$

$\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 21.

The choice of the edge $e$ in the line 2 is independent from the choice of $\rho$ in the line 4 of the Algorithm 3.

Lemma 22.

Let $u\in V(C)=V(P)$ be an arbitrary vertex, and let $k\in\{0,\ldots,w-1\}$ be an arbitrary number.

\displaystyle\Pr[d_{G^{\prime}}(r(u),u)=k]=\begin{cases}\frac{1}{2w-1}&\quad% \textit{if}\quad k=0\\ \frac{2}{2w-1}&\quad\textit{if}\quad k=1,\ldots,w-1.\end{cases}

Proof.

Fix $k$ . Let $e$ be the random edge denoted in the line 2 in the Algorithm 3. By conditional probability, we have

\displaystyle\Pr[d_{G^{\prime}}(r(u),u)=k]=\sum_{f\in E(C)}\Pr[d_{G^{\prime}}(% r(u),u)=k\;|\;e=f]\Pr[e=f].

$\Pr[e=f]=\frac{1}{len(C)}$ for all $f\in E(C)$ . Now, to compute $\Pr[d_{G^{\prime}}(r(u),u)=k\;|\;e=f]$ , we fix $e=f$ . Lemma 20 implies that $d_{G^{\prime}}(r(u),u)=|m_{w}(d_{G^{\prime}}(v_{0},v)-\rho)|$ , where $\rho$ is the random number denoted in the line 4 of the Algorithm 3. Note that $d_{G^{\prime}}(v_{0},v)$ is a fixed value assuming $e=f$ is fixed. If $k=0$ , then $d_{G^{\prime}}(r(u),u)=0$ iff $m_{w}(d_{G^{\prime}}(v_{0},v)-\rho)=0$ , and this is equivalent to $d_{G^{\prime}}(v_{0},v)=\rho\mod 2w-1$ . It can be derived that $\Pr[\rho=d_{G^{\prime}}(v_{0},v)\mod 2w-1]=\frac{1}{2w-1}$ . Thus, $\Pr[d_{G^{\prime}}(r(u),u)=0\;|\;e=f]=\frac{1}{2w-1}$ . If $k\in\{1,\ldots,w-1\}$ , then $d_{G^{\prime}}(r(u),u)=k$ iff $m_{w}(d_{G^{\prime}}(v_{0},v)-\rho)\in\{k,-k\}$ . It can be derived that the events $m_{w}(d_{G^{\prime}}(v_{0},v)-\rho)=k$ and $m_{w}(d_{G^{\prime}}(v_{0},v)-\rho)=-k$ are disjoint from each other, and each has probability $\frac{1}{2w-1}$ . Thus, $\Pr[d_{G^{\prime}}(r(u),u)=k\;|\;e=f]=\frac{2}{2w-1}$ . This completes the proof. $\hfill\blacktriangleleft$

Lemma 23.

Let $f\in E(G)\setminus E(C)$ , i.e., $f\in E(T(u))$ for some $u\in V(u)$ . $\Pr[f\in F]\leq\frac{2}{2w-1}$ .

Proof.

As stated in the Definition 8, $\{F_{k}^{i}(T(u),u)\}_{i=0}^{k-1}$ is a partition of $E(T(u))$ . Assume $f\in F_{w}^{j}(T(u),u)$ for some $j=0,\ldots,w-1$ . Line 10 implies that $f\in F$ iff $j=l(u)=w-1-d_{G^{\prime}}(r(u),u)$ . So, $e\in F$ iff $d_{G^{\prime}}(r(u),u)=w-1-j$ . Lemma 22 implies that

\displaystyle\Pr[d_{G^{\prime}}(r(u),u)=w-1-j]=\begin{cases}\frac{1}{2w-1}&% \quad\textit{if}\quad j=w-1\\ \frac{2}{2w-1}&\quad\textit{if}\quad j=0,\ldots,w-2.\end{cases}

$\hfill\blacktriangleleft$

Lemma 24.

Let $f\in E(C)$ be an arbitrary edge. $\Pr[f\in F]\leq\frac{2}{2w-1}$ .

Proof.

Let $A$ denote the event that $e=f$ , where $e$ is the random edge denoted in the line 2 of the Algorithm 3. Denote $\bar{A}$ as the complement of $A$ . We compute $\Pr[f\in F]$ by conditioning on $A$ . We have

\displaystyle\Pr[f\in F]=\Pr[f\in F|A]P[A]+\Pr[f\in F|\bar{A}]P[\bar{A}].

We know that $\Pr[A]=\frac{1}{len(C)}$ and $\Pr[\bar{A}]=\frac{len(C)-1}{len(C)}$ . Now, if $A$ happens, meaning that $e=f$ , then $f$ is added to the set $F^{\prime}$ in the line 13 iff the end-points of $e=f$ are in different connected components in $G^{\prime}\setminus F^{\prime}$ . Note that the endpoints of $e=f$ are indeed the endpoints of the path $P$ . Since $G^{\prime}$ is a tree, then $e=f$ is added to $F^{\prime}$ iff $F^{\prime}\cap E(P^{\prime})\neq\emptyset$ . We have two cases to consider:

1.

$len(C)\geq 2w$ ; then $len(P)\geq 2w-1$ , which means that $F^{\prime}\cap E(P^{\prime})\neq\varnothing$ by Remark 15. Thus, $\Pr[f\in F|A]=1\leq\frac{len(C)-1}{2w-1}$ in this case.
2.

$len(C)<2w$ ; Remark 15 implies that each edge of $P^{\prime}$ is contained in $F^{\prime}$ with probability $\frac{1}{2w-1}$ , assuming $e=f$ is fixed. Using union bound, we have

$\Pr[F^{\prime}\cap E(P)\neq\varnothing]\leq\sum_{f^{\prime}\in E(P)}\Pr[f^{% \prime}\in F^{\prime}]=\frac{len(C)-1}{2w-1}.$

Thus, $\Pr[f\in F|A]=\frac{len(C)-1}{2w-1}$ .

Now, we compute $\Pr[f\in F|\bar{A}]$ . Assuming $\bar{A}$ means $f\in E(P)$ , and as mentioned before each edge of $P^{\prime}$ is present in $F^{\prime}$ with probability $\frac{1}{2w-1}$ assuming $e\neq f$ is fixed. So, $\Pr[f\in F|\bar{A}]=\frac{1}{2w-1}$ . Thus,

\Pr[f\in F]=\frac{len(C)-1}{2w-1}\times\frac{1}{len(C)}+\frac{1}{2w-1}\times% \frac{len(C)-1}{len(C)}\leq\frac{2}{2w-1}.\

$\hfill\blacktriangleleft$

Corollary 25.

For the family UNICYCLIC, we have $\alpha_{\textsc{UNICYCLIC}}\leq 2$ .

Proof.

Fix $w^{\prime}\in\mathbb{N}$ . By Algorithm 3, for any unicyclic graph $G$ each edge is removed with probability at most $\tfrac{2}{2w^{\prime}-1}$ , and the algorithm outputs a random $F\in\mathcal{F}_{2w^{\prime}}(G)$ . Hence there exists an $SDD(G,2w^{\prime},\tfrac{2}{2w^{\prime}-1})$ .
Now fix $k\in\mathbb{N}$ and let $w^{\prime}=2kw$ for arbitrary $w\in\mathbb{N}$ . Then $SDD\!\left(G,4kw,\tfrac{2}{4kw-1}\right)$ exists for every unicyclic $G$ . Since $\tfrac{2}{4kw-1}\;\leq\;\frac{2\cdot\frac{4k}{4k-1}}{4kw}$ , we also have $SDD\!\left(G,4kw,\tfrac{2\cdot\frac{4k}{4k-1}}{4kw}\right)$ . Lemma 6 implies that for every unicyclic $G$ and $\forall w\in\mathbb{N}$ there exists $SDD\!\left(G,2w,\tfrac{2\cdot\frac{4k}{4k-1}}{2w}\right)$ . Applying Theorem 5 yields $\alpha_{\textsc{UNICYCLIC}}\;\leq\;2\cdot\frac{4k}{4k-1}$ . Letting $k\to\infty$ gives $\alpha_{\textsc{UNICYCLIC}}\leq 2$ . $\hfill\blacktriangleleft$

6 Path Cactus

In this section, we outline the algorithm for the path cactus. Due to space constraints, we omit the analysis here and defer it to the section 2.8 of the first author’s Master’s thesis [12]. We first recall the definition of a path cactus graph.

Definition 26.

Let $G$ be a cactus, we say that $G$ is a path cactus if it is $2$ -edge connected and each cycle shares a common vertex with at most $2$ more cycles, or equivalently it is a path of consecutive cycles. (Figure 4)

Figure 4: Path Cactus.

Definition 27.

Let $P=(v_{1},\ldots,v_{n})$ be an even-length path. We denote the mid-vertex of $P$ by $v_{\lceil\frac{n+1}{2}\rceil}$ .

Definition 28.

Assume $n\geq 3$ . Let $P=(v_{1},\ldots,v_{n})$ be a path. Let $e_{1}=(v_{i},v_{i+1}),e_{2}=(v_{j},v_{j+1})\in E(P)$ be two distinct edges such that $i<j$ . The distance between $e_{1},e_{2}$ in $P$ is denoted as $d_{P}(e_{1},e_{2})=j-i-1$ . Note that $e_{1},e_{2}$ are consecutive edges in $P$ iff $j=i+1$ .

Definition 29.

Let $C=(v_{1},\ldots,v_{n},v_{1})$ be an even-length cycle. For any vertex $v_{i}$ , we denote the opposite vertex of $v_{i}$ in $C$ as

\displaystyle\begin{cases}v_{i+\frac{n}{2}},&\text{if}\ i\leq\frac{n}{2}\\ v_{i-\frac{n}{2}},&\text{otherwise}\end{cases}

Let $G$ be a path cactus with consecutive cycles $C_{1},\ldots,C_{k}$ , such that $V(C_{i})\cap V(C_{i+1})=\{u_{i}\}$ for $i=1,\ldots,k-1$ . Let $u_{0}\neq u_{1}$ be an arbitrary vertex in $C_{1}$ , and also $u_{k}\neq u_{k-1}$ an arbitrary vertex in $C_{k}$ . As mentioned before, we can assume that length of all cycles are even. There are exactly $2$ simple paths between each pair of $u_{i-1},u_{i}$ in the cycle $C_{i}$ for $i=1,\ldots,k$ . Let $S_{i}$ denotes the shorter, and $L_{i}$ denotes the longer one. (Figure 5)

Figure 5:

S_{i}

and

L_{i}

.

Let $P=S_{1}\oplus\cdots\oplus S_{k}$ with endpoints $u_{0},u_{k}$ . We refer $v_{1}=u_{0},\ldots,v_{n}=u_{k}$ as the ordered vertices of $P$ . To perform the Algorithm 4, we need to consider a super graph of $G$ . Let $P_{\textit{left}}=(v_{-2w},\ldots,v_{0}),P_{\textit{right}}=(v_{n+1},\ldots,v_% {n+2w})$ be $2$ new paths. Extend $G$ to $G^{\prime}$ by adding an edge $(v_{0},v_{1})$ , and another edge $(v_{n},v_{n+1})$ . Let $P^{\prime}=P_{\textit{left}}\oplus(v_{0},v_{1})\oplus P\oplus(v_{n},v_{n+1})% \oplus P_{\textit{right}}$ . (Figure 6)

Figure 6:

G^{\prime}

and

P^{\prime}

.

$\blacktriangleright$ Remark 30.

$d_{G^{\prime}}(u,v)=d_{G}(u,v)$ for any two vertives $u,v\in V(G)$ . Moreover, $u_{0},u_{1},\ldots,u_{k}$ are cut-vertices of $G^{\prime}$ .

Given $w\in\mathbb{N}$ , Algorithm 4 selects “blue” edges on $P^{\prime}$ so that consecutive blue edges are spaced at distance $2w-1$ . Based on these blue edges, it removes additional edges from $G^{\prime}$ . We have the following theorem (proof omitted here due to space; see the thesis [13]):

Theorem 31.

Let $w\in\mathbb{N}$ , let $G$ be a path–cactus graph in which every cycle has even length, and let $G^{\prime}$ be the extended graph used by Algorithm 4. Then Algorithm 4 outputs a random set $F^{\prime}\in\mathcal{F}_{2w}(G^{\prime})$ such that

\Pr[e\in F^{\prime}]\;\leq\;\tfrac{1}{w}\qquad\text{for all }e\in E(G^{\prime}).

Hence $SDD(G^{\prime},2w,\tfrac{1}{w})$ exists. Since $G$ is a subgraph of $G^{\prime}$ , the same diameter and marginal bounds hold for edges of $G$ , and therefore $SDD(G,2w,\tfrac{1}{w})$ exists as well.

To describe Algorithm 4, we first introduce the following definitions.

Definition 32.

We say that a cycle $C_{i}$ is long if $len(L_{i})>2w-1$ . For each long cycle $C_{i}$ , let $a_{i}$ be the mid-vertex of $L_{i}$ . Let $Q_{i}=L_{i}[u_{i-1},a_{i}],Q^{\prime}_{i}=L_{i}[a_{i},u_{i}]$ . Note that $len(Q_{i})=len(Q^{\prime}_{i})\geq w$ . (Figure 7(a))

Definition 33.

We say that a cycle $C_{i}$ is short if $len(L_{i})\leq 2w-1$ . For each short cycle $C_{i}$ , let $a_{i},b_{i}$ be the opposite points of $u_{i-1},u_{i}$ in $C_{i}$ , respectively. Let $Q_{i}=L_{i}[u_{i-1},a_{i}],Q^{\prime}_{i}=L_{i}[u_{i},b_{i}]$ . Also, let $\tilde{Q}_{i}=L_{i}[b_{i},a_{i}]$ be the common sub-path of $Q_{i},Q^{\prime}_{i}$ . Let $C_{i}$ be a short cycle. Let $a^{\prime}_{i}\in V(P^{\prime}[u_{i},v_{n+2w}])$ be the unique vertex with $d(u_{i-1},a^{\prime}_{i})=\frac{len(C_{i})}{2}$ . Similarly, let $b^{\prime}_{i}\in V(P^{\prime}[v_{-2w},u_{i-1}])$ be the unique vertex with $d(u_{i},b^{\prime}_{i})=\frac{len(C_{i})}{2}$ . Moreover, let $P_{i}=P^{\prime}[a^{\prime}_{i},b^{\prime}_{i}]$ . (Figure 7(b))

(a) Long cycle.

(b) Short cycle.

Figure 7: Path-cactus illustrations: (a) long cycle; (b) short cycle.

Now, we are ready to describe the Algorithm 4.

Algorithm 4 Path Cactus Algorithm.

References

[1] Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. SIAM Journal on Computing, 48(3):1120–1145, 2019. doi:10.1137/17M1112406.
[2] Cédric Bentz. Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs. Electronic Notes in Discrete Mathematics, 22:55–60, 2005. doi:10.1016/J.ENDM.2005.06.010.
[3] Jonathan Conroy and Arnold Filtser. How to protect yourself from threatening skeletons: Optimal padded decompositions for minor-free graphs. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2281–2292, 2025. doi:10.1145/3717823.3718252.
[4] R Diestel. Graph theory (vol. 173), 2010.
[5] 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. doi:10.1007/978-3-540-45198-3_4.
[6] Arnold Filtser, Tobias Friedrich, Davis Issac, Nikhil Kumar, Hung Le, Nadym Mallek, and Ziena Zeif. Optimal padded decomposition for bounded treewidth graphs. arXiv preprint arXiv:2407.12230, 2024. doi:10.48550/arXiv.2407.12230.
[7] Lester Randolph Ford and Delbert R Fulkerson. Maximal flow through a network. Canadian journal of Mathematics, 8:399–404, 1956.
[8] Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, and Ziena Zeif. Approximate max-flow min-multicut theorem for graphs of bounded treewidth. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1325–1334, 2023. doi:10.1145/3564246.3585150.
[9] 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. doi:10.1137/S0097539793243016.
[10] 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. doi:10.1007/BF02523685.
[11] T Chiang Hu. Multi-commodity network flows. Operations research, 11(3):344–360, 1963.
[12] Sina Kalantarzadeh. Cuts in optimization and approximation: Generalized MIR cutting plane and integrality gap bounds for the planar multicut problem. Master’s thesis, University of Waterloo, 2025.
[13] Sina Kalantarzadeh. Cuts in Optimization and Approximation: Generalized MIR Cutting Plane and Integrality Gap Bounds for the Planar Multicut Problem. Master’s thesis, University of Waterloo, 2025. URL: https://hdl.handle.net/10012/22484.
[14] Sina Kalantarzadeh and Nikhil Kumar. Improved lower bounds on multiflow-multicut gaps, 2025. doi:10.48550/arXiv.2507.06576.
[15] 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. doi:10.1145/167088.167261.
[16] 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. doi:10.1016/0020-0190(93)90228-2.

Appendix A $\frac{3}{2}$ Lower Bound for CYCLE

In the following, Lemma 34 shows that $\alpha_{\textsc{CYCLE}}\geq\tfrac{3}{2}-\tfrac{2}{2k+1}$ for any $k\in\mathbb{N}$ . Letting $k\to\infty$ implies $\alpha_{\textsc{CYCLE}}\geq\tfrac{3}{2}$ .

Lemma 34.

Let $M$ be the following minimum multicut instance. The base graph is a cycle $C$ with $2k+1$ vertices and unit edge costs $c_{e}=1$ for all $e\in E(C)$ . The source–sink pairs are $\{(u,v)\mid d_{C}(u,v)=k\}$ . Then

\frac{\textsc{OPT}_{IP}(M)}{\textsc{OPT}_{LP}(M)}\;\geq\;\frac{3}{2}-\frac{2}{% 2k+1}.

Proof.

We claim $\textsc{OPT}_{IP}(M)=3$ . Indeed, removing any two edges from $C$ yields two path components whose total length is $(2k+1)-2=2k-1$ . Hence one component has length at least $k$ . That component contains a subpath of length exactly $k$ , which separates some designated source–sink pair at distance $k$ ; thus two edges never suffice. Conversely, deleting three suitably placed edges clearly disconnects all such pairs, so $\textsc{OPT}_{IP}(M)=3$ .
For the LP relaxation (1), set $x_{e}=\tfrac{1}{k}$ for all $e\in E(C)$ . Every designated $s$ – $t$ path has exactly $k$ edges, so $x(P)=\sum_{e\in P}x_{e}=k\cdot\tfrac{1}{k}=1$ , and $x$ is feasible. Therefore

\textsc{OPT}_{LP}(M)\;\leq\;\sum_{e\in E(C)}c_{e}x_{e}\;=\;(2k+1)\cdot\tfrac{1% }{k}\;=\;\frac{2k+1}{k}.

It follows that

\frac{\textsc{OPT}_{IP}(M)}{\textsc{OPT}_{LP}(M)}\;\geq\;\frac{3}{(2k+1)/k}\;=% \;\frac{3k}{2k+1}\;=\;\frac{3}{2}-\frac{2}{2k+1}.\

$\hfill\blacktriangleleft$

Appendix B Proof of Lemma 6

Proof.

Fix $G\in\mathcal{G}$ and $w\in\mathbb{N}$ . Create $G^{\prime}$ from $G$ by subdividing every edge of $G$ into a path of length $2k$ . Since $\mathcal{G}$ is closed under subdivisions, $G^{\prime}\in\mathcal{G}$ ; moreover, every cycle length in $G^{\prime}$ is multiplied by $2k$ , hence divisible by $2k$ , so $G^{\prime}\in\mathcal{G}^{\prime}$ . By assumption, there exists an SDD distribution $\mathcal{D}^{\prime}=\{y^{\prime}_{F^{\prime}}\}_{F^{\prime}\in\mathcal{F}_{4% kw}(G^{\prime})}$ with

\Pr_{F^{\prime}\sim\mathcal{D}^{\prime}}[e^{\prime}\in F^{\prime}]\;\leq\;% \tfrac{\alpha}{4kw}\qquad\text{for every }e^{\prime}\in E(G^{\prime}).

Coarsening map.

For $F^{\prime}\subseteq E(G^{\prime})$ , define the coarsening

\Phi(F^{\prime})\;=\;\{\,e\in E(G)\ :\ \text{at least one subdivision edge of % $e$ lies in }F^{\prime}\,\}.

We claim: if $F^{\prime}$ is a $(4kw)$ -diameter decomposition of $G^{\prime}$ , then $\Phi(F^{\prime})$ is a $(2w)$ -diameter decomposition of $G$ . Indeed, distances in $G^{\prime}$ are exactly $2k$ times the corresponding distances in $G$ (every original edge became a path of length $2k$ ). Removing $F^{\prime}$ leaves every component of $G^{\prime}$ with diameter $<4kw$ (in the $G^{\prime}$ metric), which translates to diameter $<(4kw)/(2k)=2w$ in the $G$ metric after contracting each subdivided path back to its original edge. Thus $\Phi(F^{\prime})\in\mathcal{F}_{2w}(G)$ . Define a distribution $\mathcal{D}=\{y_{F}\}_{F\in\mathcal{F}_{2w}(G)}$ by

y_{F}\;=\;\sum_{\begin{subarray}{c}F^{\prime}\in\mathcal{F}_{4kw}(G^{\prime})% \\ \Phi(F^{\prime})=F\end{subarray}}y^{\prime}_{F^{\prime}}.

This is a valid probability distribution since the $\Phi$ -preimages of distinct $F$ ’s are disjoint and $\sum_{F^{\prime}}y^{\prime}_{F^{\prime}}=1$ . Fix $e\in E(G)$ , and let its $2k$ subdivision edges in $G^{\prime}$ be $e_{1}^{\prime},\ldots,e_{2k}^{\prime}$ . Then

	$\displaystyle\Pr_{F\sim\mathcal{D}}[e\in F]\;=\;\Pr_{F^{\prime}\sim\mathcal{D}% ^{\prime}}[\Phi(F^{\prime})\ni e]\;$	$\displaystyle=\;\Pr_{F^{\prime}\sim\mathcal{D}^{\prime}}\Big[\,\bigvee_{i=1}^{% 2k}(e_{i}^{\prime}\in F^{\prime})\,\Big]\;$
		$\displaystyle\leq\;\sum_{i=1}^{2k}\Pr_{F^{\prime}\sim\mathcal{D}^{\prime}}[e_{% i}^{\prime}\in F^{\prime}]\;\leq\;2k\cdot\tfrac{\alpha}{4kw}\;=\;\tfrac{\alpha% }{2w},$

where we used the union bound and the marginal bound in $\mathcal{D}^{\prime}$ . Therefore $\mathcal{D}$ witnesses $SDD(G,2w,\alpha/(2w))$ , as required. $\hfill\blacktriangleleft$

Appendix C $2$ Lower Bound for PATH-CACTUS

We give a path–cactus instance with integrality gap approaching $2$ . Let the graph consist of $n$ triangles $\Delta_{1},\ldots,\Delta_{n}$ in a path, where $\Delta_{i}$ has vertices $u_{i-1},u_{i},v_{i}$ and consecutive triangles share $u_{i}$ . Set $c(u_{i},v_{i})=c(u_{i-1},v_{i})=1$ for all $i$ , and assign arbitrarily large cost to all other edges. Let the demand pairs be all $(v_{i},v_{j})$ with $1\leq i<j\leq n$ .

Figure 8: Path–cactus lower-bound construction.

Fractional solution: set $x(u_{i},v_{i})=x(u_{i-1},v_{i})=\tfrac{1}{2}$ for all $i$ . Every $v_{i}\!-\!v_{j}$ path crosses $2(j-i)$ such edges, so $x(P)\geq 1$ ; the LP cost is $n$ .
Integral cost: to separate all $(v_{i},v_{j})$ pairs, at least two unit-cost edges must be cut in each of at least $n-1$ triangles, hence any multicut costs $\geq 2n-2$ .
Therefore the gap is

\frac{\textsc{OPT}_{IP}}{\textsc{OPT}_{LP}}\;\geq\;\frac{2n-2}{n}\xrightarrow[% n\to\infty]{}2,

so $\alpha_{\textsc{PATH\text{-}CACTUS}}\geq 2$ .

[bib.bib1] [1] Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. SIAM Journal on Computing, 48(3):1120–1145, 2019. doi:10.1137/17M1112406.

[bib.bib2] [2] Cédric Bentz. Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs. Electronic Notes in Discrete Mathematics, 22:55–60, 2005. doi:10.1016/J.ENDM.2005.06.010.

[bib.bib3] [3] Jonathan Conroy and Arnold Filtser. How to protect yourself from threatening skeletons: Optimal padded decompositions for minor-free graphs. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2281–2292, 2025. doi:10.1145/3717823.3718252.

[bib.bib4] [4] R Diestel. Graph theory (vol. 173), 2010.

[bib.bib5] [5] 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. doi:10.1007/978-3-540-45198-3_4.

[bib.bib6] [6] Arnold Filtser, Tobias Friedrich, Davis Issac, Nikhil Kumar, Hung Le, Nadym Mallek, and Ziena Zeif. Optimal padded decomposition for bounded treewidth graphs. arXiv preprint arXiv:2407.12230, 2024. doi:10.48550/arXiv.2407.12230.

[bib.bib7] [7] Lester Randolph Ford and Delbert R Fulkerson. Maximal flow through a network. Canadian journal of Mathematics, 8:399–404, 1956.

[bib.bib8] [8] Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, and Ziena Zeif. Approximate max-flow min-multicut theorem for graphs of bounded treewidth. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1325–1334, 2023. doi:10.1145/3564246.3585150.

[bib.bib9] [9] 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. doi:10.1137/S0097539793243016.

[bib.bib10] [10] 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. doi:10.1007/BF02523685.

[bib.bib11] [11] T Chiang Hu. Multi-commodity network flows. Operations research, 11(3):344–360, 1963.

[bib.bib12] [12] Sina Kalantarzadeh. Cuts in optimization and approximation: Generalized MIR cutting plane and integrality gap bounds for the planar multicut problem. Master’s thesis, University of Waterloo, 2025.

[bib.bib13] [13] Sina Kalantarzadeh. Cuts in Optimization and Approximation: Generalized MIR Cutting Plane and Integrality Gap Bounds for the Planar Multicut Problem. Master’s thesis, University of Waterloo, 2025. URL: https://hdl.handle.net/10012/22484.

[bib.bib14] [14] Sina Kalantarzadeh and Nikhil Kumar. Improved lower bounds on multiflow-multicut gaps, 2025. doi:10.48550/arXiv.2507.06576.

[bib.bib15] [15] 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. doi:10.1145/167088.167261.

[bib.bib16] [16] 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. doi:10.1016/0020-0190(93)90228-2.

Improved Upper Bounds on Multiflow-Multicut Gaps in Cactus Graphs

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

2 Preliminaries

Definition 1.

Definition 2.

2.1 Graphs Classes

2.2 Linear Programming Relaxation for the Minimum Multicut Problem

Definition 3.

2.3 Transition from the Minimum Multicut Problem to the Small Diameter Decomposition Problem

Definition 4 (Small Diameter Decomposition (SDD)).

Theorem 5 (Theorem 2 of [14]).

Lemma 6 (see Appendix B for the proof in the appendix).

2.4 Small Diameter Decomposition for Trees

Theorem 7.

Proof.

Definition 8.

3 Cycle

▶ Remark 9.

Lemma 10.

Proof.

4 Cactus

Lemma 11.

Proof.

▶ Remark 12.

Lemma 13.

Proof.

Lemma 14.

Proof.

5 Unicyclic Graphs

▶ Remark 15.

Lemma 16.

Proof.

Claim 17.

Proof.

Claim 18.

Proof.

Definition 19.

Lemma 20.

Proof.

▶ Remark 21.

Lemma 22.

Proof.

Lemma 23.

Proof.

Lemma 24.

Proof.

Corollary 25.

Proof.

6 Path Cactus

Definition 26.

Definition 27.

Definition 28.

Definition 29.

▶ Remark 30.

Theorem 31.

Definition 32.

Definition 33.

References

Appendix A 𝟑𝟐 Lower Bound for CYCLE

Lemma 34.

Proof.

Appendix B Proof of Lemma 6

Proof.

Coarsening map.

Appendix C 𝟐 Lower Bound for PATH-CACTUS

$\blacktriangleright$ Remark 9.

$\blacktriangleright$ Remark 12.

$\blacktriangleright$ Remark 15.

$\blacktriangleright$ Remark 21.

$\blacktriangleright$ Remark 30.

Appendix A $\frac{3}{2}$ Lower Bound for CYCLE

Appendix C $2$ Lower Bound for PATH-CACTUS