Edge-Cuts and Rooted Spanning Trees

2025-05-03 0 0 167.22KB 16 页 10玖币

侵权投诉

arXiv:2210.13320v1 [math.CO] 24 Oct 2022

Mohit Dagaa,∗

aKTH Royal Institute of Technology, Stockholm - Sweden

Abstract

We give a closed form formula to determine the size of a k-respecting cut.

Further, we show that for any k, the size of the k-respecting cut can be found

only using the size of 2-respecting cuts.

Keywords:

1. Introduction

An edge-cut of a graph is said to krespect a given spanning tree, if the cut

shares kedges with the tree. The technique of ﬁnding cuts that k-respect a given

set of spanning trees is used in designing algorithms to ﬁnd the size of cuts. The

pioneering use appears in two breakthrough results by Karger (ACM STOC 1996

and JACM 2000) and Thorup (ACM STOC 2001 and Combinatorica 2007). The

former [Kar00] gives the ﬁrst linear time algorithm to ﬁnd the size of a min-cut,

whereas the later [Tho07] gives the ﬁrst fully dynamic algorithm for min-cuts.

A common technique among these is to ﬁnd the size of a minimum 2-respecting

cut in a given set of spanning trees. Over the years this technique of ﬁnding a 2-

respecting cut have found applications in designing algorithms to ﬁnd min-cuts

in several diﬀerent settings and computational models: centralized, parallel,

distributed, streaming, and dynamic.

In the centralized setting post the breakthrough result by Karger, recent

results by Kwarabayashi and Thorup [KT15], improved further by Henzinger

et al. [HRW20] give a deterministic linear time. Several simpler algorithms

∗Corresponding author

Email address: mdaga@kth.se (Mohit Daga)

have been designed that ﬁnd the size of a min cut using new algorithms to

ﬁnd the size of a 2-respecting cut given a set of trees [BLS20, GMW20, Sar21].

Further, a recent breakthrough result that ﬁnds all pairs max ﬂow in ˜

O(n2) uses

4-respecting cuts [AKL+21]. .

In the distributed setting the ﬁrst sub linear algorithm [DHNS19] uses the

concept of 2-respecting cut. Here the algorithms to ﬁnd the min-cut has two

parts: algorithm to reduce the size of the graph through a contraction mech-

anism and given a set of trees provide eﬃcient algorithm to ﬁnd the size of

a 2-respecting cut. The result in [DHNS19] is further improved by providing

better algorithm for one of the two parts, even leading to an optimal algorithm

to ﬁnd the size of min-cut [DEMN21, GZ22, GNT20, MN20]. Though, the un-

derlying similarity of ﬁnding the size of a minimum 2-respecting cut is common

among all. There are several open problems that still remain here, for example

the size of a small cut [PT11, Par19], for a constant k.

Most of the aforementioned results rely on a closed form expression to ﬁnd

size of 2-respecting cuts, and the fact that only a small number of trees are re-

quired to be constructed in order to ﬁnd a tree that 2-respects the minimum cut.

The guarantees regarding the small number of trees come from Nash Williams,

which states that the number of disjoint trees in a k-connected graph is at most

k/2 [CMW+94, Die12]. In this paper, we extend the closed form expression to

ﬁnd size of any k-respecting cut. Furthermore, we show that the size of any k-

respecting cut can just be found using the size of 2-respecting cuts. Our results

rely on the cut-space concept from graph-theory. First, we give a closed form

expression that ﬁnds the size of any k-respecting cut (Theorem 1.1). Secondly,

we show that the size of any k-respecting cut can be ﬁnd if we know the size of

1-respecting cuts, and 2-respecting cuts (Theorem 1.2).

Let G= (V, E) be the given tree. Given a rooted spanning tree T, let E(T)

be the edges in the tree, and let eT(v), be the tree edge between vand its parent

for all v∈V, except the root. For any A⊂V, let δ(A) be the edges in the cut

(A, V \A). For any rooted spanning tree T, let v↓Tdenote the set of vertices

that are decedents of vin T, including vitself.

Theorem 1.1. Let G= (V, E)be a given graph, let Tbe a rooted spanning

tree of Gand A⊂V. Suppose E(T)∩δ(A) = {eT(v1),...,eT(vk)}, for some

