Hacker News Reader

Comment by bongodongobob | Hacker News Reader

All that is completely irrelevant, you're overcomplicating it. Each person has 1 of 2 states, connected or not. If 4 are connected, 2 aren't, if 4 aren't 2 are, etc.

View on HN

No, each edge in the graph has 2 states. There are 15 edges between the 6 people.

But the edge states don't matter, the node states do. They're either connected friends or they aren't. What's the third state?

In this encoding of the problem, the graph is fully connected, the edges indicate the state of a connection (ie. friendship) between 2 users, and the goal is to check that there is either a chain of 2 "connected" edges (A to B and B to C for any A,B,C in the nodes) or 2 "disconnected" edges, which indeed isn't easy to do the tedious way.

The crucial property here is the symmetry between connected and disconnected edges: for any given configuration, if it's difficult to check it on one hand, then it should be easy to do it on the other.

No, the connections are what matters. A may be friends with both B and C, but that doesn't mean that B is necessarily friends with C.

I understand that. That's the encoding of being "connected".

Where did you get "connected" from? We're talking about whether they are "a trio of mutual friends" or not; that requires them all to be friends with each other, not merely "connected".

2 groups of 3 mutual friends is a different graph than 3 pairs of friends

Reply on news.ycombinator.com