# On $t$-relaxed coloring of complete multi-partite graphs ††thanks: Supported
by NSFC No. 11771080.

Jun Lana and Wensong Lina,111Corresponding author. E-mail address:
<EMAIL_ADDRESS>
a School of Mathematics, Southeast University, Nanjing 210096, P.R. China

###### Abstract

Let $G$ be a graph and $t$ a nonnegative integer. Suppose $f$ is a mapping
from the vertex set of $G$ to $\\{1,2,\dots,k\\}$. If, for any vertex $u$ of
$G$, the number of neighbors $v$ of $u$ with $f(v)=f(u)$ is less than or equal
to $t$, then $f$ is called a $t$-relaxed $k$-coloring of $G$. And $G$ is said
to be $(k,t)$-colorable. The $t$-relaxed chromatic number of $G$, denote by
$\chi_{t}(G)$, is defined as the minimum integer $k$ such that $G$ is
$(k,t)$-colorable. A set $S$ of vertices in $G$ is $t$-sparse if $S$ induces a
graph with a maximum degree of at most $t$. Thus $G$ is $(k,t)$-colorable if
and only if the vertex set of $G$ can be partitioned into $k$ $t$-sparse sets.
It was proved by Belmonte, Lampis and Mitsou (2017) that the problem of
deciding if a complete multi-partite graph is $(k,t)$-colorable is NP-
complete. In this paper, we first give tight lower and up bounds for the
$t$-relaxed chromatic number of complete multi-partite graphs. And then we
design an algorithm to compute maximum $t$-sparse sets of complete multi-
partite graphs running in $O((t+1)^{2})$ time. Applying this algorithm, we
show that the greedy algorithm for $\chi_{t}(G)$ is $2$-approximate and runs
in $O(tn)$ time steps (where $n$ is the vertex number of $G$). In particular,
we prove that for $t\in\\{1,2,3,4,5,6\\}$, the greedy algorithm produces an
optimal $t$-relaxed coloring of a complete multi-partite graph. While, for
$t\geq 7$, examples are given to illustrate that the greedy strategy does not
always construct an optimal $t$-relaxed coloring.

Keywords: channel assignment problem, $t$-sparse set, $t$-relaxed chromatic
number, complete multi-partite graph.

2010 Mathematics Subject Classification:: 05C15, 05C85.

##  1 Introduction

Suppose there are many transmitters in an area. We need to assign a channel to
each transmitter through which it can transmit signals. To avoid interference,
“close” transmitters are required to receive different channels. The problem
is to assign channels to transmitters so that the number of channels assigned
is as small as possible. This channel assignment problem can be modeled as the
graph coloring problem. We use vertices of a graph to denote the transmitters
and if two transmitters are “close” to each other then the corresponding two
vertices are adjacent. The graph so obtained is referred as the interference
graph of the channel assignment problem. To minimize the number of channels
assigned to transmitters is equivalent to determine the chromatic number of
the interference graph.

In practice, sometimes, low level of interference is acceptable. Thus the
requirement that “close” transmitters must receive different channels can be
relaxed in some extend. This leads to the concept of relaxed (or improper, or
defective) coloring of a graph. Please refer to [1, 3, 5].

Let $G$ be a graph and $t$ a nonnegative integer. Suppose $f$ is a mapping
from the vertex set of $G$ to $\\{1,2,\dots,k\\}$. If, for any vertex $u$ of
$G$, the number of neighbors $v$ of $u$ with $f(v)=f(u)$ is less than or equal
to $t$, then $f$ is called a $t$-relaxed $k$-coloring of $G$. And $G$ is said
to be $(k,t)$-colorable. The $t$-relaxed chromatic number of $G$, denote by
$\chi_{t}(G)$, is defined as the minimum integer $k$ such that $G$ is
$(k,t)$-colorable. It is clear that $\chi_{0}(G)$ is the same as $\chi(G)$,
the chromatic number of $G$.

Let $S$ be a subset of $V(G)$. If the induced subgraph $G[S]$ has the maximum
degree at most $t$ then we call $S$ a $t$-sparse set of $G$. Let
$\beta_{t}(G)$ denote the order of the largest $t$-sparse set of $G$. It is
obvious that in a $t$-relaxed coloring of $G$ each color class is a $t$-sparse
set. Thus $\chi_{t}(G)\geq|V(G)|/\beta_{t}(G)$ for any graph $G$. For a graph
$G$, let $\Delta(G)$ denote the maximum degree of $G$. Let $\omega(G)$ denote
the clique number of $G$ (the number of vertices in a maximum complete
subgraph of $G$). The Brooks type result about the $t$-relaxed chromatic
number can be derived from a result proved by Lovász in [8].

###### Theorem 1.1

[8] Let $G$ be a graph and $k_{1},k_{2},\dots,k_{m}$ nonnegative integers such
that $\Delta(G)\leq\sum\limits_{i=1}^{m}(k_{i}+1)-1$, then there is a
partition of $V(G)$ into $m$ classes $V_{1},V_{2},\dots,V_{m}$ such that
$\Delta(G[V_{i}])\leq k_{i}$ for $i=1,2,\dots,m$, where $G[V_{i}]$ is the
subgraph of $G$ induced by the vertex set $V_{i}$.

By letting $k_{i}=t$ for $i=1,2,\dots,m$, we see that if
$m\geq\lceil\frac{\Delta(G)+1}{t+1}\rceil$ then $G$ is $(m,t)$-colorable. This
yields the following upper bound for $t$-relaxed chromatic number of a graph.

###### Corollary 1.2

For any graph $G$, $\chi_{t}(G)\leq\lceil\frac{\Delta(G)+1}{t+1}\rceil$.

There is also a relation between $\chi_{t}(G)$ and $\chi(G)$.

###### Theorem 1.3

For any graph $G$, $\chi_{t}(G)\geq\lceil\frac{\chi(G)}{t+1}\rceil$.

Proof. Let $k=\chi_{t}(G)$. Suppose $f$ is a $t$-relaxed coloring of $G$ that
partitions $V(G)$ into $k$ color classes $V_{1},V_{2},\dots,V_{k}$. Then, for
each $i=1,2,\dots,k$, the maximum degree of the subgraph $G[V_{i}]$ (the
subgraph induced by $V_{i}$) is at most $t$. By the Brook’s Theorem,
$\chi(G[V_{i}])\leq t+1$. That is, each $V_{i}$ can be decomposed into at most
$t+1$ independent sets. It follows that $\chi(G)\leq k(t+1)=\chi_{t}(G)(t+1)$,
implying $\chi_{t}(G)\geq\frac{\chi(G)}{t+1}$. Since $\chi_{t}(G)$ is
integral, the theorem follows.

Denote by $K_{n}$ the complete graph on $n$ vertices. From Corollary 1.2 and
Theorem 1.3, we have $\chi_{t}(K_{n})=\lceil\frac{n}{t+1}\rceil$. Thus both
the upper bound for $\chi_{t}(G)$ in Corollary 1.2 and the lower bound in
Theorem 1.3 are attainable.

For any two fixed integers $k\geq 2$ and $t\geq 1$, it was proved in [4] that
the problem of deciding if a graph is $(k,t)$-colorable is NP-complete. All
planar graphs are proved to be $(3,2)$-colorable in [3]. And in [4], the
authors proved the NP-completeness of the $(2,t)$-colorable problem ($t\geq
1$) and $(3,1)$-colorable problem for planar graphs. Havet, Kang, and Sereni
in [6] showed that the problem of deciding if a unit disk graph is
$(k,t)$-colorable is NP-complete for any two fixed integers $k\geq 3$ and
$t\geq 0$. A graph is an interval graph if its vertices are closed intervals
of $\mathbb{R}$ and two vertices are adjacent if the corresponding two
intervals intersect. For any two fixed nonnegative integers $k$ and $t$, it
was proved in [6] that the problem of deciding if an interval graph is
$(k,t)$-colorable is solvable in polynomial time. A unit interval graph is an
interval graph with every interval having unit length. It was proved in [6]
that, for any unit interval graph $G$,
$\lceil\frac{\omega(G)}{t+1}\rceil\leq\chi_{t}(G)\leq\lceil\frac{\omega(G)}{t+1}\rceil+1$.
However, as indicated by the authors in [6], even for unit interval graphs, it
is not known, for fixed integer $t\geq 1$, whether there is a polynomial time
algorithm to determine its $t$-relaxed chromatic number. For any two positive
integers $n$ and $r$ with $n\geq r+1$, denote by $P_{n}^{r}$ the $r$th power
of a path on $n$ vertices. Let $t$ be any positive integer, the $t$-relaxed
chromatic number of $P_{n}^{r}$ was determined in [7].

It was proved by Belmonte etc. in [2] that deciding if a complete multi-
partite graph is $(k,t)$-colorable is a NP-complete problem. Based on dynamic
programming method, they showed that there is an algorithm which decides if a
cograph admits a $(k,t)$-coloring in time $O^{*}(k^{O(t^{4})})$. Note that
complete multi-partite graphs are cographs. Thus if $t$ is bounded then the
$(k,t)$-colorable problem in cographs is polynomial-time solvable.

This paper focuses on $t$-relaxed colorings of complete multi-partite graphs.
Tight lower and up bounds for the $t$-relaxed chromatic number of complete
multi-partite graphs are given in next section. In Section 3, we first design
an algorithm to compute the maximum $t$-sparse set of a complete multi-partite
graph running in $O((t+1)^{2})$ time. Applying this algorithm, we then
describe the greedy algorithm that compute a $t$-relaxed coloring of a
complete multi-partite graph in $O(tn)$ time steps (where $n$ is the vertex
number of a graph). The approximation ratio of the greedy algorithm is proved
to be at most $2$. In Section 4 and 5, we show that the greedy algorithm
actually outputs an optimal $t$-relaxed coloring of a complete multi-partite
graph for $t=1,3$, respectively. The similar arguments in Section 4 and 5 work
for the case when $1\leq t\leq 6$. However, if $t\geq 7$ they do not work any
more. In Section 6, for $t\geq 7$, examples are given to illustrate that the
greedy strategy does not always construct an optimal $t$-relaxed coloring.

##  2 Lower and upper bounds

Let $s\geq 2$ be an integer. Let $n_{1},n_{2},\dots,n_{s}$ be $s$ positive
integers. For convenience, we always assume $n_{1}\geq n_{2}\geq\cdots\geq
n_{s}$. Denote by $K(n_{1},n_{2},\dots,n_{s})$ the complete $s$-partite graph
with the $s$ parts having $n_{1},n_{2},\dots,n_{s}$ vertices, respectively.
For $i=1,2,\dots,s$, let $V_{i}$ be the set of vertices in the $i$th part of
$K(n_{1},n_{2},\dots,n_{s})$. It is obvious that
$\chi(K(n_{1},n_{2},\dots,n_{s}))=s=\omega(K(n_{1},n_{2},\dots,n_{s}))$.

