On Fair Edge Deletion Problems
Petr Kolman, Bernard Lidický, Jean‐Sébastien Sereni · 2009
In edge deletion problems, we are given a graph G and a graph property π and the task is to find a subset of edges the deletion of which results in a subgraph of G satisfying the property π. Typically the objective is to minimize the total number of deleted edges while in less common fair versions the objective is to minimize the maximum number of edges removed from a single vertex. We focus on the minimum fair odd cycle transversal (OCT) problem where the task is to make the graph bipartite; the problem is closely related to improper colorings of graphs. Though the classical version of the problem was diligently studied, the minimum fair version brings new challenges. We describe a Θ(√n) approximation algorithm for general graphs and an exact polynomial time algorithm for graphs of bounded treewidth. Though there are several general frameworks (e.g., MSOL) for dealing with optimization problems on graphs of bounded treewidth, the minimum fair OCT does not seem to fit into any of them. Analogous results are proved for minimum fair cut problem.