Consider a graph G=(V,E) where a vertex v∈V is designated as the center if it is connected to every other vertex u∈V, such that both uv and vu are present in E. A graph is deemed ‘good’ if it has a single center, and all other vertices have equal in-degrees and out-degrees of 2.

Given a directed graph G=(V,E), my objective is to transform it into a ‘good’ graph by making the fewest possible modifications. Each modification can either be the deletion or addition of a directed edge. If the time complexity to find a maximum matching in a bipartite graph is T(n), I aim to devise an algorithm with a time complexity of O(nT(n)) that determines the minimum number of changes needed to convert G into a ‘good’ graph.

I think I kinda should connect minimum modifications needed to maximum mathcing somehow and use it n times. But I’m really stuck on finding such a realtion. I would be extremely grateful for any assistance with this problem.