Skip to main content
SpringerLink
Log in

Approximation and Tidying—A Problem Kernel for s-Plex Cluster Vertex Deletion

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abu-Khzam, F.N.: A kernelization algorithm for d-hitting set. J. Comput. Syst. Sci. 76(7), 524–531 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  2. Alba, R.D.: A graph-theoretic definition of a sociometric clique. J. Math. Sociol. 3, 3–113 (1973)

    Article  MathSciNet  Google Scholar 

  3. Balasundaram, B., Butenko, S., Hicks, I.V.: Clique relaxations in social network analysis: The maximum k-plex problem. Operations Research (2011, to appear)

  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)

    Chapter  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Google Scholar 

  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)

    Chapter  Google Scholar 

  10. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)

    Book  Google Scholar 

  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

    Google Scholar 

  12. Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)

    Google Scholar 

  13. Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31–45 (2007)

    Article  Google Scholar 

  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)

    Chapter  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  16. Hüffner, F., Niedermeier, R., Wernicke, S.: Techniques for practical fixed-parameter algorithms. Comput. J. 51(1), 7–25 (2008)

    Article  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  18. Kolaitis, P.G., Thakur, M.N.: Logical definability of NP optimization problems. Inf. Comput. 115(2), 321–353 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  19. Kratsch, S.: Polynomial kernelizations for MIN F+Π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)

    Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

  21. Marx, D., Schlotter, I.: Parameterized graph cleaning problems. Discrete Appl. Math. 157(15), 3258–3267 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  22. McClosky, B., Hicks, I.: Combinatorial algorithms for the maximum k-plex problem. J. Comb. Optim. (2011). doi:10.1007/s10878-010-9338-2

    Google Scholar 

  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)

    Chapter  Google Scholar 

  24. Mokken, R.J.: Cliques, clubs and clans. Qual. Quant. 13, 161–173 (1979)

    Article  Google Scholar 

  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)

    Google Scholar 

  26. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)

    Book  MATH  Google Scholar 

  27. Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299–301 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  28. Schaeffer, S.E.: Graph clustering. Comput. Sci. Rev. 1(1), 27–64 (2007)

    Article  MathSciNet  Google Scholar 

  29. Seidman, S.B., Foster, B.L.: A graph-theoretic generalization of the clique concept. J. Math. Sociol. 6, 139–154 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  30. Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Appl. Math. 144(1–2), 173–182 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, 10623, Berlin, Germany

    René van Bevern & Rolf Niedermeier

  2. Institut für Informatik, Friedrich-Schiller-Universität Jena, Ernst-Abbe-Platz 2, 07743, Jena, Germany

    Hannes Moser

Authors
  1. René van Bevern
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hannes Moser
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rolf Niedermeier
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to René van Bevern.

Additional information

Supported by the DFG, project AREG, NI 369/9. An extended abstract of this paper appeared under the title “Kernelization Through Tidying—A Case-Study Based on s-Plex Cluster Vertex Deletion” in Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN’10), Oaxaca, México, April 2010, volume 6034 of Lecture Notes in Computer Science, pages 528–539, Springer, 2010. Whereas in the extended abstract the proofs focused on 2-Plex Cluster Vertex Deletion, here we present the kernelization for the general s-plex cluster vertex deletion set problem, which is only slightly more technical.

Rights and permissions

Reprints and permissions

About this article

Cite this article

van Bevern, R., Moser, H. & Niedermeier, R. Approximation and Tidying—A Problem Kernel for s-Plex Cluster Vertex Deletion. Algorithmica 62, 930–950 (2012). https://doi.org/10.1007/s00453-011-9492-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-011-9492-7

Keywords

Search

Navigation