数理解析研究所講究録
第 1644 巻 2009 年 128-134

128

Reconstruction of Connected Interval Graphs
Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara
School of Information Science, JAIST,
Asahidai 1-1, Nomi, Ishikawa 923-1292, Japan.
{mkiyomi,toshikis,uehara}@jaist.ac.jp
Abstract
The graph reconstruction $coi$}$|ecture$ is a long-standing open problem in graph theory. There
are many algorithxnic studies related it besides mathematical studies, such as DECK CHECKING,LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study
these algorithmic problems limiting the graph class to interval graphs. Since we can solve GRAPHISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs iseasily done in polynomial time. We present in this paper that the other three problems above aresolvable in polynomial time on connected interval graphs.
Keywords: the graph reconstmction conjecture, interval graphs, polynomial time algorithm

1

Introduction

Given a simple graph $G=(V, E)$ , we call the multi-set $\{G-v|v\in V\}$ the deck of $G$ where $G-v$ is agraph obtained from $G$ by removing vertex and incident edges. The graph reconstruction conjecture
by Uram and Kellyl is that for any multi-set $D$ of graphs with at least two vertices there is at mostone graph whose deck is $D$ . We call a graph whose dcck is $D$ a preimage of $D$ . No counter example is
known for this conjecture, and there are many mathematical results about this conjecture. For cxample
trecs, rcgular graphs, and disconnected graphs are reconstructible (i.e. the $coi$}$|ecture$ is true for theseclasses) [5]. About interval graphs, Rimscha showed that interval graphs are recognizable in the sensethat looking at the deck of $G$ one can decide whether or not $G$ belongs to interval graphs [10]. Rimschaalso showed in the same paper that many subclasses of perfect graphs including perfect graphs themselves
are recognizable, and somc of subclasses including unit interval graphs are reconstructible. There aremany good surveys about this conjecture. See for example [1, 4].
Besides these mathematical results, there are some algorithmic results. We enumerate the algorithmic
problems that we address in this paper.
$v$

.
.
.
.

Given a graph$G$and a multi-set of graphs $D$ , check whether $D$ is a deck of $G$ (DECK CHECKING).

Given a multi-set of graphs $D$ , determine whether there is a graph whose deck is $D$ (LEGITIMATE
DECK).

Given a multi-set of graphs$D$TION).

