Thin Trees for near Minimum Cuts

To prove Theorem 1, we will reduce this problem to the strong thin tree conjecture for laminar families of cuts, which was shown to be true by Klein and Olver [15]. Their result is phrased in the language of finding spanning trees satisfying prescribed cut bounds on a given laminar family. Here we state a version of their theorem for our setting.

This is a slightly different form of the theorem stated in [15], and the quantitative improvement for our setting where all sets in the laminar family are near-minimum cuts requires unpacking their proof slightly. We discuss these details in Appendix A.

Given the existence of thin trees for laminar families, it is very natural to try and leverage this. A plausible first attempt is to take an arbitrary maximal laminar family $ℒ$ of near minimum cuts and find a tree that is thin with respect to $ℒ$ using Theorem 2. In the case of minimum cuts, this works: taking a maximal laminar family of min cuts and finding a tree which is thin for $ℒ$ implies that $|T\cap \delta (S)|\le O(1)$ for all minimum cuts $S$. This can be shown in a straightforward manner using the cactus representation of the minimum cuts [8]. It is perhaps unsurprising that this works given that minimum cuts can be uncrossed; if $S$ and $T$ are crossing minimum cuts, then so are $S\cap T$ and $S\cup T$.

So, one might hope that this simple approach extends to the set of $\eta$-near minimum cuts for some $\eta >0$. Unfortunately, this is not the case. For an extreme example, consider the following graph with an even number of vertices $n$ displayed in Figure 1. Begin with a Hamiltonian cycle $H_1=v_1,\mathrm{\dots },v_n$ in clockwise order with $k$ edges between adjacent vertices. Then, add a single copy of a second Hamiltonian cycle $H_2=v_1,v_2,v_n,v_3,v_{n-1},v_4,v_{n-2},\mathrm{\dots },v_{n/2+1},v_1$. In other words, to construct $H_2$, begin with $v_1$ and then alternately add the first new vertex clockwise of $v_1$ and the first new vertex counterclockwise of $v_1$, terminating at $v_{n/2+1}$, at which point we return to $v_1$.

Taking $k\gg n$ (although this is not strictly necessary for the example to work), it is the case that every interval of $H_1$ is a near minimum cut if we consider the set of $\eta$-near minimum cuts for any constant $\eta >0$. Thus, we can choose $ℒ$ to be any set of intervals. Define

In other words, we choose $n-2$ sets to be in $ℒ$, with the $i$th set consisting of the first $i+1$ vertices of $H_2$ (starting with $v_1$). But now, taking the edges of $H_2$ (without the last one) is a thin tree for $ℒ$. But it is far from thin for the cut $\{v_2,\mathrm{\dots },v_{n/2}\}$; in fact, it has every edge of the tree.

We remark that the set of $\eta$-near minimum cuts cannot be uncrossed; if $A$ and $B$ are crossing $\eta$-near minimum cuts, $A\cap B$ and $A\cup B$ are both necessarily $2\eta$-near minimum cuts, but this enlargement of $\eta$ can compound over taking combinations of many cuts. This is the key reason that near minimum cuts can give rise to much richer structures than minimum cuts.

Despite this, we are able to show that a very carefully constructed laminar family suffices. The construction is quite delicate. We make heavy use of the polygon representation of $1/5$-near-minimum cuts [5, 6, 7], which we will discuss in detail in the next section.

We remark that we have prioritized a more structured, modular analysis over obtaining the best possible constants. We anticipate that a more refined analysis (possibly with some adjustments to the algorithm) can show the result for some larger $\eta$. The polygon representation applies to the set of $\eta$-near minimum cuts for any $\eta \le 1/5$. Thus, a natural question is whether our techniques can be made to work up to this limit; this seems to require some additional ideas.

Another natural question is whether the use of the polygon representation can be avoided in order to obtain the result for $\eta >1/5$. A result of this type would be of significant interest, as it could shed light on how to handle much more general cut families.

The thin tree conjecture is known to hold for planar and bounded genus graphs [19]. As already mentioned, the best known result for general graphs is $O(\mathrm{poly}\log \log n/k)$ thinness [1]; this result is not constructive. The best known constructive result gives thinness of $O(\frac{\log n}{\log \log n\cdot k})$ [2].³³3We remark that since this is a randomized algorithm and it is not known how to test the thinness of a tree in polynomial time, this is not fully constructive.

