Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Parameterized Aspects of Triangle Enumeration

  • Conference paper
  • First Online:
Fundamentals of Computation Theory (FCT 2017)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10472))

Included in the following conference series:

Abstract

Listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration, providing both positive results (new enumerative kernelizations, “subcubic” parameterized solving algorithms) as well as negative results (uselessness in terms of possibility of “faster” parameterized algorithms of certain parameters such as diameter).

A full version is available at https://arxiv.org/abs/1702.06548.

T. Fluschnik—Supported by the DFG, project DAMM (NI 369/13-2).

A. Nichterlein—Supported by a postdoc fellowship of the DAAD while at Durham University, UK.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    \(\omega \) is a placeholder for the best known \(n\times n\)-matrix multiplication exponent.

  2. 2.

    Degeneracy measures graph sparseness. A graph G has degeneracy d if every subgraph contains a vertex of degree at most d; thus G contains at most \(n\cdot d\) edges.

  3. 3.

    The 3SUM problem asks whether a given set S of n integers contains three integers \(a, b, c \in S\) summing up to 0. The 3SUM-conjecture states that for any constant \(\varepsilon > 0\) there is no \(O(n^{2-\varepsilon })\)-time algorithm solving 3SUM. The connection between 3SUM and listing/detecting triangles is well studied [24, 29].