, construct a graph whose deck is $D$ (PREIMAGE CONSTRUC-

Given a multi-set of graphs , compute the number of (pairwise nonisomorphic) graphs whose
decks are $D$ (PREIMAGE COUNTING).
$D$

lDetermining the first person who proposed the graph reconstruction conjecture is difficult, actually. See [4] for thedetail.

129

Graph class specified versioiis of LEGITIMATE DECK and PREIMAGE CONSTRUCTION assume
that preimages are in the specificd graph class. Kratsch and Hemaspaandra showed that these problems
arc solvable in polynomial time for graphs of bounded degree, partial k-trees for any fixed and graphsof bounded genus, in particular for planner graphs [7]. In the samc paper they proved many GI related
complcxity results.
There is a linear timc algorithm for determining if given two interval graphs are isomorphic [9]. Thus
dcveloping a polynomial time algorithm for DECK CHECKING for interval graphs is easy.
$k_{I}$

Theorem 1 There is an $0(n(n+m))$ time algorithm of DECK CHECKING for n-vertex m-edge graphand its deck (or a deck candidate) that consists of interval graphs.

We will give the proof in Section 3.

LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING for connected interval graphs are solvable by almost the same algorithm. In order to develop such an algorithm wc show that given a set of interval graphs $D$ there is at most $O(n^{2})$ connected interval graphs(preimages) whose deck is $D$ . Ifurther we can construct such $O(n^{2})$ preimage candidates. Our algorithm
checks these $O(n^{2})$ candidates one by one whether its deck is $D$ with DECK CHECKING algorithm.
Our algorithm constructs preimage candidates from $O(n)$ different interval representations of eachinterval graph in $D$ by inserting an interval to them. The key is that the number of preimage candidates
is $O(n^{2})$ while a naive algorithm which inserts an interval to an interval representation constructs
candidatcs (Consider the case that $O(n)$ intervals terminate at some point , and we insert a new left
end-point to . The number of the ways of insertions issince there are $O(n)$ times choices whctherthe new interval intersects the old ones. Further, there may be many, say $O(2^{n})$ , different compact
interval representations for an interval graph. Therefore the number of preimage candidates will be veryhuge if we construct the candidatcs from all of them).
The following is our main theorem.
$n$

$n$

$\Omega(2^{n})$

$t$

$t$

$\Omega(2^{n})$Theorem 2 There are $O(n^{3}(n+m))$ time algorithms for LEGITIMATE DECK and PREIMAGE CON$STR$ UCTION, and there is an $O(n^{4}(n+m))$ time algorithm
for PREIMAGE COUNTING, for connectedinterval graphs.
Note that is the number of vertices and $m$ is the number of edges in the preimage. Kelly’s lemma [5]shows that we can compute and $m$ from the deck.
We state terminologies in Section 2, then explain about interval graphs in Section 3. In Scction 3
we introduce many small lemmas for those who unfamiliar to interval graphs. Most of these lemmas
may be well-known and $/or$ basic for those who familiar to interval graphs and the theory of PQ-tree [2]and MPQ-tree [6]. However these lcmmas play important roles in this paper. Then we show that the
number of preimagc candidates is $O(n^{2})$ , and we present our algorithm in Section 4. Finally we makc
some remarks in Section 5.
$n$

$n$

2

Terminology

Graphs in this parer are all simple and undirccted, unless explicitly stated. We denote by $N_{G}[v]$ theclosed neighbor set of vertex in graph G. “Closed” means that $N_{G}[v]$ contains itself. We dcnote by$\deg_{G}(v)$ the degree of vertex
in graph . We omit the subscript when there is no confusion about
the base graph. The sum of degrees of all vertices in graph $G$ is denoted by degsum(G). Notice thatdcgsum(G) is equal to twice the number of edges in . We denote by the graph obtained by adding
one universal vcrtex to the graph such that the vertex connects to every vertex in $G$ . Notice that $G$
is always connected. Given two graphs, we define the disjoint union
and
of
and
as
, and
such thatis isomorphic to, whereis isomorphic tomeans the disjoint union.
$v$

$v$

$G$

$v$

$G$

$G$

$\tilde{G}$$G$$G_{1}$$(V_{1}\cup V_{2}, E_{1}\cup E_{2})$$(V_{1}, E_{1})$$Gi\cup G_{2}$$G_{2}$$G_{1}$$(V_{2}, E_{2})$$G_{1}$$G_{2}$$G_{2}$$\cup$

130,$\frac{Il1I1}{012345\prime-}!.$

Figure 1: The figure shows a compact interval representation of an interval graph. Every interval graphhas at least one compact interval representation. Vertices corresponding to the encloscd intervals are
end-vertcx set.

3

Interval Graphs

A graph $G=$

with $V=\{v_{1}, v_{2}, \ldots, v_{n}\}$ is an interval graph iff there is a multi-setof closed intervals on the real line such that $\{v_{i}, v_{j}\}\in E$ if and only if
for cach and with $1\leq i,j\leq n$ . We call the multi-set an interval representation of $G$ . An intervalgraph may have infinitely many interval representation. We use tractable one called compact interval
rcpresentation among them.
$(V, E)$$\mathcal{I}=$$\{I_{v_{1}}, I_{v_{2}}, \ldots, I_{v_{n}}\}$

$i$

3.1

.

$I_{v_{t}}\cap I_{v_{j}}\neq\emptyset$$j$$\mathcal{I}$compact representation and basic lemmas

Definition 1 An interval representation.
.

$\mathcal{I}$of an $inten!al$ graph $G=(V, E)$ is compact iff

coordinates of end-points of interwals in are finite non-negative integers (We denote by $K$ thecoordinates of end-points for convenien ce. We sometimes call $K$ the length of ),$\mathcal{I}$$la\tau gest$

there

$e$

$\mathcal{I}$ists at least one end-point whose coordinate is$inten!al$ multi-set $\mathcal{I}_{k}=\{I\in \mathcal{I}|k\in I\}$

differs from$k$for every integer $k\in[0, K]$ , and$\mathcal{I}_{l}=\{I\in \mathcal{I}|l\in I\}$

each other, for eve Zt distinct integers $k,$ $l\in[0, K]$ .

, and they do not include

We show an example of a compact interval representation of an interval graph in Fig. 1. Note that therc
may be still multiple compact interval representations of an interval graph. However compact interval
represcntations have some good properties.
Lemma 1 Let andbe compact $inten!al$ representations of an interval graph $G=(V, E)$ , and let
be the length of , and let
be the length of . Then the following holds.
$\mathcal{I}$$\mathcal{J}$$K_{2}$$\mathcal{I}$$K_{1}$$\mathcal{J}$$\{\{I\in \mathcal{I}|0\in I\}, \{I\in \mathcal{I}|1\in I\}, \ldots, \{I\in \mathcal{I}|K_{1}\in I\}\}=$$\{\{I\in \mathcal{J}|0\in I\}, \{I\in \mathcal{J}|1\in I\}, \ldots, \{I\in \mathcal{J}|K_{2}\in I\}\}$

Proof:

Wc denote by the set of multi-set of intervals $\{\{I\in \mathcal{I}|0\in I\},$ $\{I\in \mathcal{I}|1\in I\},$$\{I\in$, and we denote by
the set of multi-set $oi$ intervals $\{\{I\in \mathcal{J}|0\in I\},$ $\{I\in \mathcal{J}|1\in$$\{I\in \mathcal{J}|K_{2}\in I\}\}$ . The vertices represented by the multi-set of intervals
correspond to a clique in . Assume thatnever appears in for some . Since . represents a clique$C$ ,there must be a set of intervals representing a clique C’ containing $C$ in(otherwise, cliquecan
not be represented in ). Then for the same reason, must contain a set of intervals representing acliquc containing $C$ ‘. This contradicts the compactness of .
$\tilde{\mathcal{I}}$$\ldots,$$\mathcal{I}|K_{1}\in I\}\}$$I\},$$\vec{\mathcal{J}}$$\mathcal{I}_{i}=\{I\in \mathcal{I}|i\in I\}$$\ldots,$$G$$\overline{\mathcal{J}}$$\mathcal{I}_{l}$$i$$\mathcal{I}_{*}$$\overline{\mathcal{J}}$$\mathcal{J}$$C$$\tilde{\mathcal{I}}$$\square$$\mathcal{I}$

From the proof of Lemma 1, the following lemmas are straight-forward.

Lemma 2 Let be a compact interval repre sentation of an interval graph $G=(V, E)$ , and let $K$ be thelength of . Then $\{I\in \mathcal{I}|i\in I\}$ for each $i\in\{0, \ldots, K\}$ corresponds to each maximal clique of .
$\mathcal{I}$$\mathcal{I}$

$G$

131

boolean function deck-checking(graph $G=(V,$ $E)$ ) {Let $G’$ be an cmpty graph.
for each vertcx $v\in V$ $\{ G’ :=G’\cup(G-v). \}$if $G’$ is isomorphic toreturn True else retum False.
$G_{1}\cup G_{2}\cup\ldots\cup G_{n}$$\}$Figure 2: The deck checking algorithm.
Lemma 3 The length of a compact interwal representation of an n-vertex $intert$) $al$ graph is at most

