Editing Graphs to Satisfy Diversity Requirements

Let G be a graph where every vertex has a colour and has specified diversity constraints, that is, a minimum number of neighbours of every colour. Every vertex also has a max-degree constraint: an upper bound on the total number of neighbours. In the Min-Edit-Cost problem, we wish to transform G using edge additions and/or deletions into a graph \(G'\) where every vertex satisfies all diversity as well as max-degree constraints. We show an \(O(n^5 \log n)\) algorithm for the Min-Edit-Cost problem, and an \(O(n^3 \log n \log \log n)\) algorithm for the bipartite case. Given a specified number of edge operations, the Max-Satisfied-Nodes problem is to find the maximum number of vertices whose diversity constraints can be satisfied while ensuring that all max-degree constraints are satisfied. We show that the Max-Satisfied-Nodes problem is W[1]-hard, in parameter \(r+ \ell \), where r is the number of edge operations and \(\ell \) is the number of vertices to be satisfied. We also show that it is inapproximable to within a factor of \(n^{1/2-\epsilon }\). For certain relaxations of the max-degree constraints, we are able to show constant-factor approximation algorithms for the problem.