Fair edge deletion problems

The notation of fair edge-deletion problems is introduced. These arise when it is desirable to control the number of edges incident to any node that are either deleted or remain following edge deletion. Six such problems were formulated for the case where the resultant graph is known to be acyclic, and the complexity of four of these is easily determined from known results. The remaining two are the authors´ focus. It is shown that the problem of finding a minimum-degree deletion graph H such that G-H is acyclic is NP-hard when G is undirected, and is solvable in linear time when G is directed