Note that the number of maximal cliques in an n-vertex interval graph is at most

$n$

$n$

.

(see [3]).

Lemma 4 All the compact interval representations of an interval graph have the same length.
Lemma 5 Intervals in different $C0tnpact$ interval representations corresponding to an identical vertex
have the same length.
From Lemma 5, lengths of intervals corresponding to a vertex that corresponds to an interval of length
zero in some interval representation are always (i.e. in any interval representations) zero. Such vertex iscalled simplicial.
Noticc that all the members in a deck of an interval graph are interval graphs since removing a vcrtex
from an interval graph results in another interval graph.

3.2

deck checking
Now we prove Theorem 1. Our main algorithm enumerates the preimage candidates, and chccks whether
each candidate is really a preimage of the input deck. Thus the theorem is one of the basic part of ouralgorithm.
Proof: [Proof of Thcorem 1] We can determine whether or not the given multi-set $D=\{G_{1}, G_{2}, \ldots, G_{n}\}$is a deck of the input graph $G$ by checking whether or not
is isomorphic to the deckof $G$ . Since the disjoint umion of two interval graphs is an interval graph, we can use wcll-known linear
time isomorphism algorithm [9] for this checking. We describe the algorithm in Fig. 2. Since the numberof vertices ofis $O(n^{2})$ , and since the number of edges ofis $O(mn)$ , the timecomplexity of this algorithm is $O(n(n+m))$ .
$G_{1}\cup G_{2}\cup\ldots\cup G_{n}$$G_{1}\cup\ldots\cup G_{n}$$G_{1}\cup\ldots\cup G_{n}$$\square$4

