Characterization and recognition of proper tagged
probe interval graphs

arXiv:1607.02922v1 [math.CO] 11 Jul 2016

Sourav Chakraborty∗, Shamik Ghosh†‡, Sanchita Paul§ and Malay Sen¶
July 12, 2016

Abstract
Interval graphs were used in the study of genomics by the famous molecular biologist Benzer. Later on
probe interval graphs were introduced by Zhang as a generalization of interval graphs for the study of
cosmid contig mapping of DNA.
A tagged probe interval graph (briefly, TPIG) is motivated by similar applications to genomics, where
the set of vertices is partitioned into two sets, namely, probes and nonprobes and there is an interval
on the real line corresponding to each vertex. The graph has an edge between two probe vertices if
their corresponding intervals intersect, has an edge between a probe vertex and a nonprobe vertex if the
interval corresponding to a nonprobe vertex contains at least one end point of the interval corresponding
to a probe vertex and the set of non-probe vertices is an independent set. This class of graphs have
been defined nearly two decades ago, but till today there is no known recognition algorithm for it.
In this paper, we consider a natural subclass of TPIG, namely, the class of proper tagged probe interval graphs (in short PTPIG). We present characterization and a linear time recognition algorithm for
PTPIG. To obtain this characterization theorem we introduce a new concept called canonical sequence
for proper interval graphs, which, we belief, has an independent interest in the study of proper interval
graphs. Also to obtain the recognition algorithm for PTPIG, we introduce and solve a variation of
consecutive 1’s problem, namely, oriented consecutive 1’s problem and some variations of PQ-tree algorithm. We also discuss the interrelations between the classes of PTPIG and TPIG with probe interval
graphs and probe proper interval graphs.
Keywords: Interval graph, proper interval graph, probe interval graph, probe proper interval graph,

tagged probe interval graph, consecutive 1’s property, PQ-tree algorithm.

∗

Chennai Mathematical Institute, Chennai, India. sourav@cmi.ac.in
Department of Mathematics, Jadavpur University, Kolkata - 700 032, India. sghosh@math.jdvu.ac.in
‡
(Corresponding author)
§
Department of Mathematics, Jadavpur University, Kolkata - 700 032, India. sanchitajumath@gmail.com
¶
Department of Mathematics, North Bengal University, District - Darjeeling, West Bengal, Pin - 734 430, India.
†

senmalay10@gmail.com

1

1

Introduction

