The Complexity of Diameter on H-Free Graphs

Abstract

The intensively studied DIAMETER problem is to find the diameter of a given connected graph. We investigate, for the first time in a structured manner, the complexity of DIAMETER for H-free graphs, that is, graphs that do not contain a fixed graph H as an induced subgraph. We first show that if H is not a linear forest with small components, then DIAMETER cannot be solved in subquadratic time for H-free graphs under SETH. For some small linear forests, we do show linear-time algorithms for solving DIAMETER. For other linear forests H, we make progress towards linear-time algorithms by considering specific diameter values. If H is a linear forest, the maximum value of the diameter of any graph in a connected H-free graph class is some constant dmax dependent only on H. We give linear-time algorithms for deciding if a connected H-free graph has diameter dmax for several linear forests H. In contrast, for one such linear forest H, DIAMETER cannot be solved in subquadratic time for H-free graphs under SETH. Moreover, we even show that, for several other linear forests H, one cannot decide in subquadratic time if a connected H-free graph has diameter dmax under SETH.