Main Algorithm

First we define end-vertex set. The end-vertex set is intuitively a set of vertices whose corresponding
intervals are at the left cnd. Our algorithm adds a vertex adjacent to all the vertices in an end-vcrtex
set of an interval graph in the input deck. This enables us to avoid exponential timcs’ constructions ofpreimage candidates.
Deflnition 2 For an interval graph $G=(V, E)$ , we call a vertex subset $S\subset V$ an end-vertes set
iff in some compact intervd representation $0\int G$ all the coordinates of the left end-points of intervals
corresponding to vertices in are , and is ma rimal among such vertex subsets.
$S$

$0$

$S$

See Fig. 1 for example. It is well-known that an end-vertex set has at least one simplicial vertex.
We show some simple lemmas about end-vertex sets. We can estimate that the numbcr of essentiallydiffcrcnt preimage candidates is $O(n^{2})$ by these lemmas.

132

Lemma 6 Let
be end-vertex set of an interval graph $G=(V, E)$ . If two vertices
the same degree, then $N[v]$ and $N[w]$ are the same vertex subset of $G$ .
$S$

$v$

and

$w$

in $S$ have

Proof: The statement is clear from the definition of compact interval representation (see Fig. 1 for the
better understanding).

$\square$Lemma 7 A connected interwal graph has at most $O(n)$ end-vertex sets.
Proof: An end-vertcx set of an interval graph $G$ is in the form $\{I \in \mathcal{I}|0\in I\}$ for some interval
representation of . Thus, ffom Lemma 1 and 3, there are at most $O(n)$ end-vertex sets for G.
$G$$\mathcal{I}$$\square$Now we refer the well-known lemma about the degree sequence.

Lemma 8 (Kelly’s Lemma [5]) We can calculate the degree sequence of a preimage of the input
graphs in $0(n)$ time, if we know the number of edges in each input graph.
Proof: Lct
Then there are vertices
1, 2,. Thus$G_{1},$ $G_{2},$$\{$$\ldots,$$\ldots,$$G_{n}$$n$be the input graphs. Assume that graph $G$ has a deck $\{G_{1}, G_{2}, \ldots , G_{n}\}$ .
such that G. is obtained by removing $v_{i}homG$ for each in$v_{1},$ $v_{2},$$\ldots,$$i$$v_{n}$$n\}$degsum $(G_{i})=$ degsum $(G)-2\deg_{G}(v_{t})$holds for cach $i\in\{1,2_{1}\ldots, n\}$ . Hence we havedegsum(G)$= \frac{\sum_{i=1}^{n}\deg\S um(G_{i})}{n-2}$.

