A deterministic near-linear time algorithm for finding minimum cuts in planar graphs
Parinya Chalermsook
Abstract

Jittat Fakcharoenphol

Danupon Nanongkai

with a special supernode v1 which connects to all nodes ¯ adjacent to edges between S and S . The graph G2 are We present a simple deterministic O(n log n)-time divideand-conquer algorithm for finding minimum cuts in planar constructed similarly with another v2 as a sup erno de. graphs. This can be compared to a randomized algorithm In this dividing step, we ensure that the size of the subfor general graphs by Karger that runs in time O(m log 3 n) problems decreases geometrically. We then recursively and also a deterministic algorithm for general graphs by find the minimum cuts inside b oth subproblems. On Nagamochi and Ibaraki that runs in time O(mn + n2 log n). the one hand, if the minimum cut lies entirely in one of We use shortest paths in the dual graphs to partition the these subproblems, we find it recursively. On the other problem, and use the relationship between minimum cuts hand, if the minimum cut lies across S , the structure of in primal graphs and shortest paths in dual graphs to find S allows us to find it efficiently.
2

minimum cuts that cross the partitions efficiently.

1 The problem The minimum cut problem is to find the cut that minimizes the weighted sum of edges whose ends are separated by the cut. The size of the minimum cut is the weighted edge-connectivity of the graph. The best running time for the algorithm for this problem is due to Karger [3] who improving the result by Karger and Stein [4] to get an O(m log3 n) randomized algorithm. Although his algorithm works in general graphs, it is also the previous best known for planar graphs. The best known deterministic algorithm by Nagamochi and Ibaraki runs in time O(mn + n2 log n). We refer to [3, 4] for the history of the problem. For planar graphs, we give a simple deterministic divide-and-conquer algorithm that runs in time O(n log2 n). We note that in the unweighted planar graphs, the sizes of the minimum cuts are at most 5; thus, one can use better algorithms by Alon, Yuster, and Zwick [1]. 2 The algorithm Our algorithm is a divide-and-conquer one. To find the minimum cut of graph G, we first find a dividing cut ¯ (S, S ) with some structural property that determines two smaller subproblems, G1 and G2 , which are constructed as follows. The nodes of G1 are nodes in S
 Dept of Computer Engineering, Kasetsart University, Bangkok 10900, Thailand. Emails: {fengpycs,jtf}@ku.ac.th, danupon@eng.src.ku.ac.th Work done while the second author was a graduate student at UC Berkeley and supported by the DPST scholarship and NSF grant CCR-0105533; he would like to thank Satish Rao for discussion.

2.1 Minimum cuts and a shortest path tree: the dividing step. This section describes the property of the dividing cut and how we find it in linear time. Recall that a cut in the primal graph corresponds to a cycle in the dual. This motivates us to use a shortest path tree in the dual graph to decompose the graph into two subgraphs. We note that the minimum cuts correspond to cycles of minimum length in the dual. The following lemma shows that we can use shortest paths in the dual to constrain the minimum cuts. We say that paths p1 and p2 cross if they share some node. The number of times that p1 and p2 cross is number of paths (including paths with no edges) of p1  p2 . Since a cut is a cycle in the dual graph, we can define the number of times a cut crosses any dual path similarly. The following lemma, stating that given a shortest path p in the dual graph, we only need to consider cuts which cross p at most once, can be proved using the property of shortest paths. Lemma 2.1. For any cut C in G which crosses any shortest path p in the dual G of G more than once, there exists a cut C which crosses p at most once with no longer length. The dividing cut that we use can be constructed from a shortest path tree in the dual as follows. For any graph G, consider its dual G . Let T  be a shortest path tree in G which can be found in linear time using the algorithm by Henzinger, Klein, Rao, and Subramanian [2]. The dividing cut corresponds to some cycle S  in G with the following property: there are 3 nodes a, b, and c on S  such that S  can be decomposed

Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

828


PSfrag replacements

c

T

Fa c

(a)

 Pca

 Pcb

(b)
aF  Pab b

aF  Pab b