A graph G = (V, E) is an interval graph if one can map each vertex into an interval on the real line
so that any two vertices are adjacent if and only if their corresponding intervals intersect. Such
a mapping of vertices into an interval on the real line is called an interval representation of G.
The study of interval graphs was motivated by the study of the famous molecular biologist Benzer
[2] in 1959. Since then interval graphs has been widely used in molecular biology and genetics,
particularly for DNA sequencing. Different variations of interval graphs have been used to model
different scenarios arising in the area of DNA sequencing. Literature on the applications of different
variations of interval graphs can be found in [5, 13, 22].
In an attempt to aid a problem called cosmid contig mapping, a particular component of the physical
mapping of DNA, in 1998 Sheng, Wang and Zhang [34] defined a new class of graphs called tagged
probe interval graphs (briefly, TPIG) which is a generalization of interval graphs. Since then one of
the main open problems in this area has been “Given a graph G, recognizing whether G is a tagged
probe interval graphs.”
Definition 1.1. A graph G = (V, E) is a tagged probe interval graph if the vertex set V can be
partitioned into two disjoint sets P (called “probe vertices”) and N (called “nonprobe vertices”)
and one can map each vertex into an interval on the real line (vertex x ∈ V mapped to Ix = [`x , rx ])
such that all the following conditions hold:
1. N is an independent set in G, i.e., there is no edge between nonprobe vertices.
2. If x, y ∈ P then there is an edge between x and y if and only if Ix ∩ Iy 6= ∅, or in other words
the mapping is an interval representation of the subgraph of G induced by P .
3. If x ∈ P and y ∈ N then there is an edge between x and y if and only if the interval corresponding to the nonprobe vertex contains at least one end point of the interval corresponding
to the probe vertex, i.e., either `x ∈ Iy or rx ∈ Iy .
We call the collection {Ix | x ∈ V } a TPIG representation of G. If the partition of the vertex set
V into probe and nonprobe vertices is given, then we denote the graph as G = (P, N, E).
Problem 1.2. Given a graph G = (P, N, E), give a linear time algorithm for checking if G is a
tagged probe interval graph.
Tagged probe inteval graphs have been defined nearly two decades ago and since then this problem
has not seen much progress. Untill this paper there was no known algorithm for tagged probe
2

interval graphs or any natural subclass of tagged probe interval graphs, excepting probe proper
interval graphs (cf. Subsection 1.2.3).
A natural and well studied subclass of interval graphs are the proper interval graphs. A proper
interval graph G is an interval graph in which there is an interval representation of G such that
no interval contains another properly. Such an interval representation is called a proper interval
representation of G. Proper interval graphs is an extremely rich class of graphs and we have a
number of different characterizations of proper interval graphs.
In this paper, we study a natural special case of tagged probe interval graphs which we call proper
tagged probe interval graph (in short, PTPIG). The only extra condition that a PTPIG should
satisfy over TPIG is that the mapping of the vertices into intervals on the real line that gives a
TPIG representation of G should be a proper interval representation of the subgraph of G
induced by P .
In this paper we present a linear time (linear in (|V | + |E|) recognition algorithm for PTPIG.
The backbone of our recognition algorithm is the characterization of proper tagged probe interval
graphs that we obtain in Theorem 3.4. To obtain this characterization theorem we introduce a
new concept called “canonical sequence” for proper interval graphs, which we believe would
be of independent interest in the study of proper interval graphs. Also to obtain the recognition
algorithm for PTPIG, we introduce and solve a variation of consecutive 1’s problem, namely,
oriented consecutive 1’s problem.

1.1

Notations

Suppose a graph G is a PTPIG (or TPIG), then we will assume that the vertex set is partitioned
into two sets P (for probe vertices) and N (for nonprobe vertices). To indicate that the partition
is known to us, we will sometimes denote G by G = (P, N, E), where E is the edge set. We will
denote by GP the subgraph of G that is induced by the vertex set P . We will assume that there
are p probe vertices {u1 , . . . , up } and q nonprobe vertices {w1 , . . . , wq }. To be consistent in our
notation we will use i or i0 or i1 , i2 , . . . as indices for probe vertices and use j or j 0 or j1 , j2 , . . . as
indices for nonprobe vertices.
Let G = (V, E) be a graph and v ∈ V . Then the set N [v] = {u ∈ V | u is adjacent to v}∪{v} is the
closed neighborhood of v in G. A graph G is called reduced if no two vertices have the same closed
neighbourhood. If the graph is not reduced then we define an equivalence relation on the vertex
set V such that vi and vj are equivalent if and only if vi and vj have the same (closed) neighbors
3

in V . Each equivalence class under this relation is called a block of G. For any vertex v ∈ V we
denote the equivalence class containing v by B(v). Let the blocks of G be B1G , B2G , . . . , BtG (or
sometimes just B1 , B2 , . . . , Bt ). So, the collection of blocks is a partition of V . The reduced graph
e = (Ve , E))
e is the graph obtained by merging all the vertices that are in the
of G (denoted by G
same equivalence class.
If M is a (0, 1)-matrix, then we say M satisfies the consecutive 1’s property if in each row and
column, 1’s appear consecutively [17, 24]. We will denote by A(G) the augmented adjacency matrix
of the graph G, in which all the diagonal entries are 1 and non-diagonal elements are same as the
adjacency matrix of G.

1.2
1.2.1

Background Materials
PQ-trees

In the past few decades many variations of interval graphs has been studied mostly in context of
modeling different scenario arising from molecular biology and DNA sequencing. Understanding the
structure and properties of these classes of graphs and designing efficient recognition algorithms are
the central problems in this field. Many times this studies have led to nice combinatorial problems
and development of important data structures.
For example, the original linear time recognition algorithm for interval graphs by Booth and
Lueker [4] in 1976 is based on their complex PQ tree data structure (also see [3]). Habib et
al. [14] in 2000 showed how to solve the problem more simply using lexicographic breadth-first
search, based on the fact that a graph is an interval graph if and only if it is chordal and its
complement is a comparability graph. A similar approach using a 6-sweep LexBFS algorithm is
described in Corneil, Olariu and Stewart [8] in 2010.
In this paper we will be using the data structure of PQ-trees quite extensively. PQ-trees are not
only used to check whether a given matrix satisfy the consecutive 1’s property, they also store all
the possible permutations such that if one permuted the rows (or column) using the permutations,
the matrix would satisfy the consecutive 1’s property. We define a generalization of the problem of
checking consecutive 1’s property to a problem called Oriented-consecutive 1’s problem and show
how the PQ-tree representation can be used to solve this problem also. Details are available in
Section 4.

4

Index

Properties

References

1

G is a Proper Interval Graph.

2

G is a Unit Interval Graph

3

G is claw-free, i.e., G does not contain K1,3 as an induced subgraph.

4

For all v ∈ V , elements of N [v] = {u ∈ V | uv ∈ E} ∪ {v} are

[27, 28, 29, 30, 12]

consecutive for some ordering of V (closed neighborhood condition).
5

There is an ordering v1 , v2 , · · · , vn of V such that
G has a proper interval graph representation
{Ivi = [ai , bi |i = 1, 2, · · · , n} where a1 < a2 < · · · < an

[6, 7, 8, 12]

and b1 < b2 < · · · < bn .
6

There is an ordering of V such that the augmented
adjacency matrix A(G) of G satisfies the consecutive 1’s property.

7

A straight enumeration of G is a linear ordering of blocks
(vertices having same closed neighborhood) in G, such that
for every block, the block and its neighboring blocks are

[9, 15, 16, 25]

consecutive in the ordering.

G has a straight enumeration
which is unique up to reversal, if G is connected.
8

e is obtained from G
The reduced graph G
by merging vertices having same closed neighborhood.
G(n, r) is a graph with n vertices x1 , x2 , . . . , xn such that
xi is adjacent to xj if and only if 0 < |i − j| 6 r, where r is a positive integer.

[19]

e is an induced subgraph of G(n, r)
G
for some positive integers n, r with n > r.
Table 1: Characterizations of proper interval graphs: equivalent conditions on an interval graph G = (V, E).

5

1.2.2

Proper Interval Graphs

For proper interval graphs we have a number of equivalent characterizations. Recall that a proper
interval graph G is an interval graph in which there is an interval representation of G such that
no interval contains another properly and such an interval representation is called a proper interval
representation of G. It is important to note that a proper interval graph G may have an interval
representation which is not proper. Linear-time recognition algorithms for proper interval graphs
are obtained in [9, 10, 15, 16]. A unit interval graph is an interval graph in which there is an
interval representation of G such that all intervals have the same length. Interestingly, these two
concepts are equivalent. Another equivalence is that an interval graph is a proper interval graph if
and only if it does not conatin K1,3 as an induced subgraph. Apart from these, there are several
other characterizations of proper interval graphs (see Table 1). Among them we repeatedly use the
following equivalent conditions in the rest of the paper:
Theorem 1.3. Let G = (V, E) be an interval graph. then the following are equivalent:
1. G is a proper interval graph.
2. There is an ordering of V such that for all v ∈ V , elements of N [v] are consecutive (the closed
neighborhood condition).
3. There is an ordering of V such that the augmented adjacency matrix A(G) of G satisfies the
consecutive 1’s property.
4. There is an ordering {v1 , v2 , . . . , vn } of V such that G has a proper interval representation
{Ivi = [ai , bi ] | i = 1, 2, . . . , n} where ai 6= bj for all i, j ∈ {1, 2, . . . , n}, a1 < a2 < · · · < an
and b1 < b2 < · · · < bn .
Remark 1.4. We note that in a proper interval graph G = (V, E), the ordering of V that satisfies
any one of the conditions (2), (3) and (4) in the above theorem also satisfies the other conditions
among them.
1.2.3

Relation between PTPIG and other variants

A very similar definition to the TPIG is the class of graphs called probe interval graphs. A graph
G = (V, E) is a probe interval graph (in short, PIG) if the vertex set V can be partitioned into two
disjoint sets probe vertices P and nonprobe vertices N and one can map each vertex into an interval
on the real line (vertex x ∈ V mapped to Ix ) such that there is an edge between two vertices x
and y if at least one of them is in P and their corresponding intervals Ix and Iy intersect. When
6

the interval representation is proper (i.e., no interval is properly contained in another interval) the
graph is called a probe proper interval graph (briefly, PPIG). Clearly PPIG is a subclass of PIG. The
concept of PIG was introduced by Zhang [37] in 1994 in an attempt to aid a problem called cosmid
contig mapping. Recognition algorithms for PIG can be found in [18, 20, 21]. A characterization
of probe interval graphs in terms of adjacency matrix was obtained in [11]. For more information
about PIG, see [5, 13, 26, 22, 23]. Only recently, Nussbaum [25] presented the first recognition
algorithms for PPIG.
While the definition of PIG is very similar to that of TPIG, the two classes of graphs are not comparable [34]. But PPIG is a proper subclass of PTPIG. In fact, since in an interval representation of
PPIG, no interval contains other properly, there is an edge between a probe and nonprobe vertices
if and only if an end point of the interval corresponding to the probe vertex belongs to the interval
corresponding the nonprobe vertex.
On the other hand, K1,3 with a single nonprobe at the center cannot be a PPIG for otherwise it
would be a proper interval graph (as any probe interval graph with a single nonprobe vertex is an
interval graph). But it is a PTPIG by choosing three disjoint intervals for probe vertices and an
interval containing all of them corresponding to the nonprobe vertex. As K1,3 is an interval graph,
it is an example of PIG and PTPIG, but not a PPIG.
Similarly, C4 with a single nonprobe vertex is a PTPIG with an interval representation {[1, 3], [2, 5], [4, 6]}
for probes and [3, 4] for a nonprobe, but this is not a PIG (for otherwise it would be an interval
graph). Now consider the graph G1 in Figure 1. That G1 is a PIG and TPIG follows from the
interval representation described in Figure 2. But G1 is not a PTPIG as the subgraph induced by
probe vertices is K1,3 which is not a proper interval graph.

1.3

Organization of the paper

The first section contains definitions, preliminaries and examples. Also we fix some notations in
Subsebtion 1.1 which we will use for the rest of the paper. In section 2, we introduce the concepts
n2
p3

p4
p1

n1

n3
p2

Figure 1: The graph G1 .

7

1 2 3 45 6 7 8 9

32

p2
n1
p1
n3
p3
n2
p4

Figure 2: Interval representation of the graph G1 in Figure 1.
of a canonical sequence of a proper interval graph and study the structural properties of the
sequence. Section 3 contains the details of the graph class PTPIG. In this section we provide the
main characterization theorem for PTPIG (cf. Theorem 3.4) with illustrative examples and more
structural properties of the canonical sequence in context of a PTPIG which are used to develop
the recognition algorithm presented in the next section. In Section 4, a linear time recognition
algorithm for PTPIG is obtained gradually special to the most general case in three subsections.
We put some concluding remarks and bibliography at the end of the paper.

2

Canonical Sequence of Proper Interval Graphs

Let G be a proper interval graph. Then there is an ordering of V that satisfies conditions (2), (3)
and (4) of Theorem 1.3. Henceforth we call such an ordering, a natural or canonical ordering of
V . But this canonical ordering is not unique. A proper interval graph may have more than one
canonical orderings of its vertices. Interestingly, it follows from Corollary 2.5 of [9] (also see [25])
that the canonical ordering is unique up to reversal for a connected reduced proper interval graph.
Definition 2.1. Let G = (V, E) be a proper interval graph. Let {v1 , v2 , . . . , vn } be a canonical
ordering of the set V with the interval representation be {Ivi = [ai , bi ] | i = 1, 2, . . . , n} where ai 6= bj
for all i, j ∈ {1, 2, . . . , n}, a1 < a2 < · · · < an and b1 < b2 < · · · < bn . Now we combine all ai
and bi (i = 1, 2, . . . , n) in an increasing sequence which we call the interval canonical sequence with
respect to the canonical ordering of vertices of G and is denoted by IG .
Now if we replace ai or bi by i for all i = 1, 2, . . . , n in IG , then we obtain a sequence of integers
belonging to {1, 2, . . . , n} each occurring twice. We call such a sequence a canonical sequence of
G with respect to the canonical ordering of vertices of G and is denoted by SG . Moreover, if we
replace i by vi for all i = 1, 2, . . . , n in SG , then the resulting sequence is called a vertex canonical
sequence of G (corresponding to the canonical sequence SG ) and is denoted by VG .
Note that SG and its corresponding VG and IG can all be obtained uniquely from each other. Thus
by abuse of notations, sometimes we will use the term canonical sequence to mean any of these.
8

[2, 4]

[3, 9]

[6, 12]

[7, 14]

[8, 17]

[10, 20]

[16, 24]

[22, 28]

v1

v2

v3

v4

v5

v6

v7

v8

[2, 4]

v1

1

1

0

0

0

0

0

0

[3, 9]

v2

1

1

1

1

1

0

0

0

[6, 12]

v3

0

1

1

1

1

1

0

0

[7, 14]

v4

0

1

1

1

1

1

0

0

[8, 17]

v5

0

1

1

1

1

1

1

0

[10, 20]

v6

0

0

1

1

1

1

1

0

[16, 24]

v7

0

0

0

0

1

1

1

1

[22, 28]

v8

0

0

0

0

0

0

1

1

Table 2: The augmented adjacency matrix A(G) of the graph G in Example 2.2

2.1

Example of Canonical Sequence

Example 2.2. Consider the proper interval graph G = (V, E) whose augmented adjacency matrix
A(G) along with a proper interval representation is given in Table 2. Note that vertices of G are
arranged in a canonical ordering as A(G) that satisfies the consecutive 1’s property. Let [ai , bi ] be
the interval corresponding to the vertex vi for i = 1, 2, . . . , 8. Then
a1 a2

a3

a4

a5

a6

a7

2

3

6

7

8

10 16 22

b1

b2

b3

b4

b5

b6

4

9

12 14 17 20 24 28

b7

a8
b8

Then the interval canonical sequence combining ai and bi is given by
IG = (a1 , a2 , b1 , a3 , a4 , a5 , b2 , a6 , b3 , b4 , a7 , b5 , b6 , a8 , b7 , b8 ).
Therefore the canonical sequence and the vertex canonical sequence with respect to the given
canonical vertex ordering is
SG = (1 2 1 3 4 5 2 6 3 4 7 5 6 8 7 8) and VG = (v1 v2 v1 v3 v4 v5 v2 v6 v3 v4 v7 v5 v6 v8 v7 v8 ).

2.2

Structure of the Canonical Sequence for Proper Interval Graphs

If a graph G is a reduced proper interval graph then the following lemma states that the canonical
sequence for G is unique upto reversal.
Lemma 2.3. Let G = (V, E) be a proper interval graph and V = {v1 , v2 , . . . , vn } be a canonical
ordering of vertices of G. Then the canonical sequence SG is independent of proper interval representations that satisfies the given canonical ordering. Moreover SG is unique up to reversal for
connected reduced proper interval graphs.
9

v1

v2

v3

v4

v5

v6

v7

v8

v1

1

1

0

v2

1

1

1

0

0

1

1

0

0

0

0

0

v3

0

1

1

1

0

1

1

0

0

v4

0

v5

0

1

1

1

1

1

1

1

0

0

1

1

1

1

0

v6
v7

0

0

0

0

1

1

1

1

1

0

0

0

1

1

1

1

v8

0

0

0

0

0

0

1

1

Table 3: The matrix A(G) of the graph G in Example 2.2 with its stair partition.
Proof. Let {Ivi = [ai , bi ] | i = 1, 2, . . . , n} and {Jvi = [ci , di ] | i = 1, 2, . . . , n} be two proper interval
representations of G that satisfy the given canonical ordering. Now for any i < j, aj < bi if and
only if vi is adjacent to vj if and only if cj < di . Thus the canonical sequence SG is independent
of proper interval graph representations. Now since the canonical ordering is unique up to reversal
for a connected reduced proper interval graph, the canonical sequence SG is unique up to reversal
for connected reduced proper interval graphs.
Now there is an alternative way to get the canonical sequence directly from the augmented adjacency
matrix. Let G = (V, E) be a proper interval graph with V = {vi | i = 1, 2, . . . , n} and A(G) be the
augmented adjacency matrix of G with consecutive 1’s property. We partition positions of A(G)
into two sets (L, U ) by drawing a polygonal path from the upper left corner to the lower right
corner such that the set L [resp. U ] is closed under leftward or downward [respectively, rightward
or upward] movement (called a stair partition [1, 31, 32]) and U contains precisely all the zeros
right to the principal diagonal of A(G) (see Table 3). This is possible due to the consecutive 1’s
property of A(G). Now we obtain a sequence of positive integers belonging to {1, 2, . . . , n}, each
occurs exactly twice, by writing the row or column numbers as they appear along the stair. We call
this sequence, the stair sequence of A(G) (see Table 4) and note that it is same as the canonical
sequence of G with respect to the given canonical ordering of vertices of G.
Proposition 2.4. Let G = (V, E) be a proper interval graph with a canonical ordering V =
{v1 , v2 , . . . , vn } of vertices of G. Let A(G) be the augmented adjacency matrix of G arranging
vertices in the same order as in the canonical ordering. Then the canonical sequence SG of G is
the same as the stair sequence of A(G).
Proof. We show that the stair sequence is a canonical sequence for some proper interval representation and so the proof follows by the uniqueness mentioned in Lemma 2.3. Given the

10

v1

v1

v2

v3

1

2

1

v2

3

v4

v5

4

5

v3

v6

v7

v8

2
6

3

v4

4

v5

7

5

v6

6

v7

8

v8

7
8

Table 4: The stair sequence (1 2 1 3 4 5 2 6 3 4 7 5 6 8 7 8) of A(G) of the graph G in Example
2.2.
matrix A(G), a proper interval representation of G is obtained as follows.
bi = U (i) + 1 −

1
i

Let ai = i and

where U (i) = max {j | j ≥ i and vi vj = 1 in A(G)} for each i = 1, 2, . . . , n.

Then {Ivi = [ai , bi ] | i = 1, 2, . . . , n} is a proper interval representation of G. [9, 15] If U (1) > 1,
to make all the end points distinct, we slightly increase the value of b1 (which is the only integer
valued right end point and is equal to aU (1) ) so that it is still less than its nearest end point which
is greater than it. Now we get a proper interval representation of G that satisfies the condition 4 of
Theorem 1.3. Then the canonical sequence merges with the stair sequence for this proper interval
representation of G as for i < j, aj = j < bi if and only if vi vj = 1 if and only if the column number
j appears before the row number i in the stair sequence.
Corollary 2.5. Let G = (V, E) be a connected proper interval graph. Then SG is unique up to
reversal.
e = (Ve , E)
e
Proof. By Lemma 2.3, the result is true if G is reduced. Suppose G is not reduced and G
be the reduced graph of G having vertices v˜1 , . . . , v˜t corresponding to the blocks B1 , . . . , Bt of G.
e has unique canonical ordering of vertices up to reversal. Consider any of these orderings.
Now G
When blocks of G are arranged according to this order in its augmented adjacency matrix A(G),
we have same rows (and hence same columns) for vertices in the same block. Thus permutation of
vertices within the same block does not change the matrix. Let bi = |Bi | for each i = 1, 2, . . . , t.
e it is clear that SG is obtained uniquely from S e
Then considering the stair sequences of G and G,
G

by replacing each i by the subsequence
i−1
i−1
i−1
X
X
X
(
bj + 1,
bj + 2, . . . ,
bj + bi )
j=1

j=1

j=1

irrespective of the permutations of vertices within a block.
11

Figure 3: The graph Gb and its TPIG representation [34]

e be the
Remark 2.6. Let G be a connected proper interval graph which is not reduced and G
e has a unique (upto reversal) canonical ordering of vertices,
reduced graph of G. Then the graph G
say, b1 , . . . , bt (corresponding to the blocks B1 , . . . , Bt ) as it is connected and reduced. Now the
canonical orderings of the vertices of G are obtained from this ordering (and its reversal) by all
possible permutation of the vertices of G within each block. In all such cases SG will remain same
up to reversal.

3

Structure of PTPIG

Let us recall the definition of proper tagged probe interval graph.
Definition 3.1. A tagged probe interval graph G = (P, N, E) is a proper tagged probe interval graph
(briefly PTPIG) if G has a TPIG representation {Ix | x ∈ P ∪ N } such that {Ip | p ∈ P } is a proper
interval representation of GP . We call such an interval representation a PTPIG representation of
G.
It is interesting to note that there are examples of T P IG, G for which GP is a proper interval
graph but G is not a P T P IG. For example, the graph Gb (see Figure 3) in [34] is a TPIG in which
(Gb )P consists of a path of length 4 along with 2 isolated vertices which is a proper interval graph.
But Gb has no TPIG representation with a proper interval representation of (Gb )P .
Now let us consider a graph G = (V, E), in general, with an independent set N and P = V r N
such that the subgraph GP of G induced by P is a proper interval graph. Let us order the vertices
of P in a canonical ordering. Now the adjacency matrix of G looks like the following:
P

N

P

A(P )

A(P, N )

N

A(P, N )T

0

12

Note that the (augmented) adjacency matrix A(P ) of GP satisfies the consecutive 1’s property and
the P × N submatrix A(P, N ) of the adjacency matrix of G represents edges between probe vertices
and nonprobe vertices. In the following lemma we obtain a necessary condition for a PTPIG.
Lemma 3.2. Let G = (P, N, E) be a PTPIG. Then for any canonical ordering of the vertices
belonging to P each column of A(P, N ) can not have more than two consecutive stretches of 1’s.
Proof. Let us prove by contradiction. Consider a canonical ordering of vertices belonging to P , say,
{u1 , u2 , . . . , um }. Let wj be a vertex in N such that in the matrix A(P, N ) the column corresponding
to wj has at least three consecutive stretches of 1’s. That is, there are five vertices in P , say
ui1 , ui2 , ui3 , ui4 and ui5 (with i1 , i2 , i3 , i4 , i5 ∈ {1, 2, . . . , m}) such that i1 < i2 < i3 < i4 < i5 and
ui1 , ui3 and ui5 are neighbors of wj while ui2 and ui4 are not neighbors of wj . Now let us prove its
impossibility. We prove it case by case.
Let the interval corresponding to the vertex vik be Ivik = [`k , rk ] for k = 1, 2, 3, 4, 5 in a PTPIG
representation. Now by Theorem 1.3, we have `1 < `2 < `3 < `4 < `5 and r1 < r2 < r3 < r4 < r5 .
Since G is a PTPIG either `i ∈ Iwj or ri ∈ Iwj for each j = 1, 3, 5.
Case 1 (`1 , `5 ∈ Iwj ): In this case, for t such that i1 ≤ t ≤ i5 , we have `t ∈ Iwj . In particular we
have `2 and `4 are in Iwj , i.e., ui2 and ui4 are neighbors of wj which is a contradiction.
Case 2 (r1 , r5 ∈ Iwj ): In this case, for all t such that i1 ≤ t ≤ i5 , we have rt ∈ Iwj . And again here
we have a contradiction just like the previous case.
Case 3 (`1 , r5 ∈ Iwj but r1 , `5 ∈
/ Iwj ): Let Iwj be [`wj , rwj ]. So in this case, a5 < `wj 6 a1 which is
a contradiction.
Case 4 (r1 , `5 ∈ Iwj ): If `3 ∈ Iwj , then `t ∈ Iwj for all t ∈ {i3 , . . . , i5 and this would mean that
`4 ∈ Iwj which is a contradiction. Similarly, if r3 ∈ Iwj , then rt ∈ Iwj for all t ∈ {i1 , . . . , i3 }
and then r2 ∈ Iwj which also gives a contradiction.
Note that all the cases are taken care of and thus each column of A(P, N ) can not have more than
two consecutive stretches of 1’s.
Unfortunately the condition in the above lemma is not sufficient as the following example shows. For
convenience, we say an interval Ip = [a, b] contains strongly an interval In = [c, d] if a < c 6 d < b,
where p ∈ P and n ∈ N .1
1

In [36], Sheng et al. used the term “contains properly” in this case. Here we consider a different term in order to
avoid confusion with the definition of proper interval graph. Note that if a 6 c 6 d < b or a < c 6 d 6 b, then also
Ip contains In properly, but not strongly.

13

p1

p2

p3

p4

p5

p6

n1

n2

p1

1

1

0

0

0

0

p2

1

1

1

1

0

0

p1

0

0

p2

1

p3

0

1

1

1

0

0

0

p3

0

0

p4

0

1

1

1

p5

0

0

0

1

1

0

p4

1

1

1

1

p5

1

1

p6

0

0

0

0

1

1

p6

0

1

Table 5: The matrix A(P ) (left) and A(P, N ) (right) of the graph G in Example 3.3
Example 3.3. Consider the graph G = (V, E) with an independent set N = {n1 , n2 } and P =
V r N = {p1 , p2 , . . . , p6 }, where the matrices A(P ) and A(P, N ) are given in Table 5. We note
that A(P ) satisfies consecutive 1’s property. So GP is a proper interval graph by Theorem 1.3.
Also note that GP is connected and reduced. Thus the given ordering and its reversal are the
only canonical ordering of vertices of GP by Lemma 2.3. Suppose G is a PTPIG with an interval
representation {Ix | x ∈ V }, where Ipi = [ai , bi ] and In1 = [c, d] such that a1 < a2 < · · · < a6 and
b1 < b2 < · · · < b6 .
Since p2 n1 = 1, we have either a2 ∈ [c, d] or b2 ∈ [c, d]. Let a2 ∈ [c, d]. Now a4 ∈ [c, d] implies
a3 ∈ [c, d]. But p3 n1 = 0, which is a contradiction. Thus b4 ∈ [c, d] and a4 ∈
/ [c, d]. But then we
have a4 < c 6 a2 as a4 < b4 , which is again a contradiction. Again b2 , b4 ∈ [c, d] would imply
b3 ∈ [c, d] and consequently p3 n1 = 1. Thus we must have b2 , a4 ∈ [c, d] and [a3 , b3 ] contains [c, d]
strongly as a2 < a3 < a4 and b2 < b3 < b4 . Again p5 n1 = 1 implies [c, d] ∩ {a5 , b5 } 6= ∅. But
p3 p5 = 0 which implies [a3 , b3 ] ∩ [a5 , b5 ] = ∅. Thus a3 < b3 < a5 < b5 as a3 < a5 . But then
[c, d] ∩ {a5 , b5 } = ∅ (as [c, d] $ [a3 , b3 ]) which is a contradiction. Similar contradiction would arise
if one considers the reverse ordering of vertices of GP . Therefore G is not a PTPIG, though each
column of A(P, N ) does not have more than two consecutive stretches of 1’s.
The following is a characterization theorem for a PTPIG. For convenience, henceforth, a continuous
stretch (subsequence) in a canonical sequence will be called a substring.
Theorem 3.4. Let G = (V, E) be a graph with an independent set N and P = V rN such that GP ,
the subgraph induced by P is a proper interval graph. Then G is a proper tagged probe interval graph
with probes P and nonprobes N if and only if there is a canonical ordering of vertices belonging to
P such that the following condition holds:
(A) for every nonprobe vertex w ∈ N , there is a substring in the canonical sequence with respect
to the canonical ordering such that all the vertices in the substring are neighbors of w and all
the neighbors of w are present at least once in the substring.
14

Proof. Necessary condition: Let G = (V, E) be a PTPIG with probes P and nonprobes N such that
V = P ∪ N . Let {Ix = [`x , rx ] | x ∈ V } be a PTPIG representation of G such that {Iu | u ∈ P } be
a proper interval representation of GP . Then a probe vertex u ∈ P is adjacent to w ∈ N if and
only if `u ∈ Iw or ru ∈ Iw . Let u1 , u2 , . . . , up be a canonical ordering of vertices in P that satisfies
the conditions of Theorem 1.3. Now consider the corresponding canonical sequence SGP , i.e., the
combined increasing sequence of `ui and rui for i = 1, 2, . . . , p. Since the sequence is increasing
and Iw is an interval all the `ui ’s and rui ’s which are belonging to Iw occur consecutively in that
sequence. Thus for any w ∈ N there exists a substring of SGP such that all the vertices in the
substring are neighbors of w and all the neighbors of w are present at least once in the substring.
Sufficiency condition: Let G = (V, E) be a graph with an independent set N and P = V r N
such that GP , the subgraph induced by P is a proper interval graph, P = {u1 , u2 , . . . , up } and
N = {w1 , w2 , . . . , wq }. Suppose there is a canonical ordering u1 , u2 , . . . , up of vertices belonging to
P such that for any nonprobe veretex w ∈ N , there is a substring in the canonical sequence S = SGP
with respect to this canonical ordering such that all the vertices in the substring are neighbors of w
and all the neighbors of w are present at least once in the substring. Let us count the positions of
each element in S from 1 to 2p. Now for each probe vertex ui , we assign the closed interval [`ui , rui ]
such that `ui and rui are position numbers of first and second occurrences of i in S respectively.
By definition of a canonical sequence, we have `u1 < `u2 < · · · < `up and ru1 < ru2 < · · · < rup .
Also since all position numbers are distinct, `ui 6= ruj for all i, j ∈ {1, 2, . . . , p}. Thus this interval
representation obeys the given canonical ordering of vertices belonging to P and by construction
the canonical sequence with respect to it is same as S.
We show that this interval representation is indeed an interval representation of GP which is proper.
Let i < j, i, j ∈ {1, 2, . . . , p}. Then `ui < `uj and rui < ruj . Thus none of [`ui , rui ] and [`uj , ruj ]
contains other properly. Now ui is adjacent to uj in GP if and only if ui uj = 1 in A(P ) when
vertices of A(P ) are arranged as in the given canonical ordering. Again ui uj = 1 with i < j if and
only if j is lying between two occurrences of i in the stair sequence of A(P ) and hence in S by
Proposition 2.4. Also since i < j, the second occurrence of j is always after the second occurrence
of i in S. Thus ui uj = 1 with i < j if and only if `uj ∈ [`ui , rui ]. This completes the verification
that {[`ui , rui ] | i = 1, 2, . . . , p} is a proper interval representation of GP and that corresponds to
S.
Next for each j = 1, 2, . . . , q, consider the substring in the canonical sequence S such that all the
vertices in the substring are neighbors of wj and all the neighbors of wj are present at least once
in the substring. Let the substring start at `wj and end at rwj in S. Then we assign the interval
15

[`wj , rwj ] to the vertex wj . If wj is an isolated vertex, then we assign a closed interval whose
end points are greater than `ui and rui for all i = 1, 2, . . . , p. Now all we need to show is that

{[`ui , rui ] | i = 1, 2, . . . , p} ∪ [`wj , rwj ] | j = 1, 2, . . . , q is a PTPIG representation of G, i.e., if ui
is a probe vertex and wj is a nonprobe vertex then there is an edge between them if and only if
either `ui ∈ [`wj , rwj ] or rui ∈ [`wj , rwj ].
First let us assume that there is an edge between ui and wj . So the vertex ui must be present
in the substring of S that contains all the neighbors of wj and contains only the neighbors of wj .
Since `wj and rwj are the beginning and ending positions of the substring respectively, either `ui or
rui must be in the interval [`wj , rwj ]. Conversely, let either `ui ∈ [`wj , rwj ] or rui ∈ [`wj , rwj ]. Then
we have either `ui or rui must be present in the substring. Since the substring contains vertices
that are neighbors of wj , we have ui must be a neighbor of wj .
Remark 3.5. If G is a PTPIG such that GP is connected and reduced, then there is a unique
(up to reversal) canonical ordering of vertices belonging to P , as we mentioned at the beginning of
Section 2. Thus the corresponding canonical sequence is also unique up to reversal. Also if condition
(A) holds for a canonical sequence, it also holds for its reversal. Thus in this case condition (A)
holds for any canonical ordering of vertices belonging to P .

p1

p2

p3

p4

p5

p6

p7

p8

n1

n2

n3

n4

n5

n6

p1

1

1

0

0

0

0

0

0

p1

0

0

0

1

0

1

p2

1

1

1

1

1

0

0

0

p2

1

1

0

1

0

1

p3

0

1

1

1

1

1

0

0

p3

0

1

0

1

0

1

p4

0

1

1

1

1

1

0

0

p4

0

1

1

1

0

1

p5

0

1

1

1

1

1

1

0

p5

1

1

1

1

0

1

p6

0

0

1

1

1

1

1

0

p6

1

1

1

1

0

1

p7

0

0

0

0

1

1

1

1

p7

0

0

1

0

0

1

p8

0

0

0

0

0

0

1

1

p8

0

0

1

0

0

1

Table 6: The matrix A(P ) and A(P, N ) of the graph G in Example 3.6

Let us illustrate the above theorem by the following example.
Example 3.6. Consider the graph G = (V, E) with an independent set N = {n1 , n2 , . . . , n6 }
and P = V r N = {p1 , p2 , . . . , p8 }, where the matrices A(P ) and A(P, N ) are given in Table
6. First note that A(P ) satisfies consecutive 1’s property. So GP is a proper interval graph.
Secondly, each column of A(P, N ) does not have more than two consecutive stretches of 1’s. Now
16

the S = SGP = (1 2 1 3 4 5 2 6 3 4 7 5 6 8 7 8). The required substrings of probe neighbors for
nonprobe vertices n1 , n2 , . . . , n6 are (5 2 6), (3 4 5 2 6 3 4), (4 7 5 6 8 7 8), (1 2 1 3 4 5 2 6 3 4),
∅, S respectively. Note that G is indeed a PTPIG with an interval representation shown in Table
7 which is constructed by the method described in the sufficiency part of Theorem 3.4.
Now consider the graph G in Example 3.3 which is not a PTPIG. From Table 5 we compute
S = S(GP ) = (1 2 1 3 4 2 3 5 4 6 5 6). The graph GP is connected and reduced. So S is unique up
to reversal. Note that the nonprobe vertex n1 is adjacent to probe vertices {p2 , p4 , p5 } and there is
no substring in S containing only {2, 4, 5}.
Definition 3.7. Let G = (V, E) be a graph with an independent set N and P = V r N such that
GP , the subgraph induced by P is a proper interval graph. Let SGP be a canonical sequence of
GP . Let w ∈ N . If there exists a substring in SGP which contains all the neighbors of w and all
the vertices in the substring are neighbors of w then we call the substring a perfect substring of w
in G. If the canonical sequence SGP contains a perfect substring of w in SGP for all w ∈ N , we call
it a perfect canonical sequence for G.
Proposition 3.8. Let G = (P, N, E) be a PTPIG such that GP is a connected reduced proper
interval graph and SGP be a canonical sequence of GP . Then for any nonprobe vertex w ∈ N , there
cannot exist more than one disjoint perfect substrings of w in SGP , unless the substring consists of
a single element.
Proof. Let u1 , u2 , . . . , up be the canonical ordering of the probe vertices of G with the proper interval
representation {[`i , ri ] | i = 1, 2, . . . , p} that satisfies the condition 4 of Theorem 1.3 and S be the
corresponding canonical sequence SGP . We first note that, since each vertex in S appears twice,
there cannot be more than two disjoint perfect substrings of S.
Now suppose there is a nonprobe vertex, say, w in G such that there are two disjoint perfect
substrings of length greater than 1. We will refer to these substrings as the first substring and

[1, 3]
[2, 7]
[4, 9]
[5, 10]
[6, 12]
[8, 13]
[11, 15]
[14, 16]

p1
p2
p3
p4
p5
p6
p7
p8

[1, 3]
p1
1
1
0
0
0
0
0
0

[2, 7]
p2
1
1
1
1
1
0
0
0

[4, 9]
p3
0
1
1
1
1
1
0
0

[5, 10]
p4
0
1
1
1
1
1
0
0

[6, 12]
p5
0
1
1
1
1
1
1
0

[8, 13]
p6
0
0
1
1
1
1
1
0

[11, 15]
p7
0
0
0
0
1
1
1
1

[14, 16]
p8
0
0
0
0
0
0
1
1

[6, 8]
n1
0
1
0
0
1
1
0
0

[4, 10]
n2
0
1
1
1
1
1
0
0

[10, 16]
n3
0
0
0
1
1
1
1
1

[1, 10]
n4
1
1
1
1
1
1
0
0

[17, 17]
n5
0
0
0
0
0
0
0
0

[1, 16]
n6
1
1
1
1
1
1
1
1

Table 7: A proper tagged probe interval representation of the graph G in Example 3.6
17

second substring corresponding to the relative location of the substrings in S. Now in S, each
number i appears twice due to li and ri only. Thus if we think of the canonical sequence as an
ordering of `i ’s and ri ’s, then we have that the first substring contains all the `i ’s and the second
substring contains all the ri ’s for all the probe vertices ui those are neighbors of w, as `i < ri and
both substrings contain all numbers i such that ui is a neighbor of w.
Moreover due to the increasing order of `i ’s and ri ’s, both the substrings contain numbers k, k +
1, . . . , k + r for some integers k, r with 1 6 k 6 m and 1 6 r 6 m − k. So the first substring must
comprise of some consecutive collection of `i and similarly for the second substring, i.e., the first
substring is `k , `k+1 , . . . , `k+r and the second substring is rk , rk+1 , . . . , rk+r (in IGP ). Therefore the
vertices uk , . . . , uk+r form a clique.
Now suppose ui is adjacent to uk+t for some i < k and 1 ≤ t ≤ r. Then `i < `k and `k+r < ri
as `k to `k+r are consecutive in the first substring (in IGP ). But this implies ui is adjacent to all
uk , uk+1 , . . . , uk+r . Similarly, one can show that if uj is adjacent to uk+t for some j > k + r and 1 ≤
t ≤ r. Then uj is adjacent to all uk , uk+1 , . . . , uk+r . Thus (closed) neighbors of uk , uk+1 , . . . , uk+r
are same in GP which contradicts the assumption that GP is reduced as r ≥ 1.
In fact, we can go one step more in understanding the structure of a PTPIG. If G is a PTPIG,
not only there cannot be two disjoint perfect substrings (of length more than 1) for any nonprobe
vertex in any canonical sequence but also any two perfect substrings for the same vertex must
intersect at atleast two places, except two trivial cases.
Lemma 3.9. Let G = (P, N, E) be a PTPIG such that GP is a connected reduced proper interval
graph with a canonical ordering of vertices {u1 , u2 , . . . , up } and let VGP be the corresponding vertex
canonical sequence of GP . Let w ∈ N be such that w has at least two neighbors in P and T1 and T2
be two perfect substrings for w in VGP intersecting in exactly one place. Then one of the following
holds:
1. VGP begins with u1 u2 u1 and only u1 and u2 are neighbors of w.
2. VGP ends with up up−1 up and only up−1 and up are neighbors of w.
Proof. Let [ai , bi ] be the interval corresponding to ui for i = 1, 2, . . . , p. Let the place where T1 and
T2 intersect be the first occurrence of the vertex uk .
Without loss of generality, let the substring T1 end with the first occurrence of uk and the substring
T2 start with the first occurrence of uk . Thus for all i > k, the vertex ui cannot appear before the

18

first occurrence of uk in the VGP . So T1 does not contain any ui such that i > k. Thus w is not a
neighbor of any ui such that i > k. Note that, it also means that for any vertex in the neighbor
of w (except for uk ) the substring T1 contains the first occurrence, while the substring T2 contains
the second occurrence. Thus the vertices in the neighborhood of w has to be consecutive vertices
in the canonical ordering of GP . Let the vertices in the neighborhood of w be uk−r , . . . , uk−1 , uk ,
where 1 ≤ r ≤ k − 1.
Now for any vertex ui such that i < k − r, we have ui is not in T1 and T2 . So the first occurrence
of ui is before the first occurrence of uk−r and the second occurrence of ui is either also before the
first occurrence of uk−r or after T2 , i.e., after the second occurrence of uk−r . But if the second
case happens, then we would violate the fact that GP is proper. So the only option is that both
the first and second occurrence of ui is before the first occurrence of uk−r and this would violate
the condition that the graph GP is connected. So the only option is there exists no ui such that
i < k − r. So k − r = 1. Thus we have the neighbors of w precisely u1 , . . . , uk .
Now if we look at the interval canonical sequence of GP , we have T1 corresponds to a1 , . . . , ak and
T2 corresponds to ak , b1 , . . . , bk−1 . But this would mean that all the vertices u1 , . . . , uk−1 have the
same (closed) neighborhood in GP which is not possible as we assumed GP is reduced, unless the
set {u1 , . . . , uk−1 } is a single element set. In that case, w has neighbors u1 and u2 and the T1 and
T2 correspond to a1 , a2 and a2 , b1 respectively (in IGP ). This is the first option in the Lemma. By
similar argument, if we assume that T1 and T2 intersect in the second occurrence of the vertex uk ,
we get the other option.
Now let us consider what happens when the graph GP induced by the probe vertices is not necessarily reduced. Let the blocks of GP be B1 , . . . , Bt . Then a canonical ordering of vertices in the
fP can be considered as a canonical ordering of blocks of GP and the corresponding
reduced graph G
canonical sequence SG
g can be considered as a canonical sequence of blocks of GP . Then a substring
P

in SG
g can also be called as a block substring. If there is a vertex in a block Bj that is a neighbor
P

of a nonprobe vertex w, we call Bj a block-neighbor of w. Also if a block substring contains all
the block neighbors of w and all the blocks in it are block-neighbors of w, then we call the block
substring a perfect block substring of w in SG
g . Then the following corollaries are immediate from
P

Proposition 3.8 and Lemma 3.9.
Corollary 3.10. Let G = (P, N, E) be a PTPIG such that GP is a connected proper interval graph.
fP . Then for any w ∈ N , there cannot exist
Let Sg be a canonical sequence for the reduced graph G
GP

more than one disjoint perfect block substrings of w in SG
g , unless the block substring consists of
P

a single element.
19

Corollary 3.11. Let G = (P, N, E) be a PTPIG such that GP is a connected proper interval
graph with a canonical ordering of blocks {B1 , B2 , . . . , Bt } and let VG
g be the corresponding vertex
P

canonical sequence of blocks of GP . Let w ∈ N be such that w has at least two block-neighbors in
GP and T1 and T2 be two perfect block substrings for w in VG
g intersecting in exactly one place.
P

Then one of the following holds:
1. VG
g begins with B1 B2 B1 and only B1 and B2 are block-neighbors of w.
P

2. VG
g ends with Bt Bt−1 Bt and only Bt−1 and Bt are block-neighbors of w.
P

4

Recognition algorithm

In this section, we present a linear time recognition algorithm for PTPIG. That is, given a graph
G = (V, E), and a partition of the vertex set into N and P = V r N we can check, in time
O(|V | + |E|), if the graph G(P, N, E) is a PTPIG. Now G = (P, N, E) is a PTPIG if and only if
it a TPIG, i.e., it satisfies the three conditions in Definition 1.1 and GP is a proper interval graph
for a TPIG representation of G. Note that it is easy to check in linear time if the graph G satisfies
the first condition, namely, if N is an independent set in the graph. Now for testing if the graph
satisfies the other two properties we will use the characterization we obtained in Theorem 3.4.
We will use the recognition algorithm for proper interval graph H = (V 0 , E 0 ) given by Booth and
Lueker [4] as a blackbox that runs in O(|V 0 | + |E 0 |). The main idea of their algorithm is that H
is a proper interval graph if and only if the adjacency matrix of the graph satisfies the consecutive
1’s property. In other words, H is a proper interval graph if and only if there is an ordering of
the vertices of H such that for any vertices v in H, the neighbors of v must be consecutive in that
ordering. So for every vertex v in H they consider restrictions, on the ordering of the vertices, of
the form “all vertices in the neighborhood of v must be consecutive”. This is done using the data
structure of P Q-trees. The PQ-tree helps to store all the possible orderings that respect all these
kind of restrictions. It is important to note that all the orderings that satisfy all the restrictions
are precisely all the canonical orderings of vertices of H.
The main idea of our recognition algorithm is that if the graph G = (P, N, E) is PTPIG then, from
Condition (A) in Theorem 3.4, we can obtain a series of restrictions on the ordering of vertices
that also can be “stored” using the PQ-tree data structure. These restrictions are on and above the
restrictions that we need to ensure the graph GP is a proper interval graph. If finally there exists
any ordering of the vertices that satisfy all the restrictions, then that ordering will be a canonical
ordering that satisfies the condition (A) in Theorem 3.4. So the main challenge is to identify all

20

the extra restrictions on the ordering and how to store them in the PQ-tree.
Once we have verified that the graph G = (P, N, E) satisfies the first condition in Definition 3.1
and we have stored all the possible canonical ordering of the vertices of the subgraph GP = (P, E1 )
of G induced by P in a PQ-tree (in O(|P | + |E1 |) time), we proceed to find the extra restrictions
that is necessary to be applied on the orderings. We present our algorithm in three steps - each
step handling a class of graphs that is a generalization of the class of graphs handled in the previous
one.
STEP

I: First we consider the case when GP is a connected reduced proper interval graph.

STEP II: Next we consider the case when GP is a connected proper interval graph, but not necessarily
reduced.
STEP III: Finally we consider the general case when the graph GP is a proper interval graph, but may
not be connected or reduced.
For all the steps we will assume that the vertices in P are v1 , . . . , vp , the vertices in N are w1 , . . . , wq
and Aj be the adjacency list of the vertex wj and let dj be the degree of the vertex wj . So the
neighbors of wj are Ai [1], Ai [2], . . . , Aj [dj ] for j = 1, 2, . . . , q.

4.1

Step I: The graph GP is a connected reduced proper interval graph

By Lemma 2.3, there is a unique (upto reversal) canonical ordering of the vertices of GP . By
Theorem 3.4, we know that the graph G is PTPIG if and only if the following condition is satisfied:
Condition (A1): For all 1 ≤ j ≤ q, there is a substring in SGP where only the neighbors of wj
appear and all the neighbors of wj appears at least once.
In this case, when the graph GP is connected reduced proper interval graph, since there is a unique
canonical ordering of the vertices, all we have to do is to check if the corresponding canonical
sequence satisfies the Condition (A1). So the rest of the algorithm in this case is to check if the
property is satisfied.
Idea of the algorithm: Since we know the canonical sequence SGP (or obtain by using known
algorithms described before in O(|P | + |E1 |) time, where E1 is the set of edges between probe
vertices), we can have two look up tables L and R such that for any vertex vi ∈ P , the L(vi ) and
R(vi ) has the index of the first and the second appearance of vi in SGP respectively. We can obtain
the look up tables in time O(|P |) steps.

21

Also by SGP [k1 , k2 ] (where 1 ≤ k1 ≤ k2 ≤ 2p) we will denote the substring of the canonical sequence
sequence SGP that start at the k1th position and ends at the k2th position in SGP .
To check the Condition (A1), we will go over all the wj ∈ N . For j ∈ {1, 2, . . . , q}, let L(Aj [1]) = `j
and R(Aj [1]) = rj . Now since all the neighbors of wj has to be in a substring, there must be
a substring of length at least dj and at most 2dj (as each number appears twice) in SGP [`j −
2dj , `j + 2dj ] or SGP [rj − 2dj , rj + 2dj ] which contains only and all the neighbors of wj . We can
identify all such possible substrings by first marking the positions in SGP [`j − 2dj , `j + 2dj ] and
SGP [rj − 2dj , rj + 2dj ] those are neighbors of wj and then by doing a double pass (Algorithm 1),
we find all the possible substrings of length greater than or equal to dj in SGP [`j − 2dj , `j + 2dj ]
and SGP [rj − 2dj , rj + 2dj ] that contains only neighbors of wj .
We prove the correctness and run-time of the algorithm in the following theorem:
Theorem 4.1. Let G = (V, E) be a graph with an independent set N and P = V r N such that
GP is a connected reduced proper interval graph. Then Algorithm 2 correctly decides whether G is
a PTPIG with probes P and nonprobes N in time O(|P | + |N | + |E2 |), where E2 is the set of edges
between probes P and nonprobes N .
Proof. For each j = 1, 2, . . . , q, we test the Condition (A1). In Line 3, ` and r are the first and
second appearance of the first probe neighbor of wj respectively. In Lines 4–9, we generate two (0, 1)
arrays X and Y , each of length 4dj +1. The probe neighbors of wj lying between [`−2dj , `+2dj ] are
marked 1 in X with positions translated by 2dj + 1 − `. Similarly Y is formed by marking 1 for the
probe neighbors of wj lying between [r − 2dj , r + 2dj ] and translated by 2dj + 1 − r. Translations are
required to avoid occurrence of a negative position. Then using Algorithm 1 we find all substrings
of probe neighbors of length greater than or equal to dj in Lines 10 and 15. Finally, in Lines
12–13 and 17–18, we check that whether the substring contains all probe neighbors of wj . Thus by
Theorem 3.4 and Remark 3.5, Algorithm 2 correctly decides whether G is a PTPIG with probes P
and nonprobes N by testing that whether the Condition A1 is satisfied.
Now we compute the running time. For each j = 1, 2, . . . , q, Algorithm 1 requires O(dj ) time. Also
Lines 4–9, 12 and 17 of Algorithm 2 require O(dj ) time. Other steps require constant times. Thus
Algorithms 1 and 2 run in O(|E2 | + |N |) times, where E2 is the set of edges between probes P and
nonprobes N and the look up tables L and R were obtained in O(|P |) time. Thus the total running
time is O(|P | + |N | + |E2 |).

22

Algorithm 1: Finding-1Subsequence
Input

: An array A[1, T ] containing only 0/1 entries, d (Assume A[T + 1] = 0).

Output : Output all (s, t) pairs such that t − s ≥ d and for all s ≤ i ≤ t, A[i] = 1,
(either s = 1 or A[s − 1] = 0) and (either t = T or A[t + 1] = 0).
1
2

Initialize ` = r = 0 while r ≤ T do
if A[r + 1] = 1 then
r =r+1

3
4

if A[r + 1] = 0 then
if r − ` ≥ d then

5

Output (` + 1, r)

6
7

`=r+1

8

r =r+1

Algorithm 2: Testing Condition (A1)
Input

: Given a graph G = (V, E)

Output : Accept if the Condition (A1) is satisfied
1

for j ← 1 to q do

2

Initialize two arrays X and Y of length 4dj + 1 by setting all the entries to 0.

3

Let ` = L(Aj [1]) and r = R(Aj [1]).

4

for each k ← 1 to dj do

5

Let s = L(Aj [k]) and t = R(Aj [k])

6

If (` − 2dj ≤ s ≤ ` + 2dj ) Mark X[s − ` + 2dj + 1] = 1

7

If (` − 2dj ≤ t ≤ ` + 2dj ) Mark X[t − ` + 2dj + 1] = 1

8

If (r − 2dj ≤ s ≤ r + 2dj ) Mark Y [s − r + 2dj + 1] = 1

9

If (r − 2dj ≤ t ≤ r + 2dj ) Mark Y [t − r + 2dj + 1] = 1

10

for all (a, b) output of Finding-1Subsequence(X, dj ) do

11

Let â = a + ` − 2dj − 1 and b̂ = b + ` − 2dj − 1.

12

if ∀1 ≤ k ≤ dj either â ≤ L(Aj [k]) ≤ b̂ or â ≤ R(Aj [k]) ≤ b̂ then

13

j =j+1

14

Go To Step 1

15

for all (a, b) output of Finding-1Subsequence(Y, dj ) do

16

Let â = a + r − 2dj − 1 and b̂ = b + r − 2dj − 1.

17

if ∀1 ≤ k ≤ dj either â ≤ L(Aj [k]) ≤ b̂ or â ≤ R(Aj [k]) ≤ b̂ then

18

j =j+1

19

Go To Step 1

20
21

REJECT
ACCEPT

Remark 4.2. Since given a graph G = (V, E) with an independent set N and P = V r N , the checking
whether GP = (P, E1 ) is a proper interval graph and obtaining SGP (from any proper interval representation
of GP ) requires O(|P | + |E1 |) time, the total recognition time is O(|P | + |N | + |E1 | + |E2 |) = O(|V | + |E|).

23

4.2

Step II: The graph GP is a connected (not necessarily reduced) proper
interval graph

In this case, that is when the graph GP is not reduced, we cannot say that there exists a unique
canonical ordering of the vertices of GP . So by Theorem 3.4, all we can say is that among the
set of canonical orderings of the vertices of GP , is there an ordering such that the corresponding
canonical sequence satisfies Condition (A) of Theorem 3.4? As mentioned before we will assume
that we have all the possible canonical ordering of the vertices of GP stored in a PQ-tree. Now we
will impose more constraints on the orderings so that the required condition is satisfied.
fP be the reduced graph of GP . By Remark 2.6, G
fP has a unique (upto reversal) canonical
Let G
ordering of vertices, say, b1 , . . . , bt (corresponding to the blocks B1 , . . . , Bt of the vertices of GP )
and the canonical orderings of the vertices of GP are obtained by all possible permutations of the
vertices of G within each block.
fP , we can have two look up tables
Since we know the canonical sequence SG
for the vertices in G
g
P
fP , L(bk ) and R(bk ) have the indices of the first and the
L and R such that for any vertex bk ∈ G
second appearance of bk in the SG
g respectively. Abusing notation, for any probe vertex v ∈ Bk ,
P

by L(v) and R(v) we will denote L(bk ) and R(bk ) respectively. We can obtain the look up tables
in time O(|P |) steps.
Definition 4.3. For any w ∈ N and any block Bk , we say that Bk is a block-neighbor of w if there
exists at least one vertex in Bk that is a neighbor of w. If all the vertices in Bk are neighbors of w,
we call Bk a full-block-neighbor of w and if there exists at least one vertex in Bk that is a neighbor
of w and at least one vertex of Bk that is not a neighbor of w we call it a partial-block-neighbor of
w. Also for any w ∈ N let us define



 0,
fw (k) =
1,


 2,

the function fw : {1, 2, . . . , t} → {0, 1, 2} as
if Bk is not a block-neighbor of w;
if Bk is a full-block-neighbor of w;
if Bk is a partial-block-neighbor of w.

By abuse of notation, for any probe vertex v ∈ Bk by fw (v) we will denote fw (k).
Note that for any wj ∈ N one can compute the function fwj in O(dj ) number of steps and can
store the function fwj in an array of size t.
4.2.1

Idea of the Algorithm

If G is PTPIG then from Condition (A) in Theorem 3.4 we can see that the following condition is
a necessary (though not a sufficient) condition:
24

Condition B1: For all 1 ≤ j ≤ q, there is a substring of SG
g where only the block-neighbors of
P

wj appear and all the block-neighbors of wj appear at least once and any block that is not at the
beginning or end of the substring must be a full-block-neighbor of wj .
Though the above Condition B1 is not a sufficient condition, but as a first step we will check
if the graph satisfies the Condition B1. For every wj ∈ N , we will identify (using algorithm
CheckConditionB1(wj )) all possible maximal substrings of SGP that can satisfy Condition B1.
If such a substring exists, then CheckConditionB1(wj ) outputs the block numbers that appear at
the beginning and end of the substring. Let for some wj , CheckConditionB1(wj ) outputs (k1 , k2 ),
then note that 1 ≤ k1 ≤ k2 ≤ t and k1 and k2 are the only possible partial neighbors of wj . The
algorithm CheckConditionB1(wj ) is very similar to the algorithm Testing Condition (A1) that
we described for the Step I, when we assumed GP is a connected reduced proper interval graph.
Now as we mentioned earlier the Condition (B1) is not sufficient for G to be a PTPIG. For G to be a
PTPIG (that is, to satisfy Condition (A) of Theorem 3.4) we will have to find a suitable canonical
ordering of the vertices or in other words, by Remark 2.6, we need to find suitable ordering of
vertices in each block. Depending on (k1 , k2 ) which is the output by CheckConditionB1(wj ), we
have a number of cases and for each of the cases some restrictions will be imposed on the ordering
of the vertices within blocks.
Let σ1 , . . . , σt be the ordering of the vertices of blocks B1 , B2 , . . . , Bt respectively. For every wj ∈ N ,
let us denote by N gbk (wj ), the vertices in the block Bk those are neighbors of wj . We list the
different cases and restriction on σ1 , . . . , σt that would be imposed in each of the cases when the
algorithm CheckConditionB1(wj ) outputs (k1 , k2 ).
• Category 0: There are no partial-block-neighbors of wj . In this case Condition (B1)
is sufficient.
• Category 1: There exists exactly one partial-block-neighbor of wj . Let k be the
block that is a partial-block-neighbor of wj . In this case we will have 4 subcategories:
– Category 1a: Bk is the only block-neighbor of wj . In that case, σk must ensure
that the vertices in N gbk (wj ) must be contiguous.
– Category 1b: All pairs returned by CheckConditionB1(wj ) is of the form
(k, k2 ) with k2 6= k. In that case, σk must ensure that the vertices in N gbk (wj ) must
be contiguous and must be flushed to the Right.
– Category 1c: All pairs returned by CheckConditionB1(wj ) is of the form
25

(k1 , k) with k1 6= k. In that case, σk must ensure that the vertices in N gbk (wj ) must
be contiguous and must be flushed to the Left.
– Category 1d: All other cases. In that case, CheckConditionB1(wj ) returns (k, k) or
returns both (k, k2 ) and (k1 , k). In both the cases σk must ensure that the vertices in
N gbk (wj ) must be contiguous and must either be flushed to the Left or to the Right.
• Category 2: There exists exactly two partial-block-neighbor of wj . Let k1 , k2 be the
two blocks which are partial-block-neighbors of wj . In this case we claim that the following
three cases may happen:
– Category 2a: {k1 , k2 } = {1, 2} and the SG
g begins with 121. In this case the
P

following two conditions must be satisfied:
∗ Condition 2a(1) σ1 must ensure that the vertices in N gb1 (wj ) are contiguous and
must be either flushed to the Right or Left and σ2 must ensure that the vertices in
N gb2 (wj ) are contiguous and must be either flushed to the Right or Left.
∗ Condition 2a(2) If the vertices in N gb1 (wj ) flushed to the Left then the vertices
of N gb2 (wj ) must be flushed to Right and if the vertices in N gb1 (wj ) flushed to the
Right then the vertices of N gb2 (wj ) must be flushed to the Left.
– Category 2b: {k1 , k2 } = {t−1, t} and the SG
g ends with t(t−1)t. Like the previous
P

condition, both the following two conditions must satisfied:
∗ Condition 2b(1) σt−1 must ensure that the vertices in N gbt−1 (wj ) are contiguous
and must be either flushed to the Right or Left and σt must ensure that the vertices
in N gbt (wj ) are contiguous and must be either flushed to the Right or Left.
∗ Condition 2b(2) If the vertices in N gbt−1 (wj ) flushed to the Left then the vertices
of N gbt (wj ) must be flushed to Right and if the vertices in N gbt−1 (wj ) flushed to
the Right then the vertices of N gbt (wj ) must be flushed to Left
– Category 2c: CheckConditionB1(wj ) outputs (k1 , k2 ). In this case (from Corollary 3.11) CheckConditionB1(wj ) cannot output both (k1 , k2 ) and (k2 , k1 ) unless in the
Category 2a and 2b. Thus in this case σk1 must ensure that the vertices in N gbk1 (wj )
are contiguous and is flushed to the Right and σk2 must ensure that the vertices in
N gbk2 (wj ) are contiguous and is flushed to the Left.
• Category 3: If for some wj , there are more than 2 partial block neighbors then G cannot
be a PTPIG.

26

Using algorithm CheckConditionB1(wj ) we can identify all the various kind of restrictions on
σ1 , . . . , σt those are necessary to be imposed so that G is a PTPIG. Note that if there exists
σ1 , . . . , σt such that the above restriction are satisfied for all wj , then G is a PTPIG. So our goal
is to check if there exists σ1 , . . . , σt such that the above restriction are satisfied for all wj .
For this we define a generalization of the consecutive 1’s problem (we call it the oriented-consecutive
1’s problem) and show how that can be used to store all the restrictions in the PQ-tree that already
stores all the restrictions which are imposed by the fact that GP is a proper interval graph. We
will first show how to handle all the conditions except for the special conditions Condition 2a(2) for
Category 2a and Condition 2b(2) for Category 2b. After we have successfully stored all the other
restrictions we will show how to handle these special conditions.
Note that except for these special conditions all the restrictions are of the following four kinds:
• All the vertices in N gbk (wj ) are consecutive and flushed to the left
• All the vertices in N gbk (wj ) are consecutive and flushed to the Right.
• All the vertices in N gbk (wj ) are consecutive and either flushed to the Left or flushed to the
Right.
• All the vertices in N gbk (wj ) are consecutive.
In the Section 4.2.2 we describe the Oriented-Consecutive 1’s problem and show how that can be
used to store all the above restrictions except for the special conditions mentioned above. The
following Lemma shows how to handle the special conditions Condition 2a(2) for Category 2a and
Condition 2b(2) for Category 2b.
Lemma 4.4. Let σ1 , . . . , σt be an ordering of blocks B1 , . . . , Bt in G such that for all k = 1, 2, . . . , t
and for all wj ∈ N , all the restrictions imposed by wj on σk is satisfied, except for the special
conditions Condition 2a(2) for Category 2a and Condition 2b(2) for Category 2b. If σkr is denotes
the reverse permutation of σk then we claim that one of the 16 possibilities obtained by reversing
or not reversing the orderings σ1 , σ2 , σt−1 and σt will be a valid ordering if G is PTPIG.
Proof. Straightforward.
So by the above lemma once we identify all the orderings σ1 , . . . , σt that satisfies all the restrictions
imposed by all wj ∈ N except for the special conditions Condition 2a(2) for Category 2a and
Condition 2b(2) for Category 2b, we have to check if any of the 16 possibilities is a valid set of
permutation.
27

4.2.2

Oriented-Consecutive 1’s problem

Problem 4.5 (Oriented-Consecutive 1’s problem). Input: A set Ω = {s1 . . . , sm } and n restrictions (S1 , b1 ), . . . , (Sn , bn ) where Si ⊆ Ω and bi ∈ {−1, 0, 1, 2}.
Question: Is there a linear ordering of Ω, say, sσ(1) , . . . , sσ(m) such that for 1 ≤ i ≤ n the following
are satisfied:
• If bi = 0, then all the elements in Si are consecutive in the linear ordering.
• If bi = −1, then all the element in Si are consecutive in the linear ordering and all the elements
of Si are flushed towards Left, i.e., sσ(1) ∈ Si .
• If bi = 1, then all the element in Si are consecutive in the linear ordering and all the elements
of Si are flushed towards Right, i.e., sσ(m) ∈ Si .
• If bi = 2, then all the element in Si are consecutive in the linear ordering and all the elements
of Si are either flushed towards Left or flushed towards Right, i.e., either sσ(1) ∈ Si or
sσ(m) ∈ Si .
Now this problem is very similar to the consecutive 1’s problem. The consecutive 1’s problem is
solved by using the PQ-tree. Recall the algorithm: given a set Ω = {s1 , . . . , sm } and a set of
subsets of Ω, say, S1 , . . . , Sm , the algorithm outputs a PQ tree T with leaves {s1 , . . . , sm } and the
property that P Q(T ) is the set of all orderings of Ω where for all Si (1 ≤ i ≤ m), the elements in
Si are contiguous. The algorithm has m iterations. The algorithms starts will a trivial PQ tree T
and at the end of the k-th iteration the PQ tree T has the property that P Q(T ) is the set of all
orderings of Ω where for all Si (1 ≤ i ≤ k − 1), the elements in Si are contiguous in the ordering.
At iteration k, the PQ tree T is updated using the algorithm Restrict(T, Sk )[4]2 . If for some Sk ,
Restrict(T, Sk ) cannot be performed, the algorithm halts and rejects.
We will use similar technique to solve the Oriented-Consecutive 1’s Problem. In fact we will reduce
the Oriented-Consecutive 1’s Problem to the standard Consecutive 1’s Problem, but we will assume
that all the restrictions of the form (Si , bi ), where bi = 2, appear at the end. That is, if for some
i we have bi = 2, then for all j ≥ i we will have bj = 2. We present Algorithm 4 for solving
the Oriented-Consecutive 1’s Problem and the following result proves that the correctness of the
algorithm.
2

In [4] they define the update algorithm as Reduce(T, S). In this paper we use the name Restrict(T, S) instead of
Reduce(T, S) as we think that the word “Restrict” is more suitable.

28

Claim 4.6. If we assume that bi = 2 implies bj = 2 for all j ≥ i, then Algorithm 4 is a correct
algorithm for the Oriented-Consecutive 1’s Problem. In fact all the valid ordering are stored in the
PQ-tree T .
Proof. First let us assume that bi 6= 2 for all i. We initialize the PQ-tree with Ω ∪ {`, a} as leaves.
Then we use Restrict(T, Ω ∪ {`}) and Restrict(T, Ω ∪ {a}) this implies that any ordering of the σ
of Ω ∪ {`, a} must have ` and a at the two ends. Note that if σ is infact a valid ordering of the
elements in Ω ∪ {`, a} that satisfies all the constraints then the reverse of σ is also a valid ordering
of the elements in Ω ∪ {`, a} that satisfies all the constraints. So we can always assume that ` is
in the beginning (i.e., the leftmost position) and a is at the end (i.e., the rightmost position).
From now on, if we say the elements of the set Si is flushed to the Left we would mean that Si ∪ {`}
is contiguous. Similarly if we say the elements of the set Si is flushed to the Right we would mean
that Si ∪ {a} is contiguous. Now let us check case by case basis:
Case 1: bj = 0. Then by using Restrict(T, Sj ) we ensure that all the elements in Sj are contiguous in
the ordering.
Case 2: bj = −1. Then by using Restrict(T, Sj ∪ {`}) we ensure that all the elements in Sj ∪ {`} are
contiguous in the ordering and since ` is at the leftmost position so that means the elements
in Sj are contiguous and flushed to the Left.
Case 3: bj = 1. Then by using Restrict(T, Sj ∪ {a}) we ensure that all the elements in Sj ∪ {a} are
contiguous in the ordering and since a is at the rightmost position so that means the elements
in Sj are contiguous and flushed to the Right.
So if bi 6= 2 for all i, then the algorithm solves the Oriented-Consecutive 1’s Problem correctly.
Now let us assume that there exists i such that for all j ≥ i, bj = 2 and for all j < i, bj 6= 2.
First consider the case that there exists an i0 ≤ i such that bi0 = 1. So at the ith iteration of the
algorithm, the permutation σ that satisfies the PQ-tree ensures that the elements in Si0 is flushed
to the Right. Now at the ith iteration, the algorithm ORestrict(T, Si ∪ {`, a}) first checks that
whether Si can be flushed to the Right or Si can be flushed to the Left. By Lemma 4.7 we note
either Si can be flushed Left or can be flushed Right. In other words there is no choice and the
algorithm will find that option. Similar argument will hold if there exists a i0 ≤ i such that bi0 = −1.
Now the complement of the above two cases is that for all i, bi is either 0 or 2. In this case, note
that if σ is a permutation that satisfies the conditions, then the reverse of permutation σ r will also
satisfy the conditions. Now if for some i, bi = 2 and we flushed Si to Left. By Lemma 4.7 if bj = 2
for all the j > i, only one option is possible. Now instead of flushing Si to Left if we had flushed
Si to Right we would be getting the reverse permutations.
29

Algorithm 3: ORestrict(T, S, {a, b})
Input

: PQ-tree T on set Ω, set S ⊂ Ω, {a, b}

Output : PQ-Tree
1
2
3
4

if Restrict(T, S ∪ {a}) is possible then
Restrict(T, S ∪ {a})
else
Restrict(T, S ∪ {b})

Algorithm 4: Oriented-Consecutive 1’s test
Input

: Ω, (S1 , b1 ), . . . , (Sn , bn )

Output : A P Q-tree T over the universe Ω such that all the remaining orderings satisfy the restrictions
(Sj , bj )
1

Initialize PQ-tree T with Ω ∪ {`, a} as leaves attached to the root (which is a P-node)

2

Restrict(T, Ω ∪ {`});

3

Restrict(T, Ω ∪ {a});

4

for j ← 1 to t do

5
6
7
8
9
10
11
12

if bj = 0 then
Restrict(T, Sj );
if bj = −1 then
Restrict(T, Sj ∪ {`});
if bj = 1 then
Restrict(T, Sj ∪ {a});
if bj = 2 then
ORestrict(T, Sj ∪ {`, a});

Lemma 4.7. Let Ω = {s1 , . . . , sm } and S1 , S2 ⊂ Ω. Then the following two conditions cannot
happen simultaneously:
1. There is an ordering of elements of Ω such that the elements of S1 and S2 are flushed Left.
2. There is an ordering of elements of Ω such that the elements of S1 are flushed Left while the
elements of S2 are flushed Right.
Proof. Let σ be an ordering of the elements of Ω such that the elements of both S1 and S2 are
flushed Left. This can happen only if either S1 ⊆ S2 or S2 ⊆ S1 . Similarly, if σ 0 be an ordering
of the elements of Ω such that the elements of S1 are flushed Left and S2 are flushed Right. This
can happen only if either (S2 ) ⊆ (S1 )c or (S1 )c ⊆ S2 , where (S1 )c is the complement of set S1 .
Note that both the conditions, that is “either S1 ⊆ S2 or S2 ⊆ S1 ” and “either (S2 ) ⊆ (S1 )c or
(S1 )c ⊆ S2 ” cannot happen simultaneously.

30

Algorithm 5: Finding-1-2-Subsequence
Input

: An array A[1, T ] containing only 0/1/2 entries, d (Assume A[T + 1] = 0).

Output : Output all (s, t) pairs such that (t − s + 1) ≥ d and for all s < i < t, A[i] = 1, A[s], A[t] ∈ {1, 2},
(either s = 1 or A[s − 1] = 0 or A[s − 1] = A[s] = 2) and (either t = T or A[t + 1] = 0 or
A[t] = A[t + 1] = 2).
1
2

Initialize ` = r = 0 while r ≤ T do
if A[r + 1] = 0 then
if r − ` ≥ d then

3

Output (` + 1, r)

4

` = r + 1; r = r + 1

5
6

if A[r + 1] = 1 then
r =r+1

7
8

if A[r + 1] = 2 then

9

if A[r] = 1 then
if r + 1 − ` ≥ d then

10

Output (` + 1, r + 1)

11

` = r; r = r + 1

12

if A[r] 6= 1 then

13

` = r; r = r + 1

14

Algorithm 6: CheckConditionB1(wj )
Input

: Given a graph G = (P, N, E), wj ∈ N . (For fwj refer to Definition 4.3).

Output : Accept if the Condition B1 is satisfied for the vertex wj .
1

Initialize two arrays X and Y of length 4dj + 1 by setting all the entries to 0.

2

Let ` = L(Aj [1]) and r = R(Aj [1]).

3

for each k ← 1 to dj do

4

Let s = L(Aj [k]) and t = R(Aj [k])

5

If (` − 2dj ≤ s ≤ ` + 2dj ) Mark X[s − ` + 2dj + 1] = fwj (Aj [k])

6

If (` − 2dj ≤ t ≤ ` + 2dj ) Mark X[t − ` + 2dj + 1] = fwj (Aj [k])

7

If (r − 2dj ≤ s ≤ r + 2di ) Mark Y [s − r + 2dj + 1] = fwj (Aj [k])

8

If (r − 2dj ≤ t ≤ r + 2dj ) Mark Y [t − r + 2dj + 1] = fwj (Aj [k])

9

for all (a, b) output of Find-1-2-Subsequence(X, dj ) do

10

Let â = a + ` − 2dj − 1 and b̂ = b + ` − 2dj − 1.

11

if ∀1 ≤ k ≤ dj Either â ≤ L(Aj [k]) ≤ b̂ OR â ≤ R(Aj [k]) ≤ b̂ then

12

Return(k1 , k2 ) such that (Either L(bk1 ) = â OR R(bk1 ) = â) AND (Either L(bk2 ) = b̂ OR R(bk2 ) = b̂)

13

for all (a, b) output of Find-1-2-Subsequence(Y, dj ) do

14

Let â = a + r − 2dj − 1 and b̂ = b + r − 2dj − 1.

15

if ∀1 ≤ k ≤ dj Either â ≤ L(Aj [k]) ≤ b̂ OR â ≤ R(Aj [k]) ≤ b̂ then

16

17

Return(k1 , k2 ) such that (Either L(bk1 ) = â OR R(bk1 ) = â) AND (Either L(bk2 ) = b̂ OR R(bk2 ) = b̂)
If nothing is returned then REJECT

31

Algorithm 7: Testing if G is PTPIG
Input : Given a graph G = (P, N, E)
Output: Accept if G is a PTPIG
1

for k ← 1 to t do

2

Initialize PQ-tree Tk with Bk ∪ {`, a} as leaves attached to the root (which is a P-node)

3

Restrict(Tk , Bk ∪ {`}); Restrict(Tk , Bk ∪ {a});

4
5

for j ← 1 to q do
if Condition B1 is satisfied by node wj then
if Number of Partial-Block Neighbors of wj is 0 then

6

j =j+1

7

if Number of Partial-Block-Neighbors of wj is 1 (let Bk be the partial-block-neighbor) then

8

if Number of Block-Neighbors of wj is 1 then

9

Restrict(Tk , N gbk (wj )); j = j + 1

10

if All pairs returned by CheckConditionB1(wj ) are of the form (k, k2 ) with k2 6= k then

11

Restrict(Tk , N gbk (wj )∪ `); j = j + 1

12

if All pairs returned by CheckConditionB1(wj ) are of the form (k1 , k) with k1 6= k then

13

Restrict(Tk , N gbk (wj )∪ a); j = j + 1

14

else

15

ORestrict(Tk , N gbk (wj ), {`, a}); j = j + 1

16

if Number of Block Neighbors of wj is 2 (let Bk1 , Bk2 be the partial-block-neighbors) then

17

if ({k1 , k2 } = {1, 2} & SG
starts with 121) Or ({k1 , k2 } = {t − 1, t} & SG
ends with t(t − 1)t)
g
g
P
P

18

then
ORestrict(Tk1 , N gbk1 (wj ), {`, a}); ORestrict(Tk2 , N gbk2 (wj ), {`, a}); j = j + 1

19

else

20
21

Let CheckConditionB1(wj ) returns (k1 , k2 )

22

Restrict(Tk1 , N gbk1 (wj ) ∪ {`}); Restrict(Tk2 , N gbk2 (wj ) ∪ {a}); j = j + 1
if Number of Block Neighbors of wj is ≥ 3 then

23

REJECT

24

25

Let σ1 , σ2 , . . . , σt be permutations satisfying the PQ-trees T1 , . . . , Tt .

26

if σ1 , σ2 , . . . , σt−1 , σt satisfies Condition (A) of Theorem 3.4, where σs = σs or, σsr for s = 1, 2, t − 1, t then

27
28
29

ACCEPT
else
REJECT

32

4.2.3

The algorithm

The Algorithm 6 ckecks if for a given wj ∈ N the Condition (B1) is satisfied. The algorithm is
similar to the one in Step I where we assumed that the graph GP is a connected reduced proper
interval graph. Once we have the Algorithm 6 for checking if the graph satisfies Condition (B1)
for every wj ∈ N , the Algorithm 7 checks whether the graph G = (P, N, E) is a PTPIG. In the
following theorem we prove the correctness of the algorithm.
Theorem 4.8. Given graph G = (P, N, E) such that GP is a connected proper interval graph,
the Algorithm 7 correctly decides whether G is a PTPIG with probes P and nonprobes N in time
O(|P | + |N | + |E2 |), where E2 is the set of edges between probes P and nonprobes N .
Proof. We follow notations, terminologies and ideas developed in the beginning of Step II and in the
‘Idea of the Algorithm’. In Lines 1–3 of Algorithm 7, we fix the markers a and ` at the beginning
and end of each block Bk respectively, k = 1, 2, . . . , t. Then for each j = 1, 2, . . . , q, we run the
algorithm. First, in Line 5, we check Condition B1 for wj by Algorithm 6 which takes a help from
Algorithm 5. Both algorithms are similar to Algorithm 2 and 1. The difference is that Algorithm 6
not only ensures that the graph G satisfies Condition B1 for vertex wj ∈ N but also return (k1 , k2 )
where k1 and k2 are the index of the start and end block of the substring that helps to satisfy the
Condition B1. It also ensure that no block in between k1 and k2 is a partial block neighbor of wj .
If wj has more than two partial-block neighbors, the Algorithm rejects.
Now in Lines 6–24, Algorithm 7 uses the ideas developed for Algorithm 4 for Oriented-consecutive
1’s problem to apply all the necessary restrictions on the orderings of vertices in each block, as
described in Section 4.2.1, except for the special conditions Condition 2a(2) for Category 2a and
Condition 2b(2) for Category 2b. Here we assume that all the calls to ORestrict is done at the
very end. This can be done by having two passes over the graph. Once we make all the calls to
ORestrict at the very end by Claim 4.6, we get the correctness of the algorithm so far.
Finally for checking whether special conditions Condition 2a(2) for Category 2a and Condition
2b(2) for Category 2b are satisfied, we require Lines 17-19 and 25-26. Suppose wj falls under
Category 2a and both B1 and B2 are partial-block-neighbors of wj . Then Algorithm 6 returns
both (1, 2) and (2, 1). Note that we have already ensure that both N gb1 (wj ) and N gb2 (wj ) are
either flushed Left or Right. If for some other wj 0 we have already flushed N gb1 (wj 0 ) Left or Right
then by Lemma 4.7 we had only one option when we were flushing N gb1 (wj ) to Left or Right. If
for no other wj 0 we have already flushed N gb1 (wj 0 ) Left or Right then we can consider either σ1 or
σ1r . The same argument holds for σ2 , σt and σt−1 . Thus if we check for all possibilities for σi or σir ,
33

i = 1, 2, t, t − 1 (as in Lines 25-26 of Algorithm 7) we can correctly decide whether G is a PTPIG
with probes P and nonprobes N .
Now we compute the running time. The total running time of Algorithm 6 (including the formation
of look up tables and the function fni (j) is O(|P | + |E2 |) as before, where E2 is the set of edges
between probes P and nonprobes N ). The variation of PQ-tree algorithm used in Lines 10, 12, 14,
16, 19 and 22 requires O(|P | + |N | + |E2 |) as it requires for normal PQ-tree algorithm. The Line
26 requires constant times of |E2 | steps for 4 blocks, namely, B1 , B2 , Bt−1 and Bt where σs or σsr
(s = 1, 2, t − 1, t) is required if the special cases Category 2a or 2b occur. Thus the total running
time is O(|P | + |N | + |E2 |).

4.3

Step III: The graph GP is a proper interval graph (not necessarily connected
or reduced)

Finally, we consider the graph G = (V, E) with an independent set N (nonprobes) and P = V r N
(probes) such that GP is a proper interval graph, which may not be connected. Suppose GP has
r connected components G1 , G2 , . . . , Gr with vertex sets P1 , . . . , Pr . For G to be a PTPIG, it is
essential that the subgraphs of G induced by Pk ∪ N is a PTPIG for each k = 1, 2, . . . , r. As we
have seen in the last subsection we can check if all the subgraphs are PTPIG in time O(|V | + |E|).
In fact, for each k, we can store all the possible canonical orderings of vertices in Pk such that
the corresponding canonical sequence satisfies the Condition (A) of Theorem 3.4 so that the graph
induced by Pk ∪ N is a PTPIG.
For any vertex wj ∈ N , let us call Gk a component-neighbor of wj if there is a vertex in Pk that is
adjacent to wj . Gk is called a full-component-neighbor of wj if all the vertices in Pk are neighbors
of wj . Also Gk is called a partial-component-neighbor of wj if there exists at least one vertex in Pk
that is a neighbor of wj and at least one vertex in Pk that is not a neighbor of wj .
We will just be presenting the idea of the algorithm. The steps of the algorithm is obvious from
the description given. We will be using all the algorithm developed so far in the previous sections
for this recognition algorithm.
4.3.1

Idea of the algorithm

To check if the whole graph G is a PTPIG we have to find if there exists a canonical ordering of
all the vertices in GP such that for the whole graph the Condition (A) of Theorem 3.4 is satisfied.
Note that a canonical ordering of the vertices of GP would place the vertices in each connected

34

component next to each other and moreover for each k, the ordering of the vertices of Gk would be
a canonical ordering for the graph Gk . So to check if G is a PTPIG we have to find if there exist an
ordering of the connected components and canonical ordering of vertices in each of the components
such that the corresponding canonical ordering satisfies the Condition (A) of Theorem 3.4. In fact
G is a PTPIG if and only if the following condition is satisfied:
Condition (C1): There exists a permutation π : {1, . . . , r} → {1, . . . , r} and canonical sequences
SG1 , . . . , SGr of G1 , . . . , Gr such that the canonical sequence SGP of GP obtained by concatenation
of the canonical sequences of Gπ(1) , . . . , Gπ(r) (that is, SGP = SGπ(1) . . . SGπ(r) ) has the property
that for all w ∈ N , there exists a perfect substring of w in SGP (that is, there exists a substring of
SGP where only the vertices of w appear and all the neighbors of w appears at least once).
Firstly we will use our previous algorithms to store all the possible canonical orderings of the
vertices in each component so that the graphs induced by Gk ∪ N is a PTPIG, for each k. As usual
we will store the restrictions using the PQ-tree. Next we will have to add some more restrictions
on the canonical ordering of the vertices in each of the connected components which are necessary
for the graph G to be a PTPIG. These restriction will be be stored in the same the PQ-tree. At
last we check if there exists an ordering of the components such that the corresponding canonical
ordering satisfies the Condition (A) of Theorem 3.4.
Now to find the extra restrictions on the canonical ordering we have to place we will look at several
cases depending on how many partial-component neighbors are there for each wj ∈ N . The main
idea is that the following is a necessary condition for the above Condition (C1) to be satisfied:
Condition (C2): If vertex wj has more than one component-neighbors, then for any component
Gk the canonical ordering of the vertices in Gk should ensure that not only there is a perfect
substring of wj in SGk , but also a perfect substring of wj must be present either at the beginning
or at the end of SGk .
Depending on how many partial-component-neighbors are there for each wj ∈ N and the number
of blocks in each of the partial component we list the restrictions on the canonical ordering of the
vertices in each component so the Condition (C2) is satisfied. Here we will also use the notion of
block-neighbor as defined in the previous section.
• (Case 1): wj has only one component neighbor. In this case there are no extra restrictions.
• (Case 2): wj has no partial-component neighbors. In this case there are no extra restrictions.

35

• (Case 3): wj has more than two partial-component-neighbors. In this case the graph G cannot
be a PTPIG.
• (Case 4): wj has more than one component neighbors and in one of the component neighbor
there are 2 or more partial-block-neighbors. In this case the graph G cannot be a PTPIG.
• (Case 5): wj has more than one component neighbors and let Gk be a partial-component
neighbor of wj . In this case we have two cases depending on the arrangement of blocks of Gk :
– (Case 5a): If Gk has only one block. Then we have to add the restriction that in the
canonical ordering of the vertices in Gk the neighbors of wj must be either flushed Left
or flushed Right. If the component Gk is a partial-component-neighbor of more than
one nonprobe vertex then by Lemma 4.7, the choice of whether to flush Left or Right is
fixed.
– (Case 5b): If Gk has more than one blocks and at least one of the block (say Bsk ) is
a partial-block-neighbor of wj . By Corollary 3.10 and Corollary 3.11 we see that there
is at most one direction (Left or Right) to flush the neighbors of wj in Bsk so that in
the corresponding canonical sequence there is a perfect-substring of wj either at the
beginning or the end.

Note that one can easily identify the cases above and apply the necessary restrictions on the
orderings using the PQ-tree and the same techniques as developed for the Oriented-consecutive
1’s Problem in Section 4.2.2. If after applying the restriction we see that Condition (C2) is not
satisfied, we know that G is not a PTPIG. All this can be done in time O(|V | + |E|).
Once we have been able to apply the restriction and ensure that the Condition (C2) is satisfied we
now need to check if there exits an ordering of the components so that Condition (C1) is satisfied.
For any wj ∈ N and any connected component Gk , if Gk is a component-neighbor of wj then we
know whether the perfect substring of wj is at the beginning or end of the canonical sequence of
Gk . If the perfect substring of wj is at the beginning of the canonical sequence of Gk we will call
wj left-oriented with respect to Gk and if the perfect substring of wj is at the end of the canonical
sequence of Gk we will call wj right-oriented with respect to Gk .
The problem now is to check if there exists an ordering of the connected components such that for
any wj ∈ N the following conditions are satisfied:
1. the component-neighbors of wj must be consecutive,
36

2. there exist at most one of the component-neighbors Gk of wj such that wj is right-oriented
with respect to Gk and this component-neighbor is first component-neighbor of wj in the
ordering,
3. there exist at most one of the component-neighbors Gk of wj such that wj is left-oriented with
respect to Gk and this component-neighbor is last component-neighbor of wj in the ordering.
This problem can be reduced to a consecutive 1’s problem: Let Ω = ∪rk=1 {`k , ak }. For any wj ∈ N
let us define the set Tj as follows:
• if Gk is a full-component neighbor of wj the Tj contains `k and ak
• if Gk is a partial-component-neighbor of wj and wj is right-oriented with respect to Bk then
Tj contains ak
• if Gk is a partial-component-neighbor of wj and wj is left-oriented with respect to Bk then
Tj contains `k
Now G is a PTPIG if and only if there exists a permutation of Ω that satisfies the following
properties:
• For all k, {`k , ak } are next to each other.
• For all wj ∈ N , the elements in Tj must be consecutive.
Note that the above can be tested easily using the PQ-tree in time linear in |V | and |E| and with
this we have the complete recognition algorithm for PTPIG.

5

Conclusion

The study of interval graphs was spearheaded by Benzer [2] in his studies in the field of molecular
biology. In [37], Zhang introduced a generalization of interval graphs called probe interval graphs
(PIG) in an attempt to aid a problem called cosmid contig mapping. In order to obtain a better
model another generalization of interval graphs were introduced that capture the property of overlap
information, namely tagged probe interval graphs (TPIG) by Sheng, Wang and Zhang in [34]. Still
there is no recognition algorithm for TPIG, in general.

37

In this paper we characterize and obtain linear time recognition algorithm for a special class of
TPIG, namely proper tagged probe interval graphs (PTPIG). The problem of obtaining a recognition algorithm for TPIG, in general is challenging and open till date. It is well known that an
interval graph is a proper interval graph if and only if it does not contain K1,3 as an induced subgraph of it. Similar forbidden subgraph characterization for PTPIG is another interesting problem.

References
[1] Asim. Basu, Sandip Das, Shamik Ghosh and Malay Sen, Circular-arc bigraphs and its subclasses, J. Graph Theory 73 (2013), 361 376.
[2] S. Benzer, On the topology of the genetic fine structure, Proc. Nat. Acad. Sci. USA 45 (1959),
1607–1620.
[3] K. S. Booth and G. S. Leuker, Linear algorithm to recognize interval grapha and test for the
consecutive ones property, Proc. 7th ACM Symp. Theory of computing, (1975), 255–265.
[4] K. S. Booth and G. S. Leuker, Testing for the consecutive ones property, interval graphs and
graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13 (1976), 335–379.
[5] D. E. Brown, Variations on interval graphs, Ph.D. Thesis, Univ. of Colorado at Denver, USA,
2004.
[6] D.G. Corneil, A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs,
Discrete Appl. Math. 138 (2004) 371 - 379.
[7] D.G. Corneil, S. Olariu, L. Stewart, The LBFS structure and recognition of interval graphs,
in preparation; extended abstract appeared as The ultimate interval graph recognition algorithm?, in: Proceedings of SODA 98, Ninth Annual ACM-SIAM Symposium on Discrete
Algorithms, San Francisco, CA, USA, 1998, pp. 175–180.
[8] D.G. Corneil, S. Olariu, L. Stewart, The LBFS structure and recognition of interval graphs,
SIAM J. Discrete Math., 23 (2010), 19051953.
[9] X. Deng, P. Hell and J. Huang, Linear time representation algorithms for proper circular arc
graphs and proper interval graphs, SIAM J. Comput. 25 (1996) 390–403.
[10] C.M.H. de Figueiredo, J. Meidanis and C.P. de Mello, A linear-time algorithm for proper
interval graph recognition Inform. Process. Lett. 56 (1995) 179–184.

38

[11] Shamik Ghosh, Maitry Podder and Malay Sen, Adjacency matrices of probe interval graphs,
Discrete Appl. Math. 158 (2010) 2004–2013.
[12] M. C. Golumbic, Algorithmic graph theory and perfect graphs, Annals of Disc. Math., 57,
Elsevier Sci., USA, 2004.
[13] M. C. Golumbic and A. Trenk, Tolerence Graphs, Cambridge studies in advanced mathematics,
Cambridge University Press, 2004.
[14] M. Habib, R. McConnel, C. Paul and L. Viennot, Lex-BFS and partition refinement, with
applications to transitive orientation, interval graph recognition, and consecutive ones testing,
Theor. Comput. Sci. 234 (2000) 59-84.
[15] Pavol Hell and Jing Huang, Certifying LexBFS Recognition Algorithms for Proper Interval
Graphs and Proper Interval Bigraphs, SIAM J. Discret. Math. 18 (2005) 554–570.
[16] P. Hell, R. Shamir and R. Sharan, A fully dynamic algorithm for recognizing and representing
proper interval graphs, SIAM J. Comput. 31 (2001) 289–305.
[17] Wen-Lian Hsu, A Simple Test for the Consecutive Ones Property, J. Algorithms, 43 (2002),
1–16.
[18] J. Johnson and J. Spinrad, A polynomial time recognition algorithm for probe interval graphs,
Proc. 12th annual ACM - SIAM Symposium on Disc. Algorithms, Washington D.C., 2001.
[19] D. S. Malik, M. K. Sen and S. Ghosh, Introduction to Graph Theory, Cengage Learning, New
York, 2014.
[20] R. M. McConnell, Y. Nussbaum, Linear-time recognition of probe interval graphs, in: A. Fiat,
P. Sanders (Eds.), ESA 2009, in: LNCS, vol. 5757, Springer, Heidelberg, 2009, pp. 349–360.
Full version available at: arXiv:1307.5547 [].
[21] R. M. McConnel and J. P. Spinrad, Construction of probe interval models, SODA 02 Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, (2002) 866–875.
[22] Terry A. McKee and F. R. McMorris, Topics in intersection graph theory, Siam Monographs
on Discrete Mathematics and Applications, Philadelphia, 1999.
[23] F. McMorris, C. Wang and P. Zhang, On probe interval graphs, Disc. App. Math., 88 (1998),
315–324.

39

[24] J. Meidanis, O. Porto, G. P. Telles, On the consecutive ones property, Disc. App. Math. 88
(1998), 325-354.
[25] Yahav Nussbaum, Recognition of probe proper interval graphs, Discrete Applied Mathematics,
167 (2014), 228–238.
[26] H.-J. Pan, Partitioned probe proper interval graphs. Masters Thesis, National Chung Cheng
University, Taiwan, 2008.
[27] F.S. Roberts, Representations of indifference relations, Ph. D. Thesis, Stanford Univeristy,
1968.
[28] F.S. Roberts, Indifference graphs, in: F. Harary (Ed.), Proof Techniques in Graph Theory,
Academic Press, New York, 1969, pp. 139–146.
[29] F.S. Roberts, On the compatibility between a graph and a simple order, J. Combin. Theory
Ser. B 11 (1971) 28–38.
[30] F.S. Roberts, Some applications of graph theory, Chapter in book Combinatorial and Computational Mathematics, Published by World Scientific Publishing Co. Pte. Ltd.
[31] M. Sen, S. Das, A. B. Roy and D. B. West, Interval digraphs: An analogue of interval graphs,
J Graph Theory 13 (1989), 189–202.
[32] M. Sen, S. Das, and D. B. West, Circular-arc digraphs: a characterization, J. Graph Theory,
13 (1989), 581–592.
[33] L. Sheng, Cycle free probe interval graphs, Congressus Numerantium, 140 (1999), 33–42.
[34] L. Sheng, C. Wang and P. Zhang Tagged probe interval graphs, J. Combinatorial optimization,
5 (2001), 133–142.
[35] L. Sheng, C. Wang and P. Zhang On the Perfectness of Tagged Probe Interval Graphs (with Chi
Wang, Peisen Zhang, Discrete Mathematical Problems with Medical Applications, American
Mathematical Society, Providence, RI, 159–163, 2000.
[36] L. Sheng, C. Wang and P. Zhang Tagged probe interval graphs, DIMACS Technical Report
98-12, 1998.
[37] P. Zhang, Probe interval graphs and their application to physical mapping of DNA, Manuscript,
1994.

40

