How to identify an invalid graph for operator allocation problem per machine?

Question

Recently I was answering a question (Machine Scheduling - Graph Theory), but there was an open problem that I could not solve:

• Given any graph, identify if it is valid for the operator allocation problem per machine

The original problem is more or less like this:

Are given n machines, m_1, m_2, ... m_n that need to be connected at intervals of time I_1, I_2, ... I_n respectively (hence the range I_k refers to the machine m_k). For a machine to be connected, it is necessary for an operator to keep it. An operator can only operate one machine at a time; therefore, if I_i ∩ I_j != ∅, then to operate m_i and m_j two different operators are required. What is the minimum number of operators sufficient to operate these machines? Show the graph that models this problem

In the my answer to this question, I modeled this problem as a graph coloring problem. Significant excerpts from the modeling:

A classic optimization problem for the smallest possible is that of graph coloring. In this case, to use this schema, we need to map each graph coloring concept in our current problem.

• Vertices:
  Each vertex is a machine. The vertex i represents the machine i
• Rough edges:
  An edge ij means that the machines i and j are connected at the same time. Or more formally, the intersection I_i with I_j is not empty
• Colors:
  Each color is an operator. Since an operator can only operate one machine at a time, two neighboring vertices cannot have the same color.

I was even able to describe an algorithm for "random" generation of valid graphs, more or less like this:

To n any machines, manage n number pairs (A_i,B_i) such that A_i < B_i. These are the operating time intervals of the machines. If there happens to be a non-empty intersection between (A_i,B_i) and (A_j,B_j), then in the graph there must be the edge ij. Detected all intersections, you will have a valid graph of n vertices to this problem of worker allocation by machine

I was also able to identify and prove that the following graph is invalid for this problem (demonstration omitted here):

1 --- 2
 \   /
  \ /
   x
  / \
 /   \
3 --- 4

However, I cannot find a general algorithm to identify whether a given graph satisfies the case described in the problem.

---

Talking to the folks at my college, I got another interpretation of my problem:

Dice n continuous intervals on the real numbers, none of them with known values, and given the existence of non-empty intersections between these intervals, determine whether there are real numbers for these intervals that satisfy these intersections

In this case, the intervals would represent my vertices and the non-empty intersections would represent the edges between these vertices.

I did exactly with this matter of giving the intersections determine whether or not it is valid in the Mathematics exchange

Answer 1

As perceived by users in Mathexchange, my problem is the detection of an interval graph. Particularly I could not understand the algorithms available on the internet on the subject. So? I invented my proof.

An interval graph is a graph in which every point can be represented as a contiguous segment/interval on the real line and, if there is an intersection between two intervals, in the graph there will be an edge connecting the two vertices.

Henceforth, at any time when "interval" is mentioned, without delimiting about its continuity or not, it will be subunderstood as a "contiguous interval"

Every set of intervals is possible to represent through a graph (which in turn becomes called an "interval graph"), but the reciprocal is not true. There are graphs that cannot be represented through a set of intervals. The example has even been provided:

This recognition problem is at least NP. Maybe I’m even more specific, like P, but I don’t have the proof yet.

Before providing the solution, I will present some interesting results.

---

An interval graph represents infinite intervals

Take any interval graph G. Since it is an interval graph, then there is an interval I whatever is represented by G. I is composed of N intervals in the following format (the intervals can be opened or closed, but this does not influence the conclusion at all):

(c_1, f_1)
(c_2, f_2)
...
(c_N, f_N)

We can move all a right position intervals. How do we move an interval? Adding in the values representative of its extremes the amount desired for the displacement, obvious. Then we can shift all the intervals one position to the right and we’ll get:

(c_1 + 1, f_1 + 1)
(c_2 + 1, f_2 + 1)
...
(c_N + 1, f_N + 1)

By this definition, we have that the amount of vertices is identical

Now, be i and j two intervals that contained intersection. This means that there is an edge between the vertices i and j. After the shift, as we do not change the graph but the interval, for the graph to continue representing the shifted intervals, there must be intersection between (c_i + 1, f_i + 1) and (c_j + 1, f_j + 1).

