# Bar fight prevention

This question is influenced by the book Parameterized Algorithms by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh.

You are the bodyguard of a bar in a small town, and every friday night the bar is very busy. Since the town is small, you know almost everyone, and all the conflicts among people.

The conflicts are mutual. If one wants to fight another, then you cannot assume the other will stop.

Your aim is to let in as many people as you can. But the problem is, if you let a pair conflicting people in, then they will probably fight, causing a trouble.

1. Alice and Bob are dating. Therefore, if one fights to someone, the other will also fight.

2. Charlie and Daniel are nemeses. Thus, if one dislikes another person, the other will not fight with that person, and vice versa.

3. Charlie is a womanizer who does not like single men to be around him while he's drinking in a friday night.

4. Erik has no problems except Charlie. He plain doesn't like Charlie.

5. Fred and Jennifer are a couple, and hate Bob because Bob cheated on his former girlfriend.

6. Hillary is Bob's ex-girlfriend, and does not like Alice at all, because Bob left her for Alice.

7. Gerald is very angry at Hillary because she is getting involved into another couple's relationship.

8. Larry is a very good friend of Bob, but he doesn't like Alice since Alice does not let Bob to go out with Larry.

Question: Who should you let in, and who should you prevent from entering the bar in order to prevent a potential fight? Remember that you want to let in as many people as you can.

• I take it Charlie and Daniel would not fight each other despite being nemeses? Commented Jan 18, 2018 at 16:36
• Clarification needed on this sentence: "The conflicts are mutual. If one wants to fight another, then you cannot assume the other will take it." So are the conflicts bi-directional or not? It seems to say both. Commented Jan 18, 2018 at 16:51
• I guess Charlie and Daniel would fight to death if they cross in that bar. it is better to separate them to my humble view. Commented Jan 18, 2018 at 16:53
• @Bachrach44 "other will not take it" meaning that "stand there and take it." fixed. Commented Jan 18, 2018 at 16:53
• @padawan No names beginning with I and K?
– ngn
Commented Jan 18, 2018 at 17:06

Visual Representation

It's obvious at a glance that all of the conflict is coming from

Alice/Bob and Charlie, and Hillary's and Gerald's little tiff

For obvious reasons, I'll be restricting

Alice/Bob and Charlie from entering.

Buuuut

I will allow both Hilary and Gerald to enter, based off the fact of:
Gerald is very angry at Hillary because she is getting involved into another couple's relationship.

If the couple that Hilary is getting involved with isn't there, she can't get involved, which should remove the source of conflict (if only temporarily) between H & G, thus allowing them both to enter

D E F/J H G and L can all come into my bar, for a total of 7 ...though if H & G still decide to fight without a source of conflict being present, then I suppose it has to go down to 6, making my answer basically the same as @Untitpoi