×

zbMATH — the first resource for mathematics

Approximate association via dissociation. (English) Zbl 1354.05110
Summary: A vertex set \(X\) of a graph \(G\) is an association set if each component of \(G-X\) is a clique, and a dissociation set if each of these cliques has only one or two vertices. We observe some special structures and show that if none of them exists, then the minimum association set problem can be reduced to the minimum weighted dissociation set problem. This yields the first nontrivial approximation algorithm for the association set problem, with approximation ratio 2.5. The reduction is based on a combinatorial study of modular decomposition of graphs free of these special structures. Further, a novel algorithmic use of modular decomposition enables us to implement our algorithm in \(O(m n + n^2)\) time.

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C75 Structural characterization of families of graphs
68R10 Graph theory (including graph drawing) in computer science
68W25 Approximation algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ailon, Nir; Charikar, Moses; Newman, Alantha, Aggregating inconsistent information: ranking and clustering, J. ACM, 55, 5, 1-27, (2008), (Article 23). A preliminary version appeared in STOC 2005 · Zbl 1325.68102
[2] Bansal, Nikhil; Blum, Avrim; Chawla, Shuchi, Correlation clustering, Mach. Learn., 56, 1, 89-113, (2004), A preliminary version appeared in FOCS 2002 · Zbl 1089.68085
[3] Ben-Dor, Amir; Shamir, Ron; Yakhini, Zohar, Clustering gene expression patterns, J. Comput. Biol., 6, 3-4, 281-297, (1999)
[4] Boral, Anudhyan; Cygan, Marek; Kociumaka, Tomasz; Pilipczuk, Marcin, A fast branching algorithm for cluster vertex deletion, Theory Comput. Syst., 58, 2, 357-376, (2016) · Zbl 1336.68192
[5] Bruhn, Henning; Chopin, Morgan; Joos, Felix; Schaudt, Oliver, Structural parameterizations for boxicity, Algorithmica, 74, 4, 1453-1472, (2016), A preliminary version appeared in WG 2014 · Zbl 1339.68200
[6] Cai, Leizhen, Fixed-parameter tractability of graph modification problems for hereditary properties, Inform. Process. Lett., 58, 4, 171-176, (1996) · Zbl 0875.68702
[7] Cao, Yixin; Chen, Jianer, Cluster editing: kernelization based on edge cuts, Algorithmica, 64, 1, 152-169, (2012) · Zbl 1253.68144
[8] Charikar, Moses; Guruswami, Venkatesan; Wirth, Anthony, Clustering with qualitative information, J. Comput. System Sci., 71, 3, 360-383, (2005), A preliminary version appeared in FOCS 2003 · Zbl 1094.68075
[9] Chopin, Morgan; Nichterlein, André; Niedermeier, Rolf; Weller, Mathias, Constant thresholds can make target set selection tractable, Theory Comput. Syst., 55, 1, 61-83, (2014) · Zbl 1319.68109
[10] Doucha, Martin; Kratochvíl, Jan, Cluster vertex deletion: A parameterization between vertex cover and clique-width, (Rovan, Branislav; Sassone, Vladimiro; Widmayer, Peter, Mathematical Foundations of Computer Science, (MFCS), LNCS, vol. 7464, (2012), Springer), 348-359 · Zbl 1365.68278
[11] Fiorini, Samuel; Joret, Gwenaël; Schaudt, Oliver, Improved approximation algorithms for hitting 3-vertex paths, (Louveaux, Quentin; Skutella, Martin, Integer Programming and Combinatorial Optimization, (IPCO), LNCS, vol. 9682, (2016), Springer), 238-249 · Zbl 1419.90111
[12] Gallai, Tibor, Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hungar., 18, 25-66, (1967), Translated by Frédéric Maffray and Myriam Preissmann as in Perfect Graphs, Jorge L. Ramírez-Alfonsín and Bruce A. Reed, Eds., Wiley, 2001, pp. 25-66 · Zbl 0153.26002
[13] Habib, Michel; Paul, Christophe, A survey of the algorithmic aspects of modular decomposition, Comput. Sci. Rev., 4, 1, 41-59, (2010) · Zbl 1302.68140
[14] Heggernes, Pinar; Kratsch, Dieter, Linear-time certifying recognition algorithms and forbidden induced subgraphs, Nordic J. Comput., 14, 1-2, 87-108, (2007) · Zbl 1169.68653
[15] Hüffner, Falk; Komusiewicz, Christian; Moser, Hannes; Niedermeier, Rolf, Fixed-parameter algorithms for cluster vertex deletion, Theory Comput. Syst., 47, 1, 196-217, (2010) · Zbl 1205.68263
[16] Khot, Subhash; Regev, Oded, Vertex cover might be hard to approximate to within \(2 - \epsilon\), J. Comput. System Sci., 74, 3, 335-349, (2008), A preliminary version appeared in CCC 2003 · Zbl 1133.68061
[17] Lewis, John M.; Yannakakis, Mihalis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci., 20, 2, 219-230, (1980), Preliminary versions independently presented in STOC 1978 · Zbl 0436.68029
[18] Liu, Yunlong; Wang, Jianxin; You, Jie; Chen, Jianer; Cao, Yixin, Edge deletion problems: branching facilitated by modular decomposition, Theoret. Comput. Sci., 573, 63-70, (2015) · Zbl 1318.68128
[19] Lund, Carsten; Yannakakis, Mihalis, The approximation of maximum subgraph problems, (Lingas, Andrzej; Karlsson, Rolf G.; Carlsson, Svante, Automata, Languages and Programming, (ICALP), LNCS, vol. 700, (1993), Springer), 40-51 · Zbl 1310.68094
[20] McConnell, Ross M.; Spinrad, Jeremy P., Modular decomposition and transitive orientation, Discrete Math., 201, 1-3, 189-241, (1999), Preliminary versions appeared in SODA 1994 and SODA 1997 · Zbl 0933.05146
[21] Sumner, David P., Graphs indecomposable with respect to the \(X\)-join, Discrete Math., 6, 3, 281-298, (1973) · Zbl 0279.05125
[22] Tu, Jianhua; Zhou, Wenli, A factor 2 approximation algorithm for the vertex cover \(P_3\) problem, Inform. Process. Lett., 111, 14, 683-686, (2011) · Zbl 1260.68304
[23] Tu, Jianhua; Zhou, Wenli, A primal-dual approximation algorithm for the vertex cover \(P_3\) problem, Theoret. Comput. Sci., 412, 50, 7044-7048, (2011) · Zbl 1228.68033
[24] Wolk, E. S., The comparability graph of a tree, Proc. Amer. Math. Soc., 13, 789-795, (1962) · Zbl 0109.16402
[25] Yan, Jing-Ho; Chen, Jer-Jeong; Chang, Gerard J., Quasi-threshold graphs, Discrete Appl. Math., 69, 3, 247-255, (1996) · Zbl 0857.05082
[26] Yannakakis, Mihalis, Node-deletion problems on bipartite graphs, SIAM J. Comput., 10, 2, 310-327, (1981) · Zbl 0468.05044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.