Graph Searching and Interval Completion.
In the early studies on graph searching a graph was considered as a system of tunnels in which a fast and clever fugitive is hidden. The "classical" search  problem is to  find a search plan using the minimal number of searchers. In this paper, we consider a new criterion of optimization, namely, the search cost. First, we prove  monotone properties of searching with the smallest cost. Then, making use of  monotone properties, we prove that for any graph G the search cost of G is equal to the smallest number of edges of all interval supergraphs of G. Finally, we show how to compute the search cost of a cograph   and the corresponding search strategy in linear time.
Introduction
Search problems on graphs attract the attention of researchers from different
fields of Mathematics and Computer Science for a variety of reasons. In the
first place, this is the resemblance of graph searching to certain pebble games
[18] that model sequential computation. The second motivation of the interest
to the graph searching arises from the VLSI theory. Exploitation of game-theoretic
approaches to some important parameters of graphs layouts such as
the cutwidth [23], the topological bandwidth [22] and the vertex separation
number [11] is very useful for the construction of efficient algorithms. Yet
another reason is connections between graph searching, the pathwidth and the
treewidth. These parameters play very important role in the theory of graph
minors developed by Robertson and Seymour (see [1, 10, 29]). Also some search
Department of Operations Research, Faculty of Mathematics and Mechanics,
St.Petersburg State University, Bibliotechnaya sq.2, St.Petersburg, 198904, Russia, e-mail:
fomin@gamma.math.spbu.ru The research of this author was partially supported by the RFBR
grant N98-01-00934
y Department of Applied Mathematics, Faculty of Mathematics, Syktyvkar State Univer-
sity, Oktyabrsky pr., 55, Syktyvkar, 167001, Russia, e-mail: golovach@ssu.edu.komi.ru. The
research of this author was partially supported by the RFBR grant N96-00-00285.
problems have applications in motion coordinations of multiple robots [30] and
in problems of privacy in distributed environments with mobile eavesdroppers
('bugs') [13]. More information on graph searching and related problems one
can find in surveys [1, 12, 25].
In the 'classical' node-search version of searching (see, e.g.[18]) at every move
of searching a searcher is placed at a vertex or is removed from a vertex. Initially,
all edges are contaminated (uncleared). A contaminated edge is cleared once
both its endpoints are occupied by searchers. A clear edge e is recontaminated
if there is a path without searchers leading from e to a contaminated edge.
The 'classical' search problem is in finding the search program such that the
maximal number of searchers used at any move is minimized. In this paper we
are interested in another criterion of optimization. We are looking for node-
search programs with the minimal sum (the sum is taken over all moves of
the search program) of numbers of searchers. We call this criterion the search
cost. Loosely speaking, the cost of a search program is the total number of
'man-steps' used in this program and the search cost is the cost of an optimal
program. The reader is referred to section 2 for formal definitions of searching
and its cost.
One of the most important issues concerning searching is that of recontam-
ination. In some search problems (see [2, 20]) the recontamination does not
help to search a graph, i.e., if searchers can clear the graph then they can do it
without recontamination of previously cleared edges. We establish the monotonicity
of search programs of the smallest cost. To prove the monotonicity
result we use special constructions named clews. Clews are closely related to
crusades used by Bienstock and Seymour in [2] and the notion of clew's measure
is related to the notion of linear width introduced by Thomas in [31].
This paper is organized as follows. In x 2 we give necessary definitions. In x 3
we introduce clews and prove the monotonicity of graph searching. In x 4 it is
proved that for any graph G the search cost of G is equal to the smallest number
of edges of an interval supergraph of G. In x 5 it is shown that the problem of
computing the search cost is equivalent to the vertex separation sum problem
and profile minimization problem. In x 6 we obtain some estimates of the
search costs in terms of the vertex separation number and the sum bandwidth.
In x 7 we show how to compute the search cost of graph's product. In x 8 we
give a linear time algorithm determining the search cost of a cograph and the
corresponding search program.
2 Statement of the problem
We use the standard graph-theoretic terminology compatible with [6], to which
we refer the reader for basic definitions. Unless otherwise specified, G is an
undirected, simple (without loops and multiple edges) and finite graph with
the vertex set V (G) and the edge set E(G); n denotes the order of G, i.e.,
n. The degree of a vertex v in G is denoted by deg(v) and the
maximum degree of the vertices of a graph G by \Delta(G).
A search program \Pi on a graph G is the sequence of pairs
such that
I. for
II. for vertex incident with an edge in A j
an edge in E(G) \Gamma A j
i is in Z j
III. for
IV. (placing new searchers and clearing edges) for there is
such that Z 1
is the set of all incident with v edges having one end in Z 2
V. (removing searchers and possible recontamination) for
i is the set of all edges e 2 A 1
i such that every path
containing e and an edge of E(G) \Gamma A 1
i , has an internal vertex in Z 2
We call this the search axioms. It is useful to treat Z 1
i as the set of vertices
occupied by searchers right away after placing a new searcher at the ith step;
i as the set of vertices occupied by searchers immediately before making the
1)th step; and A 1
i as the sets of cleared edges.
The well known node search problem [18] is in finding \Pi with the smallest
(this maximum can be treated as the maximum number of
searchers used in one step). Let us suggest an alternative measure of search.
We define the cost of \Pi to be
j. One can interpret the cost of a search
program as the total number of 'man-steps' used for the search or as the total
sum that searchers earn for doing their job. The search cost of a graph G,
denoted by fl(G), is the minimum cost of a search program where minimum is
taken over all search programs on G.
A search program
if for each
(recontamination does not occur when
searchers are removed at the ith step). The monotone search cost of G,
is the cost of the minimal (over all monotone search programs) search program
on G.
Notice that search programs can be defined not only for simple graphs but
for graphs with loops and multiple edges as well. Adding loops and multiple
edges does not change the search cost.
3 Monotone programs and clews
Let G be a graph. For X ' E(G) we define V (X) to be the set of vertices
which are endpoints of X and let
We consider clews only in graphs of special structure. Let G 0 be obtained
by adding a loop at each vertex of a graph G. A clew in G 0 is the sequence
of subsets of E(G 0 ) such that
1.
2. for
3. for i the loop at v also belongs to X i .
The measure of the clew is
progressive
Notice that if a clew (X
Theorem 1 For any graph G and k - 0 the following assertions are equivalent:
(ii) Let G 0 be obtained by adding a loop at each vertex of G. There is a clew
in G 0 of measure - k.
(iii) Let G 0 be obtained by adding a loop at each vertex of G. There is a
progressive clew in G 0 of measure - k.
Proof. (i) As mentioned above,
be a search program on G 0 with the cost - k. We prove that A 2
is the clew of measure - k in G 0 . The third search axiom implies A 2
E(G). The second search axiom says that for every
m is the clew
if for every
Suppose that for some
inequality does not hold. Then there are vertices u; v such
that
Notice that loops e u at vertices u and v
belongs to A 2
. From the fifth search axiom A 1
it follows that
e
. The latter contradicts the fourth axiom.
Choose a clew (X such that
and, subject to (1),
First we prove that for i
is the clew. Using (1), we get
It is easy to check that jffij satisfies the submodular inequality
Combining (3) and (4), we obtain
the loop at v belongs to X
Therefore, V (X we obtain that
is the clew. Taking into account
(5), (1) and (2), we get jX j. Thus we have X
is the clew
contradicting (2). Hence, (X
progressive clew of measure - k in
G 0 . We define the search program on G 0 setting Z 1
ng. Suppose that at the
ith step searchers are placed at vertices of Z 1
i and all edges of X i are cleaned.
Obviously no recontamination occurs by removing all searchers from vertices of
Every edge of X is either the loop at
v, or is incident with v and with a vertex of ffi (X
. Then at the (i
step the searcher placed at v cleans all edges of X Finally,
4 Interval graphs
A graph G is an interval graph, if and only if one can associate with each
vertex an open interval I on the real line, such that for
all v; w 2 V (G), v 6= w: (v; w) 2 E(G), if and only if I v " I w 6= ;. The set of
is called an (interval) representation for G.
It is easy to check that every interval graph has an interval representation in
which the left endpoints are distinct integers Such a representation
is said to be canonical.
A graph G is a supergraph of the graph G 0 if
E(G). Let G be an interval graph and let I = fI v g v2V (G) be a canonical
representation of G. The length of G with respect to I, denoted by l(G; I), is
We define the length l(G) of an interval graph G as the minimum length over all
canonical representations of G. For any graph G we define the interval length
of G, denoted by il(G), as the smallest length over all interval supergraphs of
G.
We shall use the following property of canonical representation in the proof
of Theorem 3.
I be an interval graph of n vertices and I = fI
, be its canonical representation such that
For ng let P (i) be the set of intervals I v , containing i.
Proof. (6) implies that every interval I contains br
integers. Every ng belongs to jP (i)j intervals of I. Therefore,
For every
(the number of intervals I plus the number
of intervals I From (8) it follows that
which, combined with (7), proves Lemma 2. 2
Theorem 3 For any graph G and k ? 0 the following assertions are equivalent:
(iii) there is an interval supergraph I of G such that jE(I)j - k.
Proof. (i) then by Theorem 1 there is a monotone search
program
on G with cost - k. We choose " ! 1 and assign to each vertex v of G the
interval (l "), where a searcher is placed on v at the l v th step and this
searcher is removed from v at the r v th step, i.e., l
and r
g. After the nth step of the search program
all edges of G are cleared, hence for every edge e of G there is a step such
that both ends of e are occupied by searchers. Therefore, interval graph I with
canonical representation is the supergraph of G.
Since for sufficiently small "
(in the left hand side equality each vertex v is counted br times), we see
that
immediately from Lemma 2.
, be a canonical representation
of the minimal length of an interval supergraph I of G. It is clear that r v ! n+1,
Let us describe the following search program on G:
ng we put Z 1
is the vertex assigned
to the interval with the left endpoint
Such actions of searchers do not imply recontamination because each path in I
(and hence in G) from a vertex to a vertex u, l u
a vertex of P (i 1). For each edge e of I (and hence for each edge of G) there
is ng such that both ends of e belong to Z 1
. Then at the nth step
all edges are cleared.
The cost of the program advanced is
5 Linear layouts
A linear layout of a graph G is a one-to-one mapping ng.
There are various interesting parameters associated with linear layouts. For
example, setting bw(G; E(G)g, one can define
the bandwidth of G as
is a linear layout of Gg:
The bandwidth minimization problem for arises in different applications (see
[8] for a survey).
In some applications instead of taking the maximum difference
it is more useful to find an 'average bandwidth'. The bandwidth sum of a graph
G is
is a linear layout of Gg:
Define the profile [8] of a symmetric n \Theta n matrix as the minimum
value of the sum n
taken over all symmetric permutations of A, it being assumed that a
ng. Profile may be redefined as a graph invariant p(G) by finding a
linear layout f of G which minimizes the sum
stands for 'is adjacent or equal to'. Notice, that bw(G;
ug. Sum bandwidth and profile reductions are also
relevant to the speedup of matrix computations; see [8] for further references.
Also these problems arise in VLSI layouts.
For a linear layout f of G we define
and
cw(G;
i2f1;:::;ng
If we 'draw' G with vertices in a straight line in the order given by f then
(G; f) is the number of edges that cross the gap between i and i + 1. The
cutwidth of G is
is a linear layout of Gg:
It is easy to check that for any layout f
For
U and there exists v 2 V (G) n U such that (u; v) 2 E(G)g:
Ellis et al. [11] (see also [21]) studied the vertex separation of a graph. Let f
be a linear layout of a graph G. Denote by S i (G; f ng, the set of
vertices ig. The vertex separation with respect to layout f
is
vs(G;
and the vertex separation of a graph G, we denote it by vs(G), is the minimum
vertex separation over all linear layouts of G. Let us define an alternative
'average norm' of vertex separation. The vertex separation sum with respect to
layout f is
vs sum (G;
and the vertex separation sum of a graph G [16] denoted by vs sum (G) is the
minimum vertex separation sum over all linear layouts of G.
Owing to Billionnet [3], for any graph G, the profile of G is equal to the
smallest number of edges over all interval supergraphs of G.
Theorem 4 For any graph G and k ? 0 the following assertions are equivalent:
Proof. Because (i) , (iii) follows from [3] and Theorem 3, it remains to prove
(i) , (ii).
be a monotone search program on G with cost - k. Define a layout
ng so that f(u) ! f(v) iff u accepts a searcher before v does. By the
second search axiom for each i 2 ng jZ 2
and we conclude
that vs sum (G; f) - k.
ng be a linear layout such that vs sum (G; f) -
k. We define the following subsets of V (G):
ng we put Z 1
ng Z 2
For ng and
i be the set of edges induced by [ i
k .
Note that for each edge (u; v) 2 E(G) there is 1g such that
(v)). On this basis it is straightforward
(as in Theorem 3) to prove that the sequence
is the (monotone) search program of cost - k on G. 2
5.1 Complexity remark
The problem of Interval Graph Completion:
Instance: A graph E) and an integer k.
Question: Is there an interval graph G
is NP-complete even when G is stipulated to be an edge graph (see [14], Problem
GT35). Interval Graph Completion arises in computational biology (see,
e.g., [4]) and is known to be FPT [7, 17].
From Theorem 3 it follows immediately that the problem of Search Cost:
deciding given a graph G and an integer k, whether fl(G) - k or not, is NP-complete
even for edge graphs and that finding the search cost is FPT for a
fixed k.
An O(n 1:722 ) time algorithm was given in [19] for the profile problem for
the case that G is a tree with n vertices.
6 Estimates of the search cost
A split in a graph G is a partition of V of the vertex set of
G such that jV i and the edges of G going from V 1 to V 2
induce a complete bipartite graph. Let V be a split of G and let
be the vertices of the associated complete bipartite graph.
The following proposition can be found in [25].
Proposition 5 Every monotone search program on G has a step at which all
vertices from A 1 or all vertices from A 2 simultaneously carry a searcher.
Corollary 6 Let us think that
Proof. Suppose that the jth step is the first step of the monotone program \Pi
at which all vertices of A 1 are occupied. Then at this step
are placed in A 2 and n 1 searchers in A 1 . Therefore the cost of \Pi is at least2 (j
As an illustration of the corollary we refer to a complete bipartite graph
with bipartition (X; Y j. The monotone search
program of cost 1(n
is easily be constructed. First we
place searchers on vertices of X and then on vertices of Y . Then by Corolary 6
Owing to Theorem 3 one can formulate the following proposition.
Proposition 7 Let G be a graph on n vertices and m edges. Then
and only if G is an interval graph, and
and only if G is a complete graph.
Further estimates of the search cost are obtained by making use of the vertex
separation sum.
Proposition 8 Let G be a graph on n vertices. Then2
Moreover, if G is connected then2
Proof. Let f be a linear layout of G such that vs sum
It is readily shown that there are
(G;
for
The proof of the second inequality is similar. Note that for any i 6=
Makedon and Sudborough [23] obtain some bounds for the cutwidth in
terms of the maximal degree and the search number. By virtue of (9) it is
not surprising that there are strong connections between the bandwidth sum
and the search cost.
Proposition 9 For any linear layout f of G bw sum (G; f) - \Delta(G)vs sum (G; f).
Therefore, bw sum (G) - \Delta(G)fl(G).
Proof. The proof is apparent from (9), because for any i 2 ng cw i (G; f) -
The line graph of a graph G is the graph with vertex set E(G), two vertices
being adjacent iff they are adjacent (as edges) in G.
be the line graph of G with
Then
Proof. Let f be an optimal (for the bandwidth sum) linear layout of G. Consider
a linear layout g: E(G) of L(G) such that for any edges a = (u; v),
a
For ng we define
Using
we obtain
vs sum (L(G);
e
Summing
we get
This implies that
vs sum (L(G); g) -
By (10) and Cauchy inequality,
out
Clearly, for every \Delta(G). If we combine this with (11)
and (12), we get
vs sum (L(G)) - \Delta(G)bw sum
:7 Product of graphs
The disjoint union of graphs G and H is the graph G -
[H with the vertex set
[V (H) and the edge set E(G) -
(where -
[ is the disjoint union on
graphs and sets, respectively);
We use G \Theta H to denote the following type of 'product' of G and H : G \Theta H
is the graph with the vertex set V (G) -
[V (G) and the edge set E(G) -
The following theorem is similar to results on edge-search and node-search
numbers [15, 25] and on the pathwidth and the treewidth [5] of a graph.
Theorem 11 Let G
Proof.
(I) is trivial.
(II). Let f be an optimal layout of G 1 \Theta G 2 , i.e. vs sum (G 1 \Theta G 2
k be the smallest number ensuring
clarity's sake we suppose that
be the 're-
striction' of f to V (G 2 ), i.e. for any u; v
Clearly, for any i 2
In addition, for any i 2 Consequently

i=k\Gamman 1
Finally,
For the other direction. Let f be an arbitrary layout of G 1 and let g be a
layout of G 2 such that vs sum
g)j. Define the layout h of
by the rule
ae
It follows easily that j@S i and
1g. We
conclude that
Similarly,
8 Cographs
Theorem 11 can be used to obtain linear time algorithms for the search cost and
corresponding search strategy on cograph. Recall that a graph G is a cograph
if and only if one of the following conditions is fulfilled:
There are cographs G
There are cographs G
A similar algorithm for the treewidth and pathwidth of cographs was described
in [5]. The main idea of the algorithm is in constructing a sequence of operations
[' and `\Theta' producing the cograph G. With each cograph G one can associate
a binary labeled tree, called the cotree TG . TG has the following properties:
1. Each internal vertex v of TG has a label label(v)2 f0; 1g.
2. There is a bijection - between the set of leaves of TG and V (G).
3. To each vertex v 2 (T G ) we assign the subgraph G v of G as follows:
(a) If v is a leaf then G
(b) If v is an internal vertex and label(v)= 0 then G
[Gw , where
u; w are the sons of v.
(c) If v is an internal vertex and label(v)= 1 then G
u; w are the sons of v.
Notice that if r is the root of TG then G G. Corneil et al. [9] gave an
determining whether a given graph G is a
cograph and, if so, for constructing the corresponding cotree.
Theorem 12 The search cost of a cograph given with a corresponding cotree
can be computed in O(n) time.
Proof. Let r be the root of TG . First we call COMPUTE-SIZE(r). This
recursive procedure computes jV (G v )j for each
procedure COMPUTE-SIZE(v: vertex);
begin
if v is a leaf of TG
then
else
begin COMPUTE-SIZE(left son of v);
COMPUTE-SIZE(right son of v);
size(v):=size(left son of v)+size(right son of v);
Then we call COMPUTE-GAMMA(r).
procedure COMPUTE-GAMMA(v: vertex);
begin
if v is a leaf of TG
then fl(v):=0
else
begin COMPUTE-GAMMA(left son of v);
COMPUTE-GAMMA(right son of v);
if label(v)=0
then fl(v):=maxffl(left son of v), fl(right son of v)g
else
fl(v):= minfsize(left son of v) (size(left son of v)\Gamma1)/2 fl(right son of v),
size(right son of v) (size(right son of v)\Gamma1)/2 son of v)g
son of v)\Lambdasize(right son of v)
By Theorem 11
are called once for each vertex of TG , so the time complexity of these procedures
is O(n). 2
Theorem 13 Let G be a cograph of n vertices and e edges. The optimal search
program on G can be computed in O(n
Proof. Let TG be the cotree of G (this tree can be computed in O(n
time [9]). Let r be the root of TG . First call COMPUTE-GAMMA(r) and
COMPUTE-SIZE(r). Then call SEARCH(r).
procedure SEARCH(v: vertex);
begin
if v is the root of TG
then begin
if v is a leaf of TG
then begin
else if label(v)=0
then begin
first(left son of v):= first(v);
last(left son of v):= first(v)+ size(left son of v)\Gamma1;
first(right son of v):= first(v)+ size(left son of v);
last(right son of v):= last(v);
SEARCH(left son of v);
SEARCH(right son of v)
else (  label(v)=1)
if size(left son of v) (size(left son of v)\Gamma1)/2 +fl(right son of v)
? size(right son of v) (size(right son of v)\Gamma1)/2 +fl(left son of v)
then begin k:=first(v);
for each vertex w 2 V (G) that is a leaf descendants of the right son of v
begin place(w):=k; remove(w):=last(v); k:=k+1 end
first(left son of v):= first(v)+ size(right son of v);
last(left son of v):= last(v);
SEARCH(left son of v)
else begin k:=first(v);
for each vertex w 2 V (G) that is a leaf descendants of the left son of v
begin place(w):=k; remove(w):=last(v); k:=k+1 end
first(right son of v):= first(v)+ size(left son of v);
last(right son of v):= last(v);
SEARCH(right son of v)
For each leaf computes the numbers place(v) and
remove(v). Clearly, the procedure is linear in size of the cotree. For the vertex
of G at the place(v)th step a searcher is placed at - \Gamma1 (v) and at the
remove(v)th step the searcher is removed from - \Gamma1 (v). Determining the sets
and
can be done with bucket sort in O(n) time. Define Z 1
computing the sets
can be done in linear time. Finally, the edge sets A j
i can be constructed in
O(n+ e) time as follows. Put A 1
;. For the vertex
its neighbors and
Using the characteristic vector of [ i
i the addition of edges incident to v
can be done in O(deg(v)) steps.
We have proved that the sequence
can be constructed in O(n+e) time. By Theorem 11 this sequence is the search
program and the cost of this program is fl(G). 2
9 Concluding remarks
In this paper, we introduced a game-theoretic approach to the problem of interval
completion with the smallest number of edges. There are similar approaches
to the pathwidth and treewidth parameters. The interesting problem is whether
there is a graph-searching 'interpretation' of the fill-in problem.



--R

Graph searching
Monotonicity in graph searching



Basic graph theory: Paths and circuits


A linear recognition algorithm for cographs

The vertex separation and search number of a graph

A graph-theoretic approach to privacy in distributed systems
Computers and Intractability


Tractability of parameterized completion problems on chordal and interval graphs: Minimum fill-in and physical mapping
Searching and pebbling
The profile minimization problem in trees
Recontamination does not help to search a graph


On minimizing width in linear layouts
The complexity of searching a graph


Some extremal search problems on graphs

Graph minors - a survey
Optimal algorithms for a pursuit-evasion problem in grids
Tree decompositions of graphs.
--TR

--CTR
Yung-Ling Lai , Gerard J. Chang, On the profile of the corona of two graphs, Information Processing Letters, v.89 n.6, p.287-292, 31 March 2004
Paolo Detti , Carlo Meloni, A linear algorithm for the Hamiltonian completion number of the line graph of a cactus, Discrete Applied Mathematics, v.136 n.2-3, p.197-215, 15 February 2004
Fedor V. Fomin , Dimitrios M. Thilikos, On the monotonicity of games generated by symmetric submodular functions, Discrete Applied Mathematics, v.131 n.2, p.323-335, 12 September
Sheng-Lung Peng , Chi-Kang Chen, On the interval completion of chordal graphs, Discrete Applied Mathematics, v.154 n.6, p.1003-1010, 15 April 2006
Barrire , Paola Flocchini , Pierre Fraigniaud , Nicola Santoro, Capture of an intruder by mobile agents, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
Fedor V. Fomin , Dieter Kratsch , Haiko Mller, On the domination search number, Discrete Applied Mathematics, v.127 n.3, p.565-580, 01 May
interval graph completion;graph searching;linear layout;search cost;profile;cograph;vertex separation