Figure 1: (a) the dividing cut, (b) proof of lemma 2.3.
     into 3 paths, Pab , Pcb , and Pca where Pca and Pcb are  paths in T  and Pab is a path along some dual face F . (See Figure 1(a).) We note that from lemma 2.1, there  exists some minimum cut C that crosses each of Pca and  Pcb at most once. ¯ We will use a primal cut (S, S ) corresponding to S  to decompose the graph into two subgraphs. To find S  , we triangulate G , thus splitting some number of nodes in G. Then, we apply the following lemma.

Since the cut forms a cycle, or a closed curve, in the dual planar graph, it partitions the graph into 2 subgraphs. We now call the subgraph which contains the node vF as the inside of the cut. The other subgraph is called the outside of the cut. Because of this definition, we always use vF as the source for the max-flow computation. The problem remains to find the node on the other side.  Let's denote by e the last edge on Pac adjacent to a c . Let face Fa be the face outside S  adjacent to e . We a want to show that the minimum cuts cannot cross the cut S and contains both F and Fa . Thus, we can find the minimum cut using a single max-flow computation from vF to vFa , where vFa is a node in G corresponding to Fa . We prove this fact in the following lemma. (See example in Figure 1(b).) Lemma 2.3. Any cycle C  in G separating G into two subgraphs, the outside and the inside, which con tains F and Fa must either (1) cross the path Pac or   Pbc more than once, or (2) not cross the cycle S at al l. Proof. Assume that C  crosses S  ; thus, it must cross  S  even number of times. It must cross either Pac or   Pbc more than once if it crosses S more than two times. Therefore, we can assume that C  only crosses S  twice.   This implies that C  crosses Pac once and Pbc once. The  lemma follows because C cannot contain both F and Fa . Therefore, to find the minimum cut crossing the dividing cut S , we run one max-flow computation from vF to vFa using the max-flow algorithm for planar graphs by Weihe [6] which runs in time O(n log n). This gives the main result as claimed. References
[1] Noga Alon, Raphael Yuster, and Uri Zwick. Colorcoding. Journal of the ACM (JACM), 42(4):844­856, 1995. [2] Monika R. Henzinger, Philip N. Klein, Satish Rao, and Sairam Subramanian. Faster Shortest-Path Algorithms for Planar Graphs. Journal of Computer and System Sciences, 55(1):3­23, 1997. [3] David R. Karger. Minimum cuts in near-linear time. Journal of the ACM (JACM), 47(1):46­76, 2000. [4] David R. Karger and Clifford Stein. A new approach to the minimum cut problem. Journal of the ACM, 43(4):601­640, 1996. [5] Richard J. Lipton and Robert E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36:177­189, 1979. [6] Karsten Weihe. Maximum (s, t)-flows in planar networks in O(|V | log |V |)-time. Journal of Computer and System Sciences, 55(3):454­476, 1997.

Lemma 2.2. Given any spanning tree T in a triangulated planar graph G = (V , E ), we can find, in linear time, the fundamental cycle determined by some nontree edge e and T that separates the graph into two subgraphs, one inside the cycle and another outside, each containing at most 2/3 fractions of the faces. Proof. (Sketch) A spanning tree T in the dual graph can be formed from the dual edges corresponding to the non-tree edges. By assigning appropriate weights on the nodes of T , an edge separator in T , which exists because of the degree bound, corresponds to the edge e can be found. That proves the lemma. We note the similarity of this lemma and the one in Lipton and Tarjan's separator algorithm [5]. After applying this lemma on G and T  , we can find the cycle S  by noting that the non-tree edge e  determines the path Pab and the paths on T = T  are the other two shortest paths determining S  . 2.2 Finding the minimum cut: the conquering step. We assume that we have the cut S and show how to find the minimum cut which crosses S using one max-flow computation in time O(n log n), yielding an O(n log2 n)-time algorithm. More specifically, we show how to find two nodes in G which are on the different sides of the minimum cut crossing the dividing ¯ cut (S, S ). Recall that the dual cycle S  corresponding to the dividing cut can be decomposed into three paths one of which lies on some dual face F . Let vF be the node in the primal graph corresponding to F .

829