Polynomial algorithms for kernels in comparability, permutation and \(P_4\)-free graphs (Q816574)

A kernel in a digraph \(D=(V,A)\) is a set \(N\subseteq V\) that is absorbing (for every \(u\in V\setminus N\) there is some \(v\in N\) with \((u,v)\in A\)) and independent (\((u,v)\not\in A\) for all \(u,v\in N\)). The authors describe polynomial time algorithms for finding kernels in orientations of certain graphs where they consider the digraph \(D=(V,A)\) to be an orientation of the graph \(G=(V,E)\) if \(\{ (u,v),(v,u)\}\cap A\not=\emptyset\) if and only if \(uv\in E\) for \(u,v\in V\). Analysing Champetier's proof of the existence of kernels in Meyniel orientations (orientations where every triangle has two symmetric arcs) of comparability graphs they show how to find such a kernel in \(O(| V| ^2| E| )\) time. For permutation graphs they consider normal orientations (orientations where every clique has a sink) and prove that a kernel can be found also in \(O(| V| ^2| E| )\) time. Finally, for \(P_4\)-free graphs which are special permutation graphs they improve this running time to \(O(| V| | E| )\).