The path partition problem and related problems in bipartite graphs

The path partition problem and related problems in bipartite graphs

Operations Research Letters 35 (2007) 677 – 684 Operations Research Letters www.elsevier.com/locate/orl The path partition problem and related probl...

235KB Sizes 0 Downloads 21 Views

Operations Research Letters 35 (2007) 677 – 684

Operations Research Letters www.elsevier.com/locate/orl

The path partition problem and related problems in bipartite graphs Jérôme Monnota,∗ , Sophie Toulouseb a CNRS LAMSADE - UMR 7024, Université Paris-Dauphine, Place du Maréchal De Lattre de Tassigny, 75775 Paris Cedex 16, France b LIPN - UMR CNRS 7030, Institut Galilée, Université Paris 13, 99 av. Jean-Baptiste Clément, 93430 Villetaneuse, France

Received 18 November 2005; accepted 17 December 2006 Available online 11 January 2007

Abstract We prove that it is NP-complete to decide whether a bipartite graph of maximum degree three on nk vertices can be partitioned into n paths of length k. Finally, we propose some approximation and inapproximation results for several related problems. © 2007 Elsevier B.V. All rights reserved. Keywords: Pk -Partition; Path packing; Path partition; Bipartite graphs; APX-Hardness; Approximation algorithms

1. Introduction The Pk partitioning problem (Pk PARTITION in short) consists, given a simple graph G = (V , E) on k × n vertices, in deciding if there exists a partition of V into (V1 , . . . , Vn ) such that for 1i n, |Vi | = k and the subgraph G[Vi ] induced by Vi contains a Hamiltonian path. In other words, we want to know if there exist n vertex disjoint simple paths of length k in G. The analogous problem where the subgraph G[Vi ] induced by Vi is isomorphic to Pk (the chordless path on k vertices) will be denoted by INDUCED Pk PARTITION. These two problems are NP-complete for any k 3, and polynomial otherwise [8,13]. In fact, they both are a particular case of a more general problem called ∗ Corresponding author. Tel.: +33 1 44054552.

E-mail addresses: [email protected] (J. Monnot), [email protected] (S. Toulouse). 0167-6377/$ - see front matter © 2007 Elsevier B.V. All rights reserved. doi:10.1016/j.orl.2006.12.004

partition into isomorphic subgraphs [8]. In [13], Kirkpatrick and Hell give a necessary and sufficient condition for the NP-completeness of the partition into isomorphic subgraphs problem in general graphs. Pk PARTITION has been widely studied in the literature, mainly because its NP-completeness also implies the NP-hardness of two famous optimization problems, namely: the minimum k-path partition problem (denoted by MINk-PATHPARTITION) and the maximum Pk packing problem (MAXPk PACKING in short). MINk-PATHPARTITION consists in partitioning the vertex set of a graph G = (V , E) into the smallest number of paths such that each path has at most k vertices (for instance, MIN2-PATHPARTITION is equivalent to the maximum matching problem); the optimal value is usually denoted by k−1 (G), and by (G) when no constraint occurs on the length of the paths (in particular, we have (G) = 1 iff G has an Hamiltonian path). MINk-PATHPARTITION has been extensively

678

J. Monnot, S. Toulouse / Operations Research Letters 35 (2007) 677 – 684