In this paper, we always assume that $t$ is a fixed positive integer. Suppose
$f$ is a $t$-relaxed coloring of $K(n_{1},n_{2},\dots,n_{s})$. For any color
$i$ used by $f$, denote by $f^{-1}(i)$ the set of vertices that are assigned
the color $i$. We say the color $i$ appears on some part $V_{j}$ if there is
at least one vertex in $V_{j}$ assigned the color $i$. Let $S$ be a subset of
$V(G)$, denote by $f(S)$ the set of colors that are assigned to vertices in
$S$. Let $||f||$ denote the order of $f(V(G))$, that is, the number of
distinct colors used by $f$.

###### Lemma 2.1

Let $f$ be a $t$-relaxed coloring of $K(n_{1},n_{2},\dots,n_{s})$. If a color
$i$ appears on exact $r\geq 2$ parts of $K(n_{1},n_{2},\dots,n_{s})$, then
$|f^{-1}(i)|\leq t+\lfloor\frac{t}{r-1}\rfloor$.

Proof. Suppose the color $i$ appears on the $r$ parts
$V_{j_{1}},V_{j_{2}},\dots,V_{j_{r}}$. For $q=1,2,\dots,r$, let
$x_{q}=|V_{j_{q}}\cap f^{-1}(i)|$. Since $f$ is a $t$-relaxed coloring, for
$p=1,2,\dots,r$, we have $\sum\limits_{q=1}^{r}x_{q}-x_{p}\leq t$. Summing up
all these $r$ inequalities together, we get
$(r-1)\sum\limits_{q=1}^{r}x_{q}\leq rt$. Thus
$|f^{-1}(i)|=\sum\limits_{q=1}^{r}x_{q}\leq t+\frac{t}{r-1}$. Note that
$|f^{-1}(i)|$ is an integer, the lemma follows.

###### Corollary 2.2

Let $K(n_{1},n_{2},\dots,n_{s})$ be the complete $s$-partite with $n_{1}\geq
n_{2}\geq\cdots\geq n_{s}$. If $n\geq 2t$ then
$\beta_{t}(K(n_{1},n_{2},\dots,n_{s}))=n_{1}$, and if $n_{1}\leq 2t$ then
$\beta_{t}(K(n_{1},n_{2},\dots,n_{s}))\leq 2t$.

###### Corollary 2.3

If $n_{j}\geq 2t$ for each $j=1,2,\dots,s$, then
$\chi_{t}(K(n_{1},n_{2},\dots,n_{s}))=s$.

Proof. It is clear that $\chi_{t}(K(n_{1},n_{2},\dots,n_{s}))\leq s$. We prove
the opposite inequality by induction on $s$. It is obviously true for $s=1$.
Suppose it holds for all complete $(s-1)$-partite graphs with each part having
at least $2t$ vertices. Now consider the graph $K(n_{1},n_{2},\dots,n_{s})$
with $n_{s}\geq 2t$.

Let $f$ be any $t$-relaxed coloring of $K(n_{1},n_{2},\dots,n_{s})$. If a
color $i$ appears only on one part, say $V_{j}$, then by the induction
hypothesis, $\chi_{t}(K(n_{1},n_{2},\dots,n_{s})-V_{j})\geq s-1$, implying
that $||f||\geq s$. Thus we assume that each color appears on at least $2$
parts. By Lemma 2.1, each color is assigned to at most $2t$ vertices of
$K(n_{1},n_{2},\dots,n_{s})$, implying that $||f||\geq s$. Therefore
$\chi_{t}(K(n_{1},n_{2},\dots,n_{s}))\geq s$ and the corollary follows.

This corollary provides a class of graphs $G$ with $\chi_{t}(G)=\chi(G)$ for
any positive integer $t$.

###### Theorem 2.4

Suppose $G=K(n_{1},n_{2},\dots,n_{s})$ has $r$ parts of order at least $2t$.
Let $\sigma_{r+1,s}=\sum\limits_{j=r+1}^{s}n_{j}$. Then
$r+\lceil\frac{\sigma_{r+1,s}}{2t}\rceil\leq\chi_{t}(G)\leq
r+\lceil\frac{\sigma_{r+1,s}}{t+1}\rceil$. Both the lower and upper bounds are
attainable.

Proof. We first prove the upper bound. Let $H_{1}=K(n_{1},\dots,n_{r})$ and
$H_{2}=K(n_{r+1},\dots,n_{s})$. It is obvious that
$\chi_{t}(G)\leq\chi_{t}(H_{1})+\chi_{t}(H_{2})$. By Corollary 2.3,
$\chi_{t}(H_{1})=r$. On the other hand, by Corollary 1.2,
$\chi_{t}(H_{2})\leq\lceil\frac{\Delta(H_{2})+1}{t+1}\rceil\leq\frac{|V(H_{2})|}{t+1}=\lceil\frac{\sigma_{r+1,s}}{t+1}\rceil$.
Thus $\chi_{t}(G)\leq r+\lceil\frac{\sigma_{r+1,s}}{t+1}\rceil$.

We now show the lower bound. Suppose $f$ is an optimal $t$-relaxed coloring of
$G$. Let

$I=\\{i:\ \exists\ j\in\\{1,2,\dots,r\\}\ \mbox{s.t. $|f^{-1}(i)\cap
V_{j}|\geq t+1$}\\}.$

It is clear that, for each $i\in I$, there is an integer
$j_{i}\in\\{1,2,\dots,r\\}$ such that $f^{-1}(i)\subseteq V_{j_{i}}$. Thus
$\sum\limits_{i\in I}|f^{-1}(i)|\leq\sum\limits_{i\in I}|V_{j_{i}}|\leq
n_{1}+n_{2}+\cdots+n_{|I|}$. From the definition of $I$, if $i\in
f(G)\setminus I$ then $|f^{-1}(i)\cap V_{j}|\leq t$ for all
$j\in\\{1,2,\dots,r\\}$, implying by Lemma 2.1 that $|f^{-1}(i)|\leq 2t$. Then

$\sum\limits_{i=1}^{s}n_{i}=\sum\limits_{i\in I}|f^{-1}(i)|+\sum\limits_{i\in
f(G)\setminus I}|f^{-1}(i)|\leq n_{1}+n_{2}+\cdots+n_{|I|}+2t|f(G)\setminus
I|.$

It follows that $|f(G)\setminus
I|\geq\frac{\sum\limits_{i=|I|+1}^{r}n_{i}}{2t}+\frac{\sum\limits_{i=r+1}^{s}n_{i}}{2t}\geq
r-|I|+\frac{\sum\limits_{i=r+1}^{s}n_{i}}{2t}$. Therefore $\chi_{t}(G)\geq
r+\lceil\frac{\sigma_{r+1,s}}{2t}\rceil$.

Let $G_{1}=K(n_{1},n_{2},\dots,n_{s})$ with $n_{1}=\cdots=n_{r}=2t+1$ and
$n_{r+1}=\cdots=n_{s}=1$. Suppose $f$ is an optimal $t$-relaxed coloring of
$G_{1}$. Let $I=f(V_{1}\cup\cdots\cup V_{r})\setminus f(V_{r+1}\cup\cdots\cup
V_{s})$. It is clear that, for each $i\in I$, $|f^{-1}(i)|\leq 2t+1$. For each
$i\in f(G_{1})\setminus I$, there exists some $j\in\\{r+1,r+2,\dots,s\\}$ such
that $f^{-1}(i)\cap V_{j}\not=\emptyset$, implying that $|f^{-1}(i)|\leq t+1$.
Then $(2t+1)r+s-r\leq(2t+1)|I|+(t+1)|f(G_{1})\setminus I|$. On the other hand,
in an optimal $t$-relaxed coloring of $G_{1}$, we must have $|I|\leq r$. Thus
$|f(G_{1})\setminus I|\geq\frac{(2t+1)(r-|I|)}{t+1}+\frac{s-r}{t+1}\geq
r-|I|+\frac{s-r}{t+1}$, implying that $|f(G_{1})|\geq
r+\lceil\frac{\sigma_{r+1,s}}{t+1}\rceil$. Therefore
$\chi_{t}(G_{1})=r+\lceil\frac{\sigma_{r+1,s}}{t+1}\rceil$, attaining the
upper bound.

Let $G_{2}=K(n_{1},n_{2},\dots,n_{s})$ with $n_{1}=\cdots=n_{r}=2t$ and
$n_{r+1}=\cdots=n_{s}=t$. Define a $t$-relaxed coloring $f$ of $G_{2}$ as
follows. For each $j\in\\{1,2,\dots,r\\}$, let $f(V_{j})=\\{j\\}$. For each
$j\in\\{1,2,\dots,\lceil\frac{s-r}{2}\rceil-1\\}$, let $f(V_{r+2j-1}\cup
V_{r+2j})=\\{r+j\\}$. Finally, if $s-r$ is even then let $f(V_{s-1}\cup
V_{s})=\\{\frac{s-r}{2}\\}$, and if $s-r$ is odd then let
$f(V_{s})=\\{\lceil\frac{s-r}{2}\rceil\\}$. It is clear that
$|f(G_{2})|=r+\lceil\frac{s-r}{2}\rceil=r+\lceil\frac{\sigma_{r+1,s}}{2t}\rceil$.
Thus $\chi_{t}(G_{2})=r+\lceil\frac{\sigma_{r+1,s}}{2t}\rceil$, attaining the
lower bound.

Remark: Let $G=K(n_{1},n_{2},\dots,n_{s})$ be a complete multi-partite graph
with $s$ parts. Suppose $n_{i}<2t$ for each $i=1,2,\dots,s$. According to
Theorem 2.4,
$\lceil\frac{n_{1}+n_{2}+\cdots+n_{s}}{2t}\rceil\leq\chi_{t}(G)\leq\lceil\frac{n_{1}+n_{2}+\cdots+n_{s}}{t+1}\rceil$.
Let $n=n_{1}+n_{2}+\cdots+n_{s}$. Then, for each
$k\in[\lceil\frac{n}{2t}\rceil,\lceil\frac{n}{t+1}\rceil]$, to determine if
$G$ is $(k,t)$-colorable, the algorithm given by Belmonte etc. in [2] runs in
$O^{*}(k^{O(t^{4})})$ time steps. Even when $t=3$, the time complexity is
about $(\frac{n}{6})^{81}$. It is thus meaningful to design more efficient
algorithm for computing the $t$-relaxed chromatic numbers of complete multi-
partite graphs. We are trying to do so in the following sections.

##  3 The greedy algorithm

In this section, we present a greedy algorithm to construct a $t$-relaxed
coloring of complete multi-partite graphs. Note that the deletion of any
subset of vertices of a complete multi-partite graph results in a new complete
multi-partite graph. The key idea of the greedy algorithm is that each time we
find a maximum $t$-sparse set of the subgraph induced by all uncolored
vertices and assign a new color to all vertices in it. We need to specify the
technique how to find a maximum $t$-sparse set of the subgraph induced by all
uncolored vertices so that the complexity of the greedy algorithm can be
estimated accurately.

In general, the problem of deciding if $\beta_{t}(G)\geq k$ is NP-complete,
see [9]. However, in this section, we shall first show that $\beta(G)$ for
multi-partite graphs can be computed in $O((t+1)^{2})$ time steps, provided
that the order of parts are given in non-increasing order.