Therefore we can easily calculate the degree sequence of , i.e., (degsum $(G)-$ degsum) $/2,$ $(degsum(G)-$$(G_{2}))/2,$
$/2$
$(G)$
,
degsum) .
(degsum–degsum
Wc can calculate degsum
in constant time, provided we know the numberof edges in , fordegsumis equal to. Thus the time complexity to calculate degsum(G) is $O(n)$ , and the total
time complexity to obtain the degree sequence of is also $O(n)$ .
$G$$(G_{1})$$(G_{n})$$\ldots$$(G_{i})$$(G_{i})$$G_{i}$$m_{i}$$2m_{i}$$G$$\square$Now we prescnt an algorithm for reconstructing a connected interval graph. Suppose that an n-vcrtex
connccted interval graph $G$ has a deck of interval graphs $\{G_{1}, G_{2}, \ldots , G_{n}\}$ . Let be a compact interval
representation of $G$ . There must be an index $i\in\{1, \ldots, n\}$ such thatis obtained by removing
a simplicial vertcx in the end-vcrtcx set $S$ corresponding to . We want to reconstruct
from. To do so, we first show that we can reconstruct $G$ if we know the index . Once we provethis, we can reconstruct $G$ by checking if
is the desiredfor every $j\in\{1, \ldots, n\}$ .
It is clear thatis contained in some end-vertex set $S’$ of . Of course we do not know $S’$
. However the number of the candidates of $S$‘ is $O(n)$ by Lemma 7. Thus
if we do not know
chccking if each candidate is $S’$ can be done by $O(n)$ times trying of the algorithm below. Lct
be aninterval rcpresentation of
whose corresponding end-vertex set is $S’$ . Notice thatis easily obtained
in $O(n+m)$ time by using the data structure called MPQ-tree [6] if we know $S’$ .
, we can obtain $G$ , since $G$ has the interval representation. If we know
Now we try to know
by extending intervals corresponding to vertices in
obtainedto the left by one and adding. Since we know the degree sequence of , andan interval $[-1, -1]$ . Therefore we need to know
we can know the dcgree sequence of by Lemma 8, we can know the degree sequence of. We. Now we can obtainis the subset of $S’$
denote the degree sequence byis $(d_{1}-1, d_{2}-1, \ldots, d_{l}-1)$ . Notice that there may be manysuch that whosc degree sequence in$S$ ‘
arc $(d_{1}-1, d_{2}-1, \ldots, d_{l}-1)$ . However Lemma 6 guarantees
subsets of whose degree sequences in, i.e. all the graphs reconstructed in the assumption that somethat any of such subsets can be
subset of ‘ whose degree scquence is $(d_{1}-1\rangle d_{2}-1, \ldots, d_{l}-1)$ areare isomorphic to each other.
Thercfore we can reconstruct $G$ . The whole algorithm is described in Fig 3.
$\mathcal{I}$$G_{i}$$G_{1},$$\ldots,$$G$$\mathcal{I}$$s$$G_{n}$$i$$G_{i}$$G_{j}$$G_{i}$$S\backslash \{s\}$$S\backslash \{s\}$$\mathcal{I}_{i}$$G_{i}$$\mathcal{I}_{i}$$S\backslash \{s\}$$S\backslash \{s\}$$h:om\mathcal{I}_{i}$$S\backslash \{s\}$$S\backslash \{s\}$$G_{i}$$G$$S\backslash \{s\}$$(d_{1}, d_{2}, \ldots, d_{t})$$S\backslash \{s\};S\backslash \{s\}$$G_{i}$$G_{i}$$S\backslash \{s\}$$S$$S\backslash \{s\}$133

for each $G_{i}(i=1,2, \ldots, n)$ {for each end-vertex set $S’$ of$G_{i}${

Let be an interval representation of
whose corresponding end-vertex set is $S’$ .
$\mathcal{I}$$G_{i}$

Compute the degree sequenceof.
Let $S”$ be a subset of $S’$ whosc dcgree sequence inis $(d_{1}-1, \ldots, d_{l}-1)$ .
Let be an interval graphwhose interval reprcsentation is obtained fromby extending interval corresponding to vertices in $S”$ to the left by one
and adding an interval $[-1, -1]$ .
$(d_{1}, \ldots, d_{l})$$S\backslash \{s\}$$G_{i}$$G$$\mathcal{I}$

if deck-checking $(G)=$ True
output $G$ .
$\}$

$\}$

return No if the algorithm has output no graph.
Figure 3: The algorithm for reconstructing connected interval graphs.

Now we consider the time complexity of this algorithm. Because of the space limitation we omit thc
detail of the basic algorithms about MPQ-tree. For each , calculating an MPQ-tree ofin $o(n+m)$
time helps us to list each ‘ and in $0(n)$ time. Computing the degrce sequence
takcs$O(n)$ time from Lemma 8. Since obtaining $S”$ needs sorting of the degree sequence, it requires $o(n\log n)$time. It is clear that reconstructing an interval graph $hom$ its interval representation takes $O(n+m)$ time,
if the end-points of intervals are sorted. DECK CHECKING algorithm costs $O(n(n+m))$ . Therefore thc
total time complexity of this algorithm is $O(n((m+n)+n(n+m+n\log n+n(n+m))))=O(n^{3}(m+n))$ .
Note that we have to check every output preimage is not isomorphic to each other for PREIMAGE
COUNTING. Since the number of output preimage may be $O(n^{2})$ , we necd $O(n^{4}(n+m))$ time for thischecking. If the graph reconstruction conjecture is true, the time complexity of this checking can be$G_{l}$$S$$G_{i}$$I$$(d_{1}, d_{2}, \ldots, d_{l})$omitted.

Theorem 3 There is a polynomial time algorithm that lists up connected interval graphs that are preimages of the input interval graphs. The time complexity for outputting one connected interval graph is$O(n^{3}(n+m))f$ and that for outputting all is $O(n^{4}(m+n))$ .
$n$Thcreforc we have the main theorem (Theorem 2).

5

Concluding Remarks

The algorithms we described does not help directly the proof of the graph rcconstruction conjecture on
interval graphs. The conjecture on interval graphs remains to be open.
Thc complexities of graph reconstruction problems are strongly related that of graph isomorphism
problcms, To develop a polynomial time algorithm for a graph reconstruction problem restricting inputs
to be in GI-hard graph class seems very hard. Since graph isomorphisms of circular-arc graphs arepolynomial time solvable, circular-arc graph reconstruction problem may be a good challenge.
$tQ$

134

References[1] J. A. Bondy: A graph reconstructor’s manual. Surveys in Combinatorics, London MathematicalSociety Lecture Note Series, vol. 166 (1991) 221-252.

[2] K. S. Booth and G. S. Lueker: Testing for the consecutive ones property, interval graphs, and graphplanarity using PQ-troe algorithms. Joumal of Computer and System Sciences, vol. 13 (1976) 335-

379.

[3] D. R. lfulkerson and O. A. Gross: Incidence matrices and interval graphs. Pacific Joumal of Mathematics, vol. 15 (1965) 835-855.

[4] F. Harary: A survey of the reconstruction conjecture. Graphs and Combinatorics, Lecture Notes inMathematics, vol. 406 (1974) 18-28.
[5] P. J. Kelly: A congruence theorem for trees. Pacific Joumal of Mathematics, vol. 7 (1957) 961-968.
[6] N. Korte and R. H. Mohring: An incremental linear-timc algorithm for recognizing interval graphs.
SIAM Journal on Computing, vol. 18 (1989) 68-81.

[7] D. Kratsch and L. A. Hemaspaandra: On the complexity of graph reconstruction, Mathematical
Systems Theory, vol. 27 (1994) 257-273.
[8] C. G. Leckerkerker and J. Ch. Boland: Representation of a finite graph by a set of intervals on thereal line. hndamenta Mathematicae, vol. 51 (1962) 45-64.
[9] G. S. Lueker and K. S. Booth: A linear time algorithm for deciding interval graph isomorphism.
Journal of the ACM, vol. 26 (1979) 183-195.
[10] M. von Rimscha: Reconstructibility and perfect graphs. Discrete Mathematics, vol. 47 (1983) 283-

291.