PROBLEM:
There are $n$ people standing in a line, each with $k_i>0$ colors chosen from a set of $K$ distinct colors. The people need to be ordered such that the minimum possible number of lines are used to connect the people. The rules for connecting people with lines is as follows:
1) Each line can be associated with only 1 color.
2) Each person must have a line connected to them for every color they have
3) A person who does not have color $K_j$ cannot be connected to a line associated $K_j$.
4) A line associated with color $K_j$ can be connected to any number of people as long as they are consecutive and have color $K_j$.
The pictures below represent different orderings of the same group of people. The first image is one ordering which needs 6 lines whereas the second image has a different ordering and thus needs only 4 lines.
Is this problem solvable in polynomial time with respect to the number of distinct people (no two people have the same color)? (personally, I really don't think it's NP hard).
Inspiration:
This actually came from computer science. I have an Enum (basically a list of named elements where element $i$ has value $i$) which is nearly 1000 elements long and 40 different functions of the form
bool isRock (int obj) {
return (obj == granite || obj == obsidian || obj == limestone ...);
}
bool isBlack (int obj) {
return (obj == obsidian || obj == blackBerry || obj == blackWaterBottle ...);
}
Granite, obsidian, limestone, blackBerry, and blackWaterBottle are all elements of the 1000 element Enum.
Some of these functions have to make hundreds of comparisons and become VERY costly. Thus I wanted to see if I could reorder the Enum such that elements in the same function were adjacent in the Enum. If I could achieve this, then I could rewrite the functions as
bool isRock (int obj) {
return (obj > 15 && obj < 26);
}
bool isBlack (int obj) {
return ((obj > 535 && obj < 552) || (obj > 582 && obj < 595));
}
Each && clause represents a line, each color represents a function, and each element of the enum represents a person. By minimizing the number of lines, I will minimize the number of && clauses and thus the number of computations.
I think Hamiltonian Path can be reduced to this problem. Let's take a graph $G$ with $n$ vertices and $m$ edges, each edge will correspond to a color, and each person will correspond to vertex (and have colors of each edge incident to this vertex).
As every color is shared by at most $2$ person, and any $2$ persons share at most one color, we will need at least $2m - (n - 1)$ lines (there are total $2m$ person-color, at most $n - 1$ lines cover $2$ person-color, and the rest lines cover at most one).
There is bijection between hamoltionian paths and ordering with $2m - (n - 1)$ lines. For one direction, take any path, take vertex ordering from it, take corresponding persons ordering - we will be able to draw $n - 1$ lines covering $2$ colors from it (with colors corresponding to edges from out path). For the other, take vertex order corresponding to people order, and edges corresponding to lines of length $2$ (any two neighbor persons should be connected by such line, otherwise we will need more than $2m - (n - 1)$ lines).