There is a network of n nodes and diameter D. Suppose we have a set S of nodes,w
ID: 3885118 • Letter: T
Question
There is a network of n nodes and diameter D. Suppose we have a set S of nodes,where each node knows if it is in S or not. The goal is to verify in a distributed manner if S is a maximal independent set (MIS).
a- Show that there exists an algorithm that terminates implicitly in time O(1) in the case when such a set S is a MIS.
b- Give an algorithm that terminates explicitly, in that each node eventually enters a halting state, which indicates either yes: the set is a MIS" or o: the set is not a MIS." Estimate the time complexity. Your algorithm should rely only on the nodes having names but not on the knowledge of either n or D.
Explanation / Answer
We define the general
conflict coloring
task, which can be instantiated so as to correspond to
any given LCL task. Roughly, conflict coloring is defined by a l
ist of candidate colors given to each node (in
the same spirit as list-coloring), and a list of conflicts bet
ween colors associated to each edge (following a
convention used, e.g., when formulating unique games, CSP-
s with binary conflict relations, etc.). For edge
{
u, v
}
, a conflict is a pair of the form
(
c
u
, c
v
)
, indicating that a coloring where
u
has color
c
u
and
v
has color
c
v
is illegal. Intuitively, given a LCL, the corresponding ins
tance of conflict coloring is obtained by giving
the list of all good balls centered at
u
to every node
u
, and two balls given to adjacent nodes are in conflict
whenever they are not consistent. Every LCL task is therefor
e a possible instantiation of conflict coloring (a
given LCL task may have more than one conflict coloring repres
entation). Note however that the power of
conflict coloring extends beyond such a formulation of LCL ta
sks: depending on the instance, two colors in
conflict along an edge
e
do not, in general, need to be in conflict along another edge
e
6
=
e
.
We will speak of a conflict coloring with lists of length
l
and conflict degree
d
, or more compactly of
(
l, d
)
-conflict-coloring, when all color lists given to the nodes a
re of length at least
l
, and for every edge
e
and color
c
, the number of colors conflicting with color
c
on edge
e
does not exceed
d
. Intuitively, the
larger the value of
l
, the easier the problem is, as every node has a choice among a l
arge number of outputs.
Conversely, the larger
d
is, the harder the problem becomes as some nodes have to deal w
ith many conflicts
with at least one of their neighbors.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.