I'm working with a particular graph problem and I'm not sure how to describe it. I dug up my algorithms textbook and can't find anything exactly right. I'm trying to plot a path through a weighted undirected complete graph where the weight of the path is defined by the 1-to-1 weights between all vertices.
Here's an example. Imagine I'm making seating charts for a wedding. Some wedding guests are good friends and others… not so much. I used an undirected graph with each guest on the vertices and the 1-to-1 relationships between guests as the edges. Here's a graph of the relationships between the guests Amy, Brent, Charlie, and Donald. I abbreviated their names as A, B, C, and D.
Donald caused some drama and has negative relationships with other guests. To maintain harmony, I want don't want the sum of relationships at any table to be negative. Imagine putting Amy, Brent, and Donald at the same table.
The sum of the edge weights between these three people is 5-5-5=-5, which is less than zero. So I don't want this table arrangement. In the past, I've looked at one weight at a time when constructing paths, so this would be a path from AB (+5) that continues BC (-5), meaning the path ABC would have a weight of 0. Here I want to include the edge weight AC (-5) as well.
Is there a name for a path through a graph like this where you have to count the total 1:1 edge weights instead of just the edges used in a path?
Best Answer
If you want to sum the edge weights for all pairs of people who are seated at the same table, you are talking about a complete subgraph, which is called a clique. You might also be interested in this blog post, where the objective is to minimize the sum across tables of the maximum unhappiness at the table.