vertices S={v1,...,vk}. Then

|δ(A)|=

l=1

(−1)l−12l−1X

S′⊆[k]

|S′|=l

\

i∈S′

δ(vi↓T)

(1)

Further using some combinatorial arguments we show that the size of any

k-respecting cut can just be found using pair-wise 2-respecting cuts.

Theorem 1.2. Let G= (V, E)be a given graph, let Tbe a rooted spanning

tree of Gand A⊂V. Suppose E(T)∩δ(A) = {eT(v1),...,eT(vk)}, for some

vertices S={v1,...,vk}. Then |δ(A)|can be determined if the following is

known

•|δ(x↓T)| ∀x∈S,

•|δ(x↓T)∩δ(y↓T)| ∀x, y ∈Sand

•the path from root of Tto xfor all x∈S.

2. Preliminaries

For any rooted spanning tree T, we denote rTas its root. For any v∈V,

let v↓Tbe the vertex set that are decedents of vin the tree Tincluding itself.

Similarly, v↑Tis the set of vertices which are on the path rTto v. For all vertices

v∈V\rT, we use πT(v) to denote the parent of vin Tand eT(v) to denote

the tree edge between vand πT(v). Let ℓT(v) be the distance of vertex vfrom

the root rTin the tree T. Let childrenT(v) denote the children of the vertex v

in the tree T. If vis a leaf node, then deﬁne childrenT(v) to be ∅. For any two

vertices vand u, we say that vand uare independent w.r.t the tree T, denoted

using v⊥Tuiﬀ v↓T∩u↓T=∅. If they are not then we say that they are not

independent, and denote it using v6⊥Tu.

We will use ⊕to denote the symmetric diﬀerence operator. More precisely,

for any sets A1, A2,...,Ak, we have a∈Lk

k′=1 Ak′iﬀ |{k′∈[k] : a∈Ak′}| is

odd. Throughout this paper, when we use {}, we mean it to be set, and not

multi-set. That is each entry in {} occurs exactly once. Whenever we use an

index k, it means a whole number less than the number of vertices in the graph.

We stress the readers to familiarize with ⊕operator. We make the following

simple preposition to do the same. These qualify how the symmetric diﬀerence

operator appears when two sets are considered.

Proposition 2.1. Let A1and A2be any two sets. Suppose A1∩A2=∅, then

A1⊕A2=A1∪A2. Further, suppose, A2⊆A1, then A1⊕A2=A1\A2.

We use a well-known result that states that cut-spaces are a vector space

with respect to the ⊕operator. This can be found in standard graph theory

books, for ex. Bondy and Murty [BM76].

Lemma 2.2 (Also noted as Proposition 2.1 in [PT11]).Let Tbe a given

spanning tree and v1, v2,...,vk∈V. Then δ(v1↓T⊕v2↓T⊕... ⊕vk↓T) =

δ(v1↓T)⊕δ(v2↓T)⊕...⊕δ(vk↓T)

We also mention a set-theoretic result for the cardinality of xor operation of

ksets.

Proposition 2.3. Suppose A1,...,Akare some sets. Then



i=1

Ai

l=1

(−1)ℓ−12l−1X

S⊆[k]

|S|=l

\

i∈S

Ai

3. Cut Characterization Lemma

In this section, we prove the characterization given in Theorem 1.1. We

know that δ(A) = δ(V\A). We show that for any A⊂V, if δ(A)∩E(T) =

{eT(v1),...,eT(vk)}for some vertex set S={v1,...,vk}, where vi∈V\rT,

then either A=v1↓T⊕...⊕vk↓Tor V\A=v1↓T⊕...⊕vk↓T. This together

with Lemma 2.2 and Proposition 2.3 leads to Theorem 1.1.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.13320v1[math.CO]24Oct2022Edge-CutsandRootedSpanningTreesMohitDagaa,∗aKTHRoyalInstituteofTechnology,Stockholm-SwedenAbstractWegiveaclosedformformulatodeterminethesizeofak-respectingcut.Further,weshowthatforanyk,thesizeofthek-respectingcutcanbefoundonlyusingthesizeof2-respectingcuts.Keyword...

展开>> 收起<<

Edge-Cuts and Rooted Spanning Trees.pdf

共16页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Edge-Cuts and Rooted Spanning Trees

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: