Directed Maximal-Cut Problems
Arthur Farley, Andrzej Proskurowski
Committee:
Technical Report(May 1980)
Keywords:

A maximal-cut problem for a directed graph can be defined analogically to the undirected case. The latter problem is known to be NP-complete. Depending on the definition of the value of a cut, the resulting problem for general directed graphs is either efficiently solvable or NP-complete. We consider the latter variant of the problem and show an algorithm solving it in linear time for directed acyclic graphs. Breaking the cycles of a general graph and applying the same algorithm to the resulting forest gives an efficient solution algorithm for some classes of undirected graphs.