studied in the literature [18,17,21], and has applications in broadcasting problems, see for example [21]. MAXPk PACKING (resp., MAXINDUCEDPk PACKING), consists, given a simple graph G = (V , E), in finding a maximum number of vertex-disjoint (resp., induced) Pk . In their weighted versions (denoted MAXWPk PACKING and MAXWINDUCEDPk PACKING, respectively), the input graph G = (V , E) is given together with a weight function w on its edges; the goal is to find a collection P = {P1 , . . . , Pq } of vertex-disjoint (resp., induced Pk ) maximizing q  w(P) = e∈Pi w(e). Some approximation i=1 results for MAXWPk PACKING when the graph is complete on k × n vertices are given in [9,10,15]. In this case, each solution contains exactly n vertex disjoints paths of length k − 1 (note that, in this particular case, the minimization version may also be considered). This problem is related to the vehicle routing problem [21,3]. Here, we study the complexity of Pk PARTITION and INDUCED Pk PARTITION in the case of bipartite graphs. We first show that Pk PARTITION and INDUCED Pk PARTITION are NP-complete for any k 3 in bipartite graphs of maximum degree 3. Moreover, for k =3, this remains true even if the graph is planar. On the opposite side, Pk PARTITION, INDUCED Pk PARTITION, MINk-PATHPARTITION and MAXWPk PACKING trivially become polynomial-time computable in graphs of maximum degree 2 and in forests. Then, we prove that, in bipartite graphs of maximum degree 3, MAXPk PACKING and MAXINDUCEDPk PACKING do not have a PTAS. More precisely, we prove that there is a constant k > 0 such that it is NP-hard to decide whether a maximum (induced) Pk -packing of a bipartite graph of maximum degree 3 on kn vertices is of size n or of size upper bounded by (1 − k )n. Finally, we propose a 23 -approximation for MIN3PATHPARTITION in general graphs and a 13 (resp., 21 )approximation for MAXWP3 PACKING in general (resp., bipartite) graphs of maximum degree 3. This paper is organized as follows: in the next section, we briefly present previous related works about the hardness of solving bounded-size-path packing problems. Then, the third part is dedicated to complexity results concerning Pk PARTITION, INDUCED Pk PARTITION, MAXINDUCEDPk PACKING and MAXPk PACKING in bipartite graphs. Finally, some

approximation results concerning MAXWP3 PACKING and MIN3-PATHPARTITION are proposed in a fourth section. The notations are the usual ones according to graph theory. Moreover, we exclusively work in undirected simple graphs. In this paper, we often identify a path P of length k − 1 with Pk , even if P contains a chord. However, when we deal with INDUCED Pk PARTITION, the paths considered will be chordless. We denote by opt(I ) and apx(I ) the value of an optimal and of an approximate solution, respectively. We say that an algorithm A is an -approximation with  1 for a minimization problem (resp., with  1 for a maximization problem) if apx(I )  × opt(I ) (resp., apx(I )  × opt(I )) for any instance I (for more details, see for instance [2]).

2. Previous related work The minimum k-path partition problem is obviously NP-complete in general graphs [8], and remains intractable in comparability graphs [18], in cographs [17], and in bipartite chordal graphs [18] (when k is part of the input). Note that most of the proofs of NP-completeness actually establish the NP-completeness of Pk PARTITION. Nevertheless, the problem turns out to be polynomial-time solvable in trees [21], in cographs when k is fixed [17] or in bipartite permutation graphs [18]. Note that one can also find in the literature several results about partitioning the graph into disjoints paths of length at least 2 [20,11]. Concerning the approximability of related problems, Hassin and Rubinstein [9] proposed a generic algorithm to approximate MAXWP4 PACKING in complete graphs on 4n vertices that guarantees an approximation ratio of 43 for general distance function. More recently in [15], it has been proven that 9 this algorithm is also a 10 -approximation for the 1, 2instances. For the minimization version, it provides respectively a 23 - and a 76 -approximation for the metric and the 1, 2-instances in complete graphs on 4n vertices (in this case, we seek a maximal P4 -Packing of minimum weight). In [10], the authors proposed a (35/67 − )-approximation for MAXP3 PARTITION in complete graphs on 3n vertices using a randomized algorithm. To our knowledge, there is no specific

J. Monnot, S. Toulouse / Operations Research Letters 35 (2007) 677 – 684

approximation result for MAXWP3 PACKING in general graphs. However, using approximation results for the maximum weighted 3-packing problem (mainly based on local search techniques) [1], we can obtain a ( 21 − )-approximation for MAXWP3 PACKING. Finally, there is, to our knowledge, no approximation result for MINk-PATHPARTITION. Nevertheless, when the problem consists in maximizing the number of edges used by the paths, then we can find some approximation results, in [19] for the general case, in [5] for dense graphs.