Let the $s$ parts of $G=K(n_{1},n_{2},\dots,n_{s})$ be
$V_{1},V_{2},\dots,V_{s}$. For $j\in\\{1,2,\dots,s\\}$, let
$V_{j}=\\{v_{j}^{1},v_{j}^{2},\dots,v_{j}^{n_{j}}\\}$. Sort the parts of $G$
such that $n_{1}\geq n_{2}\geq\cdots\geq n_{s}$. If $n_{1}\geq 2t$ then
according to Corollary 2.2 the set $V_{1}$ is the largest $t$-sparse set of
$G$. Thus we assume $n_{1}<2t$.

Note that any $t$-sparse set of $G$ intersects with at most $t+1$ parts. To
find a maximum $t$-sparse set of $G$, it suffices to find, for every
$i=2,3,\dots,\min\\{s,t+1\\}$, a maximum $t$-sparse set of $G$ with the
property that it intersects exactly $i$ parts of $G$. The maximum is clearly
attained by the first $i$ parts. Thus we only need to find a maximum
$t$-sparse set of $G$ with the property that it intersects exactly the first
$i$ parts of $G$. For $j=1,2,\dots,i$, let $x_{j}$ be the number of vertices
we are going to choose from the part $V_{j}$. The objective is to maximize the
sum $x_{1}+x_{2}+\cdots+x_{i}$ subject to $1\leq x_{j}\leq n_{j}$ and
$\sum\limits_{h=1}^{i}x_{h}-x_{j}\leq t$ for each $j=1,2,\dots,i$. Again,
without loss of generality, we may assume $x_{1}\geq x_{2}\geq\cdots\geq
x_{i}$. For $i\in\\{2,3,\dots,\min\\{s,t+1\\}\\}$, we define this integral
linear programming, denote by $LP(i)$, as follows:

$\begin{array}[]{ll}LP(i):&\max:\ x_{1}+x_{2}+\cdots+x_{i}\\\
s.t.&\sum\limits_{h=1}^{i}x_{h}-x_{j}\leq t,\ j=1,2,\dots,i;\\\ &1\leq
x_{j}\leq n_{j},\ j=1,2,\dots,i;\\\ &x_{1}\geq x_{2}\geq\cdots\geq
x_{i}.\end{array}$

If $n_{i}\leq\lfloor\frac{t}{i-1}\rfloor$ then let $x_{i}=n_{i}$ and choose
$(x_{1},x_{2},\dots,x_{i-1})$ with $x_{1}\geq x_{2}\geq\cdots\geq x_{i-1}\geq
n_{i}$ so that $x_{1}+x_{2}\cdots+x_{i-1}=\min\\{t,n_{1}+\cdots+n_{i-1}\\}$.
If $n_{i}>\lfloor\frac{t}{i-1}\rfloor$ then let
$x_{i}=\lfloor\frac{t}{i-1}\rfloor$ and choose $(x_{1},x_{2},\dots,x_{i-1})$
with $x_{1}\geq x_{2}\geq\cdots\geq x_{i-1}\geq n_{i}$ so that
$x_{1}+x_{2}\cdots+x_{i-1}=t$. It is straightforward to check that this gives
an optimal solution of $LP(i)$.

###### Problem 1

(Find a maximum $t$-sparse set of a complete multi-partite graph)
Input: A complete multi-partite graph $G$.
Output: A maximum $t$-sparse set of $G$.

According to above discussions, the algorithm to compute the maximum
$t$-sparse set of a complete multi-partite graph can be describe as in
Algorithm 1.

Algorithm 1 Find a maximum $t$-sparse set of a complete multi-partite graph.

1: Sort the parts of $G$ such that $n_{1}\geq n_{2}\geq\cdots\geq n_{s}$.

2: Set $s^{*}:=\min\\{t+1,s\\}$.

3: If $n_{1}\geq 2t$ then output $x^{(1)}=(n_{1})$.

4: else for $i=2$ to $s^{*}$ do

5: Solve $LP(i)$. Set $x^{(i)}$ be the optimal solution. Set $M_{i}$ be the
optimal value of $LP(i)$.

6: Find the minimum number $k$ such that
$M_{k}=\max\\{M_{2},M_{3},\dots,M_{s^{*}}\\}$.

7: Output $x^{(k)}$.

We are now ready to present the greedy algorithm for $t$-relaxed coloring of a
complete multi-partite graph.

###### Problem 2

(Find an optimal $t$-relaxed coloring of a complete multi-partite graph)
Input: A complete multi-partite graph $G$.
Output: An optimal $t$-relaxed coloring of $G$.

For a subset $S$ of $V(G)$, we use $G[S]$ to denote the subgraph of $G$
induced by $S$.

Algorithm 2 Construct a $t$-relaxed coloring of a complete multi-partite graph

1: Set $V=V_{1}\cup V_{2}\cup\cdots\cup V_{s}$.

2: Set $i:=1$ and $R:=\emptyset$.

3: While $V\setminus R$ is not empty do: Use Algorithm 1 to find a maximum
$t$-sparse set $W$ of $G[V\setminus R]$. Assign the color $i$ to all vertices
in $W$. Set $R:=R\cup W$ and $i:=i+1$.

4: Output the coloring.

It is easy to see that Algorithm 1 runs in $O((t+1)^{2})$ time. While
Algorithm 2 will call Algorithm 1 at most $\lceil\frac{n}{t+1}\rceil$ times.
Thus the overall complexity of Algorithm 2 is $O(tn)$.

Suppose $G=K(n_{1},n_{2},\dots,n_{s})$ has $r$ parts of order at least $2t$.
Let $\sigma_{r+1,s}=\sum\limits_{j=r+1}^{s}n_{j}$. Then by Theorem 2.4, we
have $r+\lceil\frac{\sigma_{r+1,s}}{2t}\rceil\leq\chi_{t}(G)\leq
r+\lceil\frac{\sigma_{r+1,s}}{t+1}\rceil$. According to the steps of Algorithm
2, the $t$-relaxed coloring produced by Algorithm 2 will use at most
$r+\lceil\frac{\sigma_{r+1,s}}{t+1}\rceil$ colors. Thus the approximation
ratio of Algorithm 2 is at most
$\frac{r+\lceil\frac{\sigma_{r+1,s}}{t+1}\rceil}{r+\lceil\frac{\sigma_{r+1,s}}{2t}\rceil}\leq
2$.

In what follows, we first prove that for $t\in\\{1,2,3,4,5,6\\}$, the greedy
algorithm produces an optimal $t$-relaxed coloring of a complete multi-partite
graph. And then, for $t\geq 7$, we construct examples to illustrate that the
greedy strategy does not always construct an optimal $t$-relaxed coloring. We
only present the proofs of $t=1$ and $t=3$. Though the idea behind the proofs
are the same, the proofs of $t=4,5,6$ are somewhat complicated than that of
$t=3$. So we omit them here.

##  4 Determining the $1$-relaxed chromatic number of
$K(n_{1},n_{2},\dots,n_{s})$

###### Lemma 4.1

Let $j$ be an integer in $\\{1,2,\dots,s\\}$. If $n_{j}\geq 2$ then there is
an optimal $1$-relaxed coloring $f$ of $K(n_{1},n_{2},\dots,n_{s})$ with
$|f(V_{j})|=1$.

Proof. Without loss of generality, we may assume that $n_{j}=2$. Let $f$ be an
optimal $1$-relaxed coloring of $K(n_{1},n_{2},\dots,n_{s})$. If
$|f(V_{j})|=1$ then we are done.

Suppose $|f(V_{j})|=2$. Let $v_{j}^{1}$ and $v_{j}^{2}$ be the two vertices in
$V_{j}$ with $f(v_{j}^{1})=i_{1}$ and $f(v_{j}^{2})=i_{2}$, where
$i_{1}\not=i_{2}$. If the color $i_{1}$ (resp. $i_{2}$) does not appear on any
vertex outside $V_{j}$, then, by recoloring the vertex $v_{j}^{2}$ (resp.
$v_{j}^{1}$) with the color $i_{1}$ (resp. $i_{2}$), we get a $1$-relaxed
coloring of $K(n_{1},n_{2},\dots,n_{s})$. Denote this coloring by
$f^{\prime}$. It is clear that $f^{\prime}$ is optimal and
$|f^{\prime}(V_{j})|=1$.

Thus we assume that there are two vertices $w_{1}$ and $w_{2}$ outside $V_{j}$
with $f(w_{1})=i_{1}$ and $f(w_{2})=i_{2}$. Since $f$ is a $1$-relaxed
coloring, $f^{-1}(i_{1})=\\{v_{j}^{1},w_{1}\\}$ and
$f^{-1}(i_{2})=\\{v_{j}^{2},w_{2}\\}$. Now, by recoloring the vertex $w_{1}$
with the color $i_{2}$ and the vertex $v_{j}^{2}$ with the color $i_{1}$, one
gets an optimal $1$-relaxed coloring of $K(n_{1},n_{2},\dots,n_{s})$. Denote
the so obtained coloring by $f^{\prime\prime}$. It is clear that
$f^{\prime\prime}$ is optimal and $|f^{\prime\prime}(V_{j})|=1$. The lemma
follows.

We immediately have the following corollary.

###### Corollary 4.2

Let $j$ be an integer in $\\{1,2,\dots,s\\}$. If $n_{j}\geq 2$ then
$\chi_{1}(K(n_{1},n_{2},\dots,n_{s}))=\chi_{1}(K(n_{1},n_{2},\dots,n_{s})-V_{j})+1$.

Since $\chi_{t}(K_{n})=\lceil\frac{n}{t+1}\rceil$, Corollary 4.2 implies the
following theorem.

###### Theorem 4.3

Let $G$ be any complete $s$-partite graph. Suppose there are $r$ single vertex
parts in $G$. Then $\chi_{1}(G)=s-r+\lceil\frac{r}{2}\rceil$.

It follows from the theorem that Algorithm 2 presented in the previous section
will output an optimal $1$-relaxed coloring of a complete multi-partite graph.

##  5 Computing the $3$-relaxed chromatic number of
$K(n_{1},n_{2},\dots,n_{s})$

In this section, we prove that the greedy algorithm produces an optimal
$t$-relaxed coloring of a complete multi-partite graph for $t\leq 6$. This
would be proved one by one for $t=2,3,4,5,6$. However the idea behind the
proof is essentially the same. Thus, in the following, we only present the
proof for $t=3$.

Let $V=\cup_{j=1}^{s}V_{j}$ be the vertex set of $K(n_{1},n_{2},\dots,n_{s})$.
For an integer $j\in\\{1,2,\dots,s\\}$, the $n_{j}$ vertices in part $V_{j}$
are denoted by $v_{j}^{1},v_{j}^{2},\dots,v_{j}^{n_{j}}$. Suppose $f$ is a
$t$-relaxed coloring of $K(n_{1},n_{2},\dots,n_{s})$. Then $f(V)$ is the set
of colors used by $f$. For $r\in f(V)$ and $h\in\\{1,2,\dots,s\\}$, let
$V_{r,h}$ denote the set of vertices in $V_{h}$ that are assigned the color
$r$ under $f$. And let $m_{r,h}$ be the order of $V_{r,h}$.

###### Lemma 5.1

Suppose $G=K(n_{1},n_{2},\dots,n_{s})$ has at least one part having at least
$6$ vertices. Then there is an optimal $3$-relaxed coloring $f$ and a part
$V_{j}$ with $n_{j}\geq 6$ such that $|f(V_{j})|=1$.

