Tornad0's blog

a graph theory problem(maybe greedy)
By Tornad0, history, 8 years ago, In English

Hi, all

I have a problem wich may solved greedily.

Background: Here is a group G of a people, one maybe another's friend. How to select least number of people to be a leader of a subgroup, so that everyone in the group G has a friend as a leader?

Translate: find least number of radial-subgraph of a graph. By radial-subgraph, it means a subgraph which has at least one point which connects all the other point in the subgraph.

Thanks!

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's take the connected components, and we will use them as subgraphs. Proof: If the subgraph is part of a single components, we can get the rest of the vertices in this component and add them to the subgraph that only improve the result. Otherwise, if the subgraph contains vertexs from several components, then it is not connected (by definition of connected components)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hi, thank you but I didn't state the problem correctly. Please check the update, thanks.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

If I am understanding you correctly — please correct me I am not — this is a standard problem in graph theory known as Minimum Vertex Cover. For the general graph this problem is NP complete, but for trees and bipartite graphs there exist special conditions which means that it is solvable in polynomial time.

Interestingly, for all graphs, the minimum vertex cover is the complement or 'inverse' of the maximum independent set (maximum number of nodes such that no two nodes share an edge). Note that you can do this problem on trees with a DP in O(n).

It may also be important to note that on a bipartite graph, the minimum vertex cover is the same as the maximum matching which can be done in polynomial time.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hi, gongy, I think it is not Minimum Vertex Cover problem.In wikipedia, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. Here I want to find a vertex cover that each vertex of the graph is connected to at least one vertex of the set, not each edge

    → Reply