Be it x a point of intersection between (c_i, f_i) and (c_j, f_j). So that means we have the following 4 inequalities as truth (written in a compressed form):

c_i, c_j <= x <= f_i, f_j

If we add 1 in all terms, the inequalities remain true:

c_i + 1, c_j + 1 <= x + 1 <= f_i + 1, f_j + 1

Then we have to x + 1 belongs to the intersection of (c_i + 1, f_i + 1) and (c_j + 1, f_j + 1).

This result ensures that all edges continue to exist.

Now, let’s take the breaks k and l that have no intersection. Without losing generality, we can say that f_k < c_l and that therefore there are no elements at the intersection. By adding 1 of the two sides, the inequality remains true and therefore there is no intersection.

This result ensures that there is no new edge being created.

Therefore, the interval graph formed from the displacement of the original intervals has the same vertices, no less edge and no more edge, so it is the same graph. This demonstrates that a single interval graph represents an infinite class of interval sets.

A single vertex is a valid interval graph

Take the break (0, 1). To represent him, I need a vertex and no edge.

An empty graph is an interval graph

Take an empty set of breaks. You will not have edges or vertices, so an empty graph is a valid interval graph, the trivial interval graph.

Adding an edge-free vertex to an interval graph generates a valid interval graph

Take G an interval graph. Take one of its possible intervals that it represents, either. So, it is possible to say that it has a point to the right. Be that point MAX. Add the range (MAX+1, MAX+2). There is no interval with any previous interval, so there are no edges, and it consists of a valid interval graph.

Every interval graph with n+1 vertices can only be formed by the operation of adding vertices to another interval graph with n vertices

The accretion operation of a vertex consists of adding this vertex and also possibly edges that have this vertex as the terminal. That means in the graph A--B--C, when adding D, we can add the edges A--D, B--D, C--D, but we can’t add A--C.

The demonstration is trivial: adding an interval to the set will (possibly) bring intersections of this new interval with the old intervals, but it will not cause old intervals to intersect with each other. This means that by adding the range D, the intersection will not be created A--C, described in the previous paragraph.

The 1-vertex graph is generated from the trivial graph.

Every click is an interval graph

One click is possible through accretion operations. Let’s take the smallest click with edges: A--B. A set of intervals representing this graph is:

(c, f)
(c, f)

Yes, that’s right, the first break (c, f) represents A and the second interval (c, f) represents B. We can add as many times as we want this same interval to distinct vertices, so all new vertices need to be connected to each other and also connected with all old ones as well.

Every open line is an interval graph

Take a vertex of the graph such that it only has a single neighbor. Associate with it the following closed interval:

[c, c + 1]

Take your neighbor point. Associate to it the following closed interval:

[c+1, c+2]

Your other neighbor will have the break closed [c+2, c+3] and so on, so that if the distance between the vertex X and the initial vertex is n, then the interval that X represents is the following closed interval:

[c+n, c+n+1]

This ensures that each interval only intersects with your soon-to-be-smaller neighbor and your soon-to-be-larger neighbor. Therefore, I got a set of intervals from any (open) line graph, so every (open) line graph is an interval graph.

Every star is an interval graph

Take a star formed by 1 center and n satellites. To the center, place the closed interval at the beginning and open at the end [0, n).

Arbitrary order of the n satellites of 0 until n-1. To the index satellite i assign the closed interval at the beginning and open at the end [i, i+1). This ensures that every satellite intersects with the central vertex because its interval is contained integrally within the interval of the central vertex. Nor is there any intersection with another vertex, therefore constituting a star graph.

Any accretion subgraph of an interval graph is also an interval graph

An accretion subgraph S of a graph G is a graph composed of a subset of the vertices of G and all the edges connecting these vertices and belonging to G.

Take a subset of ranges of the set used to generate the full graph. So, if the ranges A and B selected in the subset had an edge on the complete graph, so they would have it in the subgraph. If they didn’t, they would still have it. Then any selected accretion subgraph will be a valid interval graph.

Note that from an accretion subgraph, it is possible to generate the graph again.

It is possible to generate a noninterval graph from an interval graph through the accretion operation

Take the graph B--A--C. Since it is an open line, then it is an interval graph. Add D as the apex and also the edges C--D and B--D. This will generate the following graph, which is known to be a graph that is not of interval:

Every accretion graph generated from a noninterval graph will also not be interval graph

Take the property qualquer subgrafo de acresção de um grafo de intervalo é, também, um grafo de intervalo. If I generate a graph after an accretion operation and this new graph is interval, this implies that the previous graph is an accretion subgraph, and therefore it should also be an interval graph.

This implies that any and every accretion graph generated from a graph that is not of interval will also not be of interval.

Every cycle with 4 or more vertices is not an interval graph

Let’s prove to a cycle of size n + 4.

Take an open length line n + 3. That means she’ll be the way A -- B -- (...n vértices...) -- W. This means that there are no values at the intersection between A and W. We can agree that the end of A is less than the beginning of W without losing generality.

Only the shape of the line, then, implies that c_A <= c_B <= f_A, that f_B > f_A and that f_B <= c_Z.

Let’s add the vertex Z and only the edges Z--A and Z--W (therefore, an accretion operation). If the new graph is an interval graph, this implies that there are values at the intersection A--Z and at the intersection Z--W.

Like f_A < c_W, a possible value for c_Z = f_a - ε1, for f_A - c_a > ε1 >= 0 with ε1 very small. So that means f_Z = c_W + ε2, for f_Z - c_z > ε2 >= 0 with ε2 very small. An interval with these values, however, implies that f_B is contained within it, so it should have an edge Z--B to be an interval graph. Since there are no such edges, then this addition generates a graph that is not interval.

A cycle of size 3 is a valid interval graph

We can do this demonstration in two ways:

1. a cycle with 3 vertices is a click
2. take the breaks [0,3], [1,4], [2,5] and mount the interval graph; you will get a cycle.

There are acyclic graphs that are not interval

A related acyclic undirected graph is a tree. Consider as being a trunk of an acyclic graph as being the longest path between the root and a leaf. If there is a vertex whose distance to all vertices of the trunk is greater than 2, then the graph is not of interval.

Without losing generality, assume that c_M1 <= c_M2 <= c_M3. Note that M2 has no edge nor with M1 nor with M3. This means that, to be a valid interval, the interval that C represents accurate:

• fully contain the range of M2
• intersect with M1 right at the beginning of the break
• intersect with M3 right at the end of the break

Like M2 is contained in C and E2 intersects with M2, then E2 should also intersect with C. Therefore, this graph is not an interval graph.

Note that this does not mean that the following graph is not an interval graph:

This is due to the fact that the trunk is E1--M1--C--M2--E2, nay E1--M1--C--M3. So the longest distance between a vertex and its trunk is 1 (M3--C).

With this result, we can extrapolate so that, from any connected interval graph, if three distinct radicals in the format are coupled to it E--M-- disjoint, the resulting graph is not interval.

Yeah, but what do I do with it?

So far, we have been able to find two classes of graphs that are not interval:

• cycles (cordless) of a length of more than or equal to 4
• 3 radicals E--M-- disjoint each other connected in the same connected graph

Unfortunately, I was unable to demonstrate that these are the only classes of graphs that are not disjoint (there are others, such as exchanging M or E connected subgraphs, but not connecting any vertex of E with the subgraph on the other side of M). We also get a very interesting result:

• every graph of accretion mounted from a graph that is not of interval, is also not an interval graph

This last result indicates that we just need to find an accretion subgraph that is a string-free cycle of size greater than or equal to 4 to identify that it is not an interval graph. It also indicates that anything that vaguely resembles this as

(with C a related subgraph) is also not an interval subgraph.

---

On top of all that has been put, I have some suggestions on how to do this validation:

Nondeterministic algorithm

A first solution to demonstrate that the problem is in NP.

As a good NP algorithm, a certificate is required for entry, so on top of that certificate and input, it is possible to get the correct answer.

The certificate consists of, for a graph with n vertices (all labelled), a set of n ranges also labelled, so that the label of a vertex matches the label of one of the ranges provided.

The validation then becomes just check:

1. if all labels are valid
2. if the edges are intersections (this is done in O(e), being e the amount of edges in the graph)
3. if there are intersections that are not edges (this is done in O(n^2))

