# A min-max relation in flowgraphs

下载积分：3000

内容提示： A min-max relation in flowgraphsCarlos E. Ferreira1,2Institute of Mathematics and StatisticsUniversity of S˜ ao Paulo, S˜ ao Paulo, Brazil´Alvaro J. P. Franco1,2Ararangu´ a CampusFederal University of Santa Catarina, Araranguá, BrazilAbstractWe have considered the problem of finding vertex-disjoint dipaths in flowgraphs andwe observed an interesting min-max relation: given a flowgraph G, the minimumsize of a dominator cover in G is equal to the maximum size of a junction partitionof G. In many optimiz...

文档格式：PDF|
浏览次数：1719|
上传日期：2015-12-28 07:17:32|
文档星级：

**********
A min-max relation in flowgraphsCarlos E. Ferreira1,2Institute of Mathematics and StatisticsUniversity of S˜ ao Paulo, S˜ ao Paulo, Brazil´Alvaro J. P. Franco1,2Ararangu´ a CampusFederal University of Santa Catarina, Araranguá, BrazilAbstractWe have considered the problem of finding vertex-disjoint dipaths in flowgraphs andwe observed an interesting min-max relation: given a flowgraph G, the minimumsize of a dominator cover in G is equal to the maximum size of a junction partitionof G. In many optimization problems those relations are closely related to efficientalgorithms to solve them.Keywords: Flowgraphs, dominators, junctions, vertex-disjoint dipaths.1 IntroductionIn [2] we described an efficient algorithm that receives an acyclic digraph Dand a vertex s of D, and returns a partition B of the set of vertices of D suchthat, taking any pair of vertices {u,v}, u and v are in different parts of B if1Supported by CNPq Proc. 456792/2014-7 and FAPESP Proc. 2013/03447-62Emails: cef@ime.usp.br, alvaro.junio@ufsc.brAvailable online at www.sciencedirect.comElectronic Notes in Discrete Mathematics 50 (2015) 109–1141571-0653/© 2015 Elsevier B.V. All rights reserved.www.elsevier.com/locate/endmhttp://dx.doi.org/10.1016/j.endm.2015.07.019
and only if there are vertex-disjoint dipaths from s to u and from s to v, forshort, s is a junction of u and v. In that time, we realized a min-max relationfor reducible flowgraphs. Here, we generalize this relation for any flowgraph.A flowgraph G = (V,A,s) is a digraph where the vertex s reaches anyother vertex in G, i.e., there is in G a dipath from s to any other vertex in G.A vertex w dominates a vertex u if and only if all dipaths from s to u passthrough by w. We say that vertex s trivially dominates all vertices of G. Avertex different from s which dominates u is called a non-trivial dominator ofu. If there are at least two vertex-disjoint dipaths from s to u, then the onlynon-trivial dominator of u is the vertex u itself. A vertex w is the immediatedominator of u if and only if either s = w and there are vertex-disjoint dipathsfrom s to u; only one arc s → u entering in u; or w non-trivially dominatesu and each dominator of u also dominates w, except for u. The conceptof immediate dominator appears in many works such as [4]. In contrast withimmediate dominator, a vertex w is the farthest dominator of a vertex u (?= s)if and only if w is a non-trivial dominator of u and s is the unique vertex whichdominates w. Lastly, a vertex s is a junction of vertices u and v if and only ifthere are internally vertex-disjoint dipaths from s to u and from s to v.Given a flowgraph G = (V,A,s), we define a dominator cover A in Gas a set that contains s, and at least one non-trivial dominator for each udifferent from s in G. Formally, we have that a dominator cover in G is aset A = ∪ u∈G A u where A s = {s}, and A u is a non-empty set of non-trivialdominators of u for all u different from s in G. Note that we could have morethan one dominator cover in G, and we want a cover with the minimum numberof dominators. For example, a possible dominator cover in the flowgraph ofFig. 1 is the set A 1 = {s,a,b,c,e,f,g,h,i,k}.sabcdefghijklmFig. 1: A flowgraph with root inthe bold vertex s.To see why A 1 is a dominatorcover, observe that vertices s, a, b,c, e, f, h, i and k have in-degreemore than 1, and they are non-trivialdominators from themselves (except swhich is in the set by definition). Thevertices a, c, g, and i are parents ofvertices whose in-degree is equal to 1,so they are non-trivial dominators ofthe remaining vertices. However, theshorter set A 2 = {s,a,b,e,f,h,i,k} isalso a dominator cover: a dominates(non-trivially) a, c, d, g and j, i dominates i, l and m, and the remainingC.E. Ferreira, Á.J.P. Franco / Electronic Notes in Discrete Mathematics 50 (2015) 109–114 110
vertices in A 2 dominate themselves.Given a flowgraph G = (V,A,s), the set B = {B 1 ,...,B k } is a junctionpartition of G if it is a partition of V , and the following property holds: ifvertex u belongs to B i and vertex v belongs to B j (i ?= j), then s is a junctionof vertices u and v.The following set is a junction partition of the flowgraph in Fig. 1:{{s},{a,c,d,g,h,j,k},{b,e,f,i,l,m}}. However, the following set is a largerjunction partition: {{s},{a,c,d,g,h,j,k},{b,e,f},{i,l,m}}. It is not so hardto check that these partitions are both junction partitions. We want to find ajunction partition with maximum size.In Section 2, we show that the minimum size of a dominator cover of agiven flowgraph G is equal to the maximum size of a junction partition ofG. As far as we know, there are two main min-max relations in reducibleflowgraphs (a subclass of flowgraphs). Frank and Gy´ arfás [3] proved thatgiven a reducible flowgraph D, the maximum number of vertex-disjoint cyclesin D is equal to the minimum size of a set of vertices which intersect all cyclesin D. In this same work, Frank and Gy´ arfás conjectured the arc version oftheir theorem. Ramachandran proved the conjecture in reducible flowgraphs[5]. We conclude our work in Section 3.2 A min-max relation in flowgraphsWe start this section with the following results.Proposition 2.1 Given a flowgraph G, each vertex different from s in G hasa unique farthest dominator. 2Lemma 2.2 Given a flowgraph G = (V,A,s), and two distinct vertices u 1and u 2 . Let vertices w 1 and w 2 be the farthest dominators of u 1 and u 2 ,respectively. If w 1 is not equal to w 2 , then s is a junction of w 1 and w 2 . 2Lemma 2.3 Given a flowgraph G = (V,A,s), and a junction partition B ={B 1 ,...,B k } for some integer k ≥ 1. Let u (?= s) be a vertex in B i for some iin {1,...,k}. Therefore, all non-trivial dominators of u are in B i .Proof. If there are vertex-disjoint dipaths from s to u, then u is the onlynon-trivial dominator of itself. Since u is in B i , the lemma holds. If there isno vertex-disjoint dipath from s to u, then let w be a non-trivial dominatorof u different from u. If there is no way to take w different from u (i.e., thereexists arc s → u), then w is in B i , and it finishes the proof. From now on, wesuppose that w is a non-trivial dominator of u, and different from u. As wC.E. Ferreira, Á.J.P. Franco / Electronic Notes in Discrete Mathematics 50 (2015) 109–114 111
dominates u, we know that all dipaths from s to u pass through by w. Thus,s is not a junction of vertices w and u. On the other hand, if w is in B j forsome j in {1,...,k} and j ?= i, then, by the junction partition property, sshould be a junction of vertices w and u, a contradiction. Thus, w is in B i .2Lemma 2.4 shows that the problem of finding a dominator cover and theproblem of finding a junction partition of flowgraphs are dual to each other.Lemma 2.5 states the main result of this work.Lemma 2.4 Given a flowgraph G, the size of any dominator cover in G isgreater than or equal to the size of any junction partition of G.Proof. Let A be a dominator cover in G and B be a junction partition of G.We have to show that there exists a different dominator in A for each elementof B. Take any part of B, say B i , and consider the following cases.1. |B i | = 1. Consider that B i = {u}. If u ?= s, then, by Lemma 2.3, u is itsunique non-trivial dominator. The set A u (the non-empty set composed bynon-trivial dominator of u) is equal to {u} = B i . If u = s, then A s = {s} isthe only set which has s. Therefore, we have shown that u occurs in A by B i .2. |B i | ≥ 2. Take u and v in B i such that u ?= v. If s is a junction of u and v,then s is the unique vertex which dominates both u and v. Thus, |A u ∪A v | ≥ 2.By Lemma 2.3, the vertices of A u and A v are in B i . Therefore, such vertices arenot considered again in other part of B. If s is not a junction of u and v, thenthere exists a non-trivial dominator of both u and v. Therefore, |A u ∪A v | ≥ 1.By Lemma 2.3, all vertices of A u and A v are in B i . Once again, such verticesare not considered by other parts of B.Thus, we have shown that there exists a different dominator in A for eachpart of B. Therefore, |A| ≥ |B|. 2Lemma 2.5 Given a flowgraph G, the minimum size of a dominator coverin G is equal to the maximum size of a junction partition of G.Proof. Let B = {B 1 ,...,B k } be a junction partition of G such that k ismaximum. In such partition, some B i = {s} since s is a junction of s and ufor any u in G. W.l.o.g., consider B 1 = {s}. Take a part of B, say B j wherej is in {2,...,k}, and consider two vertices u 1 and u 2 from B j . Consider w 1and w 2 to be the farthest dominators of vertices u 1 and u 2 , respectively. ByLemma 2.3, w 1 and w 2 are in B j . The first goal is to prove that w 1 and w 2are a single vertex. If u 1 = u 2 , then, by Proposition 2.1, we have w 1 = w 2 . Ifu 1 ?= u 2 , then suppose that w 1 ?= w 2 (we will obtain a contradiction). Lemma2.2 ensures that s is a junction of w 1 and w 2 . Let P be a dipath from s to w 1 , Qbe a dipath from s to w 2 , and P and Q be internally vertex-disjoint. ConsiderC.E. Ferreira, Á.J.P. Franco / Electronic Notes in Discrete Mathematics 50 (2015) 109–114 112
B 1jand B 2jto be the set of vertices dominated by w 1 and w 2 , respectively. Notethat a vertex z in B 1j(resp. B 2j ) is in B j , otherwise, by junction partition, wewill obtain a contradiction since s will be a junction of z and w 1 (resp. w 2 ).Take a vertex x in B 1j(resp. y in B 2j ). Take a dipath R 1from w 1 to x (resp.R 2 from w 2 to y). All vertices of R 1 (resp. R 2 ) are in B 1j(resp. B 2j ), otherwise,there will be a dipath from s to x (resp. to y) without w 1 (resp. w 2 ), andthen, w 1 (resp. w 2 ) will not be a dominator of x (resp. y) (see Fig. 2 (a)).Therefore, R 1 and Q (resp. R 2 and P) do not have a common vertexwhereas R 1 and P (resp. R 2 and Q) have only w 1 (resp. w 2 ) in common.Moreover, R 1 and R 2 do not have a common vertex. If there will be a commonvertex z in both R 1 and R 2 (z ?= w 1 and z ?= w 2 since w 1 ?= w 2 ), then therewould be a dipath from s to x without w 1 (resp. from s to y without w 2 ), andw 1 would not be a dominator of x (resp. w 2 would not be a dominator of y)(see Fig. 2 (b)). It shows that B 1j∩ B 2j= ∅ and s is a junction of x and y.s s w 1w 1w 2zzxxyPQ(a) (b)Fig. 2. (a) R 1 is a dipath from w 1 to x passing through z which is not dominatedby w 1 (there is a dipath from s to z “jumping” w 1 ). This implies the followingcontradiction: w 1 does not dominate x. (b) If z is a common vertex in dipaths R 1and R 2 , then we have a contradiction: the highlight dipaths from s to x withoutw 1 and from s to y without w 2 .Since we have taken any x in B 1jand y in B 2j , in particular, s is a junction ofu 1 and u 2 (vertices in B j ). Furthermore, if there exists other vertex u 3 whosefarthest dominator is w 3 , w 3 ?= w 1 and w 3 ?= w 2 , then s is a junction of verticesu 1 and u 3 , and u 2 and u 3 . Let u 1 ,u 2 ,...,u t be vertices of B j whose farthestdominator are, respectively, w 1 ,w 2 ,...,w t , all distinct from each other. Notethat? ti=1 Bij= B j and B i?j∩ B i??j= ∅ for all i ? and i ?? in {1,...,t}. So, it ispossible to partition B j in sets B 1j ,...,Btjsuch that B ijcontains all verticesdominated by w i for i = 1,...,t. It is a new junction partition B ? larger thanB. However, B has maximum size, therefore, we obtain a contradiction. Thus,taken two vertices u 1 and u 2 in B j , if u 1 ?= u 2 , then w 1 = w 2 , i.e., all verticesin B j have the same farthest dominator.To finish the proof, we construct a dominator cover A such that |A| =|B| = k, and then, Lemma 2.4, ensures that the dominator cover constructedhas minimum size. The set A s = {s}. For every j = 2,...,k, and for everyC.E. Ferreira, Á.J.P. Franco / Electronic Notes in Discrete Mathematics 50 (2015) 109–114 113
vertex u in B j , make A u = {w u } where w u is the farthest dominator of u inB j . Finally, we set A = ∪ u∈G A u and |A| = k. 2We showed previously a dominator cover of the flowgraph in Fig. 1: A 2 ={s,a,b,e,f,h,i,k}. If we show a junction partition of the same flowgraphwhose size is equal to 8, then we know that both, dominator cover and junctionpartition are optimum. The next junction partition of the flowgraph in Fig.1 has size equals to 8: {{s},{a,c,d,g,j},{b},{e},{f},{h},{i,l,m},{k}}.3 ConclusionWe introduced the concepts of dominator cover and junction partition of agiven flowgraph G, and we proved that the minimum size of a dominatorcover in G is equal to the maximum size of a junction partition of G. Beforeour result, at least two min-max relations were known in reducible flowgraphs(a subclass of the class considered in this paper). The first is a theorem dueto Frank and Gyárf´ as [3] which proved that, given a reducible flowgraph D,the maximum number of vertex-disjoint cycles in D is equal to the minimumsize of a set of vertices which intersect all cycles in D. The second is atheorem due to Ramachandran [5] which proved the arc version of the Frankand Gyárf´ as theorem. As usual in optimization problems, min-max relationsand efficient algorithms come together in many problems. In a companionpaper [1] we study an algorithm to obtain dominator cover, junction partitionand dominator tree of a reducible flowgraph. A dominator tree is a datastructure used, for example, to optimize programs [4].References[1] C.E. Ferreira and´A.J.P. Franco. Dominator cover and junction partition offlowgraphs. In preparation.[2] C.E. Ferreira and´A.J.P. Franco. Algorithms for junctions in acyclic digraphs.In Facets of Combinatorial Optimization, pages 175–194. Springer, 2013.[3] A. Frank and A. Gy´ arfás. Directed graphs and computer programs. Probl´ emesCombinatoires et Th´ eorie des Graphes, pages 157–158, 1976.[4] T. Lengauer and R.E. Tarjan. A fast algorithm for finding dominators in aflowgraph. ACM Trans. Program. Lang. Syst., 1(1):121–141, 1979.[5] Vijaya Ramachandran. A minimax arc theorem for reducible flow graphs. SIAMJ. on Disc. Math., 3(4):554–560, 1990.C.E. Ferreira, Á.J.P. Franco / Electronic Notes in Discrete Mathematics 50 (2015) 109–114 114