Proof. Let $f$ be an optimal $3$-relaxed coloring of
$K(n_{1},n_{2},\dots,n_{s})$. Choose $i\in f(V)$ and $j\in\\{1,2,\dots,s\\}$
such that $m_{i,j}=\max\\{m_{r,h}:\ r\in f(V)\ \mbox{and
$h\in\\{1,2,\dots,s\\}$ with $n_{h}\geq 6$}\\}$. We consider the following
four cases.

Case 1. $m_{i,j}\geq 4$. Since $f$ is a $3$-relaxed coloring of $G$, in this
case, we have $m_{i,p}=0$ for each $p\in\\{1,2,\dots,s\\}\setminus\\{j\\}$. If
there are some vertices in $V_{j}$ that are not colored by the color $i$, then
we can recolor them by the color $i$. And the resulting coloring is the
desired one.

Case 2. $m_{i,j}=3$. If $f^{-1}(i)\cap(V\setminus V_{j})=\emptyset$ then we
can deal with it as in Case 1. Otherwise, there is exactly one other part of
$G$, say $V_{p}$, with $V_{i,p}\not=\emptyset$. Let
$V_{i,p}=\\{v_{p}^{1},\dots,v_{p}^{b}\\}$ for some $b\in\\{1,2,3\\}$. Then we
define a new $3$-relaxed coloring $f^{\prime}$ as follows

$\begin{array}[]{ll}f^{\prime}(v_{j}^{d})=i,~{}\mbox{for}~{}1\leq d\leq
n_{j},\\\ f^{\prime}(v_{p}^{d})=f(v_{j}^{3+d}),~{}\mbox{for}~{}1\leq d\leq
b,\\\ f^{\prime}(u)=f(u),~{}\mbox{for all other vertices $u$
of}~{}G.\end{array}$

It is easy to check that $f^{\prime}$ is an optimal $3$-relaxed coloring of
$G$ with $|f^{\prime}(V_{j})|=1$.

Case 3. $m_{i,j}=2$. Then $m_{i^{*},j}\leq 2$ for any $i^{*}\in f(V)$. In this
case, there are at most two other parts of $G$ with vertices assigned the
color $i$. If there is at most one other part of $G$ with vertices assigned
the color $i$, then we can deal with it as in Case 2. Thus we assume that
there are exact two other such parts of $G$, say $V_{p}$ and $V_{q}$. Since
$f$ is a $3$-relaxed coloring, we must have $m_{i,p}=m_{i,q}=1$. Let
$v_{p}^{1}$ and $v_{q}^{1}$ be the two vertices in $V_{i,p}$ and $V_{i,q}$.
Since $m_{i,j}=2$ and $n_{j}\geq 6$, except the color $i$, there are at least
two other distinct colors, say $i_{1}$ and $i_{2}$, in $f(V_{j})$. We now
define a new $3$-relaxed coloring $f^{\prime}$ as follows

$\begin{array}[]{ll}f^{\prime}(v_{j}^{d})=i,~{}\mbox{for}~{}1\leq d\leq
n_{j},\\\
f^{\prime}(v_{p}^{1})=i_{1},~{}\mbox{and}~{}f^{\prime}(v_{q}^{1})=i_{2},\\\
f^{\prime}(u)=f(u),~{}\mbox{for all other vertices $u$ of}~{}G.\end{array}$

It is easy to check that $f^{\prime}$ is an optimal $3$-relaxed coloring of
$G$ with $|f^{\prime}(V_{j})|=1$.

Case 4. $m_{i,j}=1$. Then $m_{i^{*},j}\leq 1$ for any $i^{*}\in f(V)$. Let $b$
be the number of vertices in $V\setminus V_{j}$ that are assigned the color
$i$ and let $w_{1},w_{2},\dots,w_{b}$ be these $b$ vertices. Since $f$ is a
$3$-relaxed coloring of $G$, we have $b\leq 3$. Note that $n_{j}\geq 6$ and
$m_{i^{*},j}\leq 1$ for any $i^{*}\in f(V)$, there are at least $5$ different
colors, say $i_{1},i_{2},\dots,i_{5}$, each appearing on exact one vertex in
$V_{j}$. We now define a new $3$-relaxed coloring $f^{\prime}$ as follows

$\begin{array}[]{ll}f^{\prime}(v_{j}^{d})=i,~{}\mbox{for}~{}1\leq d\leq
n_{j},\\\ f^{\prime}(w_{d})=i_{d},~{}\mbox{for}~{}1\leq d\leq b,\\\
f^{\prime}(u)=f(u),~{}\mbox{for all other vertices $u$ of}~{}G.\end{array}$

It is easy to check that $f^{\prime}$ is an optimal $3$-relaxed coloring of
$G$ with $|f^{\prime}(V_{j})|=1$.

By Lemma 5.1, we immediately have the following corollary.

###### Corollary 5.2

Let $j$ be an integer in $\\{1,2,\dots,s\\}$. If $n_{j}\geq 6$ then
$\chi_{3}(K(n_{1},n_{2},\dots,n_{s}))=\chi_{3}(K(n_{1},n_{2},\dots,n_{s})-V_{j})+1$.

From Corollary 5.2, to compute the $3$-relaxed chromatic number of a complete
multi-partite graph it suffices to consider those complete multi-partite
graphs with each part having at most $5$ vertices. Thus, from now on, we
assume that $G$ is a complete multi-partite graph $K(n_{1},n_{2},\dots,n_{s})$
with $n_{j}\leq 5$ for $j=1,2,\dots,s$.

Let $f$ be an optimal $3$-relaxed coloring of $K(n_{1},n_{2},\dots,n_{s})$.
For convenience, for each part $V_{j}$, we relabel all vertices in $V_{j}$
according to the colors assigned to them. After the relabeling, for any two
vertices $v_{j}^{x}$ and $v_{j}^{y}$ in $V_{j}$ with $x<y$, if
$f(v_{j}^{x})=f(v_{j}^{y})$ then $f(v_{j}^{q})=f(v_{j}^{x})$ for all
$q\in\\{x,x+1,\dots,y\\}$, and if $f(v_{j}^{x})\not=f(v_{j}^{y})$ then
$|f^{-1}(f(v_{j}^{x}))|\geq|f^{-1}(f(v_{j}^{y}))|$. For example, suppose
$f(V_{j})=\\{1,2,4\\}$ and $|f^{-1}(1)|=2$, $|f^{-1}(2)|=1$ and
$|f^{-1}(4)|=3$, then $f^{-1}(4)=\\{v_{j}^{1},v_{j}^{2},v_{j}^{3}\\}$,
$f^{-1}(1)=\\{v_{j}^{4},v_{j}^{5}\\}$ and $f^{-1}(2)=\\{v_{j}^{6}\\}$.

###### Lemma 5.3

Let $G$ be a complete multi-partite graph $K(n_{1},n_{2},\dots,n_{s})$ with
$n_{j}\leq 5$ for $j=1,2,\dots,s$. Suppose $G$ has at least two parts of order
at least $3$. Then there is an optimal $3$-relaxed coloring of $G$ which
assigns three vertices of $V_{1}$ and three vertices of $V_{2}$ the same
color.

Proof. Let $f$ be an optimal $3$-relaxed coloring of
$K(n_{1},n_{2},\dots,n_{s})$. Choose $i\in f(V)$ and $j\in\\{1,2\\}$ such that
$m_{i,j}=\max\\{m_{r,h}:r\in f(V)\ \mbox{and $h\in\\{1,2\\}$}\\}$. Let
$\\{j,q\\}=\\{1,2\\}$. We consider the following four cases.

Case 1. $m_{i,j}\geq 4$. Then $m_{i,p}=0$ for each
$p\in\\{q\\}\cup\\{3,4,\dots,s\\}$. We now define a new coloring $f^{\prime}$
as follows

$\begin{array}[]{ll}f^{\prime}(v_{j}^{d})=i,~{}\mbox{for}~{}1\leq d\leq 3,\\\
f^{\prime}(v_{q}^{d})=i,~{}\mbox{for}~{}1\leq d\leq 3,\\\
f^{\prime}(v_{j}^{d})=f(v_{q}^{d-3}),~{}\mbox{for}~{}4\leq d\leq n_{j},\\\
f^{\prime}(u)=f(u),~{}\mbox{for all other vertices $u$ of}~{}G.\end{array}$

It is clear that $|f^{\prime}(V)|\leq|f(V)|$. If
$f(v_{q}^{1})\not=f(v_{q}^{4})$ then we also have
$f(v_{q}^{2})\not=f(v_{q}^{4})$. It is easy to see that $f^{\prime}$ is the
desired $3$-relaxed coloring of $G$. If $f(v_{q}^{1})=f(v_{q}^{4})$ then
$f(v_{q}^{2})=f(v_{q}^{3})=f(v_{q}^{4})$. It follows that the color
$f(v_{q}^{1})$ only appears on vertices in $V_{q}$, implying that $f^{\prime}$
is the desired $3$-relaxed coloring of $G$.

Case 2. $m_{i,j}=3$. Then $m_{i,q}\leq 3$ and there is at most one integer
$p\in\\{q\\}\cup\\{3,4,\dots,s\\}$ with $m_{i,p}>0$. If $m_{i,p}=0$ for all
$p\in\\{q\\}\cup\\{3,4,\dots,s\\}$ then by recoloring the three vertices
$v_{q}^{1},v_{q}^{2},v_{q}^{3}$ with the color $i$ we obtain a desired
$3$-relaxed coloring of $G$. Suppose $m_{i,q}>0$. If $m_{i,q}=3$ then we are
done. If $m_{i,q}<3$ then choose any $3-m_{i,q}$ vertices in $V_{q}$ that are
not colored by $i$ and recolor them with the color $i$, resulting a desired
$3$-relaxed coloring of $G$.

Now suppose $m_{i,q}=0$ and there is an integer $p\in\\{3,4,\dots,s\\}$ with
$m_{i,p}>0$. Then $1\leq m_{i,p}\leq 3$. Let $m_{i^{*},q}=\max\\{m_{r,q}:r\in
f(V_{q})\\}$. If $m_{i^{*},q}=3$ then recolor the three vertices
$v_{q}^{1},v_{q}^{2},v_{q}^{3}$ with the color $i$ and recolor the vertices in
$V_{i,p}$ with the color $i^{*}$. It is not difficult to check that the
resulting coloring is the desired one. If $m_{i^{*},q}=1$ then recolor the
three vertices $v_{q}^{1},v_{q}^{2},v_{q}^{3}$ with the color $i$ and recolor
the vertices in $V_{i,p}$ with different colors from
$\\{f(v_{q}^{1}),f(v_{q}^{2}),f(v_{q}^{3})\\}$. Again we can check that the
resulting coloring is the desired one.