For example, for

A valid certificate would be:

E1: [0, 5]
M1: [5, 10]
C:  [10. 20]
M3: [13, 14]
M2: [20, 25]
E2: [25, 30]

The validations:

1. has 6 intervals and 6 vertices, all interval labels are also vertex labels
   checked, positive

2. each edge has an intersection

    E1--M1: {5}
    M1--C:  {10}
    C--M3:  [13, 14]
    C--M2:  {20}
    E2--M2: {25}
   

3. has no other possible intersection, so it is not "missing edges" in the graph to represent that specific graph.

Deterministic algorithm

This algorithm is highly influenced by the above certificate.

First, we set up a "permutation" of the vertices. What do you mean? We sort the vertices in a list, simple as that. If I have n vertices, so I have n! possible permutations. For the above graph there are 6! = 720 possible permutations; some of them are:

C,M1,M2,M3,E1,E2
M1,E1,C,M2,E3,M3
E1,M1,C,M3,M2,E2

In this permutation, we make the assumption that they are ordered in such a way that the element in the position i+1 has an interval whose smallest element is greater than the smallest element of the range of the position element i. For example, the third permutation above could represent the following intervals:

      0  1  2  3  4  5  6  7
 E1:  ****
 M1:     ******
 C:           ********
 M3:             **
 M2:                 *****
 E2:                     ****

Numerically would be:

• E1: [0, 1]
• M1: [1, 2.7]
• C: [2.7, 5]
• M3: [3.7, 4]
• M2: [4.7, 6.3]
• E2: [6.3, 7.3]

To be an interval graph, there must be at least one such permutation that, with this interpretation of the initial number always increasing according to the position in the list, every vertex and its neighbors share the following property (considering A come before Z in permutation, without losing generality):

• if there is an edge A--Z, then this can be represented by substring in permutation AZ
• if there is an edge A--Z, and permutation has some other vertices in the middle of the way, so these vertices are all neighbors of A; for example, ABCZ implies that A is a neighbor of B and of C also
• if one of the above two conditions cannot be met, then this permutation is invalid

Let’s take the three permutations we used in the beginning to analyze.

The first, C,M1,M2,M3,E1,E2. C is actually neighbor to M1,M2,M3. So the neighborhood of C is valid. However M1 is a neighbor of E1 but not of M2, nor of M3, so this permutation is invalid.

The second permutation, M1,E1,C,M2,E3,M3. M1 is a neighbor of E1,C. E1 there’s no other neighbor, so it’s okay with him. C has as remaining neighbors M2 and M3, but has not E3. Therefore invalid permutation.

Let’s take the third permutation: E1,M1,C,M3,M2,E2. E1 has as neighbor only M1, then it’s all right so far. M1 has as another neighbor C. C, in turn, has as neighbor M2 and M3, and they appear in order M3,M2. M3 no more neighbors left, so we’re good till here. M2 still needs the neighbor E2, that comes right after. E2 no new neighbors. So permutation is valid and it is possible to write a set of intervals for that permutation.

Let us now take a case where it is not interval graph:

The possible permutations are:

ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA

All of them must be invalid. Let’s start by eliminating those that start with the following sequences:

• AD
• DA
• BC
• CB

Because there are no edges A--D nor B--C and all these vertices have edges, so not the second letter of the sequence should be one of its neighbors. So, we remained:

ABCD
ABDC
ACBD
ACDB
BACD
BADC
BDAC
BDCA
CABD
CADB
CDAB
CDBA
DBAC
DBCA
DCAB
DCBA

There are still 16 sequences to be eliminated. We can eliminate all that have the sequence BCD, for there is no B--C but there is B--D. Similar to the opposite sequence, DCB, and also to ADB, ADC, BCA and its inverses BDA, CDA and ACB. After filtering:

ABDC
ACDB
BACD
BDCA
CABD
CDBA
DBAC
DCAB

There are still 8 of them. Note that now, for all these other elements, the first element has a connection with the second element (as in A--B), do not have with the third but have with the last. Therefore, none of these permutations is valid.

This algorithm has expected average time to function O(n! * e), since they are n! permutations and, for each permutation, I must check edge to edge whether the permutation is valid.