Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Finding Small Complete Subgraphs Efficiently

Dumitrescu, Adrian and Lingas, Andrzej LU (2023) 34th International Workshop on Combinatorial Algorithms, IWOCA 2023 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 13889 LNCS. p.185-196
Abstract

(I) We revisit the algorithmic problem of finding all triangles in a graph G= (V, E) with n vertices and m edges. According to a result of Chiba and Nishizeki (1985), this task can be achieved by a combinatorial algorithm running in O(mα) = O(m3 / 2) time, where α= α(G) is the graph arboricity. We provide a new very simple combinatorial algorithm for finding all triangles in a graph and show that is amenable to the same running time analysis. We derive these worst-case bounds from first principles and with very simple proofs that do not rely on classic results due to Nash-Williams from the 1960s. (II) We extend our arguments to the problem of finding all small complete subgraphs of a given fixed size. We show that the... (More)

(I) We revisit the algorithmic problem of finding all triangles in a graph G= (V, E) with n vertices and m edges. According to a result of Chiba and Nishizeki (1985), this task can be achieved by a combinatorial algorithm running in O(mα) = O(m3 / 2) time, where α= α(G) is the graph arboricity. We provide a new very simple combinatorial algorithm for finding all triangles in a graph and show that is amenable to the same running time analysis. We derive these worst-case bounds from first principles and with very simple proofs that do not rely on classic results due to Nash-Williams from the 1960s. (II) We extend our arguments to the problem of finding all small complete subgraphs of a given fixed size. We show that the dependency on m and α in the running time O(αℓ-2· m) of the algorithm of Chiba and Nishizeki for listing all copies of Kℓ, where ℓ≥ 3, is asymptotically tight. (III) We give improved arboricity-sensitive running times for counting and/or detection of copies of Kℓ, for small ℓ≥ 4. A key ingredient in our algorithms is, once again, the algorithm of Chiba and Nishizeki. Our new algorithms are faster than all previous algorithms in certain high-range arboricity intervals for every ℓ≥ 7.

(Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
graph arboricity, rectangular matrix multiplication, subgraph detection/counting, triangle
host publication
Combinatorial Algorithms - 34th International Workshop, IWOCA 2023, Proceedings
series title
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
editor
Hsieh, Sun-Yuan ; Hung, Ling-Ju and Lee, Chia-Wei
volume
13889 LNCS
pages
12 pages
publisher
Springer Science and Business Media B.V.
conference name
34th International Workshop on Combinatorial Algorithms, IWOCA 2023
conference location
Tainan, Taiwan
conference dates
2023-06-07 - 2023-06-10
external identifiers
  • scopus:85163991645
ISSN
1611-3349
0302-9743
ISBN
9783031343469
DOI
10.1007/978-3-031-34347-6_16
language
English
LU publication?
yes
id
565c876a-63c8-4e92-ac46-06177cd8d6e0
date added to LUP
2023-10-06 15:11:42
date last changed
2024-04-19 02:03:22
@inproceedings{565c876a-63c8-4e92-ac46-06177cd8d6e0,
  abstract     = {{<p>(I) We revisit the algorithmic problem of finding all triangles in a graph G= (V, E) with n vertices and m edges. According to a result of Chiba and Nishizeki (1985), this task can be achieved by a combinatorial algorithm running in O(mα) = O(m<sup>3 / 2</sup>) time, where α= α(G) is the graph arboricity. We provide a new very simple combinatorial algorithm for finding all triangles in a graph and show that is amenable to the same running time analysis. We derive these worst-case bounds from first principles and with very simple proofs that do not rely on classic results due to Nash-Williams from the 1960s. (II) We extend our arguments to the problem of finding all small complete subgraphs of a given fixed size. We show that the dependency on m and α in the running time O(α<sup>ℓ</sup><sup>-</sup><sup>2</sup>· m) of the algorithm of Chiba and Nishizeki for listing all copies of K<sub>ℓ</sub>, where ℓ≥ 3, is asymptotically tight. (III) We give improved arboricity-sensitive running times for counting and/or detection of copies of K<sub>ℓ</sub>, for small ℓ≥ 4. A key ingredient in our algorithms is, once again, the algorithm of Chiba and Nishizeki. Our new algorithms are faster than all previous algorithms in certain high-range arboricity intervals for every ℓ≥ 7.</p>}},
  author       = {{Dumitrescu, Adrian and Lingas, Andrzej}},
  booktitle    = {{Combinatorial Algorithms - 34th International Workshop, IWOCA 2023, Proceedings}},
  editor       = {{Hsieh, Sun-Yuan and Hung, Ling-Ju and Lee, Chia-Wei}},
  isbn         = {{9783031343469}},
  issn         = {{1611-3349}},
  keywords     = {{graph arboricity; rectangular matrix multiplication; subgraph detection/counting; triangle}},
  language     = {{eng}},
  pages        = {{185--196}},
  publisher    = {{Springer Science and Business Media B.V.}},
  series       = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}},
  title        = {{Finding Small Complete Subgraphs Efficiently}},
  url          = {{http://dx.doi.org/10.1007/978-3-031-34347-6_16}},
  doi          = {{10.1007/978-3-031-34347-6_16}},
  volume       = {{13889 LNCS}},
  year         = {{2023}},
}