3. Complexity results Theorem 3.1. Pk PARTITION and INDUCED Pk PARTITION are NP-complete in bipartite graphs of maximum degree 3, for any k 3. As a consequence, MAXPk PACKING and MINk-PATHPARTITION are NPhard in bipartite graphs with maximum degree 3, for any k 3. Proof. The paths of length k − 1 used in the reduction are chordless; thus, the result holds for both problems. The proof is based on a reduction from the k-dimensional matching problem, denoted by kDM, which is known to be NP-complete [8]. An instance of kDM consists of a subset C = {c1 , . . . , cm } ⊆ X1 × · · · × Xk of k-tuples, where X1 , . . . , Xk are k pairwise disjoint sets of size n. A matching is a subset M ⊆ C such that no two elements in M agree in any coordinate, and the purpose of kDM is to answer the question: does there exist a perfect matching M on C, that is, a matching of size n? Given an instance I = (C, X1 × · · · × Xk ) of kDM, we build an instance G = (V , E) of Pk PARTITION depending on the parity of k, where G is a bipartite graph of maximum degree 3, as follows: Case 1: k is odd. • To each k-tuple ci ∈ C, we associate a gadget H (ci ) that consists of a collection {P i,1 , . . . , P i,k } of k vertex-disjoint Pk with i,q i,q P i,q ={a1 , . . . , ak } for q=1, . . . , k. We add to i,q i,q+1 H (ci ) the edges [a1 , a1 ] for q = 1 to k − 1, in order to form a (k + 1)th Pk {a1i,1 , . . . , a1i,k } (see Fig. 1 for an illustration when k = 3).

679

Fig. 1. The gadget H (ci ) when ci is a 3-uplet.

Fig. 2. The gadget H (ej ) for k = 3 and d j = 2.

• For each element ej ∈ X1 ∪ · · · ∪ Xk , let d j denote the number of k-tuples ci ∈ C that contain ej ; the gadget H (ej ) is defined as a cycle j j j {v1 , . . . , vN j +1 , v1 } on N j + 1 vertices, where N j = k(2d j − 1). Moreover, for p = 1 to d j , we j denote by lp the vertex of index 2k(p − 1) + 1 (see Fig. 2 for an illustration of H (ej ) when k=3 and d j = 2). • Finally, for any couple (ej , ci ) such that ej is the value of ci on the qth coordinate, the two gadgets H (ci ) and H (ej ) are connected using i,q j j an edge [a2 , lpi ]. The vertices lpi that will be linked to a given gadget H (ci ) must be chosen in j such a way that each vertex lp from any gadget H (ej ) will be connected to exactly one gadget H (ci ) (this is possible since each H (ej ) contains j exactly d j vertices lp ). This construction obviously leads to a graph G of maximum degree 3, on 3k 2 m + (1 − k)kn vertices: consider, on the one hand, that each gadget H (ci ) is a graph on k 2 vertices and, on the other hand, that  kn j j =1 d = km (wlog., we may assume that each element ej appears at least once in C). Finally, one can see that G is bipartite. Case 2: k is even. The construction is quite identical, except the construction of the H (ej ) gadgets: H (ej ) is a cycle j j j {v1 , . . . , vN j , v1 } on N j vertices, plus an additional j

j

j

edge [vN j , vN j +1 ]. The special vertices lp are defined j

j

j

by lp = v2k(p−1)+1 for p = 1, . . . , d j (note that ld j j

never matches vN j ). We can easily see that H (ej ) is bipartite (N j is even).

680

J. Monnot, S. Toulouse / Operations Research Letters 35 (2007) 677 – 684

In any case, we claim that there exists a perfect matching M ⊆ C iff there exists a partition P∗ of G into Pk . The argument is mainly based on the definition of the following path partitions Pi and Qi on V (Hi ), for any i = 1, . . . , m: ⎧ i k P = q=1 P i,q ∪ {a1i,1 , a1i,2 , . . . , a1i,k } ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ with P i,q = {a i,q , . . . , a i,q , li,q } ∀q, 2 k k i i,q ⎪ ⎪ Q = q=1 Q ⎪ ⎪ ⎪ ⎩ i,q i,q i,q with Qi,q = {ak , . . . , a2 , a1 } ∀q where li,q denotes the vertex from some H (ej ) i,q