We are now left with the case $m_{i^{*},q}=2$. Let
$V_{i^{*},q}=\\{v_{q}^{1},v_{q}^{2}\\}$. If $m_{i,p}\leq 2$ then recolor the
three vertices $v_{q}^{1},v_{q}^{2},v_{q}^{3}$ with the color $i$ and recolor
the vertices in $V_{i,p}$ with the color $i^{*}$. It is straightforward to
check that the resulting coloring is the desired one. Thus we assume
$m_{i,p}=3$. If there is a color $i^{\prime}$ appearing on exact one vertex,
say $v_{q}^{d}$, in $V_{q}$, then recolor the three vertices
$v_{q}^{1},v_{q}^{2},v_{q}^{3}$ with the color $i$ and recolor the three
vertices in $V_{i,p}$ with the colors $i^{*}$ and $i^{\prime}$, two of them
with $i^{*}$ and the other with $i^{\prime}$. It can be checked that the
resulting coloring is the desired one. The remaining case now is that each
color appears on exact two vertices in $V_{q}$, implying $n_{q}=4$. Let
$i^{*}$ and $i^{\prime}$ be the two colors appearing on vertices in $V_{q}$
with $V_{i^{*},q}=\\{v_{q}^{1},v_{q}^{2}\\}$ and
$V_{i^{\prime},q}=\\{v_{q}^{3},v_{q}^{4}\\}$. If $|f^{-1}(i^{\prime})\setminus
V_{q}|\leq 2$ then recolor the three vertices $v_{q}^{1},v_{q}^{2},v_{q}^{3}$
with the color $i$ and recolor the three vertices in $V_{i,p}$ with the colors
$i^{*}$ and $i^{\prime}$, two of them with $i^{*}$ and the other with
$i^{\prime}$. It is easy to see that the resulting coloring is the desired
one. If $|f^{-1}(i^{\prime})\setminus V_{q}|=3$ then there is a part $V_{l}$
with $f^{-1}(i^{\prime})\setminus V_{q}=V_{i^{\prime},l}$. Recolor the three
vertices $v_{q}^{2},v_{q}^{3},v_{q}^{4}$ with the color $i$ and recolor the
three vertices in $V_{i,p}$ with the same color $i^{\prime}$. It is not
difficult to check that the resulting coloring is the desired one.

Case 3. $m_{i,j}=2$. Let $V_{i,j}=\\{v_{j}^{1},v_{j}^{2}\\}$. Then
$m_{r,h}\leq 2$ for all $r\in f(G)$ and $h\in\\{1,2\\}$ and there are at most
two integers $p\in\\{q\\}\cup\\{3,4,\dots,s\\}$ with $m_{i,p}>0$. Furthermore,
if $p$ and $p^{\prime}$ are two integers in $\\{q\\}\cup\\{3,4,\dots,s\\}$
with $m_{i,p}>0$ and $m_{i,p^{\prime}}>0$ then $m_{i,p}=m_{i,p^{\prime}}=1$.
It is clear that $|f^{-1}(i)\setminus V_{j}|\leq 3$ and if
$|f^{-1}(i)\setminus V_{j}|=3$ then there is some
$p\in\\{1,2,\dots,s\\}\setminus\\{j\\}$ with $V_{i,p}=f^{-1}(i)\setminus
V_{j}$.

If $f(v_{j}^{3})\not=f(v_{j}^{4})$ then recolor the vertex $v_{j}^{3}$ with
the color $i$ and recolor a vertex in $f^{-1}(i)\setminus V_{j}$ with the
color $f(v_{j}^{3})$. It is easy to see that the resulting coloring is also an
optimal $3$-relaxed coloring of $G$ and we are back to Case 2.

Now suppose $f(v_{j}^{3})=f(v_{j}^{4})=i^{*}$. If $|f^{-1}(i^{*})\setminus
V_{j}|\leq 2$ then we can do the same thing as in the previous paragraph and
go back to Case 2. Thus we assume $|f^{-1}(i^{*})\setminus V_{j}|=3$ and there
is a part $V_{p}$ with $V_{i^{*},p}=f^{-1}(i^{*})\setminus V_{j}$. If
$|f^{-1}(i)\setminus V_{j}|\leq 2$ then we let the color $i^{*}$ replace the
role of the color $i$ and deal with it as in the previous paragraph. Therefore
we assume $|f^{-1}(i)\setminus V_{j}|=3$ and there is a part $V_{q}$ with
$V_{i,q}=f^{-1}(i)\setminus V_{j}$. Then recolor all vertices in $V_{i^{*},j}$
with the color $i$ and all vertices in $V_{i,q}$ with the color $i^{*}$ and go
back to Case 1.

Case 4. $m_{i,j}=1$. Then $m_{i^{*},h}\leq 1$ for any $i^{*}\in f(V)$ and
$h\in\\{j,q\\}$. Let $f(v_{j}^{1})=i$ and $f(v_{j}^{2})=i^{*}$. It is obvious
that $|f^{-1}(i^{*})\setminus V_{j}|\leq 3$. Then, by recoloring the vertex
$v_{j}^{2}$ with the color $i$ and a vertex in $f^{-1}(i)\setminus V_{j}$ with
the color $i^{*}$, we obtain a new optimal $3$-relaxed coloring of $G$ with
$m_{i,j}=2$ and we are back to Case 3.

By repeatedly applying Lemmas 5.1 and 5.3, one can reduce the problem to
construct an optimal $3$-relaxed coloring of $K(n_{1},n_{2},\dots,n_{s})$ to
the case when $n_{j}\leq 2$ for all $j\in\\{1,2,\dots,s\\}$ or the case when
$3\leq n_{1}\leq 5$ and $n_{j}\leq 2$ for all $j\in\\{2,3,\dots,s\\}$. These
cases are going to be discussed in the following three lemmas.

###### Lemma 5.4

Let $G$ be a complete multi-partite graph $K(n_{1},n_{2},\dots,n_{s})$ with
$3\leq n_{1}\leq 5$ and $n_{2}=2$. Then there is an optimal $3$-relaxed
coloring of $G$ which assigns three vertices of $V_{1}$ and the two vertices
of $V_{2}$ the same color.

Proof. Let $f$ be an optimal $3$-relaxed coloring of
$K(n_{1},n_{2},\dots,n_{s})$. Choose the color $i$ such that
$m_{i,1}=\max\\{m_{r,1}:\ r\in f(V_{1})\\}$. We consider the following four
cases.

Case 1. $m_{i,1}\geq 4$. Then $m_{i,p}=0$ for all $p\in\\{2,,3,\dots,s\\}$. We
can recolor the two vertices in $V_{2}$ with the color $i$ and recolor the
vertices $v_{1}^{d}$ for $4\leq d\leq m_{i,1}$ with colors from
$\\{f(v_{2}^{1}),f(v_{2}^{2})\\}$. It is easy to see that the resulting
coloring is the desired one.

Case 2. $m_{i,1}=3$. Then there is at most one $p\in\\{2,3,\dots,s\\}$ with
$m_{i,p}>0$. If $m_{i,p}=0$ for $p\in\\{3,4,\dots,s\\}$ then we are done by
just recoloring all vertices in $V_{2}\setminus V_{i,2}$ with the color $i$.
If there is some $p\in\\{3,4,\dots,s\\}$ with $m_{i,p}>0$ then recolor the two
vertices in $V_{2}$ with the color $i$ and recolor the vertices in $V_{i,p}$
with colors from $\\{f(v_{2}^{1}),f(v_{2}^{2})\\}$. It is clear that the
resulting coloring is what we are desiring.

Case 3. $m_{i,1}=2$. Since $n_{p}\leq 2$ for all $p\in\\{2,3,\dots,s\\}$, we
must have $|f^{-1}(i)\setminus V_{1}|\leq 2$. Then recolor the vertex
$v_{1}^{3}$ with the color $i$ and recolor a vertex in $f^{-1}(i)\setminus
V_{1}$ with the color $f(v_{1}^{3})$. It is not difficult to check that the
resulting coloring is also an optimal $3$-relaxed coloring of $G$ and we are
back to Case 2.

Case 4. $m_{i,1}=1$. Let $V_{i,1}=\\{v_{1}^{1}\\}$. It is obvious that
$|f^{-1}(i)\setminus V_{1}|\leq 3$. By recoloring the vertex $v_{1}^{2}$ with
the color $i$ and a vertex in $f^{-1}(i)\setminus V_{1}$ with the color
$f(v_{1}^{2})$, we obtain a new optimal $3$-relaxed coloring of $G$ with
$m_{i,1}=2$ and we are back to Case 3.

###### Lemma 5.5

Let $G$ be a complete multi-partite graph $K(n_{1},n_{2},\dots,n_{s})$ with
$3\leq n_{1}\leq 5$ and $n_{2}=1$. If $n_{1}\geq 4$ then there is an optimal
$3$-relaxed coloring $f$ of $G$ with $|f(V_{1})|=1$. And if $n_{1}=3$ then
there is an optimal $3$-relaxed coloring of $G$ which assigns three vertices
of $V_{1}$ and the only vertex of $V_{2}$ the same color.

Proof. Let $f$ be an optimal $3$-relaxed coloring of
$K(n_{1},n_{2},\dots,n_{s})$. Choose the color $i$ such that
$m_{i,1}=\max\\{m_{r,1}:\ r\in f(V_{1})\\}$. Let
$V_{i,1}=\\{v_{1}^{1},\dots,v_{1}^{m_{i,1}}\\}$.

Suppose $4\leq n_{1}\leq 5$. If $m_{i,p}=0$ for all $p\in\\{2,3,\dots,s\\}$
then we can color all vertices in $V_{1}$ with the color $i$. Thus we assume
$1\leq m_{i,1}\leq 3$ and $f^{-1}(i)\setminus V_{1}\not=\emptyset$. Then it is
clear that $h=|f^{-1}(i)\setminus V_{1}|\leq 4-m_{i,1}$. Let the $h$ vertices
in $f^{-1}(i)\setminus V_{1}$ be $w_{1},w_{2},\dots,w_{h}$. By recoloring the
vertices $v_{1}^{d}$ ($m_{i,1}+1\leq d\leq n_{1}$) with the color $i$ and
$w_{g}$ ($1\leq g\leq h$) with the color $f(v_{1}^{m_{i,1}+g})$, we obtain an
optimal $3$-relaxed color of $G$ that assigns all vertices in $V_{1}$ the same
color.

Suppose $n_{1}=3$. If $1\leq m_{i,1}\leq 2$ then similar as above we can
recolor all vertices in $V_{1}$ with the same color $i$ and left at most one
vertex with color $i$ not in $V_{1}$. And we can easily obtain the desired
coloring.

###### Lemma 5.6

Let $G$ be a complete multi-partite graph $K(n_{1},n_{2},\dots,n_{s})$ with
$1\leq n_{j}\leq 2$ for all $j\in\\{1,2,\dots,s\\}$. Then
$\chi_{3}(G)=\lceil\frac{n_{1}+n_{2}+\dots+n_{s}}{4}\rceil$.

Proof. Let $f$ be an optimal $3$-relaxed coloring of $G$. By Lemma 2.1, since
$1\leq n_{j}\leq 2$ for all $j\in\\{1,2,\dots,s\\}$, it is clear that $f$
assigns each color to at most $4$ vertices of $G$. Thus
$\chi_{3}(G)\geq\lceil\frac{n_{1}+n_{2}+\dots+n_{s}}{4}\rceil$. On the other
hand, since $\beta_{t}(G)\geq\min\\{t+1,|V(G)|\\}$ for any graph $G$, the
greedy algorithm uses at most $\lceil\frac{n_{1}+n_{2}+\dots+n_{s}}{4}\rceil$
colors.

