Computing and Listing Avoidable Vertices and Paths

A simplicial vertex of a graph is a vertex whose neighborhood is a clique. It is known that listing all simplicial vertices can be done in $O(nm)$ time or $O(n^{\omega})$ time, where $O(n^{\omega})$ is the time needed to perform a fast matrix multiplication. The notion of avoidable vertices generalizes the concept of simplicial vertices in the following way: a vertex $u$ is avoidable if every induced path on three vertices with middle vertex $u$ is contained in an induced cycle. We present algorithms for listing all avoidable vertices of a graph through the notion of minimal triangulations and common neighborhood detection. In particular we give algorithms with running times $O(n^{2}m)$ and $O(n^{1+\omega})$, respectively. However, we propose a faster algorithm that runs in time $O(n^2 + m^2)$, and thus matches the corresponding running time of listing the simplicial vertices on sparse graphs with $m=O(n)$. To complement our results, we consider their natural generalizations of avoidable edges and avoidable paths. We propose an $O(nm)$-time algorithm that recognizes whether a given induced path is avoidable.