The study of thinness for particular cut sets began with Fürer and Raghavachari [9], who constructed thin trees with respect to the singleton cuts. This predates the thin tree conjecture, but questions concerning the existence of spanning trees satisfying bounds across given cuts, in this case singleton cuts, are well-studied in their own right. Goemans [11] and Singh and Lau [22] studied minimum cost bounded degree spanning trees. Bansal et al. [4] studied the problem of designing a spanning tree which crosses each cut in a laminar family at most a specified number of times, and showed how to obtain a tree with additive $O(\log n)$ violation whenever the fractional relaxation is feasible. Olver and Zenklusen [18] showed one can achieve thinness for any chain of cuts $S_1\subset S_2\subset \mathrm{\cdots }\subset S_k\subset V$, and Linhares and Swamy [16] resolved the minimum cost version of this question up to a small approximation factor in cost.

Near minimum cuts have been studied in several contexts, for example, Karger and Stein [13] gave bounds on how many such cuts can exist, and Benczúr [5, 6] and Benczúr and Goemans [7] studied their structure and defined the polygon representation of near minimum cuts, which we will rely upon heavily in this work. Karlin, Klein, and Oveis Gharan [14] further studied the polygon representation to improve the integrality gap of the subtour polytope and proved some properties we will make use of in this work. Bansal, Cheriyan, Grout, and Ibrahimpur [3] studied the problem of finding a minimum cover of all $\alpha$-near minimum cuts in a $k$-edge-connected graph (i.e. a minimum cardinality set of edges so that each near minimum cut includes an edge from the set), and give a 16-approximation for any $\alpha$.

Given a (multi-)graph $G=(V,E)$ and $S\subset V$, we will use $\delta (S)$ to denote the set of edges with exactly one endpoint in $S$. Recall a graph is $k$-edge-connected if $|\delta (S)|\ge k$ for all $\mathrm{\varnothing }⊊S⊊V$.

We will often identify a cut $(S,\overline{S})$ with (an arbitrary) one of its shores $S$ and $\overline{S}$, as in the following definition.

The following is standard and we simply cite a place it is proved.

Benczúr and Goemans [7] showed that any connected component of $\eta$-near minimum cuts admits a so-called polygon representation so long as $\eta \le 1/5$. Here we define a polygon $P$ representing a connected component $𝒞$ of $\eta$-near minimum cuts (for $\eta \le 1/5$) of a $k$-edge-connected graph.

1. 1.

   A polygon representation is a convex regular polygon with a collection of diagonals connecting vertices of the polygon. All polygon edges and diagonals are drawn using straight lines in the plane. The diagonals partition the polygon into cells.

2. 2.

   Each atom $a\in 𝒜(𝒞)$ is mapped to a cell of the polygon. If one of these cells is bounded by some portion of the polygon boundary it is non-empty and we call its atom an outside atom. We call the atoms of all other non-empty cells inside atoms. Note that some cells may not contain any atom. WLOG label the outside atoms $a_0,\mathrm{\dots },a_{m-1}$ in counterclockwise order, and label the inside atoms arbitrarily. We also label points of the polygon $p_0,\mathrm{\dots },p_{m-1}$ such that outside atom $a_i$ is on the side $(p_i,p_{i+1})$ and $a_0$ is on the side $(p_{m-1},p_0)$.

3. 3.

   No cell has more than one incident outer polygon edge.

4. 4.

   Each diagonal (often called a representing diagonal) defines a cut such that each side of the cut is given by the union of the atoms on each side. Furthermore, the collection of cuts given by these diagonals is exactly $𝒞$.

For set of vertices $S$ and a polygon $P$ for connected component $𝒞$, let $O_P(S)$ denote the set of outside atoms contained in $S$. By the definition of polygons, $S,S^{\prime }\in 𝒞$ cross if and only if $O_P(S)$ and $O_P(S^{\prime })$ cross. When the polygon is clear from context, we will sometimes simply use $O(S)$.

Inside atoms only exist if certain structures called $k$-cycles appear in the connected component $𝒞$ being represented by $P$.

In [14], the following lemmas were shown. The following lemma shows that cells of $P$ that can be described with few diagonals and do not intersect any side of $P$ are empty.

It is clear that in any polygon representing a connected component of cuts $𝒞$, for any $S,T\in 𝒞$, $S=T$ if and only if $O(S)=O(T)$ and similarly $S,T$ cross if and only if $O(S),O(T)$ cross. The following two lemmas extend this notion to all $1/5$-NMC, even in polygons which were constructed for smaller values of $\eta$.

In this subsection, we describe a recursive top-down procedure to construct $ℒ$, the desired laminar family. Before describing the algorithm formally, we start by giving some intuition for the algorithm and an overview of its general steps. For this intuition, assume that there is a single polygon and there are no inside atoms.