Let $G$ be a complete multi-partite graph $K(n_{1},n_{2},\dots,n_{s})$ with
$n_{1}\geq n_{2}\geq\cdots n_{s}$. Note that if $n_{1}\geq 6$ then
$\beta_{3}(G)=6$, if $3\leq n_{2}\leq n_{1}\leq 5$ then $\beta_{3}(G)=6$ and
three vertices of $V_{1}$ together with three vertices of $V_{2}$ forms a
maximum $3$-sparse set of $G$, if $3\leq n_{1}\leq 5$ and $n_{2}=2$ then
$\beta_{3}(G)=5$ and three vertices of $V_{1}$ together with the two vertices
in $V_{2}$ forms a maximum $3$-sparse set of $G$, if $n_{1}\geq 4$ and
$n_{2}=1$ then $\beta_{3}(G)=n_{1}$ and $V_{1}$ is a maximum $3$-sparse set of
$G$, if $n_{1}=3$ and $n_{2}=1$ then $\beta_{3}(G)=4$ and the three vertices
of $V_{1}$ together with the vertex in $V_{2}$ forms a maximum $3$-sparse set
of $G$, while if $n_{1}\leq 2$ then $\beta_{3}(G)=\min\\{4,|V(G)|\\}$. Keeping
in mind these facts, Lemmas and Corollaries in this section imply that
Algorithm 2 always outputs an optimal $3$-relaxed coloring of a complete
multi-partite graph.

In next section, we shall illustrate by examples that the same idea is not
applicable to the case $t\geq 7$.

##  6 Counterexamples for $t\geq 7$ to the greedy algorithm

In this section, we present examples for which the greedy algorithm does not
produce an optimal $t$-relaxed coloring of a complete multi-partite graph. We
first deal with the case that $t$ is an odd number.

###### Example 6.1

Let $t\geq 7$ be an odd number. Let $G$ be the graph $K(n_{1},\dots,n_{6})$
with $n_{1}=2t-1$, $n_{2}=t+1$ and $n_{3}=n_{4}=n_{5}=n_{6}=(t-1)/2$. Then
$\chi_{t}(G)=3$. While the greedy algorithm uses $4$ colors.

From the structure of $G$, it is easy to observe that each color can be
assigned to at most $2t$ vertices of $G$. Since $G$ has $5t-2>4t$ vertices,
$\chi_{t}(G)\geq 3$.

A $t$-relaxed coloring using $3$ colors is presented as follows. Use $g$
denote this coloring. $g^{-1}(i)$ is the set of vertices with color $i$. We
use the notation $g^{-1}(i)=(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})$ to indicate
that for $j\in\\{1,2,\dots,6\\}$ there are $x_{j}$ vertices in $V_{j}$ that
are assigned the color $i$. Then the $t$-relaxed coloring $g$ using $3$ colors
is defined as

$\begin{array}[]{llllllllllllll}g^{-1}(1)=(2t-1,&0,&0,&0,&0,&0&),\\\
g^{-1}(2)=(0,&\frac{t+1}{2},&\frac{t-1}{2},&\frac{t-1}{2},&0,&0&),\\\
g^{-1}(3)=(0,&\frac{t+1}{2},&0,&0,&\frac{t-1}{2},&\frac{t-1}{2}&).\end{array}$

Thus $\chi_{t}(G)=3$.

Use $(n_{1},n_{2},n_{3},n_{4},n_{5},n_{6})$ to denote the complete multi-
partite graph with the $j$th part having $n_{j}$ vertices for
$j\in\\{1,2,\dots,6\\}$. Let $f$ be the coloring produced by the greedy
algorithm. The algorithm works as follows.

$\begin{array}[]{llllllllllllll}&&&&&&&(2t-1,&t+1,&\frac{t-1}{2},&\frac{t-1}{2},&\frac{t-1}{2},&\frac{t-1}{2}&)\\\
f^{-1}(1)=(t,&t,&0,&0,&0,&0&)\rightarrow&(t-1,&1,&\frac{t-1}{2},&\frac{t-1}{2},&\frac{t-1}{2},&\frac{t-1}{2}&)\\\
f^{-1}(2)=(\frac{t+1}{2},&0,&\frac{t-1}{2},&\frac{t-1}{2},&0,&0&)\rightarrow&(\frac{t-3}{2},&1,&0,&0,&\frac{t-1}{2},&\frac{t-1}{2}&)\\\
f^{-1}(3)=(\frac{t-3}{2},&0,&0,&0,&\frac{t-1}{2},&\frac{t-1}{2}&)\rightarrow&(0,&1,&0,&0,&0,&0&)\\\
f^{-1}(4)=(0,&1,&0,&0,&0,&0&)\rightarrow&(0,&0,&0,&0,&0,&0&)\end{array}$

Thus the greedy algorithm uses $4$ colors.

###### Example 6.2

Let $t\geq 7$ be an even number. Let $G$ be the graph $K(n_{1},\dots,n_{6})$
with $n_{1}=2t-1$, $n_{2}=t+1$ and $n_{3}=n_{4}=t/2$, and $n_{5}=n_{6}=t/2-1$.
Then $\chi_{t}(G)=3$. While the greedy algorithm uses $4$ colors.

The analysis of Example 6.2 is similar to that of Example 6.1. So we omit the
details.

## References

  * [1] J. Araujoa, J-C. Bermonda, F. Giroirea, F. Haveta, D. Mazaurica, and R. Modrzejewski, Weighted improper colouring, J. of Discrete Algorithms 16 (2012) 53-66.
  * [2] R. Belmonte, M. Lampis, and V. Mitsou, Defective coloring on classes of perfect graphs, In: Bodlaender H., Woeginger G. (eds) Graph-Theoretic Concepts in Computer Science. WG 2017. Lecture Notes in Computer Science, vol 10520. Springer, Cham. https://doi.org/10.1007/978-3-319-68705-6_9.
  * [3] L. Cowen, R. Cowen, and D. Woodall, Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valence, J. of Graph Theory 10 (1986) 187-195.
  * [4] L. Cowen, W. Goddard, and C.E. Jesurum, Defective coloring revisited, J. of Graph Theory 24(3) (1997) 205-219.
  * [5] B.A. Gudmundsson, T.K. Magnusson, and B.O. Saemundsson, Bounds and fixed-parameter algorithms for weighted improper coloring, Electron. Notes Theor. Comput. Sci. 322 (2016) 181-195.
  * [6] F. Havet, R.J. Kang, and J.-S. Sereni, Improper coloring of unit disk graphs, Networks 54(3) (2009) 150-164.
  * [7] J. Lan and W. Lin, On $t$-relaxed chromatic number of $r$-power paths, Discrete Math. Algorithm. Appl. 10(2) (2018) 1850017.
  * [8] L. Lovász, On decompositions of graphs, Studia Sci. Math. Hungar. 1 (1966) 237-238.
  * [9] J.M. Lewis and M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. Syst. Sci. 20(2) (1980) 219-230.


# gComm: An environment for
investigating generalization in Grounded Language Acquisition

Rishi Hazra
Indian Institute of Science, Bangalore
<EMAIL_ADDRESS>
&Sonu Dixit
Indian Institute of Science, Bangalore
<EMAIL_ADDRESS>

###### Abstract

gComm111codes & baselines: https//github.com/SonuDixit/gComm is a step towards
developing a robust platform to foster research in grounded language
acquisition in a more challenging and realistic setting. It comprises a 2-d
grid environment with a set of agents (a stationary speaker and a mobile
listener connected via a communication channel) exposed to a continuous array
of tasks in a partially observable setting. The key to solving these tasks
lies in agents developing linguistic abilities and utilizing them for
efficiently exploring the environment. The speaker and listener have access to
information provided in different modalities, i.e. the speaker’s input is a
natural language instruction that contains the target and task specifications
and the listener’s input is its grid-view. Each must rely on the other to
complete the assigned task, however, the only way they can achieve the same,
is to develop and use some form of communication. gComm provides several tools
for studying different forms of communication and assessing their
generalization.

##  1 Environment Description

Recently, datasets embodied in action and perception have been used to train
models for various tasks Vries et al. (2018); Mao et al. (2019). One such
dataset is the grounded SCAN (gSCAN) dataset Ruis et al. (2020) which is used
for systematic generalization. We base our environment gComm on the gSCAN
dataset which is a grounded version of SCAN benchmark Lake and Baroni (2018).
While both these tasks focus on generalization with the meaning grounded in
states of a grid-world, there are however, certain key differences between
gComm and gSCAN: (i) Firstly, gSCAN focuses on rule-based generalization for
navigation tasks, wherein, an agent learns to map a natural language
instruction and its corresponding grid-view to a sequence of action
primitives. Contrary to that, we present emergent communication as our main
theme, using a pair of bots, a stationary speaker and a mobile listener, that
process the language instruction and the grid-view respectively; (ii)
Secondly, unlike the supervised framework adopted for learning gSCAN tasks, we
use a more realistic RL-framework, wherein, the listener learns by exploring
its environment and interacting with it. Our environment is conceptually
similar to the BabyAI platform Chevalier-Boisvert et al. (2019). However,
contrary to BabyAI , which focuses on language learning, we intend to project
gComm as a general purpose platform for investigating generalization from the
perspective of grounded language acquisition through emergent communication. A
companion paper Hazra et al. (2020) introduced a intrinsic reward framework to
induce compositionality in the emergent language using the gComm environment.
In this paper, we intend to expound on the environment details.

Figure 1: gComm Environment

#### Object Attributes:

The gComm grid-world is populated with objects of different characteristics
like shape, color, size and weight.

  * •

Shapes: circle, square, cylinder, diamond

  * •

Colors: red, blue, yellow, green

  * •

Sizes: $1,2,3,4$

  * •

Weights: light, heavy

The weight attribute can be fixed corresponding to the object size at the
beginning of training. For instance, smaller sized objects are lighter and
vice versa. Alternatively, the weight can be set as an independent attribute.
In the latter option, the weight is randomly fixed at the start of each
episode so that the listener cannot deduce the same from the grid information
(object size), and must rely on the speaker.

###  1.1 Reinforcement Learning framework

#### Setup:

In each round, a task is assigned to a stationary Speaker-Bot, the details of
which (task and target information) it must share with a mobile Listener-Bot
by transmitting a set of messages $m_{i=1}^{n_{m}}$, via a communication
channel. At each time-step $t$, the listener agent selects an action from its
action space $\mathcal{A}$, with the help of the received messages
$m_{i=1}^{n_{m}}$ and its local observation (grid-view) $o_{t}\in\mathcal{O}$.
The environment state is updated using the transition function $\mathcal{T}$:
$\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S}$. The environment provides
a reward to the agent at each time-step using a reward function $r$:
$\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$. The goal of the agent is
to find a policy $\bm{\pi}_{\theta}$ :
$(\mathcal{O},m_{i=1}^{n_{m}})\rightarrow\Delta(\mathcal{A})$ that chooses
optimal actions so as to maximize the expected reward,
$\mathcal{R}=\mathrm{E}_{\bm{\pi}}[\sum_{t}\gamma^{t}r^{(t)}]$ where $r^{t}$
is the reward received by the agent at time-step $t$ and $\gamma\in(0,1]$ is
the discount factor. At the beginning of training, their semantic repertoires
are empty, and the speaker and listener must converge on a systematic usage of
symbols to complete the assigned tasks thus, giving rise to an original
linguistic system.

