m15s's blog

Need help with this graph theory question — any ideas??

By m15s, history, 2 years ago, In English

A given graph represents friendship relations between a group of people. Each node is a person and an edge between any nodes means that the two people are friends. The problem wants us to find a group of 3 or more people such that every member of the group is friends with atleast two other members in the same group. In the case that there are multiple such groups satisfying this, they want us to return any one. In case that there is no such group satisfying the condition, we can return an empty list.

Any ideas for this? I was thinking of working with connected components but i'm not too sure on how to build on that. Please do help me out!! thanks

  • Vote: I like it
  • -14
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it -16 Vote: I do not like it

I think answer will be a connected component of persons which size>=3.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think any edge biconnected subgraph with more than 2 nodes is OK

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

Firstly, if a solution exists, then there is a connected subgraph satisfying the conditions. (Otherwise, if all solutions returned a subgraph with more than one connected component, then any of the connected components would also satisfy the conditions, which is a contradiction). Therefore, we will only consider connected subgraphs as possible solutions.

Also, we can show that the solution must contain a cycle. (If it didn't, then the returned subgraph would be a tree, where the leaves would break the conditions).

Finally, we observe that any cycle would satisfy the conditions, as each node would have a degree of 2 in the subgraph. Hence, we can simply find a cycle using any method (e.g. DFS) and return it.

→ Reply