Parametrised Algorithms for Finding Triangles in Graphs - Detection, Counting and Enumeration
Matthias Bentert (TU Berlin)
Finding triangles in graphs is a simple yet frequently required task that is well known to be solvable in polynomial time. However, no algorithm is known that solves the task in worst case time at most quadratic in the number of vertices of the input graph. We study the problem from a parametrised point of view, recently referred to as "FPT in P". Herein, we consider the problem given along with a parameter, e.g. the degeneracy of the input graph. We give a broad overview on our results with respect to different parametrisations. On the one hand, we present parametrised algorithms as well as kernelisations. On the other hand, we introduce a new notion of hardness that is used to prove that if certain parameters are bounded, then finding triangles in graphs cannot be done any faster than on graphs with unbounded parameters.
Back to the research colloquium site.