On restrictions of balanced 2-interval graphs
On restrictions of balanced 2-interval graphs
On restri
tions of balan
ed 2-interval graphs
Philippe Gambette
LIAFA, UMR CNRS 7089, Université Paris 7, Fran
e
Département Informatique, ENS Ca
han, Fran
e
gambette�liafa.jussieu.fr
Stéphane Vialette
LRI, UMR CNRS 8623, Université Paris-Sud 11, Fran
e
vialette�lri.fr
Abstra
t
The 
lass of 2-interval graphs has been introdu
ed for modelling s
heduling and allo
ation
problems, and more re
ently for spe
i�
 bioinformati
 problems. Some of those appli
ations
imply restri
tions on the 2-interval graphs, and justify the introdu
tion of a hierar
hy of
sub
lasses of 2-interval graphs that generalize line graphs: balan
ed 2-interval graphs, unit
2-interval graphs, and (x,x)-interval graphs. We provide instan
es that show that all the
in
lusions are stri
t. We extend the NP-
ompleteness proof of re
ognizing 2-interval graphs
to the re
ognition of balan
ed 2-interval graphs. Finally we give hints on the 
omplexity
of unit 2-interval graphs re
ognition, by studying relationships with other graph 
lasses:
proper 
ir
ular-ar
, quasi-line graphs, K1,5-free graphs, . . .
Keywords: 2-interval graphs, graph 
lasses, line graphs, quasi-line graphs, 
law-free
graphs, 
ir
ular interval graphs, proper 
ir
ular-ar
 graphs, bioinformati