References

  1. Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: Proceedings of the 55th FOCS, pp. 434–443. IEEE Computer Society (2014)

    Google Scholar 

  2. Abboud, A., Williams, V.V., Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: Proceedings of the 27th SODA, pp. 377–391. SIAM (2016)

    Google Scholar 

  3. Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM J. Comput. 27(4), 942–959 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  4. Becchetti, L., Boldi, P., Castillo, C., Gionis, A.: Efficient semi-streaming algorithms for local triangle counting in massive graphs. In: Proceedings of the 14th ACM KDD, pp. 16–24. ACM (2008)

    Google Scholar 

  5. Björklund, A., Pagh, R., Williams, V.V., Zwick, U.: Listing triangles. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 223–234. Springer, Heidelberg (2014). doi:10.1007/978-3-662-43948-7_19

    Google Scholar 

  6. Bretscher, A., Corneil, D.G., Habib, M., Paul, C.: A simple linear time LexBFS cograph recognition algorithm. SIAM J. Discret. Math. 22(4), 1277–1296 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  7. Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210–223 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  8. Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14(4), 926–934 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  9. Creignou, N., Meier, A., Müller, J.S., Schmidt, J., Vollmer, H.: Paradigms for parameterized enumeration. Theory Comput. Syst. 60(4), 737–758 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  10. Doucha, M., Kratochvíl, J.: Cluster vertex deletion: a parameterization between vertex cover and clique-width. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 348–359. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32589-2_32

    Chapter  Google Scholar 

  11. Ferrara, E.: Measurement and analysis of online social networks systems. In: Alhajj, R., Rokne, J. (eds.) Encyclopedia of Social Network Analysis and Mining, pp. 891–893. Springer, New York (2014). doi:10.1007/978-1-4614-6170-8_242

    Google Scholar 

  12. Fluschnik, T., Komusiewicz, C., Mertzios, G.B., Nichterlein, A., Niedermeier, R., Talmon, N.: When can graph hyperbolicity be computed in linear time? In: Ellen F., Kolokolova A., Sack J.R. (eds.) Proceedings of the 15th WADS. LNCS, vol. 10389, pp. 397–408. Springer, Heidelberg (2017). doi:10.1007/978-3-319-62127-2_34. ISBN 978-3-319-62126-5

  13. Fomin, F.V., Lokshtanov, D., Pilipczuk, M., Saurabh, S., Wrochna, M.: Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. In: Proceedings of the 28th SODA, pp. 1419–1432. SIAM (2017)

    Google Scholar 

  14. Giannopoulou, A.C., Mertzios, G.B., Niedermeier, R.: Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs. In: Proceedings of the 10th IPEC, LIPIcs, vol. 43, pp. 102–113. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)

    Google Scholar 

  15. Grabow, C., Grosskinsky, S., Kurths, J., Timme, M.: Collective relaxation dynamics of small-world networks. Phys. Rev. E 91, 052815 (2015)

    Article  MathSciNet  Google Scholar 

  16. Green, O., Bader, D.A.: Faster clustering coefficient using vertex covers. In: Proceedings of the 6th SocialCom, pp. 321–330. IEEE Computer Society (2013)

    Google Scholar 

  17. Habib, M., Paul, C., Viennoti, L.: A synthesis on partition refinement: a useful routine for strings, graphs, boolean matrices and automata. In: Morvan, M., Meinel, C., Krob, D. (eds.) STACS 1998. LNCS, vol. 1373, pp. 25–38. Springer, Heidelberg (1998). doi:10.1007/BFb0028546

    Google Scholar 

  18. Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput. 7(4), 413–423 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  19. Khamis, M.A., Ngo, H.Q., Ré, C., Rudra, A.: Joins via geometric resolutions: worst case and beyond. ACM Trans. Database Syst. 41(4), 22:1–22:45 (2016)

    Article  MathSciNet  Google Scholar 

  20. Kopelowitz, T., Pettie, S., Porat, E.: Dynamic set intersection. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 470–481. Springer, Cham (2015). doi:10.1007/978-3-319-21840-3_39

    Chapter  Google Scholar 

  21. Kopelowitz, T., Pettie, S., Porat, E.: Higher lower bounds from the 3SUM conjecture. In: Proceedings of the 27th SODA, pp. 1272–1287. SIAM (2016)

    Google Scholar 

  22. Lagraa, S., Seba, H.: An efficient exact algorithm for triangle listing in large graphs. Data Min. Knowl. Disc. 30(5), 1350–1369 (2016)

    Article  MathSciNet  Google Scholar 

  23. Latapy, M.: Main-memory triangle computations for very large (sparse (power-law)) graphs. Theor. Comput. Sci. 407(1–3), 458–473 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  24. Lee, T., Magniez, F., Santha, M.: Improved quantum query algorithms for triangle detection and associativity testing. Algorithmica 77(2), 459–486 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  25. 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  MathSciNet  MATH  Google Scholar 

  26. Mertzios, G.B., Nichterlein, A., Niedermeier, R.: The power of linear-time datareduction for maximum matching. In: Proceedings of the 42nd MFCS, LIPIcs, vol. 83, pp. 46:1–46:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)

    Google Scholar 

  27. Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  28. Park, H., Silvestri, F., Kang, U., Pagh, R.: Mapreduce triangle enumeration with guarantees. In: Proceedings of CIKM 2014, pp. 1739–1748. ACM (2014)

    Google Scholar 

  29. Patrascu, M.: Towards polynomial lower bounds for dynamic problems. In: Proceedings of the 42nd STOC, pp. 603–610. ACM (2010)

    Google Scholar 

  30. Schank, T., Wagner, D.: Finding, counting and listing all triangles in large graphs, an experimental study. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol. 3503, pp. 606–609. Springer, Heidelberg (2005). doi:10.1007/11427186_54

    Chapter  Google Scholar 

  31. Sorge, M., Weller, M.: The graph parameter hierarchy, TU Berlin (2016). Unpublished Manuscript

    Google Scholar 

  32. Zhang, Y., Parthasarathy, S.: Extracting analyzing and visualizing triangle \(k\)-core motifs within networks. In: Proceedings of the 28th ICDE, pp. 1049–1060. IEEE Computer Society (2012)

    Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Matthias Bentert, Till Fluschnik, André Nichterlein & Rolf Niedermeier

Authors
  1. Matthias Bentert
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Till Fluschnik
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. André Nichterlein
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Rolf Niedermeier
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Matthias Bentert .

Editor information

Editors and Affiliations

  1. CNRS, University of Bordeaux, Talence cedex, France

    Ralf Klasing

  2. LaBRI, University of Bordeaux, Talence cedex, France

    Marc Zeitoun

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer-Verlag GmbH Germany

About this paper

Cite this paper

Bentert, M., Fluschnik, T., Nichterlein, A., Niedermeier, R. (2017). Parameterized Aspects of Triangle Enumeration. In: Klasing, R., Zeitoun, M. (eds) Fundamentals of Computation Theory. FCT 2017. Lecture Notes in Computer Science(), vol 10472. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-55751-8_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-662-55751-8_9

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-662-55750-1

  • Online ISBN: 978-3-662-55751-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation