# Some Results on $k$-Critical $P_{5}$-Free Graphs

Qingqiong Cai College of Computer Science, Nankai University, Tianjin 300350,
China.Supported by Natural Science Foundation of Tianjin (19JCQNJC14400). Jan
Goedgebeur Department of Applied Mathematics, Computer Science and Statistics,
Ghent University, 9000 Ghent, Belgium.Department of Computer Science, KU
Leuven Campus Kulak, 8500 Kortrijk, Belgium. Shenwei Huang The corresponding
author. College of Computer Science, Nankai University, Tianjin 300350, China.
Supported by the National Natural Science Foundation of China (11801284) and
Natural Science Foundation of Tianjin (20JCYBJC01190).

(August 12, 2021)

###### Abstract

A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every
proper induced subgraph of $G$ has chromatic number less than $k$. The study
of $k$-vertex-critical graphs for graph classes is an important topic in
algorithmic graph theory because if the number of such graphs that are in a
given hereditary graph class is finite, then there is a polynomial-time
algorithm to decide if a graph in the class is $(k-1)$-colorable.

In this paper, we prove that for every fixed integer $k\geq 1$, there are only
finitely many $k$-vertex-critical ($P_{5}$,gem)-free graphs and
$(P_{5},\overline{P_{3}+P_{2}})$-free graphs. To prove the results we use a
known structure theorem for ($P_{5}$,gem)-free graphs combined with properties
of $k$-vertex-critical graphs. Moreover, we characterize all $k$-vertex-
critical ($P_{5}$,gem)-free graphs and $(P_{5},\overline{P_{3}+P_{2}})$-free
graphs for $k\in\\{4,5\\}$ using a computer generation algorithm.

Keywords. Graph coloring; $k$-critical graphs; forbidden induced subgraphs;
computer generation algorithm.

##  1 Introduction

All graphs in this paper are finite and simple. We say that a graph $G$
contains a graph $H$ if $H$ is isomorphic to an induced subgraph of $G$. A
graph $G$ is $H$-free if it does not contain $H$. For a family of graphs
$\mathcal{H}$, $G$ is $\mathcal{H}$-free if $G$ is $H$-free for every
$H\in\mathcal{H}$. When $\mathcal{H}$ consists of two graphs, we write
$(H_{1},H_{2})$-free instead of $\\{H_{1},H_{2}\\}$-free.

A _$q$ -coloring_ of a graph $G$ is a function
$\phi:V(G)\longrightarrow\\{1,\ldots,q\\}$ such that $\phi(u)\neq\phi(v)$
whenever $u$ and $v$ are adjacent in $G$. Equivalently, a $q$-coloring of $G$
is a partition of $V(G)$ into $q$ independent sets. A graph is $q$-colorable
if it admits a $q$-coloring. The _chromatic number_ of a graph $G$, denoted by
$\chi(G)$, is the minimum number $q$ for which $G$ is $q$-colorable. The
_clique number_ of $G$, denoted by $\omega(G)$, is the size of a largest
clique in $G$.

A graph $G$ is $k$-chromatic if $\chi(G)=k$. We say that $G$ is $k$-critical
if it is $k$-chromatic and $\chi(G-e)<\chi(G)$ for any edge $e\in E(G)$. For
instance, $K_{2}$ is the only 2-critical graph and odd cycles are the only
3-critical graphs. A graph is critical if it is $k$-critical for some integer
$k\geq 1$. Critical graphs were first defined and studied by Dirac [11, 12,
13] in the early 1950s, and then by Gallai and Ore [14, 15, 24] among many
others, and more recently by Kostochka and Yancey [22].

A weaker notion of criticality is the so-called vertex-criticality. A graph
$G$ is $k$-vertex-critical if $\chi(G)=k$ and $\chi(G-v)<k$ for any $v\in
V(G)$. For a set $\mathcal{H}$ of graphs and a graph $G$, we say that $G$ is
$k$-vertex-critical $\mathcal{H}$-free if it is $k$-vertex-critical and
$\mathcal{H}$-free. We are mainly interested in the following question.

The meta question. Given a set $\mathcal{H}$ of graphs and an integer $k\geq
1$, are there only finitely many $k$-vertex-critical $\mathcal{H}$-free
graphs?

This question is important in the study of algorithmic graph theory because of
the following theorem, whose proof can be found in [4].

######  Theorem 1 (Folklore).

Given a set $\mathcal{H}$ of graphs and an integer $k\geq 1$, if the set of
all $k$-vertex-critical $\mathcal{H}$-free graphs is finite, then there is a
polynomial-time algorithm to determine whether an $\mathcal{H}$-free graph is
$(k-1)$-colorable.

As usual, $P_{t}$ and $C_{s}$ denote the path on $t$ vertices and the cycle on
$s$ vertices, respectively. The complete graph on $n$ vertices is denoted by
$K_{n}$. For two graphs $G$ and $H$, we use $G+H$ to denote the _disjoint
union_ of $G$ and $H$. For a positive integer $r$, we use $rG$ to denote the
disjoint union of $r$ copies of $G$. The _complement_ of $G$ is denoted by
$\overline{G}$. A clique (resp. independent set) in a graph is a set of
pairwise adjacent (resp. nonadjacent) vertices. If a graph $G$ can be
partitioned into $k$ independent sets $S_{1},\ldots,S_{k}$ such that there is
an edge between every vertex in $S_{i}$ and every vertex in $S_{j}$ for all
$1\leq i<j\leq k$, $G$ is called a complete $k$-partite graph; each $S_{i}$ is
called a part of $G$. If we do not specify the number of parts in $G$, we
simply say that $G$ is a complete multipartite graph. We denote by
$K_{n_{1},\ldots,n_{k}}$ the complete $k$-partite graph such that the $i$th
part $S_{i}$ has size $n_{i}$, for each $1\leq i\leq k$.

In this paper, we continue to study $k$-vertex-critical graphs in the class of
$P_{5}$-free graphs. Our research is mainly motivated by the following
dichotomy result.

######  Theorem 2 ([5]).

Let $H$ be a graph of order 4 and $k\geq 5$ be a fixed integer. Then there are
infinitely many $k$-vertex-critical $(P_{5},H)$-free graphs if and only if $H$
is $2P_{2}$ or $P_{1}+K_{3}$.

This Theorem completely settles the finiteness question of $k$-vertex-critical
$(P_{5},H)$-free graphs for graphs of order 4. In [5], the authors also posed
the natural question of which five-vertex graphs $H$ lead to finitely many
$k$-vertex-critical $(P_{5},H)$-free graphs. It is known that there are
exactly 13 5-vertex-critical $(P_{5},C_{5})$-free graphs [19], and that there
are finitely many 5-vertex-critical ($P_{5}$,banner)-free graphs [4, 20], and
finitely many $k$-vertex-critical $(P_{5},\overline{P_{5}})$-free graphs for
every fixed $k$ [10]. Hell and Huang proved that there are finitely many
$k$-vertex-critical $(P_{6},C_{4})$-free graphs [18]. This was later
generalized to $(P_{t},K_{r,s})$-free graphs in the context of $H$-coloring
[21]. This gives an affirmative answer for $H=K_{2,3}$. Apart from these,
there seem to be very few results on the finiteness of $k$-vertex-critical
graphs for $k\geq 5$. In this paper, we prove two new finiteness results
beyond 5-vertex-criticality.

###  1.1 Our Contributions

We continue to study the subclasses of $P_{5}$-free graphs. In particular, we
focus on $(P_{5},H)$-free graphs when $H$ has order 5. The gem graph is the
graph consisting of an induced $P_{4}$ with an additional vertex that is
adjacent to every vertex on the $P_{4}$. In this paper, we prove that there
are only finitely many $k$-vertex-critical $(P_{5},H)$-free graphs for every
fixed $k\geq 1$ when $H$ is gem or $\overline{P_{3}+P_{2}}$ (see Figure 1 for
drawings of gem and $\overline{P_{3}+P_{2}}$). Moreover, we characterize all
4- and 5-vertex-critical ($P_{5}$,gem)-free graphs and
$(P_{5},\overline{P_{3}+P_{2}})$-free graphs by extending the computer
generation algorithm from [17].

To prove the result on gem-free graphs, we used a known structure theorem for
($P_{5}$,gem)-free graphs that is used to give an optimal $\chi$-binding
function for the class combined with an inductive argument based on a careful
analysis of the structure. For the $\overline{P_{3}+P_{2}}$-free case, we
performed a careful structural analysis combined with the repeated use of the
pigeonhole principle based on the properties of $k$-vertex-critical graphs.

The remainder of the paper is organized as follows. We present some
preliminaries in Section 2 and prove our new results in Section 3. Finally, we
give some concluding remarks in Section 4.

Figure 1: The graphs gem (left) and $\overline{P_{3}+P_{2}}$ (right).

##  2 Preliminaries

For general graph theory notation we follow [1]. Let $G=(V,E)$ be a graph. If
$uv\in E$, we say that $u$ and $v$ are neighbors or adjacent; otherwise $u$
and $v$ are nonneighbors or nonadjacent. The _neighborhood_ of a vertex $v$,
denoted by $N_{G}(v)$, is the set of neighbors of $v$. For a set $X\subseteq
V(G)$, let $N_{G}(X)=\bigcup_{v\in X}N_{G}(v)\setminus X$. We shall omit the
subscript whenever the context is clear. For $X,Y\subseteq V$, we say that $X$
is _complete_ (resp.  _anticomplete_) to $Y$ if every vertex in $X$ is
adjacent (resp. nonadjacent) to every vertex in $Y$. If $X=\\{x\\}$, we write
“$x$ is complete (resp. anticomplete) to $Y$” instead of “$\\{x\\}$ is
complete (resp. anticomplete) to $Y$”. If a vertex $v$ is neither complete nor
anticomplete to a set $S$, we say that $v$ is mixed on $S$. We say that $H$ is
a homogeneous set if no vertex in $V-H$ is mixed on $H$. More generally, we
say that $H$ is homogeneous with respect to a subset $S\subseteq V$ if no
vertex in $S$ can be mixed on $H$. A vertex is _universal_ in $G$ if it is
adjacent to all other vertices. Two nonadjacent vertices $u$ and $v$ are said
to be _comparable_ if $N(v)\subseteq N(u)$ or $N(u)\subseteq N(v)$. A vertex
subset $K\subseteq V$ is a _clique cutset_ if $G-K$ has more components than
$G$ and $K$ induces a clique. For $S\subseteq V$, the subgraph _induced_ by
$S$, is denoted by $G[S]$. A $k$-hole in a graph is an induced cycle $H$ of
length $k\geq 4$. If $k$ is odd, we say that $H$ is an odd hole. A
$k$-antihole in $G$ is a $k$-hole in $\overline{G}$. Odd antiholes are defined
analogously.

We proceed with a few useful results that will be needed later. The first one
is a folklore property of $k$-vertex-critical graphs.

######  Lemma 1 (Folklore).

A $k$-vertex-critical graph cannot contain clique cutsets.

Another folklore property of vertex-critical graphs is that such graphs
contain no comparable vertices. A generalization of this property was
presented in [5].

######  Lemma 2 ([5]).

Let $G$ be a $k$-vertex-critical graph. Then $G$ has no two nonempty disjoint
subsets $X$ and $Y$ of $V(G)$ that satisfy all the following conditions.

  * •

$X$ and $Y$ are anticomplete to each other.

  * •

$\chi(G[X])\leq\chi(G[Y])$.

  * •

$Y$ is complete to $N(X)$.

A graph $G$ is perfect if $\chi(H)=\omega(H)$ for each induced subgraph $H$ of
$G$. An imperfect graph is a graph that is not perfect. We conclude this
section with the celebrated Strong Perfect Graph Theorem [9].

######  Theorem 3 (Strong Perfect Graph Theorem [9]).

A graph is perfect if and only if it contains no odd holes or odd antiholes.

##  3 New Results

###  3.1 Gem-Free Graphs

######  Theorem 4.

For every fixed integer $k\geq 1$, there are finitely many $k$-vertex-critical
($P_{5}$, gem)-free graphs.

To prove Theorem 4, we need a structure theorem for the class of ($P_{5}$,
gem)-free graphs that was obtained in [8]. Let $\mathcal{H}$ be the class of
connected ($P_{5}$, gem)-free graphs $G$ such that $V(G)$ can be partitioned
into seven nonempty sets $A_{1},A_{2},\ldots,A_{7}$ such that:

$\bullet$ Each $A_{i}$ induces a $P_{4}$-free graph.

$\bullet$ $A_{1}$ is complete to $A_{2}\cup A_{5}\cup A_{6}$ and anticomplete
to $A_{3}\cup A_{4}\cup A_{7}$.

$\bullet$ $A_{3}$ is complete to $A_{2}\cup A_{4}\cup A_{6}$ and anticomplete
to $A_{5}\cup A_{7}$.

$\bullet$ $A_{4}$ is complete to $A_{5}\cup A_{6}$ and anticomplete to
$A_{2}\cup A_{7}$.

$\bullet$ $A_{2}$ is anticomplete to $A_{5}\cup A_{6}\cup A_{7}$.

$\bullet$ $A_{5}$ is anticomplete to $A_{6}\cup A_{7}$.

$\bullet$ The vertex set of each component of $G[A_{7}]$ is a homogeneous set
of $G$.

$\bullet$ The adjacency between $A_{6}$ and $A_{7}$ is not specified but it is
restricted by the fact that $G$ is ($P_{5}$, gem)-free.

See Figure 2 for an illustration.

$A_{1}$$A_{2}$$A_{5}$$A_{3}$$A_{4}$$A_{6}$$A_{7}$ Figure 2: A diagram for
graphs $G\in\mathcal{H}$. A thick line between two sets means that the two
sets are complete. A normal line between two sets means that the edges are
arbitrary (subject to the ($P_{5}$,gem)-freeness). No line between two sets
means that the two sets are anticomplete. Moreover, each $A_{i}$ is
$P_{4}$-free, and the vertex set of each component of $G[A_{7}]$ is a
homogeneous set of $G$.

For two graphs $G$ and $H$, we say that $G$ is an substitution of $H$ if
$V(G)$ can be partitioned into $|V(H)|$ nonempty subsets $Q_{v}$, $v\in V(H)$
so that $Q_{u}$ and $Q_{v}$ are complete if $uv\in E(H)$ and anticomplete if
$uv\notin E(H)$ for every different vertices $u,v\in V(H)$. If each $Q_{v}$ is
$P_{4}$-free, then it is called an $P_{4}$-free substitution; if each $Q_{v}$
is a clique, then it is called a clique substitution. To state the structural
theorem, we also need 10 special graphs $G_{1},G_{2},\ldots,G_{10}$ each of
which has order at most 9. We omit the drawing of these 10 graphs and refer
the readers to [8]. Now we are ready to state the structure theorem obtained
in [8].

######  Lemma 3 ([8]).

Let $G$ be a connected ($P_{5}$, gem)-free graph that contains an induced
$C_{5}$. Then either $G\in\mathcal{H}$ or $G$ is a $P_{4}$-free substitution
of $G_{1},G_{2},\ldots,G_{10}$.

We also need a lemma from [6].

######  Lemma 4 ([6]).

Let $G$ be a connected ($P_{5}$, gem)-free graph and $H$ a homogeneous set of
$G$ that is not a clique. Then there exists a connected induced subgraph
$G^{\prime}$ of G with $|G^{\prime}|<|G|$ such that
$\omega(G^{\prime})=\omega(G)$ and $\chi(G^{\prime})=\chi(G)$.

We are now ready to prove the main result in this subsection.

###### Proof of Theorem 4.

Let $G$ be a $k$-vertex-critical ($P_{5}$,gem)-free graph. Then $G$ is
connected. We show that $|G|$ is bounded by a function of $k$. If $G$ contains
a $K_{k}$, then $G=K_{k}$. So we may assume that $G$ is $K_{k}$-free. Since
$G$ is not perfect, it follows from Theorem 3 that $G$ contains an induced
$C_{5}$. By Lemma 3, $G\in\mathcal{H}$ or $G$ is a $P_{4}$-expansion of
$G_{1},G_{2},\ldots,G_{10}$. If $G$ is a $P_{4}$-free substitution of
$G_{1},G_{2},\ldots,G_{10}$, then it must be a clique expansion of
$G_{1},G_{2},\ldots,G_{10}$ by Lemma 4. Since $|G_{i}|\leq 9$ for $1\leq i\leq
10$ (see [8]), it follows that $|G|\leq 9k$.

Therefore, we assume that $G\in\mathcal{H}$ in the following and can be
partitioned into seven nonempty subsets $A_{1},A_{2},\ldots,A_{7}$ as
described in the definition. Note that each $A_{i}$ ($1\leq i\leq 5$) is a
homogeneous set of $G$. Thus, $A_{i}$ (for $1\leq i\leq 5$) is a clique by
Lemma 4 and so $|A_{i}|\leq k$. So it remains to bound $A_{6}$ and $A_{7}$.
For the same reason, every component of $G[A_{7}]$ is a clique and has size at
most $k$.

######  Claim 1.

Let $X\subseteq A_{6}$ be a subset such that $X$ is homogeneous with respect
to $V(G)-A_{7}$. Then $|X|\leq 2^{2\omega^{2}(X)}$.

###### Proof.

We prove this by induction on $\omega(X)$. Since $A_{3}\neq\emptyset$, it
contains a vertex, say $t$. The base case is $\omega(X)=1$, i.e., $X$ is an
independent set. If $X$ contains two vertices $x_{1},x_{2}$, then by Lemma 2
and our assumption there exist vertices $y_{1},y_{2}\in A_{7}$ such that
$x_{1}y_{1},x_{2}y_{2}\in E$ but $x_{1}y_{2},x_{2}y_{1}\notin E$. Since every
component of $G[A_{7}]$ is a homogeneous set of $G$, $y_{1}y_{2}\notin E$.
Then $y_{1},x_{1},t,x_{2},y_{2}$ induces a $P_{5}$. This proves that $|X|\leq
1$.

Suppose now that $\omega:=\omega(X)\geq 2$ and the claim is true for any
subset $Y$ such that $Y$ is homogeneous with respect to $V(G)-A_{7}$ with
$\omega(Y)<\omega$. We first prove two useful facts about components of $X$.

All but at most one component of $X$ are homogeneous sets of $G$. (1)

Proof of (1). Suppose not. Then there exist two components $C$ and
$C^{\prime}$ of $X$ such that $C$ and $C^{\prime}$ are not homogeneous sets of
$G$. By our assumption on $X$, there are vertices $v,v^{\prime}\in A_{7}$ such
that $v$ is mixed on an edge $ab\in C$ with $va\notin E$ and $vb\in E$, and
$v^{\prime}$ is mixed on an edge $a^{\prime}b^{\prime}\in C^{\prime}$ with
$v^{\prime}a^{\prime}\notin E$ and $v^{\prime}b^{\prime}\in E$.

If $v,v^{\prime}$ are in the same component of $A_{7}$, then $vv^{\prime}\in
E$. Since every component of $A_{7}$ is a homogeneous set of $G$,
$vb^{\prime},v^{\prime}b\in E$ and $va^{\prime},v^{\prime}a\notin E$. Then
$a,b,v,b^{\prime},a^{\prime}$ induces a $P_{5}$.

So $v,v^{\prime}$ lie in different components of $A_{7}$. If
$vb^{\prime},v^{\prime}b\notin E$, then $v,b,t,b^{\prime},v^{\prime}$ induces
a $P_{5}$. So by symmetry we assume that $vb^{\prime}\in E$. Then
$va^{\prime}\in E$ since otherwise $a,b,v,b^{\prime},a^{\prime}$ induces a
$P_{5}$. Note that $a,b,v,b^{\prime},v^{\prime}$ induces a $P_{5}$ unless
$v^{\prime}$ is adjacent to $a$ or $b$. If $v^{\prime}b\in E$, then
$v^{\prime}a\in E$ since otherwise $a,b,v^{\prime},b^{\prime},a^{\prime}$
induces a $P_{5}$. This shows that $v^{\prime}a\in E$. But now $va^{\prime}$
and $v^{\prime}a$ induce a $2P_{2}$ and this together with $t\in A_{3}$ gives
an induced $P_{5}$. This completes the proof of (1).

There is at most one homogeneous component of $X$ of size $i$ for $1\leq
i\leq\omega$. (2)

Proof of (2). Suppose not. Then there are two homogeneous components $C$ and
$C^{\prime}$ of $X$ of size $i$ for some $1\leq i\leq k$. By Lemma 4, we know
that $C$ and $C^{\prime}$ are two cliques of size $i$, and thus
$\chi(G[C])=\chi(G[C^{\prime}])=i$. By Lemma 2, there exist $a,a^{\prime}\in
A_{7}$ such that $a\in N(C)\setminus N(C^{\prime})$ and $a^{\prime}\in
N(C^{\prime})\setminus N(C)$. Then $a,c,t,c^{\prime},a^{\prime}$ induces a
$P_{5}$, where $c\in C$, $c^{\prime}\in C^{\prime}$. This completes the proof
of (2).

Let $H$ be the possible non-homogeneous component of $X$. Then
$|X|\leq\omega^{2}+|H|$. We now bound $H$. Let
$K=\\{v_{1},v_{2},\ldots,v_{s}\\}$ be a maximum clique of $H$. Clearly,
$s\leq\omega(X)$. For every $I\subseteq K$, define

$T_{I}=\\{v\in V(H)\setminus V(K):N_{K}(v)=I\\}.$

We show that $T_{I}$ is homogeneous with respect to $V(G)-A_{7}$. First note
that $T_{K}=\emptyset$ by the choice of $K$. Suppose that
$T_{\emptyset}\neq\emptyset$. Then by the connectivity of $H$, there is a
vertex $z\in T_{\emptyset}$ that has a neighbor $y\in T_{I}$ for some
$I\neq\emptyset$. Since $y$ cannot be complete to $K$, there exist $i,j$ such
that $y$ is adjacent to $v_{i}$ but not to $v_{j}$. Then $z,y,v_{i},v_{j}$
induces a $P_{4}$, which contradicts the fact that $A_{6}$ is $P_{4}$-free. So
$T_{\emptyset}=\emptyset$.

Let $I,J\subseteq K$ with $I\neq J$. If there exist $i,j$ such that $v_{i}\in
I\setminus J$ and $v_{j}\in J\setminus I$, then $T_{I}$ and $T_{J}$ are
complete: if $t_{i}\in T_{I}$ and $t_{j}\in T_{j}$ are not adjacent, then
$t_{i},v_{i},v_{j},t_{j}$ induces a $P_{4}$. Now suppose that $I\subseteq J$.
Since $|I|<|J|$, there exists an index $j$ such that $v_{j}\in J\setminus I$.
Since $J\neq K$, there is an index $k$ such that $v_{k}\notin J$. Then if
$t_{i}\in T_{I}$ and $t_{j}\in T_{J}$ are adjacent, then
$t_{i},t_{j},v_{j},v_{k}$ induces a $P_{4}$. So $T_{I}$ and $T_{J}$ are
anticomplete.

This proves that for each $I\subseteq K$, $T_{I}$ is homogeneous with respect
to $V(G)-A_{7}$. Moreover, $\omega(T_{I})<\omega$. By the inductive
hypothesis, it follows that $|T_{I}|\leq 2^{2(\omega-1)^{2}}$. So

$|H|=\sum_{I\subseteq K}|T_{I}|+|K|\leq 2^{2(\omega-1)^{2}}2^{\omega}+\omega.$

Thus, $|X|\leq
2^{2(\omega-1)^{2}}2^{\omega}+\omega+\omega^{2}=2^{2\omega^{2}-3\omega+2}+(\omega+\omega^{2})$.
Since $\omega+\omega^{2}\leq 2^{3\omega-2}$, it follows that $|X|\leq
2^{2\omega^{2}}$. This proves the claim. ∎

Applying Claim 1 to $A_{6}$, we have that $|A_{6}|\leq
2^{2\omega^{2}(A_{6})}\leq 2^{2k^{2}}$. Finally, we bound $A_{7}$.

######  Claim 2.

$|A_{7}|\leq k2^{|A_{6}|}$.

###### Proof.

Recall that each component of $A_{7}$ is a clique and so has size at most $k$.
We now group the components by size and show that each group has at most
$2^{|A_{6}|}$ components. Suppose not. Then there are two components $C$ and
$C^{\prime}$ of $A_{7}$ having the same size $i$ with $N(C)=N(C^{\prime})$,
which contradicts Lemma 2. This proves the claim. ∎

Therefore, $|G|=\sum_{i=1}^{7}|A_{i}|\leq 5k+|A_{6}|+|A_{7}|$, which is a
function of $k$. ∎

###  3.2 $\overline{P_{3}+P_{2}}$-Free Graphs

######  Theorem 5.

For every fixed integer $k\geq 1$, there are finitely many $k$-vertex-critical
($P_{5}$, $\overline{P_{3}+P_{2}}$)-free graphs.

###### Proof.

Let $G$ be a $k$-vertex-critical ($P_{5}$, $\overline{P_{3}+P_{2}}$)-free
graph. We show that $|G|$ is bounded by a function of $k$. If $G$ contains a
$K_{k}$, then $G$ is isomorphic to $K_{k}$ and thus $|G|=k$. So assume that
$G$ is $K_{k}$-free. Since $G$ is imperfect, $G$ contains an induced $C_{5}$
by Theorem 3. Let $Q=v_{1},v_{2},v_{3},v_{4},v_{5}$ be an induced $C_{5}$. For
each $1\leq i\leq 5$, we define

$\begin{split}Z&=\\{v\in V\setminus Q:N_{Q}(v)=\emptyset\\},\\\ C_{i}&=\\{v\in
V\setminus Q:N_{Q}(v)=\\{v_{i-1},v_{i+1}\\}\\},\\\ Y_{i}&=\\{v\in V\setminus
Q:N_{Q}(v)=\\{v_{i-2},v_{i},v_{i+2}\\}\\},\\\ T_{i}&=\\{v\in V\setminus
Q:N_{Q}(v)=\\{v_{i-1},v_{i},v_{i+1}\\}\\},\\\ F_{i}&=\\{v\in V\setminus
Q:N_{Q}(v)=V(Q)\setminus\\{v_{i}\\}\\},\\\ U&=\\{v\in V\setminus
Q:N_{Q}(v)=V(Q)\\}.\\\ \end{split}$

Let $C=\cup_{1\leq i\leq 5}C_{i}$, $Y=\cup_{1\leq i\leq 5}Y_{i}$,
$T=\cup_{1\leq i\leq 5}T_{i}$ and $F=\cup_{1\leq i\leq 5}F_{i}$. We choose $Q$
so that $|Y|$ is maximum.

######  Claim 3.

$V(G)=V(Q)\cup Z\cup C\cup Y\cup T\cup F\cup U$.

###### Proof.

Suppose that the claim is false. Then there is a vertex $u$ such that
$\\{v_{i}\\}\subseteq N(u)\subseteq\\{v_{i},v_{i+1}\\}$ for some $1\leq i\leq
5$. Then $u,v_{i},v_{i+4},v_{i+3},v_{i+2}$ induces a $P_{5}$. ∎

We first bound $U$.

######  Claim 4.

For each $1\leq i\leq 5$, $Y_{i}\cup U$ and $F_{i}\cup U$ are cliques.

###### Proof.

Suppose that $Y_{i}\cup U$ contains two nonadjacent vertices $x$ and $y$, then
$\\{x,y,v_{i-2},v_{i},v_{i+2}\\}$ induces a $\overline{P_{3}+P_{2}}$. The
proof for $F_{i}\cup U$ is completely analogous. ∎

By Claim 4, it follows that $|U|<k$.

######  Claim 5.

For each $1\leq i\leq 5$, $C_{i}$, $Y_{i}$ and $F_{i}$ are independent sets.

###### Proof.

Note that for each vertex $x\in C\cup Y\cup F$, there is an index $i$ such
that $x$ is not adjacent to $v_{i}$ but adjacent to both $v_{i+1}$ and
$v_{i-1}$. If $C_{i}$ contains two adjacent vertices $x$ and $y$, then let $j$
be such that $x,y$ are not adjacent to $v_{j}$ but adjacent to both $v_{j-1}$
and $v_{j+1}$. Then $\\{x,y,v_{j-1},v_{j},v_{j+1}\\}$ induces a
$\overline{P_{3}+P_{2}}$. The proof for $Y_{i}$ and $F_{i}$ is completely
analogous. ∎

By Claim 4 and Claim 5, $|Y_{i}|\leq 1$ and $|F_{i}|\leq 1$. So $|Y|\leq 5$
and $|F|\leq 5$. Next we bound $Z$.

######  Claim 6.

$Z$ is anticomplete to $C\cup T$.

###### Proof.

Let $z\in Z$. If $z$ has a neighbor $x\in C_{i}\cup T_{i}$, then
$z,x,v_{i+1},v_{i+2},v_{i+3}$ induces a $P_{5}$. ∎

######  Claim 7.

Each vertex in $Y\cup F$ is either complete or anticomplete to each component
of $Z$.

###### Proof.

Let $v\in Y\cup F$ be that $v$ is adjacent to $a$ but not adjacent to $b$ with
$ab\in E(Z)$. Note that there is an index $i$ such that $v,v_{i},v_{i+1}$ is
an induced $P_{3}$. Then $b,a,v,v_{i},v_{i+1}$ induces a $P_{5}$. ∎

######  Claim 8.

$Z$ is an independent set.

###### Proof.

Suppose not. Let $K$ be a component of $Z$ containing an edge $ab$. By Claim
6, $N(K)\subseteq Y\cup F\cup U$. Since $G$ has no clique cutset, it follows
from Claim 7 and Claim 4 that there are two nonadjacent vertices $x$ and $y$
in $Y\cup F$ that are complete to $K$. Let $v_{i}\in V(Q)$ be a common
neighbor of $x$ and $y$. Then $\\{a,b,x,y,v_{i}\\}$ induces a
$\overline{P_{3}+P_{2}}$. ∎

By Claim 6, $N(z)\subseteq Y\cup F\cup U$ for each $z\in Z$. Note that $|Y\cup
F\cup U|\leq k+10$ and so there are $2^{10+k}$ possible neighborhoods for
vertices in $Z$. By Lemma 2 and the pigeonhole principle, $|Z|\leq 2^{10+k}$.

Next we bound $C$.

######  Claim 9.

$C_{i}$ and $C_{i+1}$ are complete to each other.

###### Proof.

Let $c_{3}\in C_{3}$ and $c_{4}\in C_{4}$. If $c_{3}c_{4}\notin E$, then
$c_{4},v_{5},v_{1},v_{2},c_{3}$ induces a $P_{5}$. ∎

######  Claim 10.

$C_{i}$ is complete to $T_{i}$.

###### Proof.

By symmetry, we prove for $i=1$. If $c_{1}\in C_{1}$ and $t_{1}\in T_{1}$ are
not adjacent, then $\\{c_{1},t_{1},v_{5},v_{1},v_{2}\\}$ induces a
$\overline{P_{3}+P_{2}}$. ∎

######  Claim 11.

$C_{i}$ is anticomplete to $T_{i+1}$ and $T_{i-1}$.

###### Proof.

If $c_{1}\in C_{1}$ is adjacent to $t_{2}\in T_{2}$, then
$\\{v_{5},c_{1},v_{1},v_{2},t_{2}\\}$ induces a $\overline{P_{3}+P_{2}}$. The
case for $T_{5}$ is similar. ∎

######  Claim 12.

No vertex in $T_{i+2}$ or $T_{i-2}$ can be mixed on $C_{i}$.

###### Proof.

Suppose that $t_{3}\in T_{3}$ is mixed on $C_{1}$. Then there are vertices
$c_{1},c^{\prime}_{1}\in C_{1}$ with $t_{3}c_{1}\in E$ and
$t_{3}c^{\prime}_{1}\notin E$. Then $c^{\prime}_{1},v_{5},c_{1},t_{3},v_{3}$
induces a $P_{5}$. The case for $T_{4}$ is similar. ∎

######  Claim 13.

For each $1\leq i\leq 5$, $|C_{i}|\leq 2^{|Y\cup F\cup U|}$.

###### Proof.

Suppose not. Then by the pigeonhole principle, there are two vertices
$c_{1},c_{2}\in C_{1}$ such that $c_{1}$ and $c_{2}$ have the same neighbors
in $Y\cup F\cup U$. By Claim 6 and Claim 9-Claim 12, it follows that $c_{1}$
and $c_{2}$ have the same neighbors in $Z\cup T\cup C_{1}\cup C_{2}\cup
C_{5}$. Since $c_{1}$ and $c_{2}$ are not comparable, there exist $d_{1}\in
N(c_{1})\setminus N(c_{2})$ and $d_{2}\in N(c_{2})\setminus N(c_{1})$. So
$d_{1},d_{2}\in C_{3}\cup C_{4}$. If $d_{1},d_{2}\in C_{3}$, then
$d_{1},c_{1},v_{5},c_{2},d_{2}$ induces a $P_{5}$. So we may assume that
$d_{1}\in C_{4}$ and $d_{2}\in C_{3}$.

Consider the induced five-cycle $Q^{\prime}=Q-\\{v_{1}\\}\cup\\{c_{1}\\}$. Let
$Y^{\prime}$ be the set of vertices in $V(G)\setminus V(Q^{\prime})$ whose
neighborhood on $Q^{\prime}$ induces a $P_{2}+P_{1}$. Note that $d_{1}\in
Y^{\prime}\setminus Y$. By the choice of $Q$, there exists a vertex $y\in
Y\setminus Y^{\prime}$. Clearly, $y\in Y_{1}\cup Y_{3}\cup Y_{4}$ and
$yc_{1}\notin E$. If $y\in Y_{1}$, then $c_{1},v_{5},v_{1},y,v_{3}$ induces a
$P_{5}$. So $y\in Y_{3}\cup Y_{4}$. By symmetry, we may assume that $y\in
Y_{4}$. Note that $yc_{2}\notin E$ since otherwise
$\\{y,c_{2},v_{1},v_{2},v_{5}\\}$ induces a $\overline{P_{3}+P_{2}}$,
$yd_{1}\in E$ since otherwise $y,v_{1},v_{5},d_{1},v_{3}$ induces a $P_{5}$,
and that $yd_{2}\notin E$ since otherwise $\\{y,d_{1},d_{2},v_{2},v_{3}\\}$
induces a $\overline{P_{3}+P_{2}}$. But now $c_{2},d_{2},d_{1},y,v_{1}$
induces a $P_{5}$, a contradiction. ∎

By Claim 13, $|C|\leq 5\times 2^{k+10}$. Finally, we bound $T$.

######  Claim 14.

For each $1\leq i\leq 5$, $T_{i}$ is $P_{2}+P_{1}$-free and thus induces a
complete multipartite graph.

###### Proof.

If $T_{i}$ contains three vertices $x,y,z$ such that $xy$ and $z$ induce a
disjoint union of an edge and a vertex, then $\\{x,y,z,v_{i-1},v_{i+1}\\}$
induces a $\overline{P_{3}+P_{2}}$. It is well-known that a graph is a
complete multipartite graph if and only if it is $P_{2}+P_{1}$-free. ∎

######  Claim 15.

For each $1\leq i\leq 5$, $T_{i}$ and $T_{i+1}$ are complete.

###### Proof.

If $t_{1}\in T_{1}$ and $t_{2}\in T_{2}$ are not adjacent, then
$t_{2},v_{3},v_{4},v_{5},t_{1}$ induces a $P_{5}$. ∎

######  Claim 16.

$|T_{i}|\leq k2^{|Z\cup C\cup Y\cup F\cup U|}$.

###### Proof.

By Claim 14, $T_{1}$ is a complete $r$-partite graph $(X_{1},\ldots,X_{r})$
for some $r\leq k$ where $X_{i}$ and $X_{j}$ are complete for all $1\leq
i<j\leq r$. If $|X_{i}|>2^{|Z\cup C\cup Y\cup F\cup U|}$, then by the
pigeonhole principle there are two nonadjacent vertices $x_{1}$ and $x_{2}$
that have the same neighbors in $Z\cup C\cup Y\cup F\cup U$. Since $x_{1}$ and
$x_{2}$ are not comparable, there are vertices $y_{1}\in N(x_{1})\setminus
N(x_{2})$ and $y_{2}\in N(x_{2})\setminus N(x_{1})$. By Claim 15,
$y_{1},y_{2}\in T_{3}\cup T_{4}$. Then $v_{4},y_{1},x_{1},v_{1},x_{2}$ induces
a $P_{5}$. ∎

By Claim 16, $|T|$ is bounded by a function of $k$ and so is $|G|$. This
completes the proof. ∎

###  3.3 Complete Characterization for $k=4$ and $k=5$

We remark that the upper bound on the order of the $k$-vertex-critical graphs
in Theorem 5 and Theorem 4 is far from being tight: the objective was to show
the existence of such a bound and so we did not try to optimize the bound.
This indicates that it may be possible to characterize all $k$-vertex-critical
graphs for small values of $k$. In this subsection, we prove that this is
indeed possible for $k=4$ and $k=5$. In particular, we prove the following
theorems.

######  Theorem 6.

There are exactly 3 4-vertex-critical ($P_{5}$,gem)-free graphs and there are
exactly 6 4-vertex-critical $(P_{5},\overline{P_{3}+P_{2}})$-free graphs.

######  Theorem 7.

There are exactly 7 5-vertex-critical ($P_{5}$,gem)-free graphs and there are
exactly 20 5-vertex-critical $(P_{5},\overline{P_{3}+P_{2}})$-free graphs.

###### Proof of Theorem 6 and Theorem 7.

The proof uses the computer program for generating $k$-vertex-critical
$\mathcal{H}$-free graphs developed in [17]. The program takes a positive
integer $k$ and a set $\mathcal{H}$ of forbidden induced subgraphs as input
and if it terminates, it outputs a complete list of $k$-vertex-critical
$\mathcal{H}$-free graphs. The source code of this algorithm can be downloaded
from [16]. We refer to [17] for more details about the generation algorithm.
The correctness of this algorithm has extensively been tested in the
literature, see [5, 7, 17] for example.

We extended the algorithm from [17] so it can also generate $H$-free graphs
where $H=$ gem or $H=\overline{P_{3}+P_{2}}$ and executed the algorithm in
with the following inputs:

  * •

$k=4$ or $k=5$;

  * •

$\mathcal{H}=\\{P_{5}$,gem$\\}$ or
$\mathcal{H}=\\{P_{5},\overline{P_{3}+P_{2}}\\}$.

In each of these 4 cases the algorithm terminates within a few seconds and
yields the graphs reported in Theorem 6, Theorem 7, and in Table 1. ∎

The counts of the vertex-critical graphs from Theorem 6 and Theorem 7 are
listed in Table 1. The 3 4-vertex-critical ($P_{5}$,gem)-free graphs from
Theorem 6 are shown in Figure 3 and the 7 5-vertex-critical ($P_{5}$,gem)-free
graphs from Theorem 7 are shown in Figure 4.

The adjacency lists of all vertex-critical graphs from Theorem 6 and Theorem 7
can be found in the Appendix and these graphs also be inspected in the
database of interesting graphs at the House of Graphs [2] by searching for the
keywords “4-critical P5Gem-free”, “5-critical P5Gem-free”, “4-critical
P5co(P2+P3)-free”, or “5-critical P5co(P2+P3)-free”.

Note that it follows from [3, 23] that there are exactly 12 4-vertex-critical
$P_{5}$-free graphs. As an independent test for the correctness of our
implementation, we took these 12 graphs and tested which of these graphs is
also gem-free or $\overline{P_{3}+P_{2}}$-free. This yielded exactly the same
graphs as in Theorem 6. As another correctness test, we modified our program
to generate all gem-free graphs and compared it with the known counts of gem-
free graphs at the On-Line Encyclopedia of Integer
Sequences111https://oeis.org/A079576. Also here the results were in complete
agreement.

Vertices | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 13 | Total
---|---|---|---|---|---|---|---|---|---
4-vertex-critical ($P_{5}$,gem)-free graphs | 1 |  |  | 1 |  |  | 1 |  | 3
5-vertex-critical ($P_{5}$,gem)-free graphs |  | 1 |  |  |  | 3 |  | 3 | 7
4-vertex-critical ($P_{5},\overline{P_{3}+P_{2}}$)-free graphs | 1 |  | 1 | 4 |  |  |  |  | 6
5-vertex-critical ($P_{5},\overline{P_{3}+P_{2}}$)-free graphs |  | 1 |  | 1 | 4 | 14 |  |  | 20
Table 1: Counts of all $k$-vertex-critical $(P_{5},H)$-free graphs for
$k\in\\{4,5\\}$ and $H\in\\{$gem,$\overline{P_{3}+P_{2}}\\}$.

Figure 3: All 3 4-vertex-critical ($P_{5}$,gem)-free graphs.

Figure 4: All 7 5-vertex-critical ($P_{5}$,gem)-free graphs.

##  4 Conclusion

In this paper we gave an affirmative answer to the problem posed in [5] for
$H\in\\{$gem$,\overline{P_{3}+P_{2}}\\}$. Moreover, we characterized all 4-
and 5-vertex-critical ($P_{5}$,gem)-free graphs and
$(P_{5},\overline{P_{3}+P_{2}})$-free graphs by extending the computer
generation algorithm from [17]. As future research it is natural to
investigate the finiteness of $k$-vertex-critical graphs in the class of
$(P_{5},H)$-free graphs for other graphs $H$ of order 5.

## References

  * [1] J. A. Bondy and U. S. R. Murty.  Graph Theory.  Springer, 2008.
  * [2] G. Brinkmann, K. Coolsaet, J. Goedgebeur, and H. Mélot.  House of graphs: a database of interesting graphs.  Discrete Applied Mathematics, 161:311–314, 2013.  Available at https://hog.grinvin.org/.
  * [3] D. Bruce, C. T. Hoàng, and J. Sawada.  A certifying algorithm for 3-colorability of $P_{5}$-free graphs.  In Proceedings of the 20th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 5878, pages 594–604, 2009.
  * [4] Q. Cai, S. Huang, T. Li, and Y. Shi.  Vertex-critical (${P}_{5}$, banner)-free graphs.  In Yijia Chen, Xiaotie Deng, and Mei Lu, editors, Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Sanya, China, April 29–May 3, 2019, Proceedings, volume 11458 of Lecture Notes in Computer Science, pages 111–120, 2019.
  * [5] K. Cameron, J. Goedgebeur, S. Huang, and Y. Shi.  $k$-critical graphs in ${P}_{5}$-free graphs.  Theoretical Computer Science, 864:80–91, 2021.
  * [6] K. Cameron, S. Huang, and O. Merkel.  A bound for the chromatic number of (${P}_{5}$,gem)-free graphs.  Bulletin of the Australian Mathematical Society, 100:182–188, 2019\.
  * [7] M. Chudnovsky, J. Goedgebeur, O. Schaudt, and M. Zhong.  Obstructions for three-coloring graphs without induced paths on six vertices.  Journal of Combinatorial Theory, Series B, 140:45-83, 2020.
  * [8] M. Chudnovsky, T. Karthick, P. Maceli, and F. Maffray.  Coloring graphs with no induced five-vertex path or gem.  Journal of Graph Theory, 95:527–542, 2020.
  * [9] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas.  The strong perfect graph theorem.  Annals of Mathematics, 164:51–229, 2006.
  * [10] H. S. Dhaliwal, A. M. Hamel, C. T. Hoàng, F. Maffray, T. J. D. McConnell, and S. A. Panait.  On color-critical (${P}_{5}$, co-${P_{5}}$)-free graphs.  Discrete Applied Mathematics, 216:142–148, 2017.
  * [11] G. A. Dirac.  Note on the colouring of graphs.  Mathematische Zeitschrift, 54:347–353, 1951.
  * [12] G. A. Dirac.  A property of 4-chromatic graphs and some remarks on critical graphs.  Journal of the London Mathematical Society, 27:85–92, 1952.
  * [13] G. A. Dirac.  Some theorems on abstract graphs.  Proceedings of the London Mathematical Society, 2:69–81, 1952.
  * [14] T. Gallai.  Kritische graphen I.  Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 8:165–92, 1963.
  * [15] T. Gallai.  Kritische graphen II.  Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 8:373–395, 1963.
  * [16] J. Goedgebeur.  Homepage of generator for $k$-critical $\mathcal{H}$-free graphs: https://caagt.ugent.be/criticalpfree/.
  * [17] J. Goedgebeur and O. Schaudt.  Exhaustive generation of $k$-critical $\mathcal{H}$-free graphs.  Journal of Graph Theory, 87:188–207, 2018.
  * [18] P. Hell and S. Huang.  Complexity of coloring graphs without paths and cycles.  Discrete Applied Mathematics, 216:211–232, 2017.
  * [19] C. T. Hoàng, B. Moore, D. Recoskiez, J. Sawada, and M. Vatshelle.  Constructions of $k$-critical ${P_{5}}$-free graphs.  Discrete Applied Mathematics, 182:91–98, 2015.
  * [20] S. Huang, T. Li, and Y. Shi.  Critical $({P}_{6},banner)$-free graphs.  Discrete Applied Mathematics, 258:143–151, 2019.
  * [21] M. Kamiński and A. Pstrucha.  Certifying coloring algorithms for graphs without long induced paths.  Discrete Applied Mathematics, 261:258–267, 2019.
  * [22] A. V. Kostochka and M. Yancey.  Ore’s conjecture on color-critical graphs is almost true.  Journal of Combinatorial Theory, Series B, 109:73–101, 2014.
  * [23] F. Maffray and G. Morel.  On $3$-colorable $P_{5}$-free graphs.  SIAM Journal on Discrete Mathematics, 26:1682–1708, 2012.
  * [24] O. Ore.  The Four Color Problem.  Academic Press, 1967.

## Appendix

Below we list the adjacency lists of all vertex-critical graphs from Theorem 6
and Theorem 7. These graphs can also be inspected in the database of
interesting graphs at the House of Graphs [2] by searching for the keywords
“4-critical P5Gem-free”, “5-critical P5Gem-free”, “4-critical
P5co(P2+P3)-free”, and “5-critical P5co(P2+P3)-free”.

### Adjacency lists of 4-vertex-critical ($P_{5}$,gem)-free graphs

  1. 1.

{0: 1 2 3; 1: 0 2 3; 2: 0 1 3; 3: 0 1 2}

  2. 2.

{0: 1 4 5; 1: 0 2 5 6; 2: 1 3 6; 3: 2 4 6; 4: 0 3 5; 5: 0 1 4; 6: 1 2 3}

  3. 3.

{0: 1 4 5; 1: 0 2 5 6 7; 2: 1 3 7; 3: 2 4 6; 4: 0 3 5 6 7; 5: 0 1 4; 6: 1 3 4
8 9; 7: 1 2 4 8 9; 8: 6 7 9; 9: 6 7 8}

### Adjacency lists of 5-vertex-critical ($P_{5}$,gem)-free graphs

  1. 1.

{0: 1 2 3 4; 1: 0 2 3 4; 2: 0 1 3 4; 3: 0 1 2 4; 4: 0 1 2 3}

  2. 2.

{0: 1 4 5 6; 1: 0 2 5 6 7 8; 2: 1 3 7 8; 3: 2 4 7 8; 4: 0 3 5 6; 5: 0 1 4 6;
6: 0 1 4 5; 7: 1 2 3 8; 8: 1 2 3 7}

  3. 3.

{0: 1 4 5 6; 1: 0 2 5 6; 2: 1 3 6 7 8; 3: 2 4 7 8; 4: 0 3 5 7 8; 5: 0 1 4 6;
6: 0 1 2 5; 7: 2 3 4 8; 8: 2 3 4 7}

  4. 4.

{0: 1 4 5 6 7; 1: 0 2 5 6 8; 2: 1 3 6 8; 3: 2 4 7 8; 4: 0 3 5 7; 5: 0 1 4 6 7;
6: 0 1 2 5 8; 7: 0 3 4 5; 8: 1 2 3 6}

  5. 5.

{0: 1 4 5 6; 1: 0 2 5 6 7 8 12; 2: 1 3 7 12; 3: 2 4 6 7 8 12; 4: 0 3 5 8; 5: 0
1 4 6; 6: 0 1 3 5 9 10 11; 7: 1 2 3 12; 8: 1 3 4 9 10 11; 9: 6 8 10 11; 10: 6
8 9 11; 11: 6 8 9 10; 12: 1 2 3 7}

  6. 6.

{0: 1 4 5 6 7 8; 1: 0 2 5 6; 2: 1 3 6 7 8 12; 3: 2 4 8 12; 4: 0 3 5 7 12; 5: 0
1 4 6 7 8; 6: 0 1 2 5; 7: 0 2 4 5 9 10 11; 8: 0 2 3 5 9 10 11 12; 9: 7 8 10
11; 10: 7 8 9 11; 11: 7 8 9 10; 12: 2 3 4 8}

  7. 7.

{0: 1 4 5 6 7 8; 1: 0 2 5 6 12; 2: 1 3 6 7 8 12; 3: 2 4 8 12; 4: 0 3 5 7; 5: 0
1 4 6 7 8; 6: 0 1 2 5 12; 7: 0 2 4 5 9 10 11 12; 8: 0 2 3 5 9 10 11 12; 9: 7 8
10 11; 10: 7 8 9 11; 11: 7 8 9 10; 12: 1 2 3 6 7 8}

### Adjacency lists of 4-vertex-critical $(P_{5},\overline{P_{3}+P_{2}})$-free
graphs

  1. 1.

{0: 1 2 3; 1: 0 2 3; 2: 0 1 3; 3: 0 1 2}

  2. 2.

{0: 1 4 5; 1: 0 2 5; 2: 1 3 5; 3: 2 4 5; 4: 0 3 5; 5: 0 1 2 3 4}

  3. 3.

{0: 1 4 5; 1: 0 2 5 6; 2: 1 3 6; 3: 2 4 6; 4: 0 3 5; 5: 0 1 4; 6: 1 2 3}

  4. 4.

{0: 1 4 5 6; 1: 0 2 5 6; 2: 1 3 5; 3: 2 4 6; 4: 0 3 5; 5: 0 1 2 4; 6: 0 1 3}

  5. 5.

{0: 1 4 5 6; 1: 0 2 5 6; 2: 1 3 5 6; 3: 2 4 6; 4: 0 3 5; 5: 0 1 2 4; 6: 0 1 2
3}

  6. 6.

{0: 1 4 5 6; 1: 0 2 5 6; 2: 1 3 6; 3: 2 4 6; 4: 0 3 5; 5: 0 1 4; 6: 0 1 2 3}

### Adjacency lists of 5-vertex-critical $(P_{5},\overline{P_{3}+P_{2}})$-free
graphs

  1. 1.

{0: 1 2 3 4; 1: 0 2 3 4; 2: 0 1 3 4; 3: 0 1 2 4; 4: 0 1 2 3}

  2. 2.

{0: 1 4 5 6; 1: 0 2 5 6; 2: 1 3 5 6; 3: 2 4 5 6; 4: 0 3 5 6; 5: 0 1 2 3 4 6;
6: 0 1 2 3 4 5}

  3. 3.

{0: 1 4 5 6 7; 1: 0 2 5 6 7; 2: 1 3 5 7; 3: 2 4 6 7; 4: 0 3 5 7; 5: 0 1 2 4 7;
6: 0 1 3 7; 7: 0 1 2 3 4 5 6}

  4. 4.

{0: 1 4 5 6 7; 1: 0 2 5 6 7; 2: 1 3 6 7; 3: 2 4 6 7; 4: 0 3 5 6; 5: 0 1 4 6;
6: 0 1 2 3 4 5 7; 7: 0 1 2 3 6}

  5. 5.

{0: 1 4 5 6 7; 1: 0 2 5 6 7; 2: 1 3 5 6 7; 3: 2 4 6 7; 4: 0 3 5 7; 5: 0 1 2 4
7; 6: 0 1 2 3 7; 7: 0 1 2 3 4 5 6}

  6. 6.

{0: 1 4 5 6; 1: 0 2 5 6 7; 2: 1 3 6 7; 3: 2 4 6 7; 4: 0 3 5 6; 5: 0 1 4 6; 6:
0 1 2 3 4 5 7; 7: 1 2 3 6}

  7. 7.

{0: 1 4 5 6; 1: 0 2 5 6 7 8; 2: 1 3 7 8; 3: 2 4 7 8; 4: 0 3 5 6; 5: 0 1 4 6;
6: 0 1 4 5; 7: 1 2 3 8; 8: 1 2 3 7}

  8. 8.

{0: 1 4 5 6 7 8; 1: 0 2 5 6 7 8; 2: 1 3 6 7; 3: 2 4 7 8; 4: 0 3 5 6 8; 5: 0 1
4 6 8; 6: 0 1 2 4 5; 7: 0 1 2 3 8; 8: 0 1 3 4 5 7}

  9. 9.

{0: 1 4 5 6 7 8; 1: 0 2 5 6 7; 2: 1 3 5 6 8; 3: 2 4 6 7 8; 4: 0 3 5 7 8; 5: 0
1 2 4 8; 6: 0 1 2 3 7 8; 7: 0 1 3 4 6; 8: 0 2 3 4 5 6}

  10. 10.

{0: 1 4 5 6; 1: 0 2 5 6; 2: 1 3 6 7 8; 3: 2 4 7 8; 4: 0 3 5 7 8; 5: 0 1 4 6;
6: 0 1 2 5; 7: 2 3 4 8; 8: 2 3 4 7}

  11. 11.

{0: 1 4 5 6 7; 1: 0 2 5 6 8; 2: 1 3 6 8; 3: 2 4 7 8; 4: 0 3 5 7; 5: 0 1 4 6 7;
6: 0 1 2 5 8; 7: 0 3 4 5; 8: 1 2 3 6}

  12. 12.

{0: 1 4 5 6 7; 1: 0 2 5 6 7; 2: 1 3 6 7 8; 3: 2 4 7 8; 4: 0 3 5 7 8; 5: 0 1 4
6 8; 6: 0 1 2 5 8; 7: 0 1 2 3 4; 8: 2 3 4 5 6}

  13. 13.

{0: 1 4 5 6 7; 1: 0 2 5 6 7; 2: 1 3 6 7 8; 3: 2 4 7 8; 4: 0 3 5 7 8; 5: 0 1 4
6; 6: 0 1 2 5; 7: 0 1 2 3 4 8; 8: 2 3 4 7}

  14. 14.

{0: 1 4 5 6 7 8; 1: 0 2 5 6 7; 2: 1 3 6 7; 3: 2 4 7 8; 4: 0 3 5 7 8; 5: 0 1 4
6 8; 6: 0 1 2 5 8; 7: 0 1 2 3 4; 8: 0 3 4 5 6}

  15. 15.

{0: 1 4 5 6 7 8; 1: 0 2 5 6 7; 2: 1 3 6 7 8; 3: 2 4 7 8; 4: 0 3 5 7 8; 5: 0 1
4 6; 6: 0 1 2 5 8; 7: 0 1 2 3 4 8; 8: 0 2 3 4 6 7}

  16. 16.

{0: 1 4 5 6 7 8; 1: 0 2 5 6 7 8; 2: 1 3 6 7 8; 3: 2 4 7 8; 4: 0 3 5 7; 5: 0 1
4 6; 6: 0 1 2 5 8; 7: 0 1 2 3 4 8; 8: 0 1 2 3 6 7}

  17. 17.

{0: 1 4 5 6 7; 1: 0 2 5 6 7 8; 2: 1 3 6 7 8; 3: 2 4 7 8; 4: 0 3 5 6; 5: 0 1 4
6; 6: 0 1 2 4 5; 7: 0 1 2 3 8; 8: 1 2 3 7}

  18. 18.

{0: 1 4 5 6 7; 1: 0 2 5 6 7 8; 2: 1 3 6 7 8; 3: 2 4 7 8; 4: 0 3 5 6; 5: 0 1 4
6 8; 6: 0 1 2 4 5; 7: 0 1 2 3 8; 8: 1 2 3 5 7}

  19. 19.

{0: 1 4 5 6 8; 1: 0 2 5 6 7 8; 2: 1 3 6 7; 3: 2 4 6 7; 4: 0 3 5 6 8; 5: 0 1 4
6 8; 6: 0 1 2 3 4 5; 7: 1 2 3 8; 8: 0 1 4 5 7}

  20. 20.

{0: 1 4 5 6; 1: 0 2 5 6 7 8; 2: 1 3 6 7 8; 3: 2 4 7 8; 4: 0 3 5 6; 5: 0 1 4 6;
6: 0 1 2 4 5; 7: 1 2 3 8; 8: 1 2 3 7}


# Thompson Sampling under Bernoulli Rewards with Local Differential Privacy

Bo Jiang  Tianchi Zhao  Ming Li

###### Abstract

This paper investigates the problem of regret minimization for multi-armed
bandit (MAB) problems with local differential privacy (LDP) guarantee. Given a
fixed privacy budget $\epsilon$, we consider three privatizing mechanisms
under Bernoulli scenario: linear, quadratic and exponential mechanisms. Under
each mechanism, we derive stochastic regret bound for Thompson Sampling
algorithm. Finally, we simulate to illustrate the convergence of different
mechanisms under different privacy budgets.

Machine Learning, ICML

##  1 Introduction

The multi-armed bandit (MAB) problem addresses the balancing of the trade-off
between exploration and exploitation and has been widely applied in many real-
world scenarios, from recommendation systems and information retrieval to
healthcare and finance. In the settings of a MAB model, there are $N$ arms
available to the agent, and each arm’s reward subjects to a particular
distribution with an unknown mean. At each time step, the agent selects one
arm. Then a reward is observed by the agent. The agent’s ultimate goal is to
gather as much cumulative reward as possible or minimize the total regret,
i.e., designing a strategy that can explore different arms and exploit well-
rewarded arm(s).

Nevertheless, personalized MAB implementations such as recommendation system
is a double-edged sword: the gained utility also comes with the risk of
privacy violation. Comparing to the offline learning models, online learning
methods directly interact with sensitive user data, e.g., user clicks or
purchasing history, and timely update the models to adjust their output, which
makes privacy an even more serious concern. For example, physicians want to
test the effect of different treatments, and he collects patients’ health
conditions after a certain treatment. However, one’s heart-beat data may
compromise one’s living routine, such as daily exercise time, sleeping time,
etc. Another example is stock recommendation. The system (agent) periodically
suggests different stocks (arms) to the user. After the suggestion, he wants
to learn the feedback about how many shares (can be 0) the user has bought.
However, directly revealing may leak the user’s buying power, personal
preference, and what kind of risks he is hedging against. In this paper, we
leverage privacy protection in the MAB problem, i.e., the MAB problem where
the observable reward at each time satisfies certain privacy constraints.

Among all the privacy notions, Differential Privacy(Dwork et al., 2006; Dwork,
2008) has been accepted as the de facto standard for quantifying privacy
leakage in the privacy community. The advantage of DP is that it provides a
rigorous privacy guarantee against the worst-case adversaries, and is amenable
for mechanism design. Recently, the local version of DP, local differential
privacy (LDP), has gained significant attention. The server/aggregator who
collects data is considered untrusted by the users, who perturb their data
before sending it to the server. LDP based mechanisms have been successfully
adopted by Google’s RAPPOR (Úlfar Erlingsson et al., 2014) for collecting web
browsing behavior, and Apple’s MacOS to identify popular emojis and media
preferences in Safari (Cormode et al., 2018; Team, ). LDP also enables a
variety of privacy-preserving mechanisms for both discrete and continuous-
valued data. Such as randomized response mechanism (Wang et al., 2017),
Laplacian mechanism (Dwork et al., 2006), Gaussian mechanism (Liu, 2019).

Non-private MAB problems have been studied for decades, among which, either
frequentist methods like UCB (Upper Confidence Bound) or Bayesian methods like
Thompson Sampling (Agrawal and Goyal, 2012) have been shown to achieve optimal
regret performance (up to constant factors). There is also a line of works
related to the regret bound of MAB algorithm (Auer et al., 2002). A privacy-
preserving MAB can be described as, in each round, a privatized/perturbed
version of the reward(s) is (are) observable, and each perturbed reward
satisfies certain privacy requirements. The earliest work that studied LDP
bandits is (Gajane et al., 2018), which proposed an LDP bandit algorithm that
works for arms with Bernoulli rewards. In (Basu et al., 2019), for bandits
with bounded rewards, a Laplace mechanism and a Bernoulli mechanism are
proposed, and corresponding UCB algorithms are developed. The upper and lower
bound are derived based on UCB algorithms. In (Wang et al., 2020), the
statistical regret bounds are derived under either DP or LDP for collaborative
LinUCB algorithm in the context of collaborative MAB. However, seldom of these
works try to derive theoretically regret bound for privacy-preserving Thompson
Sampling algorithm. The challenge is that TS is a Bayesian approach that
involves the posterior updating at the agent by observing the reward. However,
under the privacy-preserving framework, the observable reward is noisy, and
the posterior distribution is not fixed but depends on the concrete mechanism
(noisy distribution). In this paper, we consider different noisy models
providing LDP guarantees. Then under each mechanism, we derive the posterior
distribution and bound the corresponding probabilities causing the sub-optimal
selection. In this paper, for a given privacy budget for LDP, we derive upper
regret bounds for the Thompson Sampling algorithm.

Figure 1: System model for privacy-preserving MAB instantaneous rewards are
privatized independently.

The main contributions of this work are summarized as follows: 1). We propose
different privacy-preserving MAB mechanisms under Thompson Sampling satisfying
Local Differential Privacy; 2). We derive Cumulative Regret Bounds (CRB) for
these mechanisms; 3). Simulate with synthetic data to support our analysis and
compare the performance with $UCB$.

##  2 Model Setup and Problem Formulation

In this problem, we consider $N$ arms in the system, and each arm’s reward
$R\in\mathcal{R}$ follows a sub-Gaussian distribution with mean $\mu$. We use
$\mu_{i}$ to denote the mean value of $R^{i}$, where $i\in\\{1,2,...,N\\}$ is
the index of an arm. The agent, at each timestamp, selects one specific arm to
play. The selected arm and the corresponding reward at time $k$ are denoted as
$I_{k}\in\\{1,2,...,N\\}$ and $R_{k}$ respectively. Note that, in this
problem, we assume the user (all the arms belong to one user) wants to
cooperate with the agent to minimize the cumulative regret (in terms of TS
algorithm, help the agent better learn the mean value). On the other hand, the
user also wants each of his instantaneous reward’s privacy to be protected.
Therefore, the reward at each time is protected by a privacy-preserving
mechanism $M$ ($M$ is assumed to be time-invariant). We define different kinds
of privacy-preserving mechanisms later. Denote $Y_{k}\in\mathcal{Y}$ as the
privatized version of $R_{k}$, which is also the output of $M$. The agent,
after observing $Y_{k}$, can further update his belief state and the
corresponding strategy for the next time.

In this work, we investigate the Thompson Sampling algorithm, which is a very
classic algorithm for MAB problems. The algorithm can be summarized as
follows: The agent has an estimated reward distribution for each arm (usually
starting from a uniform distribution), denote $\hat{\mu}_{i}^{k}$ as the
estimated mean reward for arm $i$ at time $k$. At each time, he randomly
samples a reward for each arm from his estimated distribution and selects the
arm that has the maximal sampled reward. After each round, by observing
$Y_{k}$, he updates his belief state accordingly (the distribution of the
reward of the arm that just played).

To provide strict privacy protection to every instantaneous reward at each
time, we let $M$ satisfy $\epsilon$-LDP, which can be defined as, for any
$r,r^{\prime}\in\mathcal{R}$, $y\in\mathcal{Y}$:

$Pr(Y_{k}=y|R_{k}=r)\leq{e^{\epsilon}Pr(Y_{k}=y|R_{k}=r^{\prime})},$ (1)

where $\epsilon$ is the privacy budget, the smaller $\epsilon$, the stronger
privacy guarantee the mechanism provides. Note that the privacy-preserving
mechanism is protecting the privacy of each instantaneous reward (sampled from
a fixed distribution), not the distribution itself. On the contrary, TS
algorithm requires an estimation of the posterior distribution, which tries to
infer the data distribution by nature. From the privacy perspective, the
privacy leakage of each instantaneous reward is guaranteed to be upper bounded
by $\epsilon$, and the leakage of the distribution after observing $k$ samples
from the same arm is upper bounded by $k\epsilon$ by the composability of LDP.
The system model is depicted in Fig.1.

##  3 LDP-based Binomial Mechanisms

In this section, we first introduce three LDP-based Binomial privacy-
preserving mechanisms, including linear mechanism, quadratic mechanism, and
exponential mechanism. Then, we discuss how to implement these mechanisms into
the TS algorithm. In the following of this paper, we assume that the reward of
each arm is bounded, and the first arm $I_{1}$ is the optimal arm
($\mu_{1}=\max_{i}{\mu_{i}}$).

Bernoulli mechanism converts a bounded reward to a Bernoulli distributed one,
i.e., $Y_{k}=Bernoulli(p(r))$, where $p(r)$ denotes the probability that
$Y_{k}=1$ given the reward is $r$. Algorithm 1 shows the detail of the
algorithm for LDP based TS algorithm with Bernoulli mechanism.

Algorithm 1 TS-LDP-B (LDP TS algorithm with Bernoulli mechanism)

1: $S_{i}=0,F_{i}=0$

2: for $t=1,2,...,$ do

3: For each arm $i=1,\ldots,N$, sample $\theta_{i}(t)$ from the
Beta($S_{i}+1$,$F_{i}+1$) distribution

4: Play arm $i(t):=\arg\max\theta_{i}(t)$ and observe $Y_{t}$. ($Y_{t}$ is the
instance reward after performs Bernoulli privacy-preserving mechanisms)

5: if $Y_{t}=1$ then

6: $S_{i}=S_{i}+1$ ($S_{i}$ denotes the number of successes in the Bernoulli
trial)

7: else

8: $F_{i}=F_{i}+1$ ($F_{i}$ denotes the number of failures in the Bernoulli
trial)

9: end if

10: end for

Next, in the following theorem, we present the sufficient condition to satisfy
the $\epsilon$-LDP.

######  Theorem 1.

For a bounded Bernoulli mechanism, to satisfy $\epsilon$-LDP, the following
conditions must hold: (1) $p(0)\geq\frac{1}{e^{\epsilon}+1}$; (2)
$p(1)\leq\frac{e^{\epsilon}}{e^{\epsilon}+1}$; (3) $p(r)$ is monotonically
increasing.

In this paper, we consider three different probability functions under the
Bernoulli mechanism. Linear probability function, Quadratic probability
function, and Exponential probability function. Based on the sufficient
conditions described in Theorem 1, $p(r)$ for each mechanism are stated in the
following Corollary.

######  Corollary 1.

For linear probability function,
$p(r)=\frac{1}{1+e^{\epsilon}}[(e^{\epsilon}-1)r+1]$; For quadratic
probability function,
$p(r)=\frac{1}{1+e^{\epsilon}}[(e^{\epsilon}-1-b)r^{2}+br+1]$, where
$b\in[0,2(e^{\epsilon}-1)]$; For exponential probability function,
$p(r)=\frac{e^{\epsilon r}}{e^{\epsilon}+1}$.

(a) Regret bounds comparison for different $\epsilon$ TS algorithm under
linear mechanism

(b) Regret bounds comparison for different $\epsilon$ TS algorithm under
quadratic mechanism

(c) Regret bounds comparison for different $\epsilon$ TS algorithm under
exponential mechanism

(d) Regret bounds comparison for different $\epsilon$ UCB algorithm under
linear mechanism

(e) Regret bounds comparison for different $\epsilon$ UCB algorithm under
quadratic mechanism

(f) Regret bounds comparison for different $\epsilon$ UCB algorithm under
exponential mechanism

######  Remark 1.

It is worth noting that the non-linear probability functions are preferable to
the linear under certain circumstances. One scenario is that the mean rewards
of different arms are very close to each other, the non-linear probability
functions provide a better convergence rate compared to the linear model (it
discriminates the optimal arm faster than the linear model).

##  4 Cumulative Regret Bounds

Next, we derive CRB for TS-LDP-B, and we consider problem-dependent regret,
where the regret at each time $t$ depends on the distance between the mean
reward between arms $1$ and $i$;

###  4.1 Problem-dependent regret bound for linear probability function

The Problem-dependent regret bound for linear probability function is stated
in the following theorem with proof provided in Appendix A.

######  Theorem 2.

Given any non-zero $\Delta_{i}=\mu_{1}-\mu_{i}$, the cumulative regret for the
linear probability function is upper bounded by ($\epsilon>0$):

$(1+\gamma)^{2}\left(\frac{e^{\epsilon}+1}{e^{\epsilon}-1}\right)^{2}\left\\{\sum_{i\neq
i^{*}}\frac{\log(T)}{2\Delta_{i}}+O\left(\frac{N}{2\Delta_{min}}\right)\right\\}.$
(2)

Where $\Delta_{min}=\min_{i\in[N]}\Delta_{i}$, $\gamma\in(0,1)$ is a threshold
which helps to prove the regret bound.

Proof outline for Theorem 2: The basic idea to prove the algorithm is similar
to (Agrawal and Goyal, 2013). The difference of the proof for TS-LDP-B (linear
probability function) is that we change the term in the denominator (from
$d(\mu_{i},\mu_{1})$ to $\Delta_{i}$, which is based on the Pinsker’s
inequality). In this way, we can express how the Bernoulli mechanism affects
the regret bound.

Remark:  Note that, the regret bound of non-private TS is
$(1+\gamma)^{2}\left\\{\sum_{i\neq
i^{*}}\frac{log(T)}{2\Delta_{i}}+O(\frac{N}{2\Delta_{min}})\right\\}$, wherein
we change the denominator from $d(\mu_{i},\mu_{1})$ to $\Delta_{i}$ (loose
version of the regret bound in (Agrawal and Goyal, 2013)). Compared to non-
private TS, the regret has the term
$\left(\frac{e^{\epsilon}+1}{e^{\epsilon}-1}\right)^{2}$, which can be viewed
as the cost for preserving privacy. When $\epsilon$ approaches infinity, this
factor approaches 1, and the regret approaches that of the non-private
version. When $\epsilon$ approaches zero, the regret becomes $O(T)$.

###  4.2 Problem-dependent regret bound for non-linear probability function

The Problem-dependent regret bound for the non-linear probability function is
stated in the following Theorem with proof provided in Appendix B and C.

######  Theorem 3.

Given any non-zero $\Delta_{i}=\mu_{1}-\mu_{i}$, the cumulative regret for the
non-linear probability function is upper bounded by ($\epsilon>0$):

$(1+\gamma)^{2}\sum_{i\neq
1}\frac{\log(T)+1}{2\Delta_{i,\epsilon}^{2}}\Delta_{i}+O(N),$ (3)

where $\Delta_{i,\epsilon}$ is the noisy difference between optimal arm and
selected arm $i$.

Proof outline for Theorem 3: The proof structure of the non-linear probability
function follows the similar idea of the linear probability function by
changing the linear probability function to a non-linear probability function.

Remark: We can apply quadratic probability function and exponential
probability function into (3). In quadratic probability function,
$\Delta_{i,\epsilon}=\mu_{1,\epsilon,quad}-\mu_{i,\epsilon,quad}=\frac{\\{(e^{\epsilon}-1-b)(\mu_{1}+\mu_{i})+b\\}(\mu_{1}-\mu_{i})+(e^{\epsilon}-1-b)(\sigma_{1}^{2}-\sigma_{i}^{2})}{e^{\epsilon}+1}$,
$\mu_{i,\epsilon,quad}$ is the expected mean value of arm $i$ after performs
quadratic probability function and $\sigma_{i}$ is arm $i$’s reward variance.
we can see that it reduces to (2) when $e^{\epsilon}-1-b=0$. This result
conforms to our expectation because the linear probability function is a
special case for the quadratic probability function. In exponential
probability function,
$\Delta_{i,\epsilon,exp}=\mu_{1,\epsilon,exp}-\mu_{i,\epsilon,exp}=\frac{e^{\epsilon\mu_{i}}(e^{\epsilon\Delta_{i}}-1)+\tau_{1}(\epsilon)-\tau_{i}(\epsilon)}{e^{\epsilon}+1}$,
$\mu_{i,\epsilon,exp}$ is the expected mean value of arm $i$ after performs
exponential probability function and $\tau_{i}(\epsilon)$ is the Jensen’s gap
between $e^{\epsilon\mu_{i}}$ and $E[e^{\epsilon r}]$. To make comparison with
TS-LDP-B, we also provide UCB-LDP-B under non-linear probability function. It
is,

$\displaystyle R(T)\leq\sum_{i\neq
1}\left\\{\frac{8\log(T)}{\Delta_{i,\epsilon}^{2}}+1+\frac{\pi^{2}}{3}\right\\}\Delta_{i}.$
(4)

Our analysis is based on Ren et al. (Ren et al., 2020) proof structure.
However, the difference between our algorithm and their algorithm (LDP-UCB-B
linear) is that we change the linear probability function to a non-linear
probability function.

##  5 NUMERICAL ANALYSIS

In this section, we illustrate the numerical results of our algorithms. Due to
computation limitations, we only present the results for bandits with the
Bernoulli mechanism. In the comparison, we compare LDP-TS-B studied in this
paper to that of LDP-UCB-B (Ren et al., 2020). We also include the performance
of the non-private UCB and TS algorithm ($\epsilon=\infty$) as a baseline to
see the cost for preserving $\epsilon$-LDP.

The numerical results are illustrated in Fig. 2. In each experiment, we set
the number of arms $N=20$. The optimal arm with a mean reward of $0.9$; five
arms with $0.8$; another five arms with $0.7$; another five arms with $0.6$;
the other four arms with $0.5$. We also let the rewards of arms follow
different types of distributions: arms with mean rewards of $0.9$ or $0.6$
generate rewards from Bernoulli distributions; arms with mean rewards of $0.8$
generate rewards from Beta$(4,1)$ distribution; arms with mean rewards of
$0.7$ generate rewards from $\\{0.4,1\\}$ uniformly at random; and arms with
mean rewards of $0.5$ generate rewards from $[0,1]$ uniformly at random.
Curves in each figure are averaged over 50 independent trials.

Fig. 2(a) and Fig. 2(d) show the effect of different $\epsilon$ under linear
model. We can see that the regret increases when $\epsilon$ decreases. This
result is consistent with our theoretical results. Small $\epsilon$ has much
more privacy, and the regret becomes large. Meanwhile, LDP-TS-B (linear) has
lower regret than LDP-UCB-B (linear) under the same $\epsilon$.

Fig. 2(b) and Fig. 2(e) show the effect of different $\epsilon$ under
quadratic model. Same to the linear model, We can see that the regret
increases when $\epsilon$ decreases, and LDP-TS-B (quadratic) has lower regret
than LDP-UCB-B (quadratic) under the same $\epsilon$.

Fig. 2(c) and Fig. 2(f) show the effect of different $\epsilon$ under
exponential model. Similar to the previous observation, We can see that the
regret increases when $\epsilon$ decreases and LDP-TS-B (exponential) has
lower regret than LDP-UCB-B (exponential) under the same $\epsilon$.

##  6 Conclusion and Future Work

In this paper, we studied the Thompson Sampling algorithm with local
differential privacy guarantee. We consider three privatizing mechanisms under
the Bernoulli rewards and proved a regret upper bounds for the Thompson
Sampling algorithm. Numerical results also confirmed our theoretical results.
For future work, we are planning to derive a lower regret bound for general
mechanisms.

## References

  * Agrawal and Goyal [2012] Shipra Agrawal and Navin Goyal.  Analysis of thompson sampling for the multi-armed bandit problem.  volume 23 of _Proceedings of Machine Learning Research_ , pages 39.1–39.26, Edinburgh, Scotland, 25–27 Jun 2012. JMLR Workshop and Conference Proceedings.  URL http://proceedings.mlr.press/v23/agrawal12.html.
  * Agrawal and Goyal [2013] Shipra Agrawal and Navin Goyal.  Further optimal regret bounds for thompson sampling.  In _Artificial Intelligence and Statistics_ , pages 99–107, 2013\.
  * Auer et al. [2002] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine Learning_ , 47:235–256, 05 2002.  doi: 10.1023/A:1013689704352.
  * Basu et al. [2019] Debabrota Basu, Christos Dimitrakakis, and Aristide C. Y. Tossou.  Differential privacy for multi-armed bandits: What is it and what is its cost?  _CoRR_ , abs/1905.12298, 2019.  URL http://arxiv.org/abs/1905.12298.
  * Cormode et al. [2018] Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang.  Privacy at scale: Local differential privacy in practice.  In _Proceedings of the 2018 International Conference on Management of Data_ , SIGMOD ’18, pages 1655–1658, New York, NY, USA, 2018. ACM.  ISBN 978-1-4503-4703-7.  doi: 10.1145/3183713.3197390.  URL http://doi.acm.org/10.1145/3183713.3197390.
  * Dwork [2008] Cynthia Dwork.  Differential privacy: A survey of results.  In Manindra Agrawal, Dingzhu Du, and Zhenhua Duan, editors, _Theory and Applications of Models of Computation: 5th International Conference, TAMC_ , pages 1–19. 2008.  ISBN 978-3-540-79228-4.  doi: 10.1007/978-3-540-79228-4_1.  URL https://doi.org/10.1007/978-3-540-79228-4_1.
  * Dwork et al. [2006] Cynthia Dwork, Frank McSherry, and Kobbi Nissim.  Calibrating noise to sensitivity in private data analysis.  In _Theory of Cryptography: Third Theory of Cryptography Conference_ , pages 265–284. 2006.  ISBN 978-3-540-32732-5.  doi: 10.1007/11681878_14.  URL https://doi.org/10.1007/11681878_14.
  * Gajane et al. [2018] Pratik Gajane, Tanguy Urvoy, and Emilie Kaufmann.  Corrupt bandits for preserving local privacy.  volume 83 of _Proceedings of Machine Learning Research_ , pages 387–412. PMLR, 07–09 Apr 2018.  URL http://proceedings.mlr.press/v83/gajane18a.html.
  * Liu [2019] F. Liu.  Generalized gaussian mechanism for differential privacy.  _IEEE Transactions on Knowledge and Data Engineering_ , 31(4):747–756, 2019.
  * Ren et al. [2020] Wenbo Ren, Xingyu Zhou, Jia Liu, and Ness B Shroff.  Multi-armed bandits with local differential privacy.  _arXiv preprint arXiv:2007.03121_ , 2020.
  * [11] Differential Privacy Team.  Learning with privacy at scale.  _https: //machinelearning.apple.com/2017/12/06/ learning-with-privacy-at-scale.html_.
  * Wang et al. [2020] Huazheng Wang, Qian Zhao, Qingyun Wu, Shubham Chopra, Abhinav Khaitan, and Hongning Wang.  Global and local differential privacy for collaborative bandits.  In _Fourteenth ACM Conference on Recommender Systems_ , RecSys ’20, page 150–159, New York, NY, USA, 2020. Association for Computing Machinery.  ISBN 9781450375832.  doi: 10.1145/3383313.3412254.  URL https://doi.org/10.1145/3383313.3412254.
  * Wang et al. [2017] Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha.  Locally differentially private protocols for frequency estimation.  In _26th USENIX Security 17_ , pages 729–745. USENIX Association, 2017.  ISBN 978-1-931971-40-9.  URL https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/wang-tianhao.
  * Úlfar Erlingsson et al. [2014] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova.  Rappor: Randomized aggregatable privacy-preserving ordinal response.  In _Proceedings of the 21st ACM CCS_ , 2014.  URL https://arxiv.org/abs/1407.6981.

##  Appendix A Proof for Theorem 2

###### Proof.

The $\epsilon$-LDP of LDP-TS-B follows from the $\epsilon$-DP of CTB stated in
Lemma 5 [Ren et al., 2020].

Problem-dependent bound. According to Lemma 5 [Ren et al., 2020], for any arm
$i$, the private response generated by CTB$(i,\epsilon)$ follows the
Bernoulli$(\mu_{i,\epsilon})$ distribution, where [Ren et al., 2020]

$\displaystyle\mu_{i,\epsilon}:=\frac{1}{2}+\frac{(2\mu_{i}-1)(e^{\epsilon}-1)}{2(e^{\epsilon}+1)}$
(5)

We define $\mu_{\epsilon}^{*}=\max_{i\in[N]}\mu_{i,\epsilon}$

$\displaystyle\Delta_{i,\epsilon}:=\mu_{\epsilon}^{*}-\mu_{i,\epsilon}=\frac{e^{\epsilon}-1}{e^{\epsilon}+1}\Delta_{i}$
(6)

Next, we begin to derive regret of LDP-TS-B. The proof follows [Agrawal and
Goyal, 2013]. We fix a suboptimal arm $i\neq i^{*}$. Split according to
$\hat{\mu}_{i,\epsilon}(t)$ and $p_{i,t}$

$\displaystyle E[N_{i}(T)]=\sum_{t=1}^{T}Pr(I_{t}=i)$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\\{Pr(I_{t}=i,\hat{\mu}_{i,\epsilon}(t)>x_{i})$
$\displaystyle+$ $\displaystyle Pr(I_{t}=i,\hat{\mu}_{i,\epsilon}(t)\leq
x_{i},p_{i,t}\geq y_{i})$ $\displaystyle+$ $\displaystyle
Pr(I_{t}=i,\hat{\mu}_{i,\epsilon}(t)\leq x_{i},p_{i,t}\leq y_{i})\\},$

Where we choose $\mu_{i,\epsilon}<x_{i}<y_{i}<\mu_{\epsilon}^{*}$ as follows

$\displaystyle\mu_{i,\epsilon}<x_{i}<\mu_{\epsilon}^{*}\quad s.t.\quad
d(x_{i},\mu_{\epsilon}^{*})=\frac{d(\mu_{i,\epsilon},\mu_{\epsilon}^{*})}{1+\gamma}$
(7) $\displaystyle x_{i}<y_{i}<\mu_{\epsilon}^{*}\quad s.t.\quad
d(x_{i},y_{i})=\frac{d(x_{i},\mu_{\epsilon}^{*})}{1+\gamma}=\frac{d(\mu_{i,\epsilon},\mu_{\epsilon}^{*})}{(1+\gamma)^{2}}.$

Where $0<\gamma<1$. Eq. LABEL:eq:32 ensures that the relevant divergences are
only a constant factor different from
$d(\mu_{i,\epsilon},\mu_{\epsilon}^{*})$.

For the first probability: denote $\tau_{i,k}$ as the k-th time when
$I_{t}=i$, then

$\displaystyle\sum_{t=1}^{T}Pr(I_{t}=i,\hat{\mu}_{i,\epsilon}(t)>x_{i})$
$\displaystyle\leq$ $\displaystyle
1+E\sum_{k=1}^{T-1}\mathbbm{1}\left[\hat{\mu}_{i,\epsilon}(t)>x_{i}\right]$
$\displaystyle\leq$ $\displaystyle
1+\sum_{k=1}^{T-1}exp\left(-kd(x_{i},\mu_{i,\epsilon})\right)$
$\displaystyle\leq$ $\displaystyle
1+\frac{1}{d(x_{i},\mu_{i,\epsilon})}\stackrel{{\scriptstyle(a)}}{{\leq}}1+\frac{1}{d(x_{i},y_{i})}$
$\displaystyle\leq$ $\displaystyle
1+(1+\gamma)^{2}\frac{1}{d(\mu_{i,\epsilon},\mu_{\epsilon}^{*})}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$ $\displaystyle
1+(1+\gamma)^{2}\frac{1}{2(\mu_{i,\epsilon}-\mu_{\epsilon}^{*})^{2}},$

Inequality (a) is based on the fact that divergence is monotonically
increasing function under $y_{i}>x_{i}$ when we fix $x_{i}$. Inequality (b) is
based on the Pinsker’s inequality.

For the second probability:

$\displaystyle\sum_{t=1}^{T}Pr(I_{t}=i,\hat{\mu}_{i,\epsilon}(t)\leq
x_{i},p_{i,t}\geq y_{i})$ $\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T}Pr(I_{t}=i,p_{i,t}\geq
y_{i}|\hat{\mu}_{i,\epsilon}(t)\leq x_{i})$ $\displaystyle\leq$ $\displaystyle
m+\sum_{t=\tau_{i,m}+1}^{T}Pr(I_{t}=i,p_{i,t}\geq
y_{i}|\hat{\mu}_{i,\epsilon}(t)\leq x_{i}),$

where we choose $m=\frac{log(T)}{d(x_{i},y_{i})}$ so that

$\displaystyle\sum_{t=1}^{T}Pr(I_{t}=i,\hat{\mu}_{i,\epsilon}(t)\leq
x_{i},p_{i,t}\geq y_{i})$ (8) $\displaystyle\leq$ $\displaystyle
m+\sum_{t=\tau_{i,m}+1}^{T}Pr(I_{t}=i,p_{i,t}\geq
y_{i}|\hat{\mu}_{i,\epsilon}(t)\leq x_{i})$ $\displaystyle\leq$ $\displaystyle
m+E\left\\{\sum_{t=\tau_{i,m}+1}^{T}exp(-N_{i}(t)d(x_{i},y_{i}))\right\\}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\frac{\log(T)}{d(x_{i},y_{i})}+E\left\\{\sum_{t=\tau_{i,m}+1}^{T}\frac{1}{T}\right\\}$
$\displaystyle\leq$ $\displaystyle\frac{\log(T)}{d(x_{i},y_{i})}+1\leq
1+(1+\gamma)^{2}\frac{\log(T)}{d(\mu_{i,\epsilon},\mu_{\epsilon}^{*})}$
$\displaystyle\leq$ $\displaystyle
1+(1+\gamma)^{2}\frac{\log(T)}{2(\mu_{i,\epsilon}-\mu_{\epsilon}^{*})^{2}}.$

Inequality (a) is based on the fact that
$exp(-N_{i}(t)d(x_{i},y_{i}))\leq\frac{1}{T}$ when
$t\geq\frac{log(T)}{d(x_{i},y_{i})}$.

For the third probability, according to [Agrawal and Goyal, 2013], we have:

$\displaystyle\sum_{t=1}^{T}Pr(I_{t}=i,\hat{\mu}_{i,\epsilon}(t)\leq
x_{i},p_{i,t}\leq y_{i})=O(1).$ (9)

Combining, we get:

$\displaystyle
E[N_{i}(T)]\leq(1+\gamma)^{2}\frac{\log(T)}{2(\mu_{i,\epsilon}-\mu_{\epsilon}^{*})^{2}}+(1+\gamma)^{2}\frac{1}{2(\mu_{i,\epsilon}-\mu_{\epsilon}^{*})^{2}}$
(10) $\displaystyle+$ $\displaystyle O(1),$

The regret is

$\displaystyle
R(T)\leq(1+\gamma)^{2}(\frac{e^{\epsilon}+1}{e^{\epsilon}-1})^{2}\left\\{\sum_{i\neq
i^{*}}\frac{\log(T)}{2\Delta_{i}}+O(\frac{N}{2\Delta_{min}})\right\\},$ (11)

∎

##  Appendix B Proof for Theorem 3 under quadratic probability function

###### Proof.

Problem-dependent bound. Assumption, each arm $i$’s reward variance is
$\sigma_{i}$.

$\displaystyle\mu_{i,\epsilon}:=\frac{(\mu_{i}^{2}+\sigma_{i}^{2})(e^{\epsilon}-1-b)+b\mu_{i}+1}{e^{\epsilon}+1}$
(12)

We define $\mu_{\epsilon}^{*}=\max_{i\in[N]}\mu_{i,\epsilon}$

$\displaystyle\Delta_{i,\epsilon}:=\mu_{\epsilon}^{*}-\mu_{i,\epsilon}=$ (13)
$\displaystyle\frac{\\{(e^{\epsilon}-1-b)(\mu_{1}+\mu_{i})+b\\}(\mu_{1}-\mu_{i})+(e^{\epsilon}-1-b)(\sigma_{1}^{2}-\sigma_{i}^{2})}{e^{\epsilon}+1}$

We put the Eq. 13 value into Eq. LABEL:eq:35 The regret is

$\displaystyle R(T)\leq(1+\gamma)^{2}\sum_{i\neq
i^{*}}\frac{\log(T)}{2\Delta_{i,\epsilon}^{2}}\Delta_{i}+$ (14)
$\displaystyle(1+\gamma)^{2}\sum_{i\neq
i^{*}}\frac{1}{2\Delta_{i,\epsilon}^{2}}\Delta_{i}+O(N)$ $\displaystyle=$
$\displaystyle(1+\gamma)^{2}\sum_{i\neq
i^{*}}\frac{\log(T)+1}{2\left(\frac{\\{(e^{\epsilon}-1-b)(\mu_{1}+\mu_{i})+b\\}(\mu_{1}-\mu_{i})+(e^{\epsilon}-1-b)(\sigma_{1}^{2}-\sigma_{i}^{2})}{e^{\epsilon}+1}\right)^{2}}$
$\displaystyle\Delta_{i}+O(N),$

To prove the regret of UCB version, we use the expected time of sub-optimal
arm in A.4 in [Ren et al., 2020].

$\displaystyle
E[N_{i}(T)]\leq\frac{8\log(T)}{\Delta_{i,\epsilon}^{2}}+1+\frac{\pi^{2}}{3},$
(15)

Then, the regret of UCB algorithm

$\displaystyle R(T)\leq\sum_{i\neq
i^{*}}\\{\frac{8\log(T)}{\left(\frac{\\{(e^{\epsilon}-1-b)(\mu_{1}+\mu_{i})+b\\}(\mu_{1}-\mu_{i})+(e^{\epsilon}-1-b)(\sigma_{1}^{2}-\sigma_{i}^{2})}{e^{\epsilon}+1}\right)^{2}}$
(16) $\displaystyle+1+\frac{\pi^{2}}{3}\\}\Delta_{i},$

and if we assume all the arm i has same variance $\sigma$:

$\displaystyle\Delta_{i,\epsilon}:=\mu_{\epsilon}^{*}-\mu_{i,\epsilon}=\frac{(e^{\epsilon}-1-b)(\mu_{1}+\mu_{i})+b}{e^{\epsilon}+1}\Delta_{i}$
(17)

We put the Eq. 17 value into Eq. LABEL:eq:35 The regret is

$\displaystyle R(T)\leq(1+\gamma)^{2}\sum_{i\neq
i^{*}}\frac{\log(T)}{2\Delta_{i,\epsilon}^{2}}\Delta_{i}+(1+\gamma)^{2}\sum_{i\neq
i^{*}}\frac{1}{2\Delta_{i,\epsilon}^{2}}\Delta_{i}$ (18)
$\displaystyle+O(N)=(1+\gamma)^{2}\sum_{i\neq
i^{*}}\frac{\log(T)+1}{2(\frac{(e^{\epsilon}-1-b)(\mu_{i^{*}}+\mu_{i})+b}{e^{\epsilon}+1})^{2}\Delta_{i}^{2}}\Delta_{i}$
$\displaystyle+O(N)\leq(1+\gamma)^{2}(\frac{e^{\epsilon}+1}{(e^{\epsilon}-1-b)\mu_{i^{*}}+b})^{2}\sum_{i\neq
i^{*}}\frac{\log(T)+1}{2\Delta_{i}}$ $\displaystyle+O(N),$

To prove the regret of UCB version, we use the expected time of sub-optimal
arm in A.4 in [Ren et al., 2020].

$\displaystyle
E[N_{i}(T)]\leq\frac{8\log(T)}{\Delta_{i,\epsilon}^{2}}+1+\frac{\pi^{2}}{3},$
(19)

Then, the regret of UCB algorithm

$\displaystyle
R(T)\leq(\frac{e^{\epsilon}+1}{(e^{\epsilon}-1-b)\mu_{i^{*}}+b})^{2}\sum_{i\neq
i^{*}}\frac{8\log(T)}{\Delta_{i}}+$ (20) $\displaystyle\sum_{i\neq
i^{*}}(1+\frac{\pi^{2}}{3})\Delta_{i},$

We assume all the arm’s reward satisfies Bernoulli distribution, the variance
of arm $i$ is $(1-\mu_{i})\mu_{i}$, then the instance regret is

$\displaystyle\Delta_{i,\epsilon}:=\mu_{\epsilon}^{*}-\mu_{i,\epsilon}$ (21)
$\displaystyle=\frac{(e^{\epsilon}-1-b)(\mu_{1}^{2}-\mu_{i}^{2}+\sigma_{1}^{2}-\sigma_{i}^{2})+b(\mu_{1}-\mu_{i})}{e^{\epsilon}+1}$
$\displaystyle=$
$\displaystyle\frac{(e^{\epsilon}-1-b)\left(\mu_{1}^{2}-\mu_{i}^{2}+\mu_{1}(1-\mu_{1})-\mu_{i}(1-\mu_{i})\right)+b(\mu_{1}-\mu_{i})}{e^{\epsilon}+1}$
$\displaystyle=$
$\displaystyle\frac{(e^{\epsilon}-1-b)(\mu_{1}-\mu_{i})+b(\mu_{1}-\mu_{i})}{e^{\epsilon}+1}=\frac{e^{\epsilon}-1}{e^{\epsilon}+1}(\mu_{1}-\mu_{i})$
$\displaystyle=\frac{e^{\epsilon}-1}{e^{\epsilon}+1}\Delta_{i}$

∎

##  Appendix C Proof for Theorem 3 under exponential probability function

###### Proof.

Problem-dependent bound.

$\displaystyle\mu_{i,\epsilon}:=\frac{E[e^{\epsilon
r}]}{e^{\epsilon}+1}=\frac{e^{\epsilon\mu_{i}}+\tau_{i}(\epsilon)}{e^{\epsilon}+1}$
(22)

Where Eq. 22 is based on the Jensen’s inequality ($e^{\epsilon\mu_{i}}\leq
E[e^{\epsilon r}]$). We define $\tau_{i}(\epsilon)$ as the Jensen’s gap
between $e^{\epsilon\mu_{i}}$ and $E[e^{\epsilon r}]$. Then,

$\displaystyle\Delta_{i,\epsilon}:=\mu_{\epsilon}^{*}-\mu_{i,\epsilon}=\frac{e^{\epsilon\mu_{1}}-e^{\epsilon\mu_{i}}+\tau_{1}(\epsilon)-\tau_{i}(\epsilon)}{e^{\epsilon}+1}$
(23)
$\displaystyle=\frac{e^{\epsilon(\Delta_{i}+\mu_{i})}-e^{\epsilon\mu_{i}}+\tau_{1}(\epsilon)-\tau_{i}(\epsilon)}{e^{\epsilon}+1}$
$\displaystyle=$
$\displaystyle\frac{e^{\epsilon\mu_{i}}(e^{\epsilon\Delta_{i}}-1)+\tau_{1}(\epsilon)-\tau_{i}(\epsilon)}{e^{\epsilon}+1}$

We put the Eq. 23 value into Eq. LABEL:eq:35 The regret is

$\displaystyle R(T)\leq(1+\gamma)^{2}\sum_{i\neq
i^{*}}\frac{\log(T)}{2\Delta_{i,\epsilon}^{2}}\Delta_{i}+(1+\gamma)^{2}\sum_{i\neq
i^{*}}\frac{1}{2\Delta_{i,\epsilon}^{2}}\Delta_{i}$ (24)
$\displaystyle+O(N)=(1+\gamma)^{2}\sum_{i\neq
i^{*}}\frac{\log(T)+1}{2(\frac{e^{\epsilon\mu_{i}}(e^{\epsilon\Delta_{i}}-1)+\tau_{1}(\epsilon)-\tau_{i}(\epsilon)}{e^{\epsilon}+1})^{2}}\Delta_{i}$
$\displaystyle+O(N),$

Similarly, the regret of UCB algorithm

$\displaystyle R(T)\leq\sum_{i\neq
i^{*}}\left\\{\frac{8\log(T)}{(\frac{e^{\epsilon\mu_{i}}(e^{\epsilon\Delta_{i}}-1)+\tau_{1}(\epsilon)-\tau_{i}(\epsilon)}{e^{\epsilon}+1})^{2}}+1+\frac{\pi^{2}}{3}\right\\}\Delta_{i},$
(25)

∎