s, s
heduling.
1 2-interval graphs and restri
tions
The interval number of a graph, and the 
lasses of k-interval graphs have been introdu
ed as a
generalization of the 
lass of interval graphs by M
Guigan [M
G77℄ in the 
ontext of s
heduling
and allo
ation problems. Re
ently, bioinformati
s problems have renewed interest in the 
lass
of 2-interval graphs (ea
h vertex is asso
iated to a pair of disjoint intervals and edges denote
interse
tion between two su
h pairs). Indeed, a pair of intervals 
an model two asso
iated
tasks in s
heduling [BYHN
06℄, but also two similar segments of DNA in the 
ontext of DNA

omparison [JMT92℄, or two 
omplementary segments of RNA for RNA se
ondary stru
ture
predi
tion and 
omparison [Via04℄.
(a) (b) (
)
Figure 1: Heli
es in a RNA se
ondary stru
ture (a) 
an be modeled as a set of balan
ed 2-
intervals among all 2-intervals 
orresponding to 
omplementary and inverted pairs of letter
sequen
es (b), or as an independent subset in the balan
ed asso
iated 2-interval graph (
).
http://arxiv.org/abs/0704.1571v2
RNA (ribonu
lei
 a
id) are polymers of nu
leotides linked in a 
hain through phosphodiester
bonds. Unlike DNA, RNAs are usually single stranded, but many RNAmole
ules have se
ondary
stru
ture in whi
h intramole
ular loops are formed by 
omplementary base pairing. RNA se
-
ondary stru
ture is generally divided into heli
es (
ontiguous base pairs), and various kinds of
loops (unpaired nu
leotides surrounded by heli
es). The stru
tural stability and fun
tion of
non-
oding RNA (n
RNA) genes are largely determined by the formation of stable se
ondary
stru
tures through 
omplementary bases, and hen
e n
RNA genes a
ross di�erent spe
ies are
most similar in the pattern of nu
leotide 
omplementarity rather than in the genomi
 sequen
e.
This motivates the use of 2-intervals for modelling RNA se
ondary stru
tures: ea
h helix of
the stru
ture is modeled by a 2-interval. Moreover, the fa
t that these 2-intervals are usually
required to be disjoint in the stru
ture naturally suggests the use of 2-interval graphs. Fur-
thermore, aiming at better modelling RNA se
ondary stru
tures, it was suggested in [CHLV05℄
to fo
us on balan
ed 2-interval sets (ea
h 2-interval is 
omposed of two equal length intervals)
and their asso
iated interse
tion graphs referred as balan
ed 2-interval graphs. Indeed, heli
es
in RNA se
ondary stru
tures are most of the time 
omposed of equal length 
ontiguous base
pairs parts. To the best of our knowledge, nothing is known on the 
lass of balan
ed 2-interval
graphs.
Sharper restri
tions have also been introdu
ed in s
heduling, where it is possible to 
on-
sider tasks whi
h all have the same duration, that is 2-interval whose intervals have the same
length [BYHN
06, Kar05℄. This motivates the study of the 
lasses of unit 2-interval graphs,
and (x, x)-interval graphs. In this paper, we 
onsider these sub
lasses of interval graphs, and in
parti
ular we address the problem of re
ognizing them.
A graph G = (V,E) of order n is a 2-interval graph if it is the interse
tion graph of a set of
n unions of two disjoint intervals on the real line, that is ea
h vertex 
orresponds to a union of
two disjoint intervals Ik = Ik
∪ Ikr , k ∈ J1, nK (l for � left� and r for �right�), and there is an edge
between Ij and Ik i� Ij ∩ Ik 6= ∅. Note that for the sake of simpli
ity we use the same letter to
denote a vertex and its 
orresponding 2-interval. A set of 2-intervals 
orresponding to a graph
G is 
alled a realization of G. The set of all intervals,
k=1{I
, Ikr }, is 
alled the ground set of
G (or the ground set of {I1, . . . , In}).
The 
lass of 2-interval graphs is a generalization of interval graphs, and also 
ontains all

ir
ular-ar
 graphs (interse
tion graphs of ar
s of a 
ir
le), outerplanar graphs (have a planar
embedding with all verti
es around one of the fa
es [KW99℄), 
ubi
 graphs (maximum degree
3 [GW80℄), and line graphs (interse
tion graphs of edges of a graph).
Unfortunately, most 
lassi
al graph 
ombinatorial problems turn out to be NP-
omplete
for 2-interval graphs: re
ognition [WS84℄, maximum independent set [BNR96, Via01℄, 
ol-
oration [Via01℄, . . . Surprisingly enough, the 
omplexity of the maximum 
lique problem for
2-interval graphs is still open (although it has been re
ently proven to be NP-
omplete for
3-interval graphs [BHLR07℄).
For pra
ti
al appli
ation, restri
ted 2-interval graphs are needed. A 2-interval graph is said
to be balan
ed if it has a 2-interval realization in whi
h ea
h 2-interval is 
omposed of two
intervals of the same length [CHLV05℄, unit if it has a 2-interval realization in whi
h all intervals
of the ground set have length 1 [BFV04℄, and is 
alled a (x, x)-interval graph if it has a 2-interval
realization in whi
h all intervals of the ground set are open, have integer endpoints, and length
x [BYHN+06, Kar05℄. In the following se
tions, we will study those restri
tions of 2-interval
graphs, and their position in the hierar
hy of graph 
lasses illustrated in Figure 2.
Note that all (x, x)-interval graphs are unit 2-interval graphs, and that all unit 2-interval
graphs are balan
ed 2-interval graphs. We 
an also noti
e that (1, 1)-interval graphs are exa
tly
line graphs: ea
h interval of length 1 of the ground set 
an be 
onsidered as the vertex of a
root graph and ea
h 2-interval as an edge in the root graph. This implies for example that the
Figure 2: Graph 
lasses related to 2-interval graphs and its restri
tions. A 
lass pointing towards
another stri
tly 
ontains it, and the dashed lines mean that there is no in
lusion relationship be-
tween the two. Dark 
lasses 
orrespond to 
lasses not yet present in the ISGCI Database [BLS

oloration problem is also NP-
omplete for (2, 2)-interval graphs and wider 
lasses of graphs. It
is also known that the 
omplexity of the maximum independent set problem is NP-
omplete on
(2, 2)-interval graphs [BNR96℄. Re
ognition of (1, 2)-union graphs, a related 
lass (restri
tion of
multitra
k interval graphs), was also re
ently proven NP-
omplete [HK06℄.
2 Useful gadgets for 2-interval graphs and restri
tions
For proving hardness of re
ognizing 2-interval graphs, West and Shmoys 
onsidered in [WS84℄
the 
omplete bipartite graph K5,3 as a useful 2-interval gadget. Indeed, all realizations of this
graph are 
ontiguous, that is, for any realization, the union of all intervals in its ground set is an
interval. Thus, by putting edges between some verti
es of a K5,3 and another vertex v, we 
an
for
e one interval of the 2-interval v (or just one extremity of this interval) to be blo
ked inside
the realization of K5,3. It is not di�
ult to see that K5,3 has a balan
ed 2-interval realization,
for example the one in Figure 3.
(a) (b) (
)
Figure 3: The 
omplete bipartite graph K5,3 (a,b) has a balan
ed 2-interval realization (
):
verti
es of S5 are asso
iated to balan
ed 2-intervals of length 7, and verti
es of S3 are asso
iated
to balan
ed 2-intervals of length 11. Any realization of this graph is 
ontiguous, i.e., the union
of all 2-intervals is an interval.
However, K5,3 is not a unit 2-interval graph. Indeed, ea
h 2-interval I = Il∪Ir 
orresponding
to a degree 5 vertex interse
t 5 disjoint 2-intervals, and hen
e one of Il or Ir interse
t at least 3
intervals, whi
h is impossible for unit intervals. Therefore, we introdu
e the new gadget K4,4−e
whi
h is a (2, 2)-interval graph with only 
ontiguous realizations.
(a) (b) (
)
Figure 4: The graph K4,4 − e (a), a ni
er representation (b), and a 2-interval realization with
open intervals of length 2 (
).
Property 1. Any 2-interval realization of K4,4 − e is 
ontiguous.
Proof. Write G = (V,E) the graph K4,4− e. To study all possible realizations of G, let us study
all possible realizations of G[V − I8].
As 2-intervals I1, I2, I3 and I4 are disjoints, their ground set I
= {[li, ri], 1 ≤ i ≤ 8,
ri < li+1} is a set of eight disjoint intervals. The ground set Imobile of I
, I6 and I7 is a set of
six disjoint intervals. Let xi be the number of intervals of Imobile interse
ting i ≤ 8 intervals of
. We have dire
tly:
x0 + x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 = |Imobile| = 6. (1)
As there are 12 edges in G[V \{v8}] whi
h is bipartite, we also have:
x1 + 2x2 + 3x3 + 4x4 + 5x5 + 6x6 + 7x7 + 8x8 ≥ 12. (2)
Finally, to build a realization of G from a realization of G[V \{v8}] , one must pla
e I
so as
to interse
t three disjoint intervals of I
. Thus one of the intervals of I8 interse
ts at least
two intervals ]lk, rk[ and ]ll, rl[ (k < l) of I�xed. So there is �a hole between those two intervals�,
for example [rk, lk+1], whi
h is in
luded in one of the intervals of I
. So we noti
e that I8 has
to �ll one of the seven holes of I
. Thus, the intervals of I
mobile

an not �ll more than six
holes, and the observation that an interval interse
ting i 
onse
utive intervals (for i ≥ 1) �lls
i− 1 holes, we get:
x2 + 2x3 + 3x4 + 4x5 + 5x6 + 6x7 + 7x8 ≤ 6. (3)
Equations 1, 2 and 3 are ne
essary for any valid realization of G[V \{v8}] whi
h gives a valid
realization of G.
Let's suppose by 
ontradi
tion that the union of all intervals of the ground set of G is
not an interval. Then there is a hole, that is an interval in
luded in the 
overing interval of
{I1, . . . , I8}, whi
h interse
t no Ii. We pro
eed like for equation 3, with the 
onstraint that
another hole 
annot be �lled by the intervals of I
mobile
, so we get instead:
x2 + 2x3 + 3x4 + 4x5 + 5x6 + 6x7 + 7x8 ≤ 5. (4)
By adding 1 and 4, and subtra
ting 2, we get x0 ≤ −1 : impossible! So we have proved that
the union of all intervals of the ground set of any realization of G is indeed an interval.
3 Balan
ed 2-interval graphs
We show in this se
tion that the 
lass of balan
ed 2-interval graphs is stri
tly in
luded in the

lass of 2-interval graphs, and stri
tly 
ontains 
ir
ular-ar
 graphs. Moreover, we prove that
re
ognizing balan
ed 2-interval graphs is as hard as re
ognizing (general) 2-interval graphs.
Property 2. The 
lass of balan
ed 2-interval graphs is stri
tly in
luded in the 
lass of 2-interval
graphs.
Proof. We build a 2-interval graph that has no balan
ed 2-interval realization. Let's 
onsider
a 
hain of gadgets K5,3 (introdu
ed in previous se
tion) to whi
h we add three verti
es I
, I2,
and I3 as illustrated in Figure 5.
Figure 5: An example of unbalan
ed 2-interval graph (a) : any realization groups intervals of
the seven K5,3 in a blo
k, and the 
hain of seven blo
ks 
reates six �holes� between them, whi
h
make it impossible to balan
e the lengths of the three 2-intervals I1, I2, and I3.
In any realization, the presen
e of holes showed by 
rosses in the Figure gives the following
inequalities for any realization: l(Il
2) < l(Il
1), l(Il
3) < l(Ir
2), and l(Ir
1) < l(Ir
3) (or if the
realization of the 
hain of K5,3 appears in the symmetri
al order: l(Il
1) < l(Il
3), l(Ir
3) < l(Il
and l(Ir
2) < l(Ir
1)). If this realization was balan
ed, then we would have l(Il
1) = l(Ir
3) = l(Il
3) < l(Ir
2) = l(Il
2) (or for the symmetri
al 
ase: l(Ir
1) = l(Il
1) < l(Il
3) = l(Ir
2) = l(Ir
2)) : impossible! So this graph has no balan
ed 2-interval realization although it
has a 2-interval generalization.
Theorem 1. Re
ognizing balan
ed 2-interval graphs is an NP-
omplete problem.
Proof. We just adapt the proof of West and Shmoys [WS84, GW95℄. The problem of determining
if there is a Hamiltonian 
y
le in a 3-regular triangle-free graph is proven NP-
omplete, by
redu
tion from the more general problem without the no triangle restri
tion. So we redu
e the
problem of Hamiltonian 
y
le in a 3-regular triangle-free graph to balan
ed 2-interval re
ognition.
Let G = (V,E) be a 3-regular triangle-free graph. We build a graph G′ whi
h has a 2-
interval realization (a spe
ial one, very spe
i�
, 
alled H-representation and whi
h we prove to
be balan
ed) i� G has a Hamiltonian 
y
le.
The 
onstru
tion of G′, illustrated in Figure 6(a) is almost identi
al to the one by West
and Shmoys, so we just prove that G′ has a balan
ed realization, shown in Figure 6 (b), by

omputing lengths for ea
h interval to ensure it. All K5,3 have a balan
ed realization as shown
Figure 6: There is a balan
ed 2-interval of G′ (whi
h has been dilated in the drawing to remain
readable) i� there is an H-representation (that is a realization where the left intervals of all
2-intervals are grouped together in a 
ontiguous blo
k) for its indu
ed subgraph G i� there is a
Hamiltonian 
y
le in G.
in se
tion 1 of total length 79, in parti
ular H3. We 
an thus a�e
t length 83 to the intervals of
v0. The intervals of the other vi 
an have length 3, and their M(vi) length 79, so through the

omputation illustrated in Figure 6, intervals of z 
an have length 80 + 82 + 2(n − 1) + 3, that
is 163 + 2n. We dilate H1 until a hole between two 
onse
utive intervals of its S3 
an 
ontain
an interval of z, that is until the hole has length 165 + 2n : so after this dilating, H1 has length
79(165 + 2n). Finally if G has a Hamiltonian 
y
le, then we have found a balan
ed 2-interval
realization of G of total length 13, 273 + 241n.
It is known that 
ir
ular-ar
 graphs are 2-interval graphs, they are also balan
ed 2-interval.
Property 3. The 
lass of 
ir
ular-ar
 graphs is stri
tly in
luded in the 
lass of balan
ed 2-
interval graphs.
Proof. The transformation is simple: if we have a 
ir
ular-ar
 representation of a graph G =
(V,E), then we 
hoose some point P of the 
ir
le. We partition V in V1∪V2, where P interse
ts
all the ar
s 
orresponding to verti
es of V1 and none of the ar
s of the verti
es of V2. Then
we 
ut the 
ir
le at point P to map it to a line segment: every ar
 of V2 be
omes an interval,
and every ar
 of V1 be
omes a 2-interval. To obtain a balan
ed realization we just 
ut in half
the intervals of V2 to obtain two intervals of equal length for ea
h. And for ea
h 2-interval
[g(Il), d(Il)] ∪ [g(Ir), d(Ir)] of V1, as both intervals are lo
ated on one of the extremities of the
realization, we 
an in
rease the length of the shortest so that it rea
hes the length of the longest
without 
hanging interse
tions with the other intervals. The in
lusion is stri
t be
ause K2,3 is a
balan
ed 2-interval graph (as a subgraph of K5,3 for example) but is not a 
ir
ular-ar
 graph (we

an �nd two C4 in K2,3, and only one 
an be realized with a 
ir
ular-ar
 representation).
4 Unit 2-interval and (x,x)-interval graphs
Property 4. Let x ∈ N, x ≥ 2. The 
lass of (x, x)-interval graphs is stri
tly in
luded in the

lass of (x+ 1, x+ 1)-interval graphs.
Proof. We �rst prove that an interval graph with a representation where all intervals have length
k (and integer open bounds) has a representation where all intervals have length k + 1.
We use the following algorithm. Let S be initialized as the set of all intervals of length k,
and let T be initially the empty set. As long as S is not empty, let I = [a, b] be the left-most
interval of S, remove from S ea
h interval [α, β] su
h that α < b (in
luding I), add [α, β + 1]
to T , and translate by +1 all the remaining intervals in S. When S is empty, the interse
tion
graph of T , where all intervals have length k + 1 is the same as the interse
tion graph for the
original S.
We also build for ea
h x ≥ 2 a (x + 1, x + 1)-interval graph whi
h is not a (x, x)-interval
graph. We 
onsider the bipartite graph K2x and a perfe
t mat
hing {(vi, v
i), i ∈ J1, xK}. We 
all
K ′x the graph obtained from K2x with the following transformations, illustrated in Figure 7(a):
remove edges (vi, v
i) of the perfe
t mat
hing, add four graphs K4,4−e 
alled X1, X2, X3, X4 (for
ea
h Xi, we 
all v
and vir the verti
es of degree 3), link v
r and v
, link all vi to v
r and v
, link
all v′i to v
and v3r , and �nally add a vertex a (resp. b) linked to all vi, v
i, and to two adja
ent
verti
es of X1 (resp. X4) of degree 4. We illustrate in Figure 7(b) that K
x has a realization
with intervals of length x+ 1. We 
an prove by indu
tion on x that K ′x has no realization with
intervals of length x: it is rather te
hni
al, so we just give the idea. Any realization of K ′x for
es
the blo
k X2 to share an extremity with the blo
k X3, so ea
h 2-interval v
i has one interval
interse
ting the other extremity of X2, and the other interse
ting the other extremity of X3.
Then 
onstraints on the position of verti
es vi for
e their intervals to appear as two �stairways�
as shown in Figure 7(b). So v1r must 
ontain x extremities of intervals whi
h have to be di�erent,
so it must have length x+ 1.
Figure 7: The graph K ′4 (a) is (5,5)-interval but not (4,4)-interval.
The 
omplexity of re
ognizing unit 2-interval graphs and (x, x)-interval graphs remains open,
however the following shows a relationship between those 
omplexities.
Lemma 1. {unit 2-interval graphs} =
{(x, x)-interval graphs}.
Proof. The ⊃ part is trivial. To prove ⊂, let G = (V,E) be a unit 2-interval graph. Then it has
a realization with |V | = n 2-intervals, that is 2n intervals of the ground set. So we 
onsider the
interval graph of the ground set, whi
h is a unit interval graph. There is a linear time algorithm
based on breadth-�rst sear
h to 
ompute a realization of su
h a graph where interval endpoints
are rational, with denominator 2n [CKN+95℄. So by dilating by a fa
tor 2n su
h a realization,
we obtain a realization of G where intervals of the ground set have length 2n.
Theorem 2. If re
ognizing (x, x)-interval graphs is polynomial for any integer x then re
ognizing
unit 2-interval graphs is polynomial.
5 Investigating the 
omplexity of unit 2-interval graphs
In this se
tion we show that all proper 
ir
ular-ar
 graphs (
ir
ular-ar
 graphs su
h that no ar
is in
luded in another in the representation) are unit 2-interval graphs, and we study a 
lass of
graphs whi
h generalizes quasi-line graphs and 
ontains unit 2-interval graphs.
Re
all that, a

ording to Property 3, 
ir
ular-ar
 graphs are balan
ed 2-interval graphs.
However, 
ir
ular-ar
 graphs are not ne
essarily unit 2-interval graphs.
Property 5. The 
lass of proper 
ir
ular-ar
 graphs is stri
tly in
luded in the 
lass of unit
2-interval graphs.
Proof. As in the proof of Property 3, we 
hoose a point P on the 
ir
le of the representation of
a proper 
ir
ular-ar
 graph G, and maps the 
ut 
ir
le into a line segment. We extend the outer
extremities of intervals that have been 
ut so that no interval 
ontains another. Thus we obtain
a set of 2-intervals for ar
s 
ontaining P , and a set I of intervals for ar
s not 
ontaining P . For
ea
h interval of I, we add a new interval disjoint of any other to get a 2-interval. If we 
onsider
the interse
tion graph of the ground set of su
h a representation, it is a proper interval graph.
So it is also a unit interval graph [Rob69℄, whi
h provides a unit 2-interval representation of G.
To 
omplete the proof, we noti
e that the domino (two 
y
les C4 having an edge in 
ommon)
is a unit 2-interval graph but not a 
ir
ular-ar
 graph.
Quasi-line graphs are those graphs whose verti
es are bisimpli
ial, i.e., the 
losed neighbor-
hood of ea
h vertex is the union of two 
liques. This graph 
lass has been introdu
ed as a gener-
alization of line graphs and a useful sub
lass of 
law-free graphs [Ben81, FFR97, CS05, KR07℄.
Following the example of quasi-line graphs that generalize line graphs, we introdu
e here a new

lass of graphs for generalizing unit 2-interval graphs. Let k ∈ N∗. A graph G = (V,E) is
all-k-simpli
ial if the neighborhood of ea
h vertex v ∈ V 
an be partitioned into at most k

liques. The 
lass of quasi-line graphs is thus exa
tly the 
lass of all-2-simpli
ial graphs. Noti
e
that this de�nition is equivalent to the following: in the 
omplement graph of G, for ea
h vertex
u, the verti
es that are not in the neighborhood of u are k-
olorable.
Property 6. The 
lass of unit 2-interval graphs is stri
tly in
luded in the 
lass of all-4-simpli
ial
graphs.
Proof. The in
lusion is trivial. What is left is to show that the in
lusion is stri
t. Consider the
following graph whi
h is all-4-simpli
ial but not unit 2-interval: start with the 
y
le C4, 
all
its verti
es vi, i ∈ J1, 4K, add four K4,4 − e gadgets 
alled Xi, and for ea
h i we 
onne
t the
vertex vi to two 
onne
ted verti
es of degree 4 in Xi. This graph is 
ertainly all-4-simpli
ial.
But if we try to build a 2-interval realization of this graph, then ea
h of the 2-intervals vk has
an interval trapped into the blo
k Xk. So ea
h 2-interval vk has only one interval to realize
the interse
tions with the other vi: this is impossible as we have to realize a C4 whi
h has no
interval representation.
Property 7. The 
lass of 
law-free graphs is not in
luded in the 
lass of all-4-simpli
ial graphs.
Proof. The Kneser Graph KG(7, 2) is triangle-free, but not 4-
olorable [Lov78℄. We 
onsider
the graph obtained by adding an isolated vertex v and then taking the 
omplement graph,
i.e., KG(7, 2) ⊎ {v}. It is 
law-free as KG(7, 2) is triangle-free. And if it was all-4-simpli
ial,
then the neighborhood of v in KG(7, 2) ⊎ {v}, that is KG(7, 2), would be a union of at most
four 
liques, so KG(7, 2) would be 4-
olorable: impossible so this graph is 
law-free but not
all-4-simpli
ial.
Property 8. The 
lass of all-k-simpli
ial graphs is stri
tly in
luded in the 
lass of K1,k+1-free
graphs.
Proof. If a graph G 
ontains K1,k+1, then it has a vertex with k + 1 independent neighbors,
and hen
e G is not all-k-simpli
ial. The wheel W2k+1 is a simple example of a graph whi
h is
K1,k+1-free but in whi
h the 
enter 
an not have its neighborhood (a C2k+1) partitioned into k

liques or less.
Unfortunately, all-k-simpli
ial graphs do not have a ni
e stru
ture whi
h 
ould help unit
2-interval graph re
ognition.
Theorem 3. Re
ognizing all-k-simpli
ial graphs is NP-
omplete for k ≥ 3.
Proof. We redu
e from the Graph k-
olorability problem, whi
h is known to be NP-

omplete for k ≥ 3 [Kar72℄. Let G = (V,E) be a graph, and let G′ be the 
omplement graph of
G to whi
h we add a universal vertex v. We 
laim that G is k-
olorable i� G′ is all-k-simpli
ial.
If G is k-
olorable, then the non-neighborhood of any vertex in G is k-
olorable, so the
neighborhood of any vertex in G is a union of at most k 
liques. And the neighborhood of v is
also a union of at most k 
liques, so G′ is all-k-simpli
ial.
Conversely, if G′ is all-k-simpli
ial, then in parti
ular the neighborhood of v is a union of
at most k 
liques. Let's partition it into k vertex-disjoint 
liques X1, . . . ,Xk. Then, 
oloring G
su
h that two verti
es have the same 
olor i� they are in the same Xi leads to a valid k-
oloring
of G.
6 Con
lusion
Motivated by pra
ti
al appli
ations in s
heduling and 
omputational biology, we fo
used in this
paper on balan
ed 2-interval graphs and unit 2-intervals graphs. Also, we introdu
ed two natural
new 
lasses: (x, x)-interval graphs and all-k-simpli
ial graphs.
We mention here some dire
tions for future works. First, the 
omplexity of re
ognizing unit
2-interval graphs and (x, x)-interval graphs remains open. Se
ond, the relationships between
quasi-line graphs and sub
lasses of balan
ed 2-intervals graphs still have to be investigated.
Last, sin
e most problems remains NP-hard for balan
ed 2-interval graphs, there is thus a natural
interest in investigating the 
omplexity and approximation of 
lassi
al optimization problems on
unit 2-interval graphs and (x, x)-interval graphs.
A
knowledgments
We are grateful to Vin
ent Limouzy in parti
ular for bringing to our attention the 
lass of
quasi-line graphs, and Mi
hael Rao and Mi
hel Habib for useful dis
ussions.
Referen
es
[Ben81℄ A. Ben Rebea. Étude des stables dans les graphes quasi-adjoints. PhD thesis, Université de
Grenoble, 1981.
[BFV04℄ G. Blin, G. Fertin, and S. Vialette. New results for the 2-interval pattern problem. In
Pro
eedings of the 15
Symposium on Combinatorial Pattern Mat
hing (CPM'04), 2004.
[BHLR07℄ A. Butman, D. Hermelin, M. Lewenstein, and D. Rawitz. Optimization problems in
multiple-interval graphs. In Pro
eedings of the 18
Annual Symposium On Dis
rete Al-
gorithms (SODA'07), pages 268�277, 2007.
℄ A. Brandstädt, V. B. Le, T. Szym
zak, F. Siegemund, H.N. de Ridder, S. Knorr, M. Rze-
hak, M. Mowitz, and N. Ryabova. ISGCI: Information System on Graph Class In
lusions.
http://wwwteo.informatik.uni-rosto
k.de/isg
i/
lasses.
gi.
[BNR96℄ V. Bafna, B. O. Narayanan, and R. Ravi. Nonoverlapping lo
al alignments (weighted
independent sets of axis-parallel re
tangles). Dis
rete Applied Math., 71(1):41�54, 1996.
[BYHN
06℄ R. Bar-Yehuda, M. M. Halldórson, J. Naor, H. Sha
hnai, and I. Shapira. S
heduling split
intervals. SIAM Journal on Computing, 36(1):1�15, 2006.
[CHLV05℄ M. Cro
hemore, D. Hermelin, G. M. Landau, and S. Vialette. Approximating the 2-interval
pattern problem. In Pro
eedings of the 13
Annual European Symposium on Algorithms
(ESA'05), volume 3669 of LNCS, pages 426�437, 2005.
95℄ D. G. Corneil, H. Kim, S. Natarajan, S. Olariu, and A. P. Sprague. Simple linear time
re
ognition of unit interval graphs. Information Pro
essing Letters, 55:99�104, 1995.
[CS05℄ M. Chudnovsky and P. Seymour. The stru
ture of 
law-free graphs. In Surveys in Com-
binatori
s, volume 327 of London. Math. So
. Le
ture Notes, pages 153�172. Cambridge
University Press, 2005.
[FFR97℄ R. Faudree, E. Flandrin, and Z. Ryjá£ek. Claw-free graphs - a survey. Dis
rete Mathemati
s,
164:87�147, 1997.
[GW80℄ J. R. Griggs and D. B. West. Extremal values of the interval number of a graph. SIAM
Journal on Algebrai
 and Dis
rete Methods, 1:1�7, 1980.
[GW95℄ A. Gyárfás and D. B. West. Multitra
k interval graphs. Congress Numerantium, 109:109�
116, 1995.
[HK06℄ M. M. Halldórsson and R. K. Karlsson. Strip graphs: Re
ognition and s
heduling. In Pro-

eedings of the 32
Workshop on Graph-Theoreti
 Con
epts in Computer S
ien
e (WG'06),
volume 4271 of LNCS, pages 137�146, 2006.
[JMT92℄ D. Joseph, J. Meidanis, and P. Tiwari. Determining DNA sequen
e similarity using max-
imum independent set algorithms for interval graphs. In Pro
eedings of the Third S
andi-
navian Workshop on Algorithm Theory (SWAT'92), volume 621 of LNCS, pages 326�337,
1992.
[Kar72℄ R. M. Karp. Redu
ibility among 
ombinatorial problems, pages 85�103. Plenum Press, 1972.
[Kar05℄ R. Karlsson. A survey of split intervals and related graphs, 2005. Manus
ript.
[KR07℄ A. King and B. Reed. Bounding χ in terms of ω ans δ for quasi-line graphs, 2007. Arti
le
in preparation.
[KW99℄ A. V. Kosto
hka and D. B. West. Every outerplanar graph is the union of two interval
graphs. Congress Numerantium, 139:5�8, 1999.
[Lov78℄ L. Lovász. Kneser's 
onje
ture, 
hromati
 number, and homotopy. Journal of Combinatorial
Theory Series A, 25:319�324, 1978.
[M
G77℄ R. M
Guigan, 1977. Presentation at NSF-CBMS Conferen
e at Colby College.
[Rob69℄ F. S. Roberts. Indi�eren
e graphs. In Proof Te
hniques in Graph Theory, Pro
eedings of
the Se
ond Ann Arbor Graph Theory Conferen
e, pages 139�146, 1969.
[Via01℄ S. Vialette. Aspe
ts algorithmiques de la prédi
tion des stru
tures se
ondaires d'ARN. PhD
thesis, Université Paris 7, 2001.
[Via04℄ S. Vialette. On the 
omputational 
omplexity of 2-interval pattern mat
hing. Theoreti
al
Computer S
ien
e, 312(2-3):223�249, 2004.
[WS84℄ D. B. West and D. B. Shmoys. Re
ognizing graphs with �xed interval number is NP-

omplete. Dis
rete Applied Math., 8:295�305, 1984.
http://wwwteo.informatik.uni-rostock.de/isgci/classes.cgi
7 Appendix
We give the detailed proofs of Theorem 1 and Property 4.
Proof of Theorem 1. Let G = (V,E) be a 3-regular triangle-free graph. We build a graph G′
whi
h has a 2-interval realization (a spe
ial one, very spe
i�
, and whi
h we prove to be balan
ed)
i� G has a Hamiltonian 
y
le.
First we will detail how we build G′ starting from the graph G, and adding some verti
es,
in parti
ular K5,3 gadgets. The idea is that the edges of G will partition into a Hamiltonian

y
le and a perfe
t mat
hing i� all 2-intervals of the realization of G′ 
an have their left inter-
val realizing the Hamiltonian 
y
le, and their right interval realizing the perfe
t mat
hing. A
realization with su
h a pla
ement of the intervals is 
alled an �H-representation� of G.
We pro
eed as illustrated in Figure 6. We 
hoose some vertex of G that we 
all v0 (whi
h will
be the �origin� of the Hamiltonian 
y
le), and the other are 
alled v1, . . . , vn. For ea
h vertex
vi of G we link it to a vertex of the S5 of a K5,3 
alled M(vi) (whi
h will blo
k one of the four
extremities of the 2-interval vi). We link all verti
es to a new vertex z, whi
h is linked to no
M(v) ex
ept M(v0) (thus the interval of ea
h vi interse
ting M(vi), for i 6= 0, won't interse
t
z). We add three K5,3, H1, H2 and H3 : two verti
es of the S5 of H1 are linked to z, a third one
is linked to one vertex of the S5 of H2, one vertex of the S5 of H3 is linked to z, and all verti
es
of H3 to v0.
To explain this 
onstru
tion in detail, we study the realization of G′, if we suppose it is a
(balan
ed) 2-interval graph, and we prove that it leads us to �nd a Hamiltonian 
y
le in G.
As the realization of H1 and H2 are two 
ontiguous blo
ks of intervals then one of their
extremities must interse
t. As z is linked to two disjoint verti
es of H1, both intervals of z are
used to realize those interse
tions. But one interval of z that we 
all zr, also has to interse
t
one vertex of H3 whi
h is not linked to H1, so zr interse
ts the se
ond extremity of the blo
k
H1 (the �rst extremity being o

upied by the extremity of H2). And as zr interse
ts only one
interval of H3, it must be the extremity of H3. The other interval of z is 
ontained in the blo
k
H1, thus 
an't interse
t M(v0) neither all the verti
es vi, so all those 2-intervals interse
t zr.
And as none of them interse
t H3 ex
ept v0, all of them ex
ept v0 have an interval 
ontained
in zr, that we 
all vi,g. The other interval of ea
h vi is linked to a K5,3 so it has one extremity
o

upied by K5,3, and the other one is free.
Conversely, if G has a Hamiltonian 
y
le, then it is possible to �nd a H-representation,
su
h that all the 
onstraints indu
ed by the edges of G′ are respe
ted, as illustrated with the
realization in Figure 6. We have already proved that this realization 
an be balan
ed.
Proof of Property 4. In the following, as we only 
onsidering the interval of vi
or vir lo
ated at
one extremity of the blo
k Xi, and not the one inside, we will use v
and vir to denote those
extremity intervals. For ea
h vertex vi, we 
all vi,l its left interval and vi,r its right interval. We
do the same for v′i, and 
all l(I) the left extremity of any interval I.
We prove by indu
tion that the graph K ′x is (x + 1, x + 1)-interval but not (x, x)-interval,
and that for any unit 2-interval realization, there exists an order σ ∈ Sx su
h that :
• either l(vσ(x),l) < . . . < l(vσ(1),l) < l(v
σ(x),l
) < . . . < l(v′
σ(1),l
) and l(v′
σ(x),r
) < . . . <
σ(1),r
) < l(vσ(x),r) < . . . < l(vσ(1),r),
• or the symmetri
 
ase: l(vσ(1),l) < . . . < l(vσ(x),l) < l(v
σ(1),l
) < . . . < l(v′
σ(x),l
) and
σ(1),r
) < . . . < l(v′
σ(x),r
) < l(vσ(1),r) < . . . < l(vσ(x),r).
Those two equalities 
orrespond in fa
t to the �two stairways stru
ture� whi
h appears in Fig-
ure 7.
Base 
ase : we study all possible unit 2-interval realizations of K ′2 to prove that one of the
expe
ted inequalities is always true. We also prove that K ′2 has no (2,2)-interval realization.
First re
all that realizations of Xi subgraphs 
an only be blo
ks of 
ontiguous intervals. The
edge between v2r and v
for
es the two blo
ks of X2 and X3 to be 
ontiguous, with intervals
and v3r at their extremities. Ea
h 2-interval v
i must interse
t both v
and v3r , so one of its
intervals interse
ts v2
and the other interse
ts v3r . Thus, one same interval of v
i 
an not interse
t
both a and b whi
h are disjoint, so a interse
ts one interval of v′i (say the one interse
ting v
, the
other 
ase being treated symmetri
ally) and b interse
ts the other one (so, the one interse
ting
v3r ). Ea
h vi has to interse
t both a and b, so it has to interse
t a with its �rst interval and
b with the se
ond. But 2-interval vi must also interse
t v
r and v
whi
h are both disjoint and
disjoint to a and b. So one interval of ea
h vi must interse
t v
r and the other one must interse
t
So we have shown that any unit 2-interval realization of K ′2 has the following aspe
t (or the
symmetri
) : the extremity of the blo
k X1 interse
ting all vi whi
h interse
t a (or b) whi
h
interse
ts all v′i, whi
h interse
t the extremity X2 (or X3) whi
h interse
ts the extremity of X3
(or X2), whi
h interse
ts all v
i, whi
h interse
t b (or a), whi
h interse
ts all vi, whi
h interse
t
the extremity of X4.
Now we suppose, by 
ontradi
tion, that there exists a (2,2)-interval realization of K ′2. v
an interval of length 2, but one of its two parts of length one has to interse
t an element of X1.
The other has to interse
t both v1 and v2. As neither v1 nor v2 
an interse
t other intervals of
X1, then the �rst interval of v1 and v2 is the same interval. By pro
eeding the same way on X4
and v4
, we obtain that the se
ond interval of v1 and v2 is the same interval, so v1 and v2 should

orrespond to the same 2-interval: it 
ontradi
ts with the fa
t that verti
es v1 and v2 have a
di�erent neighborhood. So K ′2 has no (2,2)-interval realization.
To obtain the expe
ted inequalities, we have to analyze the possible positions of all vi and
v′i. We only treat the �rst two inequalities as the se
ond 
ase is symmetri
.
Suppose that l(v2,l) < l(v1,l). As v1 and v
1 are non adja
ent, then interval v1,l is stri
tly on
the left of v′1,l, so v2,l is stri
tly on the left of v
1,l. Thus those two intervals do not interse
t. But
v2 and v
1 are adja
ent, so v2 and v
1 must have interse
ting right intervals. But then we have
l(v′2,r) < l(v
1,r) < l(v2,r) < l(v1,r), and the right intervals of v
2 and v1 
an not interse
t. We
dedu
e their left intervals interse
t, so l(v2,l) < l(v1,l) < l(v
2,l) < l(v
1,l).
If we suppose that l(v1,l) < l(v2,l), we get as well that l(v
1,r) < l(v
2,r) < l(v1,r) < l(v2,r) and
l(v1,l) < l(v2,l) < l(v
1,l) < l(v
2,l). So for any unit 2-interval realization of K
2 there exists an
order σ = 12 or σ = 21 su
h that:
• either l(vσ(2),l) < l(vσ(1),l) < l(v
σ(2),l
) < l(v′
σ(1),l
) and l(v′
σ(2),r
) < l(v′
σ(1),r
) < l(vσ(2),r) <
l(vσ(1),r),
• or the symmetri
 inequalities.
Re
ursion: suppose that for some x, K ′x−1 is not (x−1, x−1)-interval but is (x, x)-interval,
and that any (x, x)-interval realization veri�es one of the expe
ted inequalities.
Graph K ′x−1 is an indu
e subgraph of K
x = (V,E) : K
x−1 = K
x[V \ {vx, v
x}]. So by the
indu
tion hypothesis, there exists an order σ ∈ Sx−1 su
h that for any unit 2-interval realization
of K ′x :
• either l(vσ(x−1),l) < . . . < l(vσ(1),l) < l(v
σ(x−1),l
) < . . . < l(v′
σ(1),l
) and l(v′
σ(x−1),r
) < . . . <
σ(1),r
) < l(vσ(x−1),r) < . . . < l(vσ(1),r),
• or the symmetri
 
ase: l(vσ(1),l) < . . . < l(vσ(x−1),l) < l(v
σ(1),l
) < . . . < l(v′
σ(x−1),l
) and
σ(1),r
) < . . . < l(v′
σ(x−1),r
) < l(vσ(1),r) < . . . < l(vσ(x−1),r).
The position of vx and v
x remains to be determined. We treat only the 
ase where the �rst
two inequalities are true, as the se
ond 
ase is symmetri
.
As vx and v
r are adja
ent, and v
σ(x−1)
and v1r are not, then l(v
r ) < l(vx,l) < l(v
σ(x−1),l
). So
we de�ne j the following way: vσ(j),l is the leftmost interval su
h that l(vx,l) ≤ l(vσ(j),l). if there
is none, we say j = 0. Then we 
all σ′ ∈ Sx the permutation de�ned by:
σ′(i) = σ(i) if i < j,
σ′(j + 1) = x,
σ′(i) = σ(i− 1) if i > j.
Then we dire
tly get inequalities:
• l(v1r ) < l(vσ′(x),l) < . . . < l(vσ′(j+1),l) ≤ l(vx,l) < l(vσ′(j−1),l) < . . . < l(vσ′(1),l) <
σ′(x),l
) < . . . < l(v′
σ′(j+1),l
) < l(v′
σ′(j−1),l
) < . . . < l(v′
σ′(1),l
• l(v′
σ′(x),r
) < . . . < l(v′
σ′(j+1),r
) < l(v′
σ′(j−1),r
) < . . . < l(v′
σ′(1),r
) < l(vσ′(x),r) < . . . <
l(vσ′(j+1),r) < l(vσ′(j−1),r) < . . . < l(vσ′(1),r)
We obtain the expe
ted inequalities by reasoning the same way as in the end of the base

ase.
So in parti
ular we have l(vσ(x),l) < . . . < l(vσ(1),l) and v
r must interse
t all those vi for
i ∈ J1, xK, but also an interval of X1 whi
h interse
ts none of the vi. So it must have length
x+ 1, thus K ′x is not a (x, x)-interval graph
Con
lusion: As the base 
ase and the re
ursion has been proved, expe
ted properties of
the graph K ′x are true for any x ≥ 2.
	2-interval graphs and restrictions
	Useful gadgets for 2-interval graphs and restrictions
	Balanced 2-interval graphs
	Unit 2-interval and (x,x)-interval graphs
	Investigating the complexity of unit 2-interval graphs
	Conclusion
	Appendix
