Efficiently recognizing the \(P_4\)-structure of trees and of bipartite graphs without short cycles (Q5935599)

The \(P_4\)-structure of a graph \(G\) is a 4-uniform hypergraph whose vertex set coincides with the vertex set of \(G\) and whose edge set consists of quadruples of vertices that form induced 4-vertex paths in \(G\). The authors propose a simple algorithm deciding if an input 4-uniform hypergraph is a \(P_4\)-structure of a bipartite graph without cycles of length 4 and 6. The running time of the algorithm is quadratic with respect to the number of vertices of the input hypergraph. In the special case of trees the algorithm has a better running time than other algorithms known to date.