Packing triangles in low degree graphs and indifference graphs
Gordana Mani´c
†and Yoshiko Wakabayashi
‡Instituto de Matem´atica e Estat´ıstica da Universidade de S˜ao Paulo — Departamento de Ciˆencia da Computac¸˜ao — Rua do Mat˜ao 1010, CEP 05508-090, S˜ao Paulo, SP – Brazil,{gocam,yw}@ime.usp.br
We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems areNP-hard. The algorithm with the best approximation guarantee known so far for these problems has ratio3/2 +ε, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver in 1989. We present improvements on the approximation ratio for restricted cases ofVTPandETPthat are known to beAPX-hard: we give an approximation algorithm forVTPon graphs with maximum degree4with ratio slightly less than1.2, and forETPon graphs with maximum degree5with ratio4/3.
We also present an exact linear-time algorithm forVTPon the class of indifference graphs.
Keywords:triangle packing, approximation algorithm, polynomial algorithm, low degree graph, indifference graph
1 Introduction
For a given family F of sets, any collection of pairwise disjoint sets is called a packing of F. The maximumk-set packingproblem is defined as follows: given a familyF of sets of sizek ≥ 2 over a certain domain, find a largest packing ofF. This problem is a fundamental combinatorial problem that underlies a range of practical and theoretical problems. The casek = 2is the well-known maximum matching problem. We study two special cases of the maximum3-set packing problem that areNP-hard.
A cycle of length3in a graphG= (VG, EG)is called atriangle. LetTV(G)(resp.TE(G)) denote the collection of the sets of vertices (resp. edges) of all triangles inG. We address the following problems on simple graphs. Vertex-Disjoint Triangle Packing(VTP): given a graphG, find a maximum size packing ofTV(G), andEdge-Disjoint Triangle Packing(ETP): given a graphG, find a maximum size packing of TE(G). For simplicity, we may also refer to a collection of vertex-disjoint (resp. edge-disjoint) triangles of a graphGas a packing ofTV(G)(resp.TE(G)).
The problemVTParises in scheduling airline flight crew (say pilots, copilots, and navigators) to air- planes, whileETPhas applications in computational biology (2). As both problems areNP-hard (7; 5), we wish to find good approximation algorithms or special instances amenable to polynomial algorithms.
Consider the following local search algorithmHS(T, t), whereT isTV(G)forVTP(resp. TE(G)for ETP) andtis a positive integer.
†Partially supported by CAPES, Brazil.
‡Partially supported by CNPq (Proc. 490333/04-4 and 308138/04-0) and PRONEX–FAPESP/CNPq (Proc. 2003/09925-5).
1365–8050 c2005 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France
AlgorithmHS(T, t): Given a collectionCof disjoint sets constructed so far, check whether there arep ≤ tdisjoint sets inT \ Cthat intersect at mostp−1sets that are inC. If this happens, swap the sets to form a larger collectionC, and repeat; otherwise, returnC.
A general result of Hurkens and Schrijver (6) on the maximumk-set packing problem implies that the above algorithm is a (32+ε)-approximation algorithm for bothVTPandETP(εis inversely proportional tot). This ratio is tight and is the best approximation ratio known so far for both problems. There are only a few more results concerning maximum triangle packings. Both problems admit a polynomial-time approximation scheme on planar graphs (1) andλ-precision unit disk graphs (a result proved by Hunt et al.
in 1998). The problemVTPisNP-complete when restricted to chordal graphs, while it is polynomially solvable on split graphs and cographs (4).
For a given integerk ≥ 3, we denote byVTP-k(resp. ETP-k), the problemVTP(resp. ETP) on graphs with maximum degreek. BothVTP-3andETP-4can be solved in polynomial time, whereas VTP-4andETP-5areAPX-hard (2). We present improvements on the approximation ratios of these APX-hard instances: a (3−
√13
2 +ε)-approximation algorithm forVTP-4, and a 43-approximation al- gorithm forETP-5. We also give an exact linear-time algorithm forVTPon indifference graphs (or, equivalently, unit interval graphs and proper interval graphs). This result is of interest in view of many applications of such graphs in management, psychology, scheduling, etc.
1.1 Basic definitions and notation
A natural reduction for both VTPand ETPconsists in deleting the edges that do not belong to any triangle. We, thus, restrict our attention to simple graphs in which every edge belongs to some triangle;
these graphs will be calledirredundant. The terminology we use is standard. One exception is that, when we writeG−U(forU ⊆VGorU ⊆EG) we assume that isolated vertices and edges that do not belong to any triangle on the graph obtained by deletingUfromGhave been removed as well. GraphsGandH intersectifG∩H is a non-empty graph. Thedegreeof a triangleT in a graphG,dG(T), is the number of triangles inG, different fromT, that intersectT. We denote byTGthe collection of all triangles inG, and by[u, v, w]the triangle with verticesu,vandw. If two trianglesT1andT2ofGhave only one vertex in common and there is no other triangle inGthat intersects bothT1andT2, we say that the subgraph T1∪T2is abutterflyinG, and denote byvT1T2 the only vertex in common toT1andT2. A collection T of vertex-disjoint triangles inGislocally optimalinGif{VT: T ∈ T }is a maximum packing of the family{VT: T ∈ TG, T intersects a triangle inT }.
Theintersection graphof a collection of setsT is the graphH withVH :=T and such thatXY ∈ EH⇔X∩Y 6=∅. A graphGis anindifference graphif there exists a positive numberδand a real-valued functionf onVGsuch that for allu, v ∈VG(u6=v),uvis an edge inGwhenever|f(u)−f(v)|< δ.
2 The problem VTP on graphs with maximum degree 4
We describe in this section an algorithm, called VT4k, for VTP on graphs with maximum degree 4.
This algorithm performs some approximation-preserving reductions to transform the input graphGinto another graphG0 in which every triangle intersects at most3other triangles. Then, on the intersection graph ofTG0 it applies the (3−
√13 2 +13−
√13
52k )-approximation algorithm of Chleb´ık and Chleb´ıkov´a (3), which we denote byMIS3k(wherekis a fixed integer parameter), for the problem of finding a maximum cardinality independent set of vertices on graphs with maximum degree3. We note that fork = 4the above ratio is slightly less than1.25; and fork >65it is slightly less than1.2.
In each iteration of the algorithmVT4k, a setT ⊆ TG,|T | ≤ 2, locally optimal inGis repeatedly added toA∗(the set to be returned by the algorithm) andGis updated. IfGcontains a triangleT with degree greater than3, the algorithm finds a certain subgraphH that containsTand applies an appropriate reduction (in a way that in the reduced graph the triangles obtained by this reduction have degree at most 3). The reduction is based on the number of triangles inHthat forms a butterfly with a triangle not inH (which is at most 2).
AlgorithmVT4k
Input:A graphGwith maximum degree4.
1 A∗← ∅
2 whileexists a triangle inGwith degree greater than3
3 do whileexistsT ⊆ TG,|T | ≤2, locally optimal inGdoAccept(T) 4 ifexists a triangleT ∈ TGwithdG(T)>3
5 thenH ←maximal connected irredundant subgraph ofGthat 6 containsT and does not contain any butterfly
7 BH← {T0∈ TH: exists a triangle inTG\THthat forms a butterfly withT0inG}
8 if|BH|= 2thenapplyReduction(H)
9 else if|BH|= 0
10 then{take a triangleTeinTH,SolH ←Te∪Commit(H−V
Te)}
11 if|BH|= 1thenSolH←Commit(H)
12 A∗← A∗∪SolH
13 ifG6=∅thenA∗← A∗∪MIS3k(intersection graph ofTG) 14 forevery application ofReduction(H)doRestauration(H) 15 returnA∗
Each of the procedures is described next in more detail.
1. Accept(T): AddT toA∗and delete fromGthe vertices of all triangles inT.
2. Commit(H): SetE :=∅. WhileH 6= ∅, find a triangleT locally optimal inH, addT toE and deleteVT fromH. ReturnE.
3. Reduction(H): TakeT0, T00 ∈ BH andTe0,Te00 ∈ TG\ TH such thatT0 ∪Te0 andT00∪Te00are butterflies inG(possiblyTe0=Te00). Let
SolT0T00:={T0, T00}∪Commit(H−VT0−VT00),SolT0T00:={T0}∪Commit(H−VT0−vT00Te00), SolT0T00:={T00}∪Commit(H−VT00−vT0
Te0), SolT0T00:=Commit(H−vT0
Te0−vT00
Te00).
(a) If|SolT0T00|=|SolT0T00|=|SolT0T00|=|SolT0T00|, thenAccept(SolT0T00).
(b) If the equalities in (a) are not satisfied andTe0 =Te00, thenAccept(SolT0T00).
(c) If|SolT0T00|−1 =|SolT0T00|=|SolT0T00|=|SolT0T00|andTe06=Te00then applyReduction1(H):
G← G−(EH\{ET0∪ET00})
∪TH,
whereTH := [v0, w, v00],wis a new vertex,v0 is any vertex ofT0different fromvT0
Te0, and v00is any vertex ofT00different fromvT00
Te00. Thus,Reduction1(H)replaces all triangles of H, exceptT0andT00, with a new triangleTH.
(d) If|SolT0T00|=|SolT0T00|=|SolT0T00|=|SolT0T00|+1andTe06=Te00, then applyReduction2(H):
G←(G−EH)∪TH1 ∪TH2 , whereTH1 := [vT0
Te0, w1, w],TH2 := [w, w2, vT00
Te00]andw1,w,w2are new vertices. Hence, this reduction replaces all triangles ofH with the new trianglesTH1 andTH2.
4. Restauration(H):
(a) If the reduction applied toHwasReduction1(H), then ifTHbelongs toA∗before applying Restauration(H), this procedure removesTH fromA∗and adds to it the setSolT0T00(com- puted in the procedureReduction(H)); ifT0, T00∈ A∗, thenA∗← A∗∪SolT0T00; ifT0∈ A∗, T00∈ A/ ∗, thenA∗← A∗∪SolT0T00; and ifT0 ∈ A/ ∗,T00∈ A∗, thenA∗← A∗∪SolT0T00. (b) If, however, the reduction applied toHwasReduction2(H), then ifTH1 belongs toA∗before
applyingRestauration(H), this procedure addsSolT0T00toA∗and removesTH1; ifTH2 ∈ A∗, then addsSolT0T00toA∗and removesTH2; and ifTH1, TH2 ∈ A/ ∗, then addsSolT0T00toA∗. Making use of the structural properties of the input graph, maximum degree4and irredundancy (that are maintained in each iteration), we can prove that the graphH defined in the algorithm is isomorphic to one of the graphs in Figure 1. Thus, for each iteration ofVT4k, the cardinality ofBH in line8 is less than3. If|BH| ≤1, thenG[VH]is a component ofGandSolHis an optimal solution in that component.
We can also prove thatReduction1,Reduction2(and corresponding restaurations) andAcceptare all approximation-preserving reductions, and thus the approximation ratio ofVT4kis that ofMIS3k.
r r
b b
b b
(a)
r r
b b b
b b
(b)
r b b
b b
b b
b
b b
· · · b
(d)
r
r b
b b b
b b
b
b b
· · ·
(c)
b b
b b
b b
b b
b
b b
· · ·
(e) Fig. 1:Possible configurations of graphH. Each square vertex is a vertex common to two triangles inGwhose union is a butterfly. The graph (c) has at least7vertices.The graphs (d) and (e) have at least9vertices, andG[VH]is a component ofG(in (d) dashed lines indicate edges not inEH).
Theorem 2.1 The algorithmVT4kis a(3−
√ 13 2 +13−
√ 13
52k )-approximation algorithm forVTP-4.
The time complexity ofVT4kis dominated by that ofMIS3k, which isO(|VG|O(k)).
3 The problem ETP on graphs with maximum degree 5
We restrict now our attention to graphs with maximum degree 5 and describe an approximation algorithm, calledET5, for the problemETPon such graphs.
AlgorithmET5
Input:A graphGwith maximum degree5.
1 A∗← ∅
2 whileGcontains a Hajos graphH =H[T1, T2, T3] (see the figure beside) 3 do{A∗← A∗∪ {T1, T2, T3}, G←G−EH}
4 returnA∗∪ {T: ET ∈HS(TE(G),3)}
b b
b
b b
b
T2 T1
T3
Lemma 3.1 The algorithmHS(TE(G),3)is a 43-approximation algorithm for the problemETP-5on a graphGthat does not contain a Haj´os graph.
The proof of Lemma 3.1 is by induction on the number of triangles inG. For that, one should prove first that ifT∗is a maximum packing ofTE(G), then there is a subcollectionA ⊆ HS(TE(G),3)with
|A| ≤3, such that, the ratio of the number of triangles fromT∗that share an edge with a triangle inAto
|A|, is at most 43; and then apply the induction hypothesis onG−S
T∈AET. Now, using Lemma 3.1 and the fact thatifGis a graph that contains a Haj´os graphH, then the number of triangles in any maximum packing ofTE(G)that share an edge withHis at most4, we obtain the approximation ratio ofET5.
Theorem 3.2 The algorithmET5is a43-approximation algorithm for the problemETP-5. Furthermore, the ratio43 is tight and the algorithm can be implemented to run inO(|VG|3)time.
4 The problem VTP on indifference graphs
For the next result we use the following characterization obtained by Looges and Olariu (8): a graphGis an indifference graph if, and only if, there exists a linear order<(which we callcanonical) onVGsuch that, for every choice of verticesu,v,wwe have that ifu < v < wanduw∈EG, thenuv, vw∈EG.
AlgorithmVTindifference Input:An indifference graphG.
1 Find a canonical orderv1< v2<· · ·< vnonVG
2 A∗← ∅
3 fori←1to|VG| −2
4 do ifvivi+2∈EGthen{T ←[vi, vi+1, vi+2], A∗← A∗∪T, G←G−VT} 5 returnA∗
One may prove by contradiction that the algorithm above solvesVTPon indifference graphs. It suffices to consider an optimal solution that has the maximum number of triangles in common with the solution found by the algorithm. Since the canonical order can be computed in linear time (8), it follows that the algorithm is linear.
References
[1] B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Com- put. Mach., 41(1):153–180, 1994.
[2] A. Caprara and R. Rizzi. Packing triangles in bounded degree graphs. Inform. Process. Lett., 84(4):175–180, 2002.
[3] M. Chleb´ık and J. Chleb´ıkov´a. On approximability of the independent set problem for low degree graphs. InLNCS 3104, pages 47–56. Springer, 2004.
[4] V. Guruswami, C. Pandu Rangan, M. S. Chang, G. J. Chang, and C. K. Wong. TheKr-packing problem.Computing, 66(1):79–89, 2001.
[5] I. Holyer. The NP-completeness of some edge-partition problems.SIAM J. Comput., 10(4):713–717, 1981.
[6] C. A. J. Hurkens and A. Schrijver. On the size of systems of sets everytof which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math., 2(1):68–72, 1989.
[7] R. M. Karp. On the computational complexity of combinatorial problems. Networks, 5(1):45–68, 1975.
[8] P. J. Looges and S. Olariu. Optimal greedy algorithms for indifference graphs.Comput. Math. Appl., 25(7):15–25, 1993.