I'm trying to build an algorithm that says if a graph is trivially perfect or not. I realized that I can look if a graph is $(C_4, P_4)$-free as they are equivalent. (https://graphclasses.org/classes/gc_343.html)
I managed to create an algorithm to recognize $C_4$ subgraphs by reading Recognition of $C_4$-free and $\frac 1 2$-hyperbolic graphs from David Coudert and Guillaume Ducoffe.
But I can't find any clue of how to make this $P_4$ recognition. Does anyone know how can I find a pseudo-code or any information that might help me?
Thank you so much.
A connected graph has no induced $P_4$ subgraphs if it has diameter at most $2$. One way to check this is to compute the square of the adjacency matrix, and verify that it has no zeroes.
This can be done in $O(n^\omega)$ time, where $\omega$ is the matrix multiplication exponent. Even if there's something more clever to be done, this is already faster than checking for induced $C_4$ subgraphs by the method in the paper you cite, so it's not going to be the bottleneck.
If the graph is not connected, we can find the connected components (in $O(n^2)$ time) and handle each of them separately.
Alternatively: when the vertices $v_1, \dots, v_n$ are sorted from highest to lowest degree, the graph is trivially perfect if for every edge $v_i v_j$ with $i<j$, $N(v_i)$ contains $N(v_j)$.
This gives (at the very least) an $O(n^\omega)$ algorithm for your original problem. After sorting in this way, let $A$ be the upper triangular half of the adjacency matrix. Then the graph is trivially perfect if $A^2$ has no positive entries anywhere that $A$ has zero entries.
Possibly we can do even better.