The Complexity of Diameter on H-free graphs
<|reference_start|>The Complexity of Diameter on H-free graphs: 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.<|reference_end|>
@article{oostveen2024the,
    title={The Complexity of Diameter on H-free graphs},
    author={Jelle J. Oostveen, Dani"el Paulusma, Erik Jan van Leeuwen},
    journal={arXiv preprint arXiv:2402.16678},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.16678},
    primaryClass={cs.DS cs.DM}
}