#### Observation Space:

To encourage communication, gComm provides a partially observable setting in
which neither the speaker nor the listener has access to the complete state
information. The speaker knows the task and target specifics through the
natural language instruction whereas, the listener has access to the grid
representation. However, the listener is unaware of either the target object
or the task, and therefore must rely on the speaker to accomplish the given
task. The observation space of the listener comprises (i) the grid
representation; (ii) the messages transmitted by the speaker.

The natural language instruction is parsed to
$\langle\mathrm{VERB},\\{\mathrm{ADJ}_{i}\\}_{i=1}^{3},\mathrm{NOUN}\rangle$
with the help of an ad hoc semantic parser222$\mathrm{VERB}$: task;
$\mathrm{ADJ}$: object attributes like color, size and weight;
$\mathrm{NOUN}$: object shape. It is then converted to the following 18-d
vector representation before being fed to the speaker: {1, 2, 3, 4, square,
cylinder, circle, diamond, r, b, y, g, light, heavy, walk, push, pull,
pickup}. Each position represents a bit and is set or unset according to the
attributes of the target object and the task. The breakdown of the vector
representation is as follows: bits [$0-3$]: target size; bits [$4-7$]: target
shape; bits [$8-11$]: target color; bits [$12-13$]: target weight; bits
[$14-17$]: task specification.

The grid information can either be a image input of the whole grid or a
predefined cell-wise vector representation of the grid. In the latter case,
each grid cell in is specified by a 17-d vector representation given by: {$1$,
$2$, $3$, $4$, square, cylinder, circle, diamond, r, b, y, g, agent, E, S, W,
N}. The breakdown is as follows: bits [$0-3$]: object size; bits [$4-7$]:
object shape; bits [$8-11$]: object color; bit $12$: agent location (is set
$=1$ if agent is present in that particular cell, otherwise $0$); bits
[$13-16$]: agent direction. For an $obstacle$ or a $wall$, all the bits are
set to $1$.

#### Action Space:

The action space comprises eight different actions that the listener agent can
perform: {left, right, forward, backward, push, pull, pickup, drop}. In order
to execute the ‘push’, ‘pull’, and ‘pickup’ actions, the agent must navigate
to the same cell as that of the object. Upon executing a pickup action, the
object disappears from the grid. Conversely, an object that has been picked up
can reappear in the grid only if a ‘drop’ action is executed in the same
episode. Also refer Section 1.2 for further details about task descriptions.

#### Rewards:

gComm generates a 0-1 (sparse) reward, i.e., the listener gets a reward of
$r=1$ if it achieves the specified task, otherwise $r=0$.

#### Communication:

Recall that the listener has incomplete information of its state space and is
thus unaware of the task and the target object. To address the information
asymmetry, the speaker must learn to use the communication channel for sharing
information. What makes it more challenging is the fact that the semantics of
the transmitted information must be learned in a sparse reward setting, i.e.
to solve the tasks, the speaker and the listener must converge upon a common
protocol and use it systematically with minimal feedback at the end of each
round.

###  1.2 Task Description

(i) Walk to a target object (ii) Push a target object in the forward
direction. (iii) Pull a target object in the backward direction. (iv) Pickup a
target object. (v) Drop the picked up object.

Additionally, there are modifiers associated with verbs, for instance: pull
the red circle twice. Here, twice is a numeral adverb and must be interpreted
to mean two consecutive ‘pull’ actions. When an object is picked up, it
disappears from the grid and appears only if a ‘drop’ action is executed in
the subsequent time-steps. However, no two objects can overlap. It should be
noted that while defining tasks, it is ensured that the target object is
unique.

#### Target and Distractor objects:

Cells in the grid-world are populated with objects divided into two classes:
the target object and the distractor objects. The distractors either have the
same color or the same shape (or both) as that of the target. Apart from
these, some random objects distinct from the target can also be sampled using
a parameter other_objects_sample_percentage. The listener and the objects may
spawn at any random location on the grid.

#### Levels:

In addition to the simple grid-world environment comprising target and
distractor objects, the task difficulty can be increased by generating
obstacles and mazes. The agent is expected to negotiate the complex
environment in a sparse reward setting. The number of obstacles and the maze
density can be adjusted.

#### Instruction generation:

Natural language instructions are programmatically generated based on
predefined lexical rules and the specified vocabulary. At the beginning of
training, the user specifies the kind of verb (transitive or intransitive),
noun (object shape), and adjectives (object weight, size, color). Note, that
he instruction templates are fixed, and as such, cannot handle ambiguities in
natural language.

###  1.3 Communication

gComm endows the agents with the ability to To encourage communication, gComm
provides a partially observable setting in which neither the speaker nor the
listener has access to the complete state information. The speaker knows the
task and target specifics through the natural language instruction whereas,
the listener has access to the grid representation. However, the listener is
unaware of either the target object or the task, and hence, it must rely on
the speaker to accomplish the given task. The observation space of the
listener comprises (i) the grid representation; (ii) the messages transmitted
by the speaker. communicate. This forms a crucial step in addressing the
partial observability problem and encouraging language acquisition. Above all,
gComm provides several tools for an in-depth analysis of grounded
communication protocols and their relation to the generalization performance.

Figure 2: Maze-grid. The maze complexity and density are user-defined
parameters. The agent is required to negotiate the obstacles while performing
the given task.

#### Communication Channel:

The communication can be divided into two broad categories.

  * •

Discrete: Discrete messages can either be binary (processed using Gumbel-
Softmax Jang et al. (2017)) or one-hot (processed using Categorical
distribution)333The use of discrete latent variables render the neural network
non-differentiable. The Gumbel Softmax gives a differentiable sample from a
discrete distribution by approximating the hard one-hot vector into a soft
version. For one-hot vectors, we use Relaxed one-hot Categorical sampling.
Since we want the communication to be discrete, we employ the Straight-Through
trick for both binary and one-hot vectors.. Discrete messages are associated
with a temperature parameter $\tau$.

  * •

Continuous: As opposed to discrete messages, continuous signals are real-
valued. Theoretically speaking, each dimension in the message can carry
32-bits of information (32-bit floating point). These messages don’t pose the
same kind of information bottleneck as their discrete counterpart, however,
they are not as interpretable.

Apart from these, the communication channel can be utilized to compare against
the following baseline implementations readily available in the gComm
environment. These baselines not only enable us to investigate the efficacy of
the emergent communication protocols, but also provides quantitative insights
into the learned communication abilities.

  * •

Random Speaker: In this baseline, the speaker transmits a set of random
symbols to the listener which it must learn to ignore (and focus only on its
local observation).

  * •

Fixed Speaker: Herein, the speaker’s transmissions are masked with a set of
ones. Intuitively, this baseline provides an idea of whether communication is
being used in the context of the given task (whether the speaker actually
influences the listener or just appears to do so).

  * •

Perfect Speaker: This baseline provides an illusion of a perfect speaker by
directly transmitting the input concept encoding, hence, acting as an upper
bound for comparing the learned protocols.

  * •

Oracle Listener: For each cell, we zero-pad the grid encoding with an extra
bit, and set it ($=1$) for the cell containing the target object. Thus, the
listener has complete information about the target in context of the
distractors. This baseline can be used as the upper limit of performance.

#### Channel parameters:

The communication channel is defined using the following parameters:

  * •

Message Length: Length of the message vector $d_{m}$ sets a limit on the
vocabulary size, i.e. higher the message length, larger is the vocabulary
size. For instance, for discrete (binary) messages, the vocabulary size is
given by $|\mathcal{V}|=2^{d_{m}}$. Note, that a continuous message can
transmit more information compared to a discrete message of the same length.

  * •

Information Rate or the number of messages $n_{m}$ transmitted per round of
communication.

These constitute the channel capacity,
$|\mathrm{C}|=\mathrm{c}_{d_{m}}^{n_{m}}$.

#### Setting:

Communication can either be modelled in form of cheap talk or costly
signalling. In the latter case, each message passing bears a small penalty to
encourage more economic and efficient communication protocols. Alternatively,
the communication can either be unidirectional (message passing from speaker
to listener only) or bidirectional (an interactive setting wherein message
passing happens in either direction). gComm uses an unidirectional cheap talk
setting.

Figure 3: Lights Out

###  1.4 Metrics:

In order to induce meaningful communication protocols, the speaker must
transmit useful information, correlated with its input (positive signalling).
At the same time, the listener must utilize the received information to alter
its behavior and hence, its actions (positive listening). In alignment with
the works of Lowe et al. (2019), we incorporate the following metrics in our
environment to assess the evolved communication protocols.

  * •

Positive signalling: Context independence (CI) is used as an indicator of
positive signalling. It captures the statistical alignment between the input
concepts and the messages transmitted by the speaker and is given by:

$\displaystyle\forall
c\in\mathcal{C}:m_{c}=\operatorname*{arg\,max}_{m}p_{cm}(c|m)$ $\displaystyle
CI(p_{mc},p_{cm})=\frac{1}{|\mathcal{C}|}\sum_{c}p_{cm}(c|m_{c})p_{mc}(m_{c}|c)$

Both $p_{cm}(c|m)$ and $p_{mc}(m|c)$ are calculated using a translation model
by saving ($m,c$) pairs and running it in both directions. Since each concept
element $c$ should be mapped to exactly one message $m$, CI will be high when
the $p_{cm}(c|m)$ and $p_{mc}(m|c)$ are high.

  * •

Positive listening: We use Causal Influence of Communication (CIC) of the
speaker on the listener as a measure of positive listening. It is defined as
the mutual information between the speaker’s message and the listener’s action
$I(m,a_{t})$. Higher the CIC, more is the speaker’s influence on the
listener’s actions, thus, indicating that the listener is utilizing the
messages.

  * •

Compositionality: Compositionality is measured using the topographic
similarity (topsim) metric Brighton and Kirby (2006). Given two pairwise
distance measures, i.e. one in the concept (input) space
$\Delta_{\mathcal{C}}^{ij}$ and another in the message space
$\Delta_{\mathcal{M}}^{ij}$, topsim is defined as the correlation coefficient
calculated between $\Delta_{\mathcal{C}}^{ij}$ and
$\Delta_{\mathcal{M}}^{ij}$. Higher topsim indicates more compositionality.

###  1.5 Additional features

We introduce a lights out feature in the gComm environment through which the
grid (including all its objects) is subjected to varying illuminations (Figure
3). The feature can be activated randomly in each episode and presents a
challenging situation for the agent where it is required to navigate the grid
using its memory of the past observation. Note that this feature is useful
only when used with an image input as the grid representation.

Task |  Baseline |  Convergence Rewards
---|---|---
Walk |  |  Simple Speaker |  $0.70$
---|---
Random Speaker |  $0.40$
Fixed Speaker |  $0.43$
Perfect Speaker |  $0.95$
Oracle Listener |  $0.99$
PUSH & PULL |  |  Simple Speaker |  $0.55$
---|---
Random Speaker |  $0.19$
Fixed Speaker |  $0.15$
Perfect Speaker |  $0.85$
Oracle Listener |  $0.90$
Table 1: Comparison of baseline convergence rewards [Task: Walk, params:
{comm_type: categorical, num_episodes: 200000, episode_len: 10, num_msgs: 3,
msg_len: 4, num_actions: 4 (left, right, forward, backward), type_grammar:
simple_intrans, weights: light, enable_maze: False, grid_size: $4\times 4$,
distractors: 4, grid_input_type: vector}][ Task: Push/Pull, params:
{comm_type: categorical, num_episodes: 400000, episode_len: 10, num_msgs: 3,
msg_len: 4, num_actions: 6 (left, right, forward, backward, push, pull),
type_grammar: simple_trans, weights: light, enable_maze: False, grid_size:
$4\times 4$, distractors: 2, grid_input_type: vector}]. Note, that these
rewards were recorded over a set of $100$ validation episodes.

##  2 Related Work

#### Emergent Communication:

With regard to emergent communication, so far, most existing works are limited
to analyzing simple referential games Lewis (1969) in simulated environments,
where a speaker communicates the input (object’s shape and color) to a
stationary listener which, then, tries to classify the reconstructed messages
from a list of classes Kottur et al. (2017); Havrylov and Titov (2017); Cao et
al. (2018); Li and Bowling (2019). These games do not involve world state
manipulation and generally comprise elementary inputs with limited attributes,
thus, restricting the scope of language usage. gComm introduces an additional
challenge for the listener to navigate and manipulate objects to achieve the
transmitted goal.

#### Visual Navigation:

The problem of navigating in an environment based on visual perception, by
mapping the visual input to actions, has long been studied in vision and
robotics. The tasks are either specified implicitly via rewards Gupta et al.
(2017), or are explicitly conditioned on the goal state (Goal-conditioned
Reinforcement Learning) Zhu et al. (2017); Nair et al. (2018); Nasiriany et
al. (2019). In contrast, gComm tasks are specified using natural language and
involves unidirectional messages from a task-aware speaker to a state-aware
listener.

#### Embodied Learning:

Recent works on embodied learning include (but are not limited to) using
embodied agents to complete tasks specified by natural language in a simple
mazeworld Oh et al. (2017), Embodied Question Answering Das et al. (2018) and
Embodied Language Grounding by mapping 2D scenes to 3D Prabhudesai et al.
(2020). We also intend to project gComm as a embodied communication
environment where the listener agent is required to ground the messages to its
corresponding visual input and associate them with actions (push a red circle
twice suggests that the red circle is heavy and the listener needs to perform
two consecutive “push" actions to move it.)

#### Instruction Execution:

These approaches focus on natural language understanding to map instructions
to actions Branavan et al. (2009); Chen and Mooney (2011); Tellex et al.
(2011). However, in gComm, the listener agent doesn’t have direct access to
the natural language instruction hence, it focuses on mapping transmitted
messages from the speaker to actions. The challenge is to address the
information bottleneck, i.e., given a limited channel capacity, the speaker
must learn to convey the required task and target specifics to the listener
based on the input instruction.

#### Visual Question Answering:

In VQA, agents are required to answer natural language questions based on a
fixed view of the environment (image or video) Antol et al. (2015); Tapaswi et
al. (2016); Fukui et al. (2016); Shah et al. (2019). However, unlike gComm,
the agents cannot actively perceive or manipulate objects.

##  3 Discussion

We compared a Simple Speaker (speaker transmitting one-hot messages) with the
baselines given in Section 1.3 for (i) Walk task wherein the listener is
required to walk to a target object; (ii) Push $+$ Pull task wherein the
listener is required to push or pull a target object. The grid we used was of
size $4\times 4$ with no obstacles. Moreover, we used 5 objects (4 distractors
$+$ 1 target) for (i) and 3 objects (2 distractors $+$ 1 target) for (ii). The
number of messages were set at 3 (i.e., one messages each for task, shape and
color).

We present our analysis based on the results from Table 1.

  * •

Simple Speaker outperforms the Fixed and Random baselines.

  * •

Perfect Speaker performs as well as Oracle Listener.

  * •

Oracle Listener had the fastest convergence ($\approx\frac{1}{5}$ of the
episodes taken by Simple Speaker), followed by Perfect Speaker
($\approx\frac{1}{2}$ of the episodes taken by Simple Speaker).

  * •

Fixed Speaker baseline converges faster than the Random Speaker baseline which
suggests that the Listener learns to ignore messages if they remain fixed over
time.

## References

  * Antol et al. (2015) Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C. Lawrence Zitnick, and Devi Parikh. 2015.  Vqa: Visual question answering.  In _2015 IEEE International Conference on Computer Vision (ICCV)_ , pages 2425–2433.
  * Branavan et al. (2009) S.R.K. Branavan, Harr Chen, Luke Zettlemoyer, and Regina Barzilay. 2009.  Reinforcement learning for mapping instructions to actions.  In _Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP_ , pages 82–90. Association for Computational Linguistics.
  * Brighton and Kirby (2006) Henry Brighton and Simon Kirby. 2006.  Understanding linguistic evolution by visualizing the emergence of topographic mappings.  _Artif. Life_.
  * Cao et al. (2018) Kris Cao, Angeliki Lazaridou, Marc Lanctot, Joel Z Leibo, Karl Tuyls, and Stephen Clark. 2018.  Emergent communication through negotiation.  In _International Conference on Learning Representations (ICLR) 2018_.
  * Chen and Mooney (2011) David L. Chen and Raymond J. Mooney. 2011.  Learning to interpret natural language navigation instructions from observations.  In _Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence_ , page 859–865.
  * Chevalier-Boisvert et al. (2019) Maxime Chevalier-Boisvert, Dzmitry Bahdanau, Salem Lahlou, Lucas Willems, Chitwan Saharia, Thien Huu Nguyen, and Yoshua Bengio. 2019.  BabyAI: First steps towards grounded language learning with a human in the loop.  In _International Conference on Learning Representations (ICLR) 2019_.
  * Das et al. (2018) Abhishek Das, Samyak Datta, Georgia Gkioxari, Stefan Lee, Devi Parikh, and Dhruv Batra. 2018.  Embodied question answering.  In _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)_ , pages 2135–213509.
  * Fukui et al. (2016) Akira Fukui, Dong Huk Park, Daylen Yang, Anna Rohrbach, Trevor Darrell, and Marcus Rohrbach. 2016.  Multimodal compact bilinear pooling for visual question answering and visual grounding.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 457–468. Association for Computational Linguistics.
  * Gupta et al. (2017) Saurabh Gupta, James Davidson, Sergey Levine, Rahul Sukthankar, and Jitendra Malik. 2017.  Cognitive mapping and planning for visual navigation.  In _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 7272–7281.
  * Havrylov and Titov (2017) Serhii Havrylov and Ivan Titov. 2017.  Emergence of language with multi-agent games: Learning to communicate with sequences of symbols.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, page 2146–2156.
  * Hazra et al. (2020) Rishi Hazra, Sonu Dixit, and Sayambhu Sen. 2020.  Infinite use of finite means: Zero-shot generalization using compositional emergent protocols.  _CoRR_ , abs/2012.05011.
  * Jang et al. (2017) Eric Jang, Shixiang Gu, and Ben Poole. 2017.  Categorical reparameterization with gumbel-softmax.  In _International Conference on Learning Representations (ICLR) 2017_.
  * Kottur et al. (2017) Satwik Kottur, José Moura, Stefan Lee, and Dhruv Batra. 2017.  Natural language does not emerge ‘naturally’ in multi-agent dialog.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2962–2967. Association for Computational Linguistics.
  * Lake and Baroni (2018) Brenden Lake and Marco Baroni. 2018.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In _Proceedings of the 35th International Conference on Machine Learning_ , Proceedings of Machine Learning Research. PMLR.
  * Lewis (1969) David K. Lewis. 1969.  _Convention: A Philosophical Study_.  Wiley-Blackwell.
  * Li and Bowling (2019) Fushan Li and Michael Bowling. 2019.  Ease-of-teaching and language structure from emergent communication.  In _Advances in Neural Information Processing Systems_ , volume 32.
  * Lowe et al. (2019) Ryan Lowe, Jakob Foerster, Y-Lan Boureau, Joelle Pineau, and Yann Dauphin. 2019\.  On the pitfalls of measuring emergent communication.  In _Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems_ , AAMAS ’19, page 693–701. International Foundation for Autonomous Agents and Multiagent Systems.
  * Mao et al. (2019) Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B. Tenenbaum, and Jiajun Wu. 2019\.  The neuro-symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision.  In _International Conference on Learning Representations (ICLR) 2019_.
  * Nair et al. (2018) Ashvin Nair, Vitchyr Pong, Murtaza Dalal, Shikhar Bahl, Steven Lin, and Sergey Levine. 2018.  Visual reinforcement learning with imagined goals.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18, page 9209–9220.
  * Nasiriany et al. (2019) Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine. 2019.  Planning with goal-conditioned policies.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc.
  * Oh et al. (2017) Junhyuk Oh, Satinder Singh, Honglak Lee, and Pushmeet Kohli. 2017.  Zero-shot task generalization with multi-task deep reinforcement learning.  In _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ICML’17, page 2661–2670. JMLR.org.
  * Prabhudesai et al. (2020) Mihir Prabhudesai, Hsiao-Yu Fish Tung, Syed Ashar Javed, Maximilian Sieb, Adam W. Harley, and Katerina Fragkiadaki. 2020.  Embodied language grounding with 3d visual feature representations.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Ruis et al. (2020) Laura Ruis, Jacob Andreas, Marco Baroni, Diane Bouchacourt, and Brenden M Lake. 2020\.  A benchmark for systematic generalization in grounded language understanding.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 19861–19872. Curran Associates, Inc.
  * Shah et al. (2019) Meet Shah, Xinlei Chen, Marcus Rohrbach, and Devi Parikh. 2019.  Cycle-consistency for robust visual question answering.  In _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 6642–6651.
  * Tapaswi et al. (2016) Makarand Tapaswi, Yukun Zhu, Rainer Stiefelhagen, Antonio Torralba, Raquel Urtasun, and Sanja Fidler. 2016.  Movieqa: Understanding stories in movies through question-answering.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 4631–4640.
  * Tellex et al. (2011) Stefanie Tellex, Thomas Kollar, Steven Dickerson, Matthew R. Walter, Ashis Gopal Banerjee, Seth Teller, and Nicholas Roy. 2011.  Understanding natural language commands for robotic navigation and mobile manipulation.  In _Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence_ , page 1507–1514.
  * Vries et al. (2018) H. D. Vries, Kurt Shuster, Dhruv Batra, D. Parikh, J. Weston, and Douwe Kiela. 2018\.  Talk the walk: Navigating new york city through grounded dialogue.  _ArXiv_.
  * Zhu et al. (2017) Yuke Zhu, Roozbeh Mottaghi, Eric Kolve, Joseph J. Lim, Abhinav Gupta, Li Fei-Fei, and Ali Farhadi. 2017.  Target-driven Visual Navigation in Indoor Scenes using Deep Reinforcement Learning.  In _IEEE International Conference on Robotics and Automation_.