Realizing Interval Graphs with Size and Distance Constraints.
We study the following problem: given an interval graph, does it have a realization which satisfies additional constraints on the distances between interval endpoints? This problem arises in numerous applications in which topological information on intersection of pairs of intervals is accompanied by additional metric information on their order, distance, or size. An important application is physical mapping, a central challenge in the human genome project. Our results are (1) a polynomial algorithm for the problem on interval graphs which admit a unique clique order (UCO graphs). This class of graphs properly contains all prime interval graphs. (2) In case all constraints are upper and lower bounds on individual interval lengths, the problem on UCO graphs is linearly equivalent to deciding if a system of difference inequalities is feasible. (3) Even if all the constraints are prescribed lengths of individual intervals, the problem is NP-complete. Hence, problems (1) and (2) are also NP-complete on arbitrary interval graphs.
Introduction
. A graph G(V; E) is an interval graph if one can assign to each vertex v an interval
I v on the real line, so that two intervals have a non-empty intersection if and only if their vertices are
adjacent. The set of intervals fI v g v2V is called a realization of G. The problems which we study here are
concerned with the existence of an interval realization to a graph, subject to various types of distance
(or difference) constraints on interval endpoints. These are inequalities of the form x
y and constant C xy . Specifically, we study the following problems (we defer
further definitions to section 2):
Distance-Constrained Interval Graph (DCIG):
INSTANCE: A graph E) and a system S of distance constraints on the
variables
QUESTION: Does G have a closed interval realization whose endpoints satisfy S?
That is, is there a set of intervals f[l which form a realization of G and
their endpoints satisfy S?
A special case is DCIG in which all constraints are lower and upper bounds on interval lengths:
Bounded Interval Graph Recognition (BIG):
INSTANCE: A graph
QUESTION: Is there a closed interval realization of G such that for each vertex v:
In the following problem, each interval must have a prescribed
Measured Interval Graph Recognition (MIG
INSTANCE: A graph E) and a length function
QUESTION: Is there a closed interval realization of G, in which for every
We shall prove here that even MIG   , the most restricted problem of the three, is strongly NP-
complete. Unlike the situation with interval graphs, the fact that the intervals must be closed causes
some loss in generality. In contrast, we show that when the interval graph admits a unique consecutive
clique order (up to complete reversal), DCIG is polynomial, and hence, so are the other two problems.
The class of graphs satisfying this property (which we call UCO graphs) properly contains the class of
prime interval graphs, and is recognizable in linear time. Our solution is based on reducing the problem
to a system of difference constraints. We also prove that we cannot do better, by showing that the
problem of solving a system of difference constraints and the problem BIG on UCO graphs are linearly
equivalent.
Interval graphs have been intensively studied, due to their central role in many applications (cf. [33,
17, 11]). They arise in many practical problems which require the construction of a time line where
each particular event or phenomenon corresponds to an interval representing its duration. Among
the applications are planning [3], scheduling [22, 31], archaeology [26], temporal reasoning [2], medical
diagnosis [29], and circuit design [36]. There are also non-temporal applications in genetics [6] and
behavioral psychology [9]. In the Human Genome Project, a central problem which bears directly on
interval graphs is the physical mapping of DNA [8, 25]: It calls for the reconstruction of a map (a
realization) for a collection of DNA segments, based on information on the pairwise intersections of
segments.
In the applications above, size and distance constraints on the intervals may occur naturally: The
lengths of events (intervals) may be known precisely, or may have upper and lower bounds. The order
or distance between two events may be known. This is often the case in scheduling problems and
temporal reasoning. In physical mapping, certain experiments provide information on the sizes of the
DNA segments [21]. Our goal here is to study how to combine those additional constraints with precise
intersection data.
Green and Xu (cf. [20]) developed and implemented a program (called SEGMAP) for construction
of physical maps of DNA, which utilizes intersection and size data. The intersection data is obtained
by experimentally testing whether each of the segments contain a sequence of DNA (called STS) which
appears in a unique, unknown location along the chromosome. Hence, two segments which contain a
common STS must intersect. Their algorithm works in two phases: the first phase ignores the size data.
It obtains a partition of the STSs into groups, and a linear order on the groups. The second phase uses
the partial order of phase 1 together with the size data to obtain the map using linear programming
algorithms. Our results in section 3 imply that faster algorithms (utilizing network flow techniques) can
be used under certain conditions on the data. However, the results in section 5 imply that the general
problem tackled by SEGMAP is intractable (unless P=NP) even with perfect data.
Recognizing interval graphs (i.e., deciding if a graph has an interval realization) can be done in linear
time [7, 28, 23]. Surprisingly, much less is known about the realization problem when the input contains
additional constraints on the realization. The special case of MIG where all intervals have equal
length corresponds to recognizing unit interval graphs [33], which can be done in linear time [10]. The
special case of DCIG where all distance constraints have the form r is the problem
of seriation with side constraints [27, 19] (also called interval graph with order constraints), which can also
be solved in linear time [32]. When DCIG is further restricted to the special case where for each pair u; v
where (u; v) 62 E, we have either the constraint r The problem is equivalent to
recognizing an interval order, which can be done in linear time [4]. Fishburn and Graham [12] discussed
a special case of BIG where all intervals have the same pair p and q of upper and lower bounds. For
each p and q, they characterized the resulting class of interval graphs (and interval orders), in terms
of the family of minimal forbidden induced subgraphs (respectively, suborders). They proved that such
a family is finite if and only if p
q is rational. In this case, for integer p and q, their characterization
yields an exponential time n O(pq) algorithm for identification of such graphs (orders), where n is the
number of vertices. Isaak [24] studied a variant of BIG in which the input is an interval order, there are
upper and lower integer bounds on individual interval lengths, and the question is whether there exist a
realization in which all endpoints are integers. Using Bellman's notion of a distance graph, Isaak gave
an O(min(n 3
log time algorithm for that problem, where C is the sum of bounds on lengths.
He also posed the more general problem of BIG, which we answer here. We generalize distance graphs
to handle both strict and weak inequalities on endpoints, in order to solve DCIG on a particular class
of graphs.
There have been other studies on the realization of a set of intervals based on partial information on
their intersection, length and order. Those are different from our problems here inasmuch the information
on intersection is incomplete, i.e., the underlying interval graph is not completely known. Among these
are studies on interval sandwich [18], interval satisfiability [19, 37, 32], on interval graphs and orders
which have realizations with at most k different lengths [11, chapter 9], on the smallest interval orders
whose representation requires at least k different lengths [11, chapter 10], and on the number of distinct
interval graphs and orders on n vertices which have a realization with k given lengths [35].
The paper is organized as follows: Section 2 contains some preliminaries and background. Section 3
studies problem DCIG on UCO graphs, and proves its linear equivalence to solving systems of difference
constraints. This implies in particular an O(min(n 3
log time algorithm for all three problems
on UCO graphs. In section 4 we sketch a simple proof that DCIG is strongly NP-complete. Section 5
proves the stronger result that MIG   is strongly NP-complete. The reduction (performed in two steps)
is rather involved, but we feel it gives insight on the interplay between the topological side of the problem
(i.e., intersection, open or closed intervals) and its metric aspect (i.e., the intervals sizes).
2. Preliminaries. A graph E) is called an intersection graph of a family of sets
is called an interval graph if it is an intersection graph of a family
of intervals on the real line. In that case, S is called a realization of G. Depending on
the convention, each interval may be either closed or open, with no loss of generality. For simplicity, we
sometimes use the same names for the intervals and for the corresponding vertices.
For an interval I denote its left and right endpoints by l(I) and r(I), respectively. The length of I,
denoted jIj, is r(I) \Gamma l(I). If G has a realization in which all the intervals are of equal length, then it is
called a unit interval graph.
be the maximal cliques in a graph vng. The clique
matrix of G is the n \Theta k zero-one matrix . If the
columns in C(G) can be permuted so that the ones in each row are consecutive, then we say that
has the consecutive ones property, and we call such a permutation of the columns a consecutive (clique)
order. According to Gilmore and Hoffman [16], G is an interval graph if and only if C(G) has the
consecutive ones property.
For two non-intersecting intervals x; y where x is completely to the left of y, we write xOEy or,
equivalently, y-x. Let be a partial order. Call ! an interval order if there exists a set of
v2V such that v ! u if and only if I v OEI u . S is called a realization for P . Call E)
the incomparability graph of P , if for each u; only if u and v are incomparable in
Hence, G is an interval graph if and only if it is the incomparability graph of
some interval order. In this case we will say that the graph G admits the order !.
For a vertex in the graph (v)[fvg.
For a vertex set U ' V denote N [U . A set M ' V is called a module
in E) if for each x; y 2 M , and for each u Surely, V is a module, and
for each v 2 V , fvg is a module. Such modules are called trivial. If all modules in G are trivial, then G
is called prime. For a subset X ae V define Xg. For a module M in the graph
G, the graph G is said to
be obtained from G by contracting M to v. We usually denote by n and m the number of vertices and
edges, respectively, in the graph.
3. Distance Constraints in UCO graphs. We call an interval graph uniquely clique-orderable
(UCO for short) if it has a unique consecutive clique order, up to complete reversal, in every realization.
An interval graph G is UCO if and only if the only non-trivial modules in it are cliques [34]. Note that
G is UCO if and only if the interval order admitted by G is unique, up to complete reversal, because
an interval order of the vertices of G uniquely determines a linear order of the maximal cliques in G,
and vice versa. Denote this order by OE G . Note also that the class of UCO graphs properly contains the
class of prime interval graphs. UCO graphs can be recognized in linear time by applying the PQ-tree
algorithm of Booth and Lueker [7], and noting that G is UCO if and only if the final tree consists of a
single internal Q-node and the leaves. This procedure also computes OE G in O(m + n) time.
In this section we study the problem DCIG when the input graph is UCO. We show how to reduce
this problem, in linear time, to the problem of deciding whether a system of difference constraints is
feasible. Hence, DCIG, BIG and MIG are all polynomial on UCO graphs. We also prove that for BIG
and DCIG, we cannot do any better, since deciding the feasibility of a system of difference constraints
can be reduced in linear time to an instance of BIG with a UCO graph.
3.1. A Polynomial Algorithm for DCIG on UCO Graphs. Let be an instance
of DCIG, where E) is UCO and A is a set of difference inequalities on the interval endpoints.
Construct two systems T and -
T of difference constraints on the variables fl v ; r v g v2V , as follows: Both
systems include all inequalities in A. In addition, for each x; y contains an
inequality r x ! l y , and -
T contains an inequality r y ! l x . If xy 2 E then both T and -
T contain an
inequality r x - l y (and r y - l x ). With these definitions we prove:
Lemma 3.1. P has a realization if and only if either T or -
T has a feasible solution.
Proof. If
r v g v2V is a feasible solution to T or to -
T , then X is a solution to A, and
realizes G. On the other hand, let
r v ]g v2V be a realization of G, whose endpoints
satisfy A. Then the order of the intervals f[ ~ l v ; ~ r v ]g v2V on the real line is either OE G , or its reversal.
Therefore, f ~ l v ; ~ r v g v2V is a feasible solution to either T or -
T .
Hence, we can solve our problem by deciding whether system T or -
T is feasible. We shall prove now
that a system S of weak and strict difference constraints on n variables is reducible in linear time to a
system S 0 which consists of weak difference constraints, with numbers only O(n) times larger. (Standard
transformation techniques [14] would give numbers O(2 L ) times larger for binary input length L.)
Assume all constants in S to be integral, and fix ffl - 1
n . Define S 0 to include every weak inequality
in S, and a weak inequality strict inequality x \Gamma y ! c in S. Note that
the number of variables and number of inequalities in the two systems is the same, and the constants in
(after multiplying by an appropriate factor to restore integrality) are larger than the constants in S
by a factor of \Theta(n).
Lemma 3.2.
S has a feasible solution if and only if S 0 has one.
Proof. The 'if' direction is trivial, since a feasible solution to S 0 also satisfies S.
To prove the 'only if', we generalize the notion of a distance graph (cf. [1, p. 103]), to handle
strict and weak inequalities: For a system T of difference constraints, construct a directed weighted
graph weights and arc labels, as follows: For every constraint x \Gamma y - C xy or
add an arc (y; x) to D(T ) with weight C xy and label the arc - or !, respectively. D(T ) is
called the distance graph of the system T . The weight of a path (or a cycle) in this graph is the sum of
the weights of its arcs. Bellman has shown that when all inequalities in T are weak, T is feasible if and
only if D(T ) contains no negative cycle ([5], see also [1, p. 103]).
Suppose S 0 is not feasible. Then D(S 0 ) must contain a negative-weight cycle c. Let w(c) and w 0 (c)
be the total weight of c in D(S) and D(S 0 ), respectively. Distinguish two cases:
ffl All arcs in c have labels -. Then
(y;x)2c
(y;x)2c
(1)
Hence, S is infeasible.
ffl c contains an arc marked !. Since the weight of each arc in c differs from the weight of the
corresponding arc in c 0 by no more than ffl, we get:
Since the weights in D(S) are integral, it follows that w(c) - 0. Since the cycle c in D(S)
contains an arc marked !, the inequality (1) is strict, namely, w(c) ? 0, so S is infeasible.
Corollary 3.3.
A system T is feasible if and only if the weight of every cycle in its distance graph D(T ) is either
positive, or it is zero and the cycle consists of - arcs only.
We now show that addition of identical strict inequalities to the equivalent systems S and S 0 above
maintains the equivalence between them. (We will need this property in section 5.3): For constants
define the following systems
2 and S 3 on the set of variables
Lemma 3.4. Let
are integers and ffl ! 1
n . S
has a feasible solution if and only if S 0 has one.
Proof. The proof is by induction on the size of I 3 . For I this is lemma 3.2. Suppose both
S and S 0 have feasible solutions, and consider adding a single strict inequality E: x \Gamma y ! C to both
systems. This implies adding an arc labeled ! with to both distance graphs D(S)
and D(S 0 ). By corollary 3.3, it suffices to prove that there exist a cycle of non-positive weight passing
through e in D(S [E) if and only if such a cycle exists in D(S 0 [E). But for every simple path p from
x to y, w S 0 is an integer. Hence, dwS 0 since
C is integral, wS
By lemma 3.1, and lemma 3.2, solving an instance of DCIG linearly reduces into determining if at
least one of two systems of difference constraints is feasible. Using the distance graph reformulation, the
feasibility of such a system with M weak inequalities on N variables, with sum of absolute values of arc
weights C, can be decided in O(min(NM;
log In our instance (G; there
are n vertices, so
Corollary 3.5. Deciding if a UCO graph with difference constraints has a realization can be done
in O(min(n 3
log nC)) time.
Note that the algorithms of [30, 13] for deciding the feasibility of a system also produce a feasible
solution if one exists. This enables construction of a realization (if one exists) in O(min(n 3
log nC))
time.
3.2. Reducing a System of Difference Constraints to BIG on UCO graphs. Given a system
of weak difference constraints, we shall show how to reduce it, in linear time, to an equivalent instance
of BIG, in which the graph is UCO. According to lemma 3.2, the assumption that all constraints are
weak can be made without loss of generality.
Let P be the following system of weak difference constraints in the variables
xN g:
a new system P 0 of difference constraints
on the same variable set X:
Note that the choice of C guarantees that c 0
can be
rewritten as:
where all right hand side terms are larger than one.
We call a solution f~x i g N
to P 0 monotone if for each
Lemma 3.6. P has a solution if and only if P 0 has a monotone solution. Moreover, if -
is a feasible solution to P for which is minimal, then -
is a monotone feasible solution to P 0 .
Proof. Suppose P 0 has a monotone solution x
N . Let ~ x
for each
Therefore, the i-th inequality in P is satisfied by f~x i g N
Hence, P has a feasible solution.
Let ~ x
xN be a solution of P , for which is minimal. (P defines
an intersection of closed half-spaces, which is a closed set, therefore there is a solution attaining this
minimal value). By [5], \Delta is the sum of arc weights along some simple path in the distance graph
By P we get, for each 1 -
is a feasible solution of
. For each 1
and X 0 is monotone.
For the above system P , define to be the following BIG instance (compare figure 1):
ffl G is the intersection graph of the set of intervals A defined as follows:
i=0 where a
ffl The length constraints are as follows:
- For integral i: U (b i
a 1
a 2
a 3
a 4
a 0
a 5
a 1
a 2
a 3
a 4
a 0
a 5
1Fig. 1. The graph G used in the reduction (top) and a realization for it (bottom)
Lemma 3.7. G is UCO.
Proof. Let G 0 be the intersection graph of A [ B. It is easy to see that G 0 is prime, and hence, it
has a unique clique order [34]. Moreover, G 0 has exactly 2N cliques, each one containing
(among other vertices) a unique and distinct b i . The set of maximal cliques in G is fN [b x namely,
each clique is distinguished by a single b i . Since G 0 is UCO, its unique clique order determines a unique
linear order on fb x jx 2 Bg, and hence, also on the maximal cliques of G. Hence, G is UCO.
Theorem 3.8. P has a feasible solution if and only if J has a realization.
Proof. Only if: Suppose f~x i g N
is a feasible solution to P , for which is
minimal. By lemma 3.6, fx 0
iC is a monotone solution to P 0 . Choose arbitrary
1. Define the following set R [ T [ S of intervals:
is monotone, the intersection graph of R[T [S is isomorphic to G. The length bounds on
vertices of T and R are trivially satisfied. If
i as required. If
satisfying the length bounds on the vertices of
S.
Suppose J has a realization. Let fy i g N
be the points in a realization of J which correspond
to the intervals fb i g N
(which have length zero). W.l.o.g. y N ? y 1 , because otherwise we can reverse
the realization. Since G is UCO, the order of the intervals in J is identical to the order of the intervals
A[B [W in the definition of G. Therefore y due to the length constraint
on be the interval corresponding to w
in the
realization. Define a system P 00 of difference constraints as follows:
i . It follows that fy i g N
is a monotone solution to P 00 . A proof similar to lemma 3.2 implies that P 0 and P 00 are equivalent, so P 0
is feasible. We would like to show that P 0 has a monotone solution. Let Q 0 be the system of constraints
have only monotone solutions. According to
lemma 3.4, adding Q 0 to both P 0 and P 00 maintains the equivalence between them. But a monotone
solution of P 00 realizes has a monotone solution and according to lemma 3.6 P is
feasible.
Corollary 3.9. The problem of deciding whether there exists a feasible solution to a system of
difference constraints is linearly reducible to the problem BIG on a UCO graph.
4. DCIG is NP-complete. We will now show, that although DCIG is polynomial when restricted
to UCO graphs, it is NP-complete in general. A stronger result will be proven in the next section, but
we include a sketch of this proof as it is much more transparent.
Theorem 4.1.
DCIG is strongly NP-complete.
Proof. We show a pseudo-polynomial reduction from the problem 3-PARTITION which is known
to be strongly NP-complete (see, e.g., [15]).
An instance of 3-PARTITION is a set X of
2 ), such that
k. The question is to determine whether there exists a partition of X into k subsets (which
have to be triplets) so that for each 1 - j - k:
xng be an instance of 3-PARTITION. Define an instance of DCIG, I = (G; S)
where G is the empty graph on the vertices fv j g n
, and S consists of the following three
types of constraints:
We shall see that I is satisfiable if and only if X is a "yes" instance (see figure 2). Assume for now that
all intervals in X must be open.
Suppose there exists a partition X
Examine the set of intervals
1-j-k;1-i-3 where I a j
I v i
). The intervals in T are disjoint, and their endpoints trivially satisfy S, hence,
T is a realization of I.
a 1 a k
a 0
Fig. 2. The v i 's can be squeezed between the a i 's if and only if a 3-partition exists
Conversely, suppose fI a i
is a realization of I. For each
g. According to the constraints, l(a
the I j 's do not intersect each other, and therefore the sets X j are disjoint. Moreover, every x i is a
member of some X j . Therefore is a partition of X. For each 1 - j - n: Since G is empty
all the I v i
's are disjoint, hence,
We assumed here that all intervals in the realization are open. To form a closed realization, it
suffices to modify the reduction by allowing an interval of length 1 (instead of length 1) for each
'gap' interval [r(a sufficiently small. (If each a
are integers, then
Since 3-partition is strongly NP-complete, and the reduction is pseudo-polynomial, our problem is
strongly NP-complete.
5. Recognizing Measured Interval Graphs is NP-Complete. In this section we prove the
NP-completeness of the problem MIG   , introduced in section 1. The main part in this proof is a
hardness result for the following, slightly more general problem, in which we specify in advance for each
interval whether it should be closed or open:
Recognizing a Measured Interval Graph with Specified Endpoints (MIG):
INSTANCE: A graph non-negative length L(v) for every v 2 V , and a
closedg.
QUESTION: Is there a realization of G, in which the length of I v is exactly L(v), and
I v is open if and only if
We shall denote such an instance by When P is a "yes" instance, we say that P is a
measured interval graph (with endpoint specification). We shall first prove that MIG is NP-complete,
and then reduce MIG to MIG   .
The issue of endpoint specification seems unnatural at first sight. It is well known that for interval
graphs in general the endpoint specification can be arbitrary, namely, a graph is interval if and only if
it has a realization for any possible specification of endpoints. This is not the case in the presence of
length constraints. For example: a K 1;3 graph with length 1 assigned to all vertices has no realization if
all intervals are open (or all closed), but it has a realization precisely if the degree-3 vertex and two of
the others are closed, as in figure 3.
a
c
d
a
c
d
Fig. 3. The K 1;3 graph shown (right) has a realization (left) if all intervals but c are closed.
We shall often use the following implicit formulation for the problem, by representing G and OE using
intervals, and using L to modify their
MIG: Implicit formulation:
INSTANCE: A pair (T; L) where x2V is a set of intervals, and
is a length function.
QUESTION: Is there a set of intervals only
if I x " I y closed if and only if I x is closed.
This formulation is sometimes more convenient as it suggests a possible realization. We need the
following notations and definitions:
Definition 5.1.
OE) be a measured interval graph with endpoints specification, and let U ' V be a set
of its vertices. Define the measured interval graph PU induced by P on U , to be (GU
GU is the subgraph of G induced on U , and LU , OE U are the restrictions of L and OE, respectively, to U .
Call two MIG instances there is a graph isomorphism
f between G and G 0 , and for each namely, the
length and closure properties of intervals are preserved by f . In this case denote P
Definition 5.2.
OE) be an instance of MIG. Let be a realization of P . Define
realization of Pg.
5.1. Basic Structures. We now describe three "gadgets" which are building blocks in our NP-completeness
construction, and prove some of their properties. The structure of these gadgets assures
us that their realization has very few degrees of freedom. To formalize this we introduce the following
notion:
Definition 5.3. Two realizations of the same interval graph are isometric if they are identical up
to reversal and an additive shift. Namely, there exists a function
j for all j. Let OE) be an instance of MIG. We call U ' V (G) rigid
in P if in any two realizations of P , the sets of intervals realizing U are isometric. In particular, all
endpoints are located at fixed distances from the leftmost endpoint, including the rightmost one. Thus in
every realization U has the same length. If V (G) is rigid in P , we call P rigid.
Note that the fact that U is rigid in P does not imply that PU is rigid. For example, the instance P
defined implicitly by the intervals in figure 3 is rigid, and in particular fb; c; dg is rigid in P , but P fb;c;dg
is not rigid.
5.1.1. The Switch. We first define the switch, a gadget which will be used as a toggle in larger
structures. For the parameter real value a - 1, define the MIG instance
(compare figure 4): G is the graph on the five vertices
assigns lengths 0; 1
respectively, and OE(v) specifies v 3 to be open, and all the
other vertices to be closed.
A realization fI of a Switch(a) will be called straight if I 1 is to the left of I 5 . Otherwise,
it will be called reversed. We say that such a realization is located at I 3 . For a straight realization U
of a Switch(a) located at by \GammaU the reverse realization located at
Hence, \GammaU is a "mirror image" of U , covering the same interval [x; x along the real line.
Lemma 5.4. Switch(a) is rigid. In particular,
Proof. Let S be a straight realization, as in the top left of figure 4. Suppose S 0 is another realization,
such that both leftmost endpoints, I 1 and I 0
are identical. The intersection graph of a Switch(a) is prime,
Fig. 4. The Switch (bottom), a straight realization (top left) and a reversed realization(top right).
hence, I 3 is between I 1 and I 5 , and l(I 5
therefore all inequalities hold as equalities. In particular,
a.
Note that lemma 5.4 implies that a realization of a straight Switch(a) located at (x; x+1) is unique.
The same is true for a reversed Switch.
Lemma 5.5.
OE) be an instance of MIG, and let be a realization for it. Let
be a module such that PU
Proof. Let
vertices numbered in the same order as in the definition of a Switch.
According to lemma 5.4, I(v 1 ) and I(v 5 ) are one unit apart, but both of them intersect I(x) and I(y).
Therefore I(x)"I(y) contains the unit length interval between I(v 1 ) and I(v 5 ), yielding jI(x)"I(y)j - 1.
5.1.2. The Fetters. Our second gadget binds two Switches and imposes a prescribed distance
between them. For positive real parameters, d; r and two sets of vertices, U 1 and U 2 , define a
five-parameter instance of MIG, F etters(d; r or in short, F etters = (G; L; OE), as follows:
are modules in G, and each of them induces a Switch. More precisely, there exist
constants a 1 ; a 2 such that F etters U1
ffl The graph ~
E), constructed from G by contracting U respectively,
is as follows (compare figure 5):
long
long
long
long
long
long
(v long
long
long
long
(v short
long
2.
long
long
endFig. 5. The F etters (bottom) and a realization of it (top). The distance between the Switches v 1 and v 2 is fixed.
ffl The lengths for the remaining intervals are:
2.
long
2.
2.
ffl OE specifies v tot to be open, and all the other intervals outside U to be closed.
When there is no confusion, we shall use the vertex and the corresponding interval in the realization
interchangeably. For example, l(v short
i ) is the position of the left endpoint of the interval corresponding
to v short
i in the realization, jv short
its length, etc.
Call a realization of F etters straight if v 1 is to the left of v 2 . Otherwise call the realization reversed.
A realization of F etters is said to be located at the interval corresponding to v tot . The F etters instance
fixes the distance between its two Switches. To formalize this notion we need the following definition:
OE) be a MIG instance. Let M;M 0 ' V (G) be modules in G where
For a realization of P , in which I and I 0 are the intervals
corresponding to the middle vertices in M and M 0 , respectively, define Dist(M;
Lemma 5.7. ~
is rigid in the F etters. In particular, in every realization of the F etters,
Proof. Recall that ~
G is the graph constructed from G by contracting U 1 and U 2 into v 1 and v 2 ,
respectively. It is easy to see that ~
G is prime. Prime interval graphs have an interval order which
is unique, up to complete reversal [34]. Hence, let us refer to the order in figure 5, where w.l.o.g.
tot is between v end
1 and v end
according to the length constraints: l(v end
long
By lemma 5.5, r(v long
long
long
yielding l(v end
long
In a similar way we prove v short
long
and the result follows.
By lemma 5.7, for a realization of the F etters(d; r which is straight (or reversed) and
located at 1), the only degrees of freedom are reversals of the Switches.
5.1.3. The Frame. We now construct an element which divides an interval into sub-intervals of
prescribed lengths. Each sub-interval is characterized by a distinct set of intervals which contain it.
This element will be used as a frame, into which the moving and toggling elements will fit, and have the
desired degrees of freedom.
be a sequence of real positive numbers, whose sum is s.
to be an instance
consists of 3r+3 vertices, where V
and g.
ffl The edges in G are:
k such that j is odd and ji \Gamma jj - 1.
are odd and ji \Gamma jj - 2.
ffl The lengths are:
ffl OE specifies ff i to be open if i is odd, and fl 4 to be open, but all other intervals to be closed.
A realization of a F rame is said to be straight if fl 1 is to the left of fl 3 . Otherwise it is called reversed.
Such a realization is located at the interval corresponding to fl 4 .
adjacent to all ff; fi
Fig. 6. A graph of a F rame (top) and its realization (bottom). The F rame structure is rigid and divides an interval
into smaller intervals of prescribed lengths and positions.
is rigid in a F rame.
Proof. Let G 0 be the subgraph of G induced on V ff [ V fi . It is easy to see that G 0 is prime, and
hence, has a unique clique order [34]. Moreover, G 0 has exactly k maximal cliques, each one containing
(among other vertices) a unique and distinct ff i . The set of maximal cliques in G is fN [ff i
namely,
each clique is distinguished by a single ff i . Since G 0 is UCO, its unique clique order determines a unique
linear order on V ff , and hence, also on the maximal cliques of G. Hence, G is UCO.
Let S and S 0 be two realizations of the same F rame. Suppose
are their leftmost endpoints,
respectively. The F rame graph is UCO, hence, the order of the ff-intervals is identical in both S and S 0 .
Moreover,
all the ff-intervals are disjoint, and must be between
1 and fl 0
3 , which
are at distance exactly s. Thus, the position of all ff endpoints is uniquely determined. It is easy to see
that also all fi-intervals except must have identical position in both realizations.
By lemma 5.8, for any straight (or reversed) realization of a F rame(x located at (x; x+ s),
the positions of all intervals except are uniquely determined.
In the sequel, when we use a realization of such a F rame to implicitly define a MIG instance, we
shall assume that fi 1 and fi k are contained in [x; x+s], so the realization has the shortest possible length.
In addition, when we use any gadget in the implicit definition, and we describe its intervals by saying
that "the gadget is located at we mean that "a straight realization of the gadget is located at
5.2. The Reduction. The realization of a MIG instance is a polynomial witness for a "yes"
instance, hence, MIG is in NP. We describe a reduction from 3-Coloring, which is NP-complete (see,
e.g., [15]). Let E) be an instance of 3-Coloring. We construct an instance P= (T; L) of MIG
(in implicit form), and prove that P is a "yes" instance if and only if G is 3-colorable.
The general plan is as follows: We construct measured interval sub-instances for each vertex and for
each edge of G. The sub-instance of a vertex is designed so that it can be realized only in three possible
ways, which will correspond to its color. The sub-instance for each edge will prevent the vertices at its
endpoints from having the same color.
5.2.1. The Vertex Sub-instance. Let 1. Define the
following set of intervals (compare figures 7 and 8):
1), located at (0; 11).
, and each of ffi 1 and ffi 2 is a Switch(3), located at (1; 2) and (7; 8),
respectively. The superscripts match the vertex numbers in each Switch.
long
long
2 g, such that i [
located at (\Gamma2M; 2M ).
Note that the intersection graph of ! [ i is prime.
For each interval I 2 S let jIj. The sub-instance of each vertex is isomorphic to (S; L), and
the F rames of the n vertices are layed out contiguously as follows: For an interval J and a real number
1g. For each
Denote
be the measured interval graph defined implicitly
by S.
\Gamma2M 2M
A frame
Fig. 7. This is the set of intervals S. ffi can be positioned in the frame. The distance between ffi 1 and ffi 2 is enforced
by the i.
Fig. 8. This is a sketch of the structure of a vertex. The Switches ffi can be positioned in the frame !. The distance
between enforced by the i.
A realization of a vertex sub-instance is called straight (respectively, reversed) if the realization of
its ! is straight (respectively, reversed).
Lemma 5.9. Let [ i2V S(i) 0 be a realization of P V
, with . Then either every
S(i) 0 is straight, or every S(i) 0 is reversed.
Proof. It suffices to prove that l(fl 1 (i)
follows from the identity of the zero-length intersecting intervals and the disjointness
of are both, by lemma 5.8, at distance 11 from the former pair, respectively.
be a straight realization of P V
. Define the function
(2)
Call Col the coloring defined by S 0
. We now show that each vertex subgraph can be realized in exactly
three distinct colors. This is also demonstrated in figure 9.
Lemma 5.10.
For each
Color 0:
Color 1:
Color 2:
Fig. 9. The three possible positions of in a vertex sub-instance, which will correspond to the three possible colors
of the vertex.
Proof. According to lemma 5.8, in each straight S(i) 0 , the positions of the intervals in ff(i) 0 relative
to l(fl 1 (i) 0 ), are fixed. Assume w.l.o.g. For each J 2 for each
But according to lemma 5.7:
Therefore,
and
5.2.2. The Edge Sub-instance. Let the edges of G be
an edge in E, where j. For each edge e k we construct an edge sub-instance, that forces the colors of
the vertices i and j to be different.
moving
frame
fixed
frame
Y
Z
Fig. 10. This is a functional sketch of the edge sub-instance. The two Switches D can only reverse in their relative
fixed positions inside the moving frame. Their distances from the corresponding Switches in the vertices respectively,
are fixed. The moving frame itself can have different positions along the fixed frame.
We first give an overview of this construction (compare Figure 10): Each edge is assigned a fixed
rame w which contains two Switches, D 1 and D 2 , which are the heart of its sub-instance. The F rames
of the edges are layed out contiguously to the right of the vertex F rames. The sub-instance is a collection
of intervals fA designed so that:
1. D 1 and are kept at a fixed distance (this is done by the Y intervals).
2. D 2 and are kept at a fixed distance (this is done by Z).
3. D 1 and D 2 are restricted to be in one of four possible relative positions, allowing the four possible
color differences between the vertices i and j (this is done by W ).
4. D 1 and D 2 together can undergo a translation, allowing the six possible color combinations of
the vertices i and j, as demonstrated in figure 12 (this is done by A 0 and w).
We now describe the construction in detail (compare Figure 11): Define the following set
of intervals. Let 11n. For readability, we
omit the parameter k whenever possible.
is a F rame(5; 12; 1), located at (0;
1), located at (7; 16) Base(k).
located at (8;
is a Switch(4) located at (11; 12) Base(k).
long
long
2 g, such that Y [ is the
located at
long
long
2 g, such that Z [ is the
located at
The length function on the sub-instance (X; L) is defined so that
the Y -s in which we set:
L(Y short
long
long
This change, together with the +1 in the first parameter of the F etters of Y , forces a +1 shift on the
location of ffi 1 (i). This shift will be crucial in forcing the vertices i and j to have different colors.
Note that the intersection graph of X(k) \Gamma D(k) is prime. Note also that the left and right ends
of the F etters sub-instances Y and Z are positioned way beyond the contiguous F rames, in all edge
sub-instances and vertex sub-instances. This allows every F etters to move independently, and no vertex
or edge subgraph is a module.
J 0 be a set of intervals with the same intersection graph
as of X, which satisfy the corrected length constraints, where X(i)
straight (respectively, reversed) realization if the frame w(i) 0 is straight (respectively, reversed). A proof
similar to that of lemma 5.9 implies:
Lemma 5.11. For each 1 only if X(j) 0 is straight.
The complete constructed instance is P= (S[ X;L), where the interval lengths L are implicit in
each of the two types of subgraphs, and the only exception is the corrected length in the Y (k)-s. Due
to this exception simple super-imposition of Sand X does not give a realization.
Lemma 5.12. If S 0
is a realization of P for which S 0
is straight, then X 0
is straight.
Proof. Recall that c 1 (1) and fl 3 (n) are the leftmost and the rightmost zero length intervals in the
leftmost edge sub-instance, and the rightmost vertex sub-instance, respectively. Suppose, to the contrary,
that X 0
is not straight. The zero-length intersecting intervals c 1 (1) 0 and fl 3 (n) 0 must be identical. W.l.o.g.
these two intervals intersect,
in contrary to our constructed interval graph.
d
Z
Z
Z
Z
tot
Z
long 2
Z
Z
long 1
Z
Z
\Gamma6k
\Gammad
Y
Y
Y
tot
Y
longY
Y
longY
shortY
\Gamma6k
\GammaD1
Base(k
Y
Fig.
1.
The
whole
edgeFig. 11. The edge sub-instance: A moving frame can be positioned inside the fixed frame. The Switches D 1 and D 2
are positioned inside the moving frame. Each of D 1 and D 2 is connected to its vertex sub-instance via F etters.
Lemma 5.13.
then for every realization S 0
of P: Col(i) 6= Col(j).
Proof. Assume w.l.o.g that the realization is straight, and that l(c 1 Base(k). Again, we omit
the parameter k whenever possible. Surely
The first inequality follows since C 0
1 and A 0
must intersect, the second inequality follows since A 0
0 and a 0should intersect, and the last equality follows since w 0 is rigid (lemma 5.8). Since Length(W
we conclude that W straight.
According to lemma 5.8 the relative positions of all the intervals in the F rame (except B 0
are fixed relative to l(C 0
The realization for each of D 1 and D 2 can be either straight or reversed,
giving rise to four possible combinations of positions (Any of these combinations fixes the positions of
with respect to l(C 0
1 )). In particular:
Due to lemma 5.7, and the realization being straight:
Therefore:
Corollary 5.14.
If P is a "yes" instance, then G is 3-colorable.
Proof. If P is a measured interval graph, then it has a straight realization (since the realization can
reversed completely). Define the coloring as described in (2). By lemma 5.13, Col
is a proper 3-Coloring of G.
Let us now prove the converse:
Lemma 5.15.
If G is 3-colorable, then P admits a realization.
Proof. Let be a proper 3-coloring of G. We build a realization S 0
for the
instance P as follows:
1. For the vertex position its Switches
2 as follows (compare figure 9):
ffl If
ffl If
ffl If
The rest of the intervals in the vertex subgraph are positioned accordingly (cf. lemma 5.10).
2. For the edge e the directions of the Switches D 1 (k) 0 and
in the realization are determined by y, thus fixing the distance between D 3
. The absolute position of these Switches is determined according to Col(i) and Col(j),
as follows (compare figure 12):
and S[ X have the same intersection graph, all interval lengths match the prescribed
lengths, and their endpoints meet the specification.
From lemma 5.15 and corollary 5.14 we can finally conclude:
Theorem 5.16. MIG is NP-complete.
In fact, the same reduction implies strong NP-completeness, as 3-Coloring is strongly NP-complete
and the reduction is also pseudo-polynomial.
5.3. Closing the Open Intervals. We have proved that recognizing a measured interval graph
with specified endpoints is NP-complete. We now show that this problem is hard even where all the
intervals are closed. Given an instance MIG, define a new instance P
MIG   (in which all intervals are closed), as follows: Let
L(v) if v is closed
Let P be an instance generated by the reduction in section 5.2. We shall prove that P has a realization
if and only if P 0
has one.
First, we observe that the construction introduced in the proof of theorem 5.16 has a special property:
Let S be a realization in which the shortest non-zero length of an interval is C. S is called discrete if all
the endpoints of its intervals are integer multiples of C. In that case, C is called the grid size of S.
Remark 5.17.
Fig. 12. The relative position of D 3and D 3forces the colors of the vertices to be different.
By the proofs of lemma 5.15 and corollary 5.14, P has a realization if and only if it has a discrete
realization, with grid size 1
.
Lemma 5.18.
If P has a realization, then P 0
has one.
Proof. If P has a realization, then by remark 5.17, it has a discrete realization fI v g v2V (G) with grid
size 1
. Construct the set of closed intervals fI 0
defined as follows: If I v is closed, let I 0
I v is open, let I 0
We lemma that this set is a realization of P 0
is discrete, the intervals I v and I u intersect
if and only if I 0
v and I 0
u intersect, since if one (or both) of I v ; I u is open, then their overlap is at least 1
.
Furthermore, clearly jI 0
Unfortunately, the converse of lemma 5.18 does not always hold for arbitrary MIG instances, as
demonstrated in figure 13. We shall prove that the converse does hold for instances generated by the
reduction in section 5.2.
Fig. 13. In the MIG instance P on the left, the the numbers denote lengths, and the four intervals corresponding to
the vertices marked 00 should be open. P has no realization, but P 0 has one, as shown on the right.
Define the following order-oriented analog of MIG and MIG   , respectively:
Recognizing a Measured Interval Order with Specified Endpoints (MIO):
INSTANCE: A partial order OE on a set V , a non-negative length L(v) for every
and a function closedg.
QUESTION: Is there an interval realization of (V; OE), in which the length of I v is
exactly L(v), and I v is open if and only if
MIO   is the restriction of MIO to instances with all intervals closed. MIO   can be solved in
polynomial time [19, 24, 32], and that solution can be generalized to deal with open intervals and solve
MIO as well.
We need to generalize the notion of rigidness in the following manner:
Definition 5.19. For a real p - 0, two realizations fI j g and fI 0
j g of the same interval graph are
p-isometric if there exists a function
that
j for all j. We call U ' V (G) p-rigid in a MIO instance if in any two realizations
of the instance, the sets of intervals realizing U are p-isometric. Note that in this case all endpoints of
U are located at fixed distances from the leftmost endpoint, up to \Sigmap. Hence, every realization has the
same length, up to \Sigmap.
For an instance Q of MIO, define the following system of inequalities S(Q), on the variables fl v
ffl If xOEy, and both x; y are closed: l x
ffl If xOEy, and at least one of x; y is open: l x
o, and both x; y are closed: l x
o, and at least one of x; y is open: l x
Q has a realization if and only if S(Q) has a feasible solution, since the left endpoints of the
realization satisfy S(Q), and vice versa. Recall that D(S(Q)) is the distance graph of S(Q), as in the
proof of lemma 3.2, and denote it D(Q), for short.
Lemma 5.20. Let Q be an instance of MIO. If U is a strongly connected component in the union
of all zero-weight cycles in D(Q), then U is rigid in Q.
Proof. For vertices there is a zero-weight cycle c in D(Q) passing through both x and y.
Let d (resp. \Gammad) be the weight of the path from x to y (resp. y to x) along c. Summing the inequalities
in S(Q) along the two paths we get l y - l x respectively, implying l y \Gamma l
every realization must satisfy S(Q), for every realization l y \Gamma l so U is rigid.
The converse holds as well:
Lemma 5.21. Let Q be a realizable instance of MIO, with U rigid in Q. Then for each x; y 2 U
there is a zero-weight cycle in D(Q) containing both x and y.
Proof. Suppose to the contrary x; y 2 U and there is no zero-weight cycle in D(Q) containing both
x and y. Either there is a cycle in D(Q) through x and y, or there is no such cycle.
If there is no cycle in D(Q) through x and y, then w.l.o.g. there is no path in D(Q) from x to y.
fxg be the set of all vertices in V to which there is a path from y in D(Q) (including y
itself). Then Q does not contain any inequalities v
Let fI v g v2V be a realization for Q. Then fI realizes Q, with a different
distance between the intervals corresponding to x and to y, contradicting the rigidness of U in Q.
If there exists a cycle in D(Q) through x and y, then let c be such a cycle of minimum weight,
and let l = w(c). By assumption l 6= 0, and since Q has a realization, by corollary 3.3 l ? 0. Let d
be the weight of the path from x to y along c. For every \Delta, d d, consider a new directed
graph D 0 (\Delta) obtained from D(Q) by adding two arcs xy and yx, both labeled -, with weights \Delta and
\Gamma\Delta, respectively. Observe that adding the two arcs does not introduce any cycles of negative-weight
or zero-weight cycles with strict arcs, into the graph. Hence, the augmented system corresponding to
0 (\Delta) has a realization. Moreover, in every realization of D 0 (\Delta), the distance between the left endpoints
of x and y is \Delta. By choosing different values of \Delta, we contradict the rigidness of U .
We can now generalize lemma 5.20:
Lemma 5.22. Let Q be a realizable instance of MIO. For a non-negative p, let C be a union of
cycles in D(Q), each of weight less than p. If U is a strongly connected component in C then U is
jU jp-rigid in Q.
Proof. For vertices by the definition of U , there is a simple path
in C. Every edge x i x i+1 is in C, therefore there exists a path P i in C from x i+1 to x i s.t. x i x i+1 and
a cycle in C. The concatenation of P path P from y to x in C. Moreover,
the concatenation of P 0 and P is a cycle c in C (not necessarily simple) of weight at most (k \Gamma 1)p. Let
we have established that w(c) = w(P
d. Summing the inequalities in S(Q)
along the two paths P 0 and P we get l y - l x realization
of Q satisfies S(Q), so \Gammad - l x any two realizations are q-isometric.
Lemma 5.23. Let OE) be a MIO instance, and let Q be the corresponding
MIO   instance (obtained by the transformation in (18)). Suppose U ' V (OE) is rigid in Q, and let
then U is 2n 2 ffl-rigid in Q 0 .
Proof. The weight of each arc in D(Q 0 ) changes by no more than 2ffl, compared to D(Q). Hence,
the weight of every simple cycle changes by at most 2nffl. U is rigid in Q, hence, by lemma 5.21 it is
contained in a strongly connected component W of a union of zero-weight cycles in D(Q). W is also
a union of simple zero-weight cycles in D(Q). The weight of each such cycle in D(Q 0 ) is at most 2nffl.
Hence, by lemma 5.22, W is 2jW jnffl-rigid in Q 0 , and so is U .
We now return to the instance P generated by the reduction in the proof of theorem 5.16. Recall
that P 0
is the instance obtained from P by the transformation (18). Suppose P 0
has a realization. Let
OE be the corresponding interval order, and let
Consider each of our
gadgets: By lemma 5.4, every Switch is rigid in Q . A slight modification of lemma 5.7 shows that every
F etters must be rigid in Q (since the directions of the Switches are set). By lemma 5.8 every F rame
is rigid in Q, with the exception of its end fi-intervals. Hence, each of these gadgets is 2n 2 ffl-rigid in
, by lemma 5.23. This imposes, up to small additive shifts, the relative positions of the intervals in
each vertex (or edge) sub-instance. Define the function Col as in (2). We shall show that the choice of
ffl makes these shifts sufficiently small so that the properties of the coloring are preserved.
Lemma 5.24. For each exist C i , jC
Proof. The proof is analogous to lemma 5.10: The relations (3)-(7) hold up to \Sigma2n 2 ffl. Hence, (8)
holds up to \Sigma4n 2 ffl.
Lemma 5.25. For every edge (i; j),
Proof. The proof is analogous to lemma 5.13: The relations hold up to \Sigma2n 2 ffl. Relations
hold up to \Sigma8n 2 ffl, as they involve up to four differences of endpoint distances.
Let round(x) be the integer closest to x. Recall that ffl ! 1
0:2. By lemma 5.25, for every edge (i; j): jCol(i)\GammaCol(j)j - 0:6. Hence, round(Col(i)) 6= round(Col(j)).
This proves that if there exist a realization to P 0
, by rounding the colors to the nearest integer we obtain
a proper 3-coloring. By lemma 5.15 this implies the existence of a realization to P. Thus, P has
a realization if and only if P 0
has one. Since the transformation described in (18) is polynomial, we
conclude:
Theorem 5.26. MIG   is NP-complete.
5.4. Related Problems. In section 1 we have introduced the recognition problem of interval
graph with individual lower and upper bounds on interval lengths (the BIG problem). Since MIG   is
a restriction of BIG and DCIG:
Corollary 5.27. BIG and DCIG are NP-complete.
When restricted to interval graphs with depth 0 decomposition trees (see [23] for a definition of the
decomposition tree), i.e., to prime interval graphs, the MIG problem can be solved in polynomial time,
using the algorithm devised in section 3 for UCO graphs. This depth bound is indeed tight, namely,
when allowing deeper decomposition trees the problem is NP-complete:
Proposition 5.28.
MIG is NP-complete even when restricted to interval graphs with decomposition tree of depth 1.
Proof. We shall see that besides the Switches ffi i (j) and D i (k), and the K 2 modules fc 3 (k); c 1 (k+1)g,
there are no non-trivial modules in the interval graph constructed
by the reduction in the proof of theorem 5.26: Let H be the graph obtained by contraction of the above
modules. Suppose to the contrary that H contains a non-trivial module M , and suppose v;
v; u are in the same vertex subgraph (or in the same edge subgraph) HU , then M " U is a non-trivial
module in HU , contradicting the primality of the vertex subgraph (and the edge subgraph). Hence,
are in different vertex/edge subgraphs. In this case, there are intervals in these subgraphs, which
intersect only one out of u; v, in contradiction to M being a module.
6.

Acknowledgments

. We thank Phil Green for illuminating conversations on the physical mapping
problems which motivated this work. We also thank Garth Isaak for helpful discussions. We further
thank the referees for their useful remarks.



--R

Network Flows: Theory
Maintaining knowledge about temporal intervals.
Reasoning about plans.
A linear time and space algorithm to recognize interval orders.
On a routing problem.
On the topology of the genetic fine structure.
Testing for the consecutive ones property
Establishing the order of human chromosome-specific DNA fragments
On the detection of structures in attitudes and developmental processes.
Linear time representation algorithms for proper circular arc graphs and proper interval graphs.
Interval Orders and Interval Graphs.
Classes of interval graphs under expanding length restrictions.
Faster scaling algorithms for network problems.
Khachiyan's algorithm for linear programming.
Computers and Intractability: A Guide to the Theory of NP-Completeness
A characterization of comparability graphs and of interval graphs.
Algorithmic Graph Theory and Perfect Graphs.
Graph sandwich problems.
Complexity and algorithms for reasoning about time: A graph-theoretic approach

Chromosomal region of the Cystic Fibrosis gene in yeast artificial chromosomes: a model for human genome mapping.

Substitution decomposition on chordal graphs and applications.
Discrete interval graphs with bounded representation.
Mapping the genome: some combinatorial problems arising in molecular biology.
Incidence matrices
Transitive orientation of graphs with side constraints.
An incremental linear time algorithm for recognizing interval graphs.
Temporally Distributed Symptoms in Technical Diagnosis.
New scaling algorithms for the assignment and minimum cycle mean problems.
Scheduling interval ordered tasks.
Satisfiability problems on intervals and unit intervals.
Discrete Mathematical Models
Partially ordered sets and their comparability graphs.
Hyperplane arrangements
Computation Structures.
Proof of an interval satisfiability conjecture.
--TR

--CTR
Peter Damaschke, Point placement on the line by distance data, Discrete Applied Mathematics, v.127 n.1, p.53-62, April
size constraints;distance constraints;interval graphs;NP-completeness;graph algorithms;computational biology