0
$\begingroup$

Consider a graph $ G = (V, E) $ where a vertex $ v \in V $ is designated as the center if it is connected to every other vertex $ u \in 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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Any specific reason why you are connecting this problem with matching? Won't a direct algorithm help? $\endgroup$
    – Lisa E.
    Commented Jun 4 at 4:47
  • $\begingroup$ Where did you encounter this task? Can you credit the original source? This looks like a classic exercise-style task. We're not particularly looking for posts that are the statement of an exercise-style task. We're looking to build an archive of knowledge that will be useful to others, but building an archive of exercises and their solutions is unlikely to be helpful to you or to others. The way to learn is not by looking at solutions others provide you, but by wrestling with the problem on your own until you can find your way to a solution; or picking easier problems where you can. $\endgroup$
    – D.W. ♦
    Commented Jun 4 at 4:55

1 Answer 1

Reset to default
0
$\begingroup$

I list some hints. If you need to reveal one hint, try to work with that hint for a good period of time (half an hour or so) to try to use it to come up with an algorithm, before revealing the next hint.

Given a vertex $v$, how many modifications are needed, to turn $v$ into a center?

If a graph starts out with 0 centers, how should you choose which vertex to make into a center?

Given a vertex $u$ that is currently not a center, how many modifications are needed, to turn $u$ into a non-center?

If a graph starts out with 2 centers, how should you choose which vertex to keep as a center?

If a graph starts out with 3 centers, how should you choose which vertex to keep as a center?

If a graph starts out with 4 centers, how should you choose which vertex to keep as a center?

If a graph starts out with 3 centers, you can certainly remove 2 of the centers by removing 2 edges (one edge per center). Can you do it by removing 1 edge?

If a graph starts out with 17 centers, how can you remove 16 centers by removing 8 edges?

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your helpful hints. After careful consideration for hours, I propose the following steps: 1. Add an edge from vertex $v$ to any other vertex and vice versa if such edges do not already exist. Remove any extra edges. 2. Select the vertex that requires the fewest modifications to become a center. 3. With a center $c$, and edges $cu$ and $uc$ present, ensure $u$ has one additional outgoing and one incoming edge by adding, keeping or removing some edges. For the rest: Retain the edge that requires the maximum modifications to transition from a center to a non-center. $\endgroup$
    – Stephen Stone
    Commented Jun 4 at 12:35
  • $\begingroup$ I’ve obtained these results, yet I’m encountering challenges in discerning the connection to maximal bipartite matchings and resolving the issue at hand. I would greatly appreciate any additional guidance. $\endgroup$
    – Stephen Stone
    Commented Jun 4 at 12:35
  • $\begingroup$ @StephenStone, I suggest revising the question to credit the context where you encountered this problem -- as I previously suggested. I added some more hints to my answer. I think you haven't thought through the case where there are multiple centers enough yet. I suggest trying some examples. How many edges do you need to remove, to turn a center into a non-center? You talk about "maximum modifications" but it's always at most one edge, right? Can removing one edge get rid of more than one center? $\endgroup$
    – D.W. ♦
    Commented Jun 4 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.