linked to a2 . One can easily see that any partition of G into Pk uses Pi and Qi collections in order to cover the H (ci ) gadgets, plus 2(d j − 1) paths on each H (ej ). Fig. 3 illustrates the construction of the paths partition on V (H (ci )) with respect to a given matching M for 3DM.  If we decrease the maximum degree of the graph down to 2, we can easily prove that Pk PARTITION, INDUCED Pk PARTITION, MAXPk PACKING and MINkPATHPARTITION are polynomial-time computable. The same fact holds for MAXWPk PACKING (what remains true in forests), although it is a little bit complicated: the proof consists of a reduction from MAXWPk PACKING in graphs with maximum degree 2 (resp., in a forest) to the problem of computing a maximum weight independent set in an interval (resp., chordal) graph, which is known to be polynomial [7]. Proposition 3.2. MAXWPk PACKING is polynomial in graphs with maximum degree 2 and in forests, for any k 3. Theorem 3.3. P3 PARTITION and INDUCED P3 PARTITION are NP-complete in planar bipartite graphs with maximum degree 3. As a consequence, MAXP3 PACKING and MIN3-PATHPARTITION are NPhard in planar bipartite graphs with maximum degree 3. Proof. We apply the proof of the previous theorem, except that we start from a restriction of the threedimensional matching problem, which is denoted by

PLANAR 3DM-3. It is well known that this restriction of 3DM is still NP-complete [6].  Using an APX-hardness result for the optimization version of kDM (denoted MAXkDM) and the reduction of Theorem 3.1, we are able to obtain an APXhardness result for MAXPk PACKING in bipartite graphs of maximum degree 3. The result used is the following: for any k 3, there is a constant k > 0, such that ∀I = (C, X1 × · · · × Xk ) instance of MAXkDM with n = |X1 | = · · · = |Xk |, it is NP-hard to decide between opt(I ) = n and opt(I )(1 − k )n, where opt(I ) is the value of a maximum matching on C. This result also holds if we restrict ourselves to instances I = (C, X1 × · · · × Xk ) such that for each element ej ∈ X1 ∪ · · · ∪ Xk , d j f (k), where f (k) is a constant (we recall that d j is the number of ktuples ci ∈ C containing ej ). For k = 3, the result is proved in [16] with f (3) = 3, and for the other values of k [12]. Theorem 3.4. For any k 3, there is a constant k > 0, such that ∀G = (V , E) instance of MAXPk PACKING (resp., MAXINDUCEDPk PACKING) where G is a bipartite graph of maximum degree 3, it is NP hard to decide between opt(G) = |V |/k and opt(G) (1 − k )(|V |/k) where opt(G) is the value of a maximum (resp., maximum induced) Pk -Packing on G. Proof. Let I = (C, X1 × · · · × Xk ) be an instance of MAXkDM with n = |X1 | = · · · = |Xk | and m = |C| and such that ∀ej ∈ X1 ∪· · ·∪Xk , d j f (k). Consider the graph G = (V , E) produced in Theorem 3.1. We recall that G is bipartite of maximum degree 3, |V |=3k 2 m+ (1 − k)n, and all paths of length k − 1 are chordless. Let P∗ be an optimal solution of MAXPk PACKING with value opt(G). We can assume that the two following properties hold: (i) In any gadget H (ci ), P∗ contains either the packing Pi , or the packing Qi . (ii) In any gadget H (ej ), P∗ contains exactly 2d j −1 paths. We know that I has a perfect matching iff opt(G) = 3km + (1 − k)n = |V |/k. Now, let M0 = {ci ∈ C : P∗ contains the packing Pi on V (H (ci ))} and m0 =|M0 |.

J. Monnot, S. Toulouse / Operations Research Letters 35 (2007) 677 – 684

681

Fig. 3. A vertex partition of a H (ci ) gadget into 2-length paths.

 Since kj =1 nd j = km (see Theorem 3.1), and using properties (i) and (ii), we deduce opt(I ) = 2km − kn + km + m0 . Thus, if a maximum matching on I for MAXkDM with value opt(I ) satisfies opt(I )(1 − k )n, we deduce m0 (1 − k )n. Hence, by setting k = (n/(3km − kn + n))k , we obtain opt(G) (1 − k )(3km − kn + n) = (1 − k )(|V |/k). Finally, since d j f (k) where f (k) is a constant, we deduce that km3f (k)n and then, k (1/(9f (k) + 1 − k))k , which concludes the proof.  Some interesting questions concern the complexity of Pk PARTITION (or INDUCED Pk PARTITION) for k 4 and the APX-hardness of MAXPk PACKING and MAXINDUCEDPk PACKING for k 3 in planar bipartite graphs with maximum degree 3. 4. Approximation results We present some approximation results for MAXWP3 PACKING and MIN3-PATHPARTITION, that are mainly based on matching and spanning tree heuristics.

of MAXWPk PACKING consists in iteratively picking a path of length k − 1 that is of maximum weight. For k = 3 and in graphs of maximum degree 3, the time complexity of this algorithm is between O(n log n) and O(n2 ) (depending on the encoding structure). Actually, in such graphs, one may reach a 13 approximate solution, even in time O((n, m)n), where  is the inverse Ackerman’s function and m 3n/2. Theorem 4.1. MAXWP3 PACKING is 13 approximable within O((n, 3n/2)n) time complexity in graphs of maximum degree 3; this ratio is tight for the algorithm we analyze. Proof. The argument uses the following observation: for any spanning tree of maximum degree 3 containing at least three vertices, one can build a cover of its edge set into three packings of P3 within linear time. Hence, by computing a maximum-weight spanning tree T = (V , ET ) on G in O((n, 3n/2)n) time [4], and by picking the best P3 -packing among the cover, the result follows. We omit the proof of the tightness. 

4.1. MAXWP3 PACKING in graphs of maximum degree 3

4.2. MAXWP3 PACKING in bipartite graphs of maximum degree 3

For this problem, the best approximate algorithm known so far provides a ratio of ( 21 − ), within high (but polynomial) time complexity. This algorithm is deduced from the one proposed in [1] to approximate the weighted k-set packing problem for sets of size 3. Furthermore, a simple greedy 1/k-approximation

If we restrict us to bipartite graphs, we slightly improve the ratio of 21 −  [1] up to 21 . We then show that, in the unweighted case, this result holds without any constraint on the graph maximum degree. From I = (G, w) where G is a bipartite graph G = (L ∪ R, E) of maximum degree 3, we build two

682

J. Monnot, S. Toulouse / Operations Research Letters 35 (2007) 677 – 684

weighted graphs (GL , dL ) and (GR , dR ), where GL = (L, EL ) and GR = (R, ER ). Two vertices x  = y from L are linked in GL iff there exists in G a path of length 2 Px,y from x to y, rigorously: [x, y] ∈ EL iff ∃z ∈ R s.t. [x, z], [z, y] ∈ E. The distance dL (x, y) is defined as dL (x, y) = max{w(x, z) + w(z, y)|[x, z], [z, y] ∈ E}. (GR , dR ) is defined by considering R instead of L. If G is of maximum degree 3, then the following fact holds: Lemma 4.2. From any matching M on GL (resp., on GR ), one can deduce a P3 packing PM of weight w(PM ) = dL (M) (resp., w(PM ) = dR (M)), when G is of degree at most 3. Weighted P3 -Packing 1 Build the weighted graphs (GL , dL ) and (GR , dR ); 2 Compute a maximum weight matching ML∗ (resp., MR∗ ) on (GL , dL ) (resp., on (GR , dR )); 3 Deduce from ML∗ (resp., MR∗ ) a P3 packing PL (resp., PR ) according to Lemma 4.2; 4 Output the best packing P among PL and PR . The time complexity of this algorithm is mainly the time complexity of computing a maximum weight matching in graphs of maximum degree 9, that is O(|V |2 log |V |) [14]. Theorem 4.3. Weighted P3 -Packing provides a 1 2 -approximation for MAXWP3 PACKING in bipartite graphs with maximum degree 3 and this ratio is tight. Proof. Let P∗ be an optimum P3 -packing on I = (G, w), we denote by P∗L (resp., P∗R ) the paths of P∗ of which the two endpoints belong to L (resp., R); thus, opt(I ) = w(P∗L ) + w(P∗L ). For any path P = Px,y ∈ P∗L , [x, y] is an edge from EL , of weight dL (x, y)w(Px,y ). Hence, ML = {[x, y]|Px,y ∈ P∗L } is a matching on GL that satisfies d(ML )w(P∗L ).

(1)

