Abstract
We investigate two NP-complete vertex partition problems on edge weighted complete graphs with 3k vertices. The first problem asks to partition the graph into k vertex disjoint paths of length 2 (referred to as 2-paths) such that the total weight of the paths is maximized. We present a cubic time approximation algorithm that computes a 2-path partition whose total weight is at least .5833 of the weight of an optimal partition; improving upon the (.5265 − ε)-approximation algorithm of [26]. Restricting the input graph to have edge weights in {0, 1}, we present a .75 approximation algorithm improving upon the .55-approximation algorithm of [16].
Combining this algorithm with a previously known approximation algorithm for the 3-Set Packing problem, we obtain a .6-approximation algorithm for the problem of partitioning a {0, 1}-edge-weighted graph into k vertex disjoint triangles of maximum total weight. The best known approximation algorithm for general weights achieves an approximation ratio of .5257 [4].
This work is supported by the Army Research Laboratory and was accomplished under Cooperative Agreement Number W911NF-09-2-0053, The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arkin, E., Hassin, R.: On local search for weighted k-set packing. Math. Operations Research 23(3), 640–648 (1998)
Babenko, M., Gusakov, A.: New exact and approximation algorithms for the star packing problem in undirected graphs. In: STACS, pp. 519–530 (2011)
Bar-Noy, A., Basu, P., Baumer, B., Rabanca, G.: Star search: Effective subgroups in collaborative social networks (unpublished)
Chen, Z.-Z., Tanahashi, R., Wang, L.: An improved randomized approximation algorithm for maximum triangle packing. In: Fleischer, R., Xu, J. (eds.) AAIM 2008. LNCS, vol. 5034, pp. 97–108. Springer, Heidelberg (2008)
Chen, Z.Z., Tanahashi, R., Wang, L.: An improved randomized approximation algorithm for maximum triangle packing. Discrete Applied Mathematics 157(7), 1640 (2009)
Chen, Z.Z., Tanahashi, R., Wang, L.: Erratum to, An improved randomized approximation algorithm for maximum triangle packing. Discrete Appl. Math. 157 (2009); Discrete Applied Mathematics 158(9), 1045–1047 (2010)
Chlebìk, M., Chlebìková, J.: Approximation hardness fo2653r small occurrence instances of NP-hard problems. In: Petreschi, R., Persiano, G., Silvestri, R. (eds.) ISAAC. LNCS, vol. 2653, pp. 152–164. Springer, Heidelberg (2003)
Gabow, H.: An efficient implementation of Edmonds’ algorithm for maximum matching on graphs. J. ACM 23(2), 221–234 (1976)
Gajewar, A., Sarma, A.S.: Multi-skill collaborative teams based on densest subgraphs. In: SDM, pp. 165–176. SIAM/Omnipress (2012)
Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Guruswami, V., Pandu Rangan, C., Chang, M.S., Chang, G.J., Wong, C.K.: The vertex-disjoint triangles problem. In: Hromkovič, J., Sýkora, O. (eds.) WG 1998. LNCS, vol. 1517, pp. 26–37. Springer, Heidelberg (1998)
Halldórsson, M.: Approximating discrete collections via local improvements. In: SODA, pp. 160–169 (1995)
Hassin, R., Rubinstein, S.: An approximation algorithm for maximum packing of 3-edge paths. Information Processing Letters 63, 63–67 (1997)
Hassin, R., Rubinstein, S.: An approximation algorithm for maximum triangle packing. Discrete Applied Math. 154(6), 971–979 (2006)
Hassin, R., Rubinstein, S.: Erratum to “An approximation algorithm for maximum triangle packing”. Discrete Applied Math. 154, 971–979 (2006); Discrete Applied Math. 154(18), 2620 (2006)
Hassin, R., Schneider, O.: A local search algorithm for binary maximum 2-path partitioning. Discrete Optimization 10(4), 333–360 (2013)
Hell, P., Kirkpatrick, D.C.: Packings by complete bipartite graphs. SIAM J. Algebraic Discrete Methods 7(2), 199–209 (1986)
Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of 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)
Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Information Processing Letters 37(1), 27–35 (1991)
Kargar, M., An, A.: Discovering top-k teams of experts with/without a leader in social networks. In: CIKM, pp. 985–994 (2011)
Li, C.T., Shan, M.K.: Team formation for generalized tasks in expertise social networks. In: SOCIALCOM, pp. 9–16 (2010)
Lonc, Z.: On the complexity of some edge-partition problems for graphs. Discrete Applied Mathematics 70(2), 177–183 (1996)
Manic, G., Wakabayashi, Y.: Packing triangles in low degree graphs and indifference graphs. Discrete Math. 308(8), 1455–1471 (2008)
Prieto, E., Sloper, C.: Looking at the stars. Theoretical Computer Science 351(3), 437–445 (2006)
Rangapuram, S., Bühler, T., Hein, M.: Towards realistic team formation in social networks based on densest subgraphs. In: WWW, pp. 1077–1088 (2013)
Tanahashi, R., Chen, Z.: A deterministic approximation algorithm for maximum 2-path packing. IEICE Tr. Inform. & Syst. E93-D(2), 241–249 (2010)
van Zuylen, A.: Multiplying pessimistic estimators: deterministic approximation of max TSP and maximum triangle packing. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol. 6196, pp. 60–69. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bar-Noy, A., Peleg, D., Rabanca, G., Vigan, I. (2015). Improved Approximation Algorithms for Weighted 2-Path Partitions. In: Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015. Lecture Notes in Computer Science(), vol 9294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48350-3_79
Download citation
DOI: https://doi.org/10.1007/978-3-662-48350-3_79
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48349-7
Online ISBN: 978-3-662-48350-3
eBook Packages: Computer ScienceComputer Science (R0)