Sparsest cuts and concurrent flows in product graphs

✍ Scribed by Paul Bonsma

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 300 KB
• Volume: 136
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00439-6

✦ Synopsis

A cut [S; S] is a sparsest cut of a graph G if its cut value |S S|=|[S; S]| is maximum (this is the reciprocal of the well-known edge-density of the cut). In the (undirected) uniform concurrent ow problem on G, between every vertex pair of G ow paths with a total ow of 1 have to be established. The objective is to minimize the maximum amount of ow through an edge (edge congestion). The minimum congestion value of the uniform concurrent ow problem on G is an upper bound for the maximum cut value of cuts in G. If both values are equal, G is called a bottleneck graph. The bottleneck properties of cartesian product graphs G × H are studied. First, a ow in G × H is constructed using optimal ows in G and H , and proven to be optimal. Secondly, two cuts are constructed in G × H using sparsest cuts of G and H . It is shown that one of these cuts is a sparsest cut of G × H . As a consequence, we can prove that G × H is (not) a bottleneck graph if both G and H are (not) bottleneck graphs.