Transcript finding a minimum independent dominating set in a permutation graph

FINDING A MINIMUM INDEPENDENT
DOMINATING SET IN A PERMUTATION GRAPH
Mikhail J. ATALLAH
Glenn K. MANACHER
J. URRUTIA
Discrete Applied Mathematics 21 (1988)
177-183
Speaker : 崔愷文
Theorem 2.1

Given permutation Π, the problem of finding a
MIDS in the permutation graph G(Π) is reducible,
in linear time, to the problem of finding a SMIS of
a sequence of numbers.
Lemma 2.2

Let I={i1,i2,…,ik} be a subset of In, i1<i2<…<ik.
Then I forms an independent set in G(Π) if and
only if Π-1(i1)<Π-1(i2)<…<Π-1(ik).
Lemma 2.3

Let I={i1,i2,…,ik} be an independent set in G(Π),
with i1<i2<…<ik. Then I is an dominating set in
G(Π) if and only if the sequence
β
= Π-1(i1)<Π-1(i2)<…<Π-1(ik)
forms a
maximal increasing subsequence of
α
= Π-1(1)<Π-1(2)<…<Π-1(n).
Proof

By Lemma 2.2 implies that sequence β is increasing, so
that it suffices to prove that I is dominating iff β is
maximal.
For the “if” part of the proof:

Suppose that β forms a maximal increasing
subsequence of α. To prove that I forms a
dominating set in G(Π), note that otherwise there
is a vertex j  I such that I  { j} is also an
independent set. Therefore, we can insert Π-1(j) in
β obtaining a new increasing subsequence of α
which properly contains β, contradicting the
maximality of β.
For the “only if” part of the proof:

Assume that I is dominating in G(Π). If β is not maximal,
then there exists a
that
jsuch
 In 
I insertion of Π-1(j)
in β results in a
which isˆan increasing subsequence of
α, e.g.
ˆ = Π-1(i1) … Π-1(il-1) Π-1(j) Π-1(il) … Π-1(ik)
Where ˆ is increasing and i1<…<il-1<j<il<…<ik.
By lemma 2.2 this implies that I∪{j} is independent,
which contradicts the fact that I is dominating in G(Π).
Proof of Theorem 2.1


By Lemma 2.3 every independent dominating set in G(Π)
generates a maximal increasing subsequence of
Π-1(1)<Π-1(2)<…<Π-1(n), and vice versa.
Then finding a minimum independent dominating set in
G(Π) is equivalent to finding a minimum maximal
increasing subsequence in Π-1(1)<Π-1(2)<…<Π-1(n).
Finding Shortest Maximal Increasing
Subsequences (SMIS)




Preliminaries
Data Structure
Algorithm
Example
Preliminaries

Let P be a set of points in the plane. Let︰
–
–
–
–
–
X(p) and Y(p) to denote the x and y coordinates of a point p.
A point pi is said to dominate pj iff X(pi) > X(pj) and Y(pi) > Y(pj).
DOM(pi) to denote the subset of points in P that are dominated by
point pi (i.e. DOM(pi) contains the points of P that are below and
to the left of pi).
A point of P is a maximum iff no other point of P dominates it.
MAX(P) to denote the set of maxima of P.
Data Structure


The algorithm use the following result of Overmars and
van Leeuwen [5] (called augmented tree structure)
[5] M.H. Overmars and J. van Leeuwen, “Maintenance of
configurations in the plane”, J. Comput. Syst. (1981) 166204.
Data Structure

There exists a data structure for dynamically maintaining
the maxima of a set of points in the plane, such that:
–
–
–
–
Insertions and deletions take time O(log2n) per operation
At any time, the maxima are available at the root, in a
concatenable queue attached to the root.
The augmented tree structure takes O(n) storage space, and
can initially be created in time O(nlogn).
Support SPLIT and CONCATENATE operations in time
O(log2n) per operation.
SPLIT and CONCATENATE


A SPLIT operation about any horizontal line y=y0 result in two
augmented tree structures : one for the points above the horizontal line,
and one for those below it.
A CONCATENATE operation has the reverse effect of a SPLIT.
Algorithm



Let a1,…,an be the input sequence. Let Bi be the set of
shortest maximal increasing subsequences of a1,…,ai
which end with ai.
All the sequences in Bi have same length as one another,
call this length label(i).
The significance of predecessor(i) is:
– Predecessor(i)=φ, if label(i)=1
– apredecessor(i)ai, otherwise
Algorithm MINAMX



Input: Sequence a1,…,an.
Output: A minimum-length maximal increasing subsequence of a1,…,an.
Method:
label(1):=1
predecessor(1):=φ
create points p1…pn, where pi=(i.ai) and create a augmented tree T
for i:=1 to n
BEGIN
SPLIT T according to the horizontal line y=Y(pi), obtaining two augmented tree Tup and Tdown
If MAX(DOM(pi)) is empty then
label(i):=1
predecessor(i):= φ
else
set predecessor(i) equal to the index of the smallest-labeled point pj of MAX(DOM(pi))
label(i):=label(j)+1
Rebuild T by doing a CONCATENATE of Tup and Tdown, then insert pi into T
END
Example

Given permutation : 314265 for 1,2,…,6