Kernel-Perfection through the Push Operation
Scott Heard, Jing Huang · 2009
Let D = (V,A) be a digraph. A kernel of D is an independent set S of vertices such that every vertex of D is either in S or dominates a vertex in S. If every induced subdigraph of D has a kernel, then D is called kernel-perfect. According to Richardson, if a digraph does not contain a directed cycle of odd length then it is kernel-perfect. Here we study the kernel-perfection through use of the push operation of digraphs. For a subset X of vertices of D, DXis the digraph obtained from D by pushing X, that is, reversing the directions of arcs between X and V - X. We prove that the problem of deciding if a digraph can be pushed to be kernel-perfect is an NP-complete problem. This is on contrast to a previous result showing the same decision problem restricted to chordal digraphs is polynomial time solvable. We further show that the problem of deciding whether a graph can be pushed to contain no directed cycle of odd length is also NP-complete.