Complexity of Fair Deletion Problems
Many important algorithmic problems in graph theory can be
stated as deletion problems – i.e. find a set such that graph
satisfies certain property after deletion of such a set. Typically we look for a smallest such set but sometimes we want the set to be fair in some sense.
For example: find a set of edges after deletion of whitch a graph is acyclic while minimizing the maximal number of deleted edges incident with a vertex.
Professor James Abello