Moreover, since ML∗ is a maximum weight matching on GL , we have dL (ML ) dL (ML∗ ). Thus, using inequality (1) and Lemma 4.2 (and by applying the same arguments on GR ), we deduce w(PL )w(P∗L ),

w(PR ) w(P∗R ).

(2)

Finally, the solution outputted by the algorithm satisfies w(P)1/2(w(PL ) + w(PR )); thus, we directly deduce from inequalities (2) the expected result. The instance I = (G, w) that provides the tightness is depicted in Fig. 4. It consists of a graph on 12n vertices on which one can easily observe that w(PL ) = w(PR ) = 2n(n + 2) and w(P∗ ) = 2n(2n + 2).  Concerning the unweighted case, we may obtain the same performance ratio without the restriction on the maximum degree of the graph. The main differences compared to the previous algorithm lie in the construction of the two graphs GL , GR : starting from G, we duplicate each vertex ri ∈ R by adding a new vertex ri with the same neighborhood as ri (this operation, often called multiplication of vertices in the literature, is used in the characterization of perfect graphs). Finally, we add the edge [ri , ri ]. If RL denotes the vertex set {ri , ri |ri ∈ R}, then the following property holds: Property 4.4. From any matching M on GL , one can deduce a matching M  on GL that saturates RL , and such that |M  | |M|. Theorem 4.5. There is a 21 -approximation for MAXP3 PACKING in bipartite graphs and this ratio is tight. √ The complexity time of this algorithm is O(m n). 4.3. MIN3-PATHPARTITION in general graphs To our knowledge, the approximability of MINkPATHPARTITION (or MINPATHPARTITION) has not been studied so far. Here, we propose a 23 -approximation for MIN3-PATHPARTITION. Although this problem can be viewed as an instance of 3-set cover (view the set of all paths of length 0, 1 or 2 in G as sets on V ), MIN3-PATHPARTITION and the minimum 3set cover problem are different. For instance, consider a star K1,2n ; the optimum value of the corresponding 3-set cover instance is n, whereas the optimum value of the 3-path partition is 2n − 1. Note that, concerning MINPATHPARTITION (that is, the approximation of (G)), we can trivially see that it is not (2 − )-approximable, from the fact that deciding whether (G) = 1 or (G) 2 is NPcomplete. Actually, we can more generally establish

J. Monnot, S. Toulouse / Operations Research Letters 35 (2007) 677 – 684

683

Fig. 4. The tightness.

that (G) is not in APX: otherwise, we could obtain a PTAS for the traveling salesman problem with weight 1 and 2 when opt(I ) = n, which is not possible, unless P = NP. Computing 2 (G) 1 Compute a maximum matching M1∗ on G; 2 Build a bipartite graph G2 = (L, R; E2 ) where L = {le |e ∈ M1∗ }, R ={rv |v ∈ V \V (M1∗ )}, and [le , rv ] ∈ / V (M1∗ ) E2 iff the corresponding isolated vertex v ∈ is adjacent in G to the edge e ∈ M1∗ ; 3 Compute a maximum matching M2∗ on G2 ; 4 Output P the 3-paths partition deduced from M1∗ , M2∗ , and V \V (M1∗ ∪ M2∗ );Precisely, if M1 ⊆ M1∗ is the set of edges adjacent to M2∗ , then the paths of length 2 are given by M1 ∪ M2∗ , the paths of length 1 are given by M1∗ \M1 , and the paths of length 0 (that is, the isolated vertices) are given by V \V (M1∗ ∪ M2∗ ).

[le , rv ] ∈ E2 iff there is an edge of P∗ that links v to an endpoint of e. By definition of V0 , we deduce that dG2 (rv ) 1 for any v ∈ V0 (V0 is an independent set of G). Moreover, we have dG2 (le ) 2 for any e ∈ M1∗ (M1∗ is an optimal matching). Thus, we get |M2∗ | 1/2|R  | = 1/2(|V | − 2|M1∗ | − |P∗0 |).

(4)

From relations (3) and (4), we deduce apx(I ) = |V | − |M1∗ | − |M2∗ | 1/2(|V | + |P∗0 |). (5) Now, consider the optimal solution. From |V | = 3|P∗2 | + 2|P∗1 | + |P∗0 |, we trivially have opt(I ) = |P∗2 | + |P∗1 | + |P∗0 | 1/3(|V | + |P∗0 |). (6) Thus, we obtain the expected result. The proof of the tightness is omitted.  Acknowledgments

