On Triangle Counting Parameterized by Twin-Width

Abstract

In this report we present an algorithm solving Triangle Counting in time $O(d^{2}n+m)$, where n and m, respectively, denote the number of vertices and edges of a graph G and d denotes its twin-width, a recently introduced graph parameter. We assume that a compact representation of a d-contraction sequence of G is given.

arXiv comment6 pages

Cited by in corpus (2)

• Neighbourhood complexity of graphs of bounded twin-width
• Bounds on the Twin-Width of Product Graphs