×

zbMATH — the first resource for mathematics

Approximation and tidying – a problem kernel for \(s\)-plex cluster vertex deletion. (English) Zbl 1236.68100
Summary: We introduce the NP-hard graph-based data clustering problem \(s\)-Plex Cluster Vertex Deletion, where the task is to delete at most \(k\) vertices from a graph so that the connected components of the resulting graph are \(s\)-plexes. In an \(s\)-plex, every vertex has an edge to all but at most \(s - 1\) other vertices; cliques are 1-plexes. We propose a new method based on “approximation and tidying” for kernelizing vertex deletion problems whose goal graphs can be characterized by forbidden induced subgraphs. The method exploits polynomial-time approximation results and thus provides a useful link between approximation and kernelization. Employing “approximation and tidying”, we develop data reduction rules that, in \(O(ksn ^{2})\) time, transform an \(s\)-Plex Cluster Vertex Deletion instance with \(n\) vertices into an equivalent instance with \(O(k ^{2} s ^{3})\) vertices, yielding a problem kernel. To this end, we also show how to exploit structural properties of the specific problem in order to significantly improve the running time of the proposed kernelization method.

MSC:
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abu-Khzam, F.N.: A kernelization algorithm for d-hitting set. J. Comput. Syst. Sci. 76(7), 524–531 (2010) · Zbl 1197.68083 · doi:10.1016/j.jcss.2009.09.002
[2] Alba, R.D.: A graph-theoretic definition of a sociometric clique. J. Math. Sociol. 3, 3–113 (1973) · Zbl 0297.92019 · doi:10.1080/0022250X.1973.9989826
[3] Balasundaram, B., Butenko, S., Hicks, I.V.: Clique relaxations in social network analysis: The maximum k-plex problem. Operations Research (2011, to appear) · Zbl 1218.90228
[4] Bodlaender, H.L.: Kernelization: New upper and lower bound techniques. In: Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC ’09). Lecture Notes in Computer Science, vol. 5917, pp. 17–37. Springer, Berlin (2009)
[5] Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009) · Zbl 1192.68288 · doi:10.1016/j.jcss.2009.04.001
[6] Chesler, E.J., Lu, L., Shou, S., Qu, Y., Gu, J., Wang, J., Hsu, H.C., Mountz, J.D., Baldwin, N.E., Langston, M.A., Threadgill, D.W., Manly, K.F., Williams, R.W.: Complex trait analysis of gene expression uncovers polygenic and pleiotropic networks that modulate nervous system function. Nat. Genet. 37(3), 233–242 (2005) · doi:10.1038/ng1518
[7] Cook, V.J., Sun, S.J., Tapia, J., Muth, S.Q., Argüello, D.F., Lewis, B.L., Rothenberg, R.B., McElroy, P.D., The Network Analysis Project Team: Transmission network analysis in tuberculosis contact investigations. J. Infect. Dis. 196, 1517–1527 (2007) · doi:10.1086/523109
[8] Díaz, J., Thilikos, D.M.: Fast FPT-algorithms for cleaning grids. In: Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS ’06). Lecture Notes in Computer Science, vol. 3884, pp. 361–371. Springer, Berlin (2006) · Zbl 1136.68456
[9] Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Proceedings of the 36th International Colloquium on Automata, Languages, and Programming (ICALP ’09). Lecture Notes in Computer Science, vol. 5555, pp. 378–389. Springer, Berlin (2009) · Zbl 1248.68243
[10] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)
[11] Fellows, M.R., Guo, J., Komusiewicz, C., Niedermeier, R., Uhlmann, J.: Graph-based data clustering with overlaps. Discrete Optim. (2010). doi: 10.1016/j.disopt.2010.09.006 · Zbl 1248.90070
[12] Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)
[13] Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31–45 (2007) · doi:10.1145/1233481.1233493
[14] Guo, J., Moser, H., Niedermeier, R.: Iterative compression for exactly solving NP-hard minimization problems. In: Algorithmics of Large and Complex Networks. Lecture Notes in Computer Science, vol. 5515, pp. 65–80. Springer, Berlin (2009) · Zbl 1248.68380
[15] Guo, J., Komusiewicz, C., Niedermeier, R., Uhlmann, J.: A more relaxed model for graph-based data clustering: s-plex cluster editing. SIAM J. Discrete Math. 24(4), 1662–1683 (2010) · Zbl 1221.05293 · doi:10.1137/090767285
[16] Hüffner, F., Niedermeier, R., Wernicke, S.: Techniques for practical fixed-parameter algorithms. Comput. J. 51(1), 7–25 (2008) · Zbl 05534205 · doi:10.1093/comjnl/bxm040
[17] Hüffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. Theory Comput. Syst. 47(1), 196–217 (2010) · Zbl 1205.68263 · doi:10.1007/s00224-008-9150-x
[18] Kolaitis, P.G., Thakur, M.N.: Logical definability of NP optimization problems. Inf. Comput. 115(2), 321–353 (1994) · Zbl 0820.68048 · doi:10.1006/inco.1994.1100
[19] Kratsch, S.: Polynomial kernelizations for MIN F+\(\Pi\)1 and MAX NP. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS ’09), IBFI Dagstuhl, Germany, pp. 601–612 (2009)
[20] Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219–230 (1980) · Zbl 0436.68029 · doi:10.1016/0022-0000(80)90060-4
[21] Marx, D., Schlotter, I.: Parameterized graph cleaning problems. Discrete Appl. Math. 157(15), 3258–3267 (2009) · Zbl 1209.05248 · doi:10.1016/j.dam.2009.06.022
[22] McClosky, B., Hicks, I.: Combinatorial algorithms for the maximum k-plex problem. J. Comb. Optim. (2011). doi: 10.1007/s10878-010-9338-2 · Zbl 1245.90109
[23] Memon, N., Kristoffersen, K.C., Hicks, D.L., Larsen, H.L.: Detecting critical regions in covert networks: A case study of 9/11 terrorists network. In: Proceedings of the 2nd International Conference on Availability, Reliability and Security (ARES ’07), pp. 861–870. IEEE Comput. Soc., Los Alamitos (2007)
[24] Mokken, R.J.: Cliques, clubs and clans. Qual. Quant. 13, 161–173 (1979) · doi:10.1007/BF00139635
[25] Moser, H., Niedermeier, R., Sorge, M.: Algorithms and experiments for clique relaxations–finding maximum s-plexes. In: Proceedings of the 8th International Symposium on Experimental Algorithms (SEA ’09). Lecture Notes in Computer Science, vol. 5526, pp. 233–244. Springer, Berlin (2009)
[26] Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006) · Zbl 1095.68038
[27] Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299–301 (2004) · Zbl 1052.05061 · doi:10.1016/j.orl.2003.10.009
[28] Schaeffer, S.E.: Graph clustering. Comput. Sci. Rev. 1(1), 27–64 (2007) · Zbl 1302.68237 · doi:10.1016/j.cosrev.2007.05.001
[29] Seidman, S.B., Foster, B.L.: A graph-theoretic generalization of the clique concept. J. Math. Sociol. 6, 139–154 (1978) · Zbl 0386.92015 · doi:10.1080/0022250X.1978.9989883
[30] Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Appl. Math. 144(1–2), 173–182 (2004) · Zbl 1068.68107 · doi:10.1016/j.dam.2004.01.007
[31] Wu, B., Pei, X.: A parallel algorithm for enumerating all the maximal k-plexes. In: Emerging Technologies in Knowledge Discovery and Data Mining. Lecture Notes in Artificial Intelligence, vol. 4819, pp. 476–483. Springer, Berlin (2007)
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.