If the set of near minimum intervals is already laminar, we are done. At the other extreme, if all intervals $⟨l,r⟩$ are near minimum, then we can set $ℒ=\{\mathrm{cut}(1,2),\mathrm{cut}(1,3),\mathrm{\dots },\mathrm{cut}(1,n)\}$ because for all $l,r$, $\mathrm{cut}(l,r)$ is covered by $\mathrm{cut}(1,r)$ and $\mathrm{cut}(1,l)$. In fact,
$ℒ=\{\mathrm{cut}(1,2),\mathrm{cut}(1,3),\mathrm{\dots },\mathrm{cut}(1,n)\}$ would always work if $⟨1,r⟩$ is the shadow of a $4\eta$-NMC for all $r$. Unfortunately, this is not always the case.

Instead, suppose we greedily add all cuts of the form $\mathrm{cut}(1,r)$ that are $4\eta$-NMCs to $ℒ$. Let $S=\mathrm{cut}(l_S,r_S)$ be an $\eta$-NMC. Let

Suppose $i$ and $j$ exists. Then, $\mathrm{cut}(1,i)$ and $\mathrm{cut}(1,j)$ covers all edges of $\delta (S)$ except the edges between $⟨1,l_S⟩$ and $⟨l_S,i⟩$ and the edges between $⟨j,r_S⟩$ and $⟨r_S,n⟩$. If we could add $\mathrm{cut}(l_S,i)$ and $\mathrm{cut}(j,r_S)$ (assuming they exist and are $4\eta$-NMCs), then we can cover all edges of $\delta (S)$. We can almost do that: since $\mathrm{cut}(1,i)$ is a $4\eta$-NMC and $\mathrm{cut}(l_S,r_S)$ is an $\eta$-NMC, by Lemma 5, $\mathrm{cut}(l_S,i)$ exists and is a $5\eta$-NMC. In the actual algorithm, instead of greedily taking all prefix $4\eta$-NMCs, we will only take a subset of $2\eta$-NMCs we define as special cuts (see Definition 18). We argue that in that case, $\mathrm{cut}(l_S,i)$ and $\mathrm{cut}(j,r_S)$ are also special.

It is still unclear whether we can add both $\mathrm{cut}(l_S,i)$ and $\mathrm{cut}(j,r_S)$ to $ℒ$. A natural way to proceed with the algorithm is to recurse on all subintervals $⟨x_k,x_{k+1}⟩$ where are indices such that $⟨1,x_k⟩$ is special. Suppose $x_a=i$ and $x_b=j$. When we recurse on $⟨x_{a-1},x_a⟩$, we need to add special intervals from the right to add $\mathrm{cut}(l_S,i)$, but when we recurse on $⟨x_b,x_{b+1}⟩$, we need to add special intervals from the left to add $\mathrm{cut}(j,r_S)$. How does the algorithm know which direction to add intervals? A wishful attempt is to alternate between adding intervals from the left and right, and surprisingly this works (modulo some technical additions). It turns out that for any $S=\mathrm{cut}(l_S,r_S)$, we can pick $O(1)$ sets added to $ℒ$ in $3$ recursion layers that covers $S$.

We define special cuts and intervals that are alluded in the outline.

By Lemma 5, any special cut is a $2\eta$-NMC; however, not every $2\eta$-NMC is necessarily special. Similarly, the set difference of two crossing special cuts is a $4\eta$-NMC, since . Note that by Corollary 17, a special interval is the intersection, union or set difference of crossing NMIs.

Here is a useful lemma about special intervals that will be used repeatedly in our proofs.

Here, we will prove a weaker coverage statement than is claimed by Theorem 14, that only refers to outside atoms.

Note that if “every pair of outside atoms” was instead “every pair of atoms”, this would yield Theorem 14.

Next, we show how to extend Lemma 22 to cover all pairs of atoms covered by an $\eta$-near minimum cut, not merely all pairs of outside atoms.

Now that we have shown how to construct a laminar family ${ℒ}_P$ on the atoms of a polygon $P$ for a connected component of cuts $𝒞$ so that all cuts in $𝒞$ are implied by ${ℒ}_P$, we will describe how to construct the overall laminar family. We will begin by constructing a cross-free family $ℛ$.

In particular, initialize a cross-free family $ℛ$. Add to $ℛ$ one side of each $\eta$-near minimum cut which is not crossed (i.e. every connected component $𝒞$ with $|𝒞|=1$). Then, construct a polygon $P$ for each connected component $𝒞$ of near minimum cuts with $|𝒞|>1$. Finally, run our construction procedure on each polygon $P$ (setting one of the outside atoms as root), and add the resulting laminar family of cuts ${ℒ}_P$ to $ℛ$.

Here we make use of the following from Benczúr: