A note on line digraphs and the directed max-cut problem (Q1174433): Difference between revisions

The support of a simple digraph is the undirected graph arising when directions of edges are ignored. The authors prove that recognizing supports of line digraphs is an NP-complete problem. Further, they observe that solvable cases of the directed max-cut problem arise from solvable cases of the maximum-weight stable set problem via supports of line digraphs. In particular, they investigate digraphs \(G\) such that the support of the line digraph \(G\) is perfect.