The time complexity of this algorithm is O(nm + n2 log n) [14]. Theorem 4.6. MIN3-PATHPARTITION is 23 -approximable in general graphs; this ratio is tight for the algorithm we analyze. Proof. Let G = (V , E) be an instance of MIN3PATHPARTITION. Let P∗ = (P∗2 , P∗1 , P∗0 ) and P = (P2 , P1 , P0 ), respectively, be an optimal solution and the approximate 3-path partition on G, where P∗i and Pi denote for i = 0, 1, 2 the set of paths of length i. By construction of the approximate solution, we have apx(I ) = |V | − |M1∗ | − |M2∗ |.

(3)

Let V0 = (V \V (M1∗ ))\P∗0 , we consider a subgraph  G2 = (L, R  ; E2 ) of G2 , where R  and E2 are defined as: R  = {rv ∈ R|v ∈ V0 } and E2 contains the edge

Many thanks to the anonymous referee and the anonymous associate editor for pertinent and useful comments and suggestions. References [1] E. Arkin, R. Hassin, On local search for weighted packing problems, Math. Oper. Res. 23 (1998) 640–648. [2] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation, Combinatorial Optimization Problems and Their Approximability Properties, Springer, Berlin, 1999. [3] C. Bazgan, R. Hassin, J. Monnot, Approximation algorithms for some routing problems, Discrete Appl. Math. 146 (2005) 3–26. [4] B. Chazelle, A minimum spanning tree algorithm with Inverse-Ackermann type complexity, J. ACM 47 (2000) 1028–1047. [5] B. Csaba, M. Karpinski, P. Krysta, Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems, SODA (2002) 74–83.

684

J. Monnot, S. Toulouse / Operations Research Letters 35 (2007) 677 – 684

[6] M. Dyer, A. Frieze, Planar 3DM is NP-complete, J. Algorithms 7 (1986) 174–184. [7] A. Frank, Some polynomial time algorithms for certain graphs and hypergraphs, Proceedings of the Fifth British Combinatorial Conference, Congressus Numerantium XV, Utilitas Mathematicae, Winnipeg, 1976, pp. 211–226. [8] M.R. Garey, D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-completeness, Freeman, CA, 1979. [9] R. Hassin, S. Rubinstein, An approximation algorithm for maximum packing of 3-edge paths, Inform. Process. Lett. 63 (1997) 63–67. [10] R. Hassin, S. Rubinstein, An approximation algorithm for maximum triangle packing, Discrete Appl. Math. 154 (2006) 971–979. [11] A. Kaneko, A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two, J. Combin. Theory Ser. B 88 (2003) 195–218. [12] M. Karpinski, Personnal communication, 2006. [13] D.G. Kirkpatrick, P. Hell, On the completeness of a generalized matching problem, Proceedings of the STOC’78, 1978, pp. 240–245.

[14] L. Lovasz, M.D. Plummer, Matching Theory, North-Holland, Amsterdam, 1986. [15] J. Monnot, S. Toulouse, Approximation results for the weighted P4 partition problem, The Symposia on Fundamentals of Computation Theory, F.C.T.’2005, Lecture Notes in Computer Science, vol. 3623, Springer, Berlin, 2005, pp. 377–385. [16] E. Petrank, The hardness of approximation: gap location, Comput. Complexity 4 (1994) 133–157. [17] G. Steiner, On the k-path partition of graphs, Theor. Comput. Sci. 290 (3) (2003) 2147–2155. [18] G. Steiner, k-Path partitions in trees, Theor. Comput. Sci. 290 (2003) 2147–2155. [19] S. Vishwanathan, An approximation algorithm for the asymmetric travelling salesman problem with distances one and two, Inform. Process. Lett. 44 (6) (1992) 297–302. [20] H. Wang, Path factors of bipartite graphs, J. Graph Theory 18 (1994) 161–167. [21] J.-H. Yan, G.J. Chang, S.M. Hedetniemi, S.T. Hedetniemi, k-path partitions in trees, 78 (1–3) (1997) 227–233.