Distributed Complexity of $P_k$-freeness: Decision and Certification

Masayuki Miyamoto

The class of graphs that do not contain a path on $k$ nodes as an induced subgraph ($P_k$-free graphs) has rich applications in the theory of graph algorithms. This paper explores…