# The RED-BLUE SEPARATION problem on graphs††thanks: This study has been
carried out in the frame of the “Investments for the future” Programme IdEx
Bordeaux - SysNum (ANR-10-IDEX-03-02). Ralf Klasing’s research was partially
supported by the ANR project TEMPOGRAL (ANR-22-CE48-0001). Florent Foucaud was
partially financed by the IFCAM project “Applications of graph homomorphisms”
(MA/IFCAM/18/39), the ANR project GRALMECO (ANR-21-CE48-0004) and the French
government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25). Tuomo Lehtilä’s
research was supported by the Finnish Cultural Foundation and by the Academy
of Finland grant 338797.

Subhadeep Ranjan Dev111ACM Unit, Indian Statistical Institute, Kolkata, India
Sanjana Dey 222National University of Singapore, Singapore 333Most of the work
of this author was done when she was in Indian Statistical Institute, Kolkata
Florent Foucaud444Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne,
Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France 555Univ. Orléans,
INSA Centre Val de Loire, LIFO EA 4022, F-45067 Orléans Cedex 2, France Ralf
Klasing666Université de Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR 5800,
Talence, France Tuomo Lehtilä777University of Turku, Department of Mathematics
and Statistics, Turku, Finland 888Most of the work of this author was done
when he was in Univ Lyon, Université Claude Bernard, CNRS, LIRIS - UMR 5205,
F69622, France

###### Abstract

We introduce the Red-Blue Separation problem on graphs, where we are given a
graph $G=(V,E)$ whose vertices are colored either red or blue, and we want to
select a (small) subset $S\subseteq V$, called _red-blue separating set_ ,
such that for every red-blue pair of vertices, there is a vertex $s\in S$
whose closed neighborhood contains exactly one of the two vertices of the
pair. We study the computational complexity of Red-Blue Separation, in which
one asks whether a given red-blue colored graph has a red-blue separating set
of size at most a given integer. We prove that the problem is NP-complete even
for restricted graph classes. We also show that it is always approximable in
polynomial time within a factor of $2\ln n$, where $n$ is the input graph’s
order. In contrast, for triangle-free graphs and for graphs of bounded maximum
degree, we show that Red-Blue Separation is solvable in polynomial time when
the size of the smaller color class is bounded by a constant. However, on
general graphs, we show that the problem is $W[2]$-hard even when
parameterized by the solution size plus the size of the smaller color class.
We also consider the problem Max Red-Blue Separation where the coloring is not
part of the input. Here, given an input graph $G$, we want to determine the
smallest integer $k$ such that, _for every possible red-blue coloring_ of $G$,
there is a red-blue separating set of size at most $k$. We derive tight bounds
on the cardinality of an optimal solution of Max Red-Blue Separation, showing
that it can range from logarithmic in the graph order, up to the order minus
one. We also give bounds with respect to related parameters. For trees however
we prove an upper bound of two-thirds the order. We then show that Max Red-
Blue Separation is NP-hard, even for graphs of bounded maximum degree, but can
be approximated in polynomial time within a factor of $O(\ln^{2}n)$.

Keywords:  separating sets, dominating sets, identifying codes

##  1 Introduction

We introduce and study the Red-Blue Separation problem for graphs. Separation
problems for discrete structures have been studied extensively from various
perspectives. In the 1960s, Rényi [28] introduced the Separation problem for
set systems (a set system is a collection of sets over a set of vertices),
which has been rediscovered by various authors in different contexts, see e.g.
[2, 6, 21, 27]. In this problem, one aims at selecting a solution subset
$\mathcal{S}$ of sets from the input set system to separate every pair of
vertices, in the sense that the subset of $\mathcal{S}$ corresponding to those
sets to which each vertex belongs to, is unique. The graph version of this
problem (where the sets of the input set system are the closed neighborhoods
of a graph), called Identifying Code [22], is also extensively studied. These
problems have numerous applications in areas such as monitoring and fault-
detection in networks [30], biological testing [27], and machine learning
[24]. The Red-Blue Separation problem which we study here is a red-blue
colored version of Separation, where instead of all pairs we only need to
separate red vertices from blue vertices.

In the general version of the Red-Blue Separation problem, one is given a set
system $(V,\mathcal{S})$ consisting of a set $\mathcal{S}$ of subsets of a set
$V$ of vertices which are either blue or red; one wishes to separate every
blue from every red vertex using a solution subset $\mathcal{C}$ of
$\mathcal{S}$ (here a set of $\mathcal{C}$ separates two vertices if it
contains exactly one of them). Motivated by machine learning applications, a
geometric-based special case of Red-Blue Separation has been studied in the
literature, where the vertices of $V$ are points in the plane and the sets of
$\mathcal{S}$ are half-planes [7]. The classic problem Set Cover over set
systems generalizes both Geometric Set Cover problems and graph problem
Dominating Set (similarly, the set system problem Separation generalizes both
Geometric Discriminating Code and the graph problem Identifying Code). It thus
seems natural to study the graph version of Red-Blue Separation.

#### Problem definition.

In the graph setting, we are given a graph $G$ and a red-blue coloring
$c:V(G)\to\\{\text{red},\text{blue}\\}$ of its vertices, and we want to select
a (small) subset $S$ of vertices, called _red-blue separating set_ , such that
for every red-blue pair $r,b$ of vertices, there is a vertex from $S$ whose
closed neighborhood contains exactly one of $r$ and $b$. Equivalently,
$N[r]\cap S\neq N[b]\cap S$, where $N[x]$ denotes the closed neighborhood of
vertex $x$; the set $N[x]\cap S$ is called the _code_ of $x$ (with respect to
$S$), and thus all codes of blue vertices are different from all codes of red
vertices. The smallest size of a red-blue separating set of $(G,c)$ is denoted
by $\operatorname{sep_{RB}}(G,c)$. Note that if a red and a blue vertex have
the same closed neighborhood, they cannot be separated. Thus, for simplicity,
we will consider only _twin-free_ graphs, that is, graphs where no two
vertices have the same closed neighborhood. Also, for a twin-free graph, the
vertex set $V(G)$ is always a red-blue separating set as all the vertices have
a unique subset of neighbors. We have the following associated computational
problem.

Red-Blue Separation Input: A red-blue colored twin-free graph $(G,c)$ and an
integer $k$. Question: Do we have $\operatorname{sep_{RB}}(G,c)\leq k$?
---

It is also interesting to study the problem when the red-blue coloring is not
part of the input. For a given graph $G$, we thus define the parameter
$\operatorname{max-sep_{RB}}(G)$ which denotes the largest size, over each
possible red-blue coloring $c$ of $G$, of a smallest red-blue separating set
of $(G,c)$. The associated decision problem is stated as follows.

Max Red-Blue Separation Input: A twin-free graph $G$ and an integer $k$.
Question: Do we have $\operatorname{max-sep_{RB}}(G)\leq k$?
---

In Figure 1, to note the difference between $\operatorname{sep_{RB}}$ and
$\operatorname{max-sep_{RB}}$, a path of 6 vertices $P_{6}$ is shown, where
the vertices are colored red or blue.

Figure 1: A path of 6 vertices where (a) $\operatorname{sep_{RB}}(P_{6},c)=1$
and (b) $\operatorname{max-sep_{RB}}(P_{6})=3$. The square vertices are blue,
the round ones are red; the members of the red-blue separating set are
circled.

#### Our results.

We show that Red-Blue Separation is NP-complete even for restricted graph
classes such as planar bipartite sub-cubic graphs, in the setting where the
two color classes111One class consists of vertices colored _red_ and the other
class consists of vertices colored _blue_. have equal size. We also show that
the problem is NP-hard to approximate within a factor of $(1-\epsilon)\ln n$
for every $\epsilon>0$, even for split graphs222A graph $G=(V,E)$ is called a
_split graph_ when the vertices in $V$ can be be partitioned into an
independent set and a clique. of order $n$, and when one color class has size
$1$. On the other hand, we show that Red-Blue Separation is always
approximable in polynomial time within a factor of $2\ln n$. In contrast, for
triangle-free graphs and for graphs of bounded maximum degree, we prove that
Red-Blue Separation is solvable in polynomial time when the smaller color
class is bounded by a constant (using algorithms that are in the parameterized
class XP, with the size of the smaller color class as parameter). However, on
general graphs, the problem is shown to be $W[2]$-hard even when parameterized
by the solution size plus the size of the smaller color class. (This is in
contrast with the geometric version of separating points by half-planes, for
which both parameterizations are known to be fixed-parameter tractable [3,
23].)

As the coloring is not specified, $\operatorname{max-sep_{RB}}(G)$ is a
parameter that is worth studying from a structural viewpoint. In particular,
we study the possible values for $\operatorname{max-sep_{RB}}(G)$. We show the
existence of tight bounds on $\operatorname{max-sep_{RB}}(G)$ in terms of the
order $n$ of the graph $G$, proving that it can range from
$\lfloor\log_{2}n\rfloor$ up to $n-1$ (both bounds are tight). For trees
however we prove bounds involving the number of support vertices (i.e. which
have a leaf neighbor), which imply that $\operatorname{max-
sep_{RB}}(G)\leq\frac{2n}{3}$. We also give bounds in terms of the (non-
colored) separation number. We then show that the associated decision problem
Max Red-Blue Separation is NP-hard, even for graphs of bounded maximum degree,
but can be approximated in polynomial time within a factor of $O(\ln^{2}n)$.

An extended abstract of this paper was presented in the conference IWOCA’22
and appeared in the proceedings as [9]. The present paper includes all the
proofs that were missing from the conference version.

#### Related work.

Red-Blue Separation has been studied in the geometric setting of red and blue
points in the Euclidean plane [3, 5, 26]. In this problem, one wishes to
select a small set of (axis-parallel) lines such that any two red and blue
points lie on the two sides of one of the solution lines. The motivation stems
from the Discretization problem for two classes and two features in machine
learning, where each point represents a data point whose coordinates
correspond to the values of the two features, and each color is a data class.
The problem is useful in a preprocessing step to transform the continuous
features into discrete ones, with the aim of classifying the data points [7,
23, 24]. This problem was shown to be NP-hard [7] but 2-approximable [5] and
fixed-parameter tractable when parameterized by the size of a smallest color
class [3] and by the solution size [23]. A polynomial time algorithm for a
special case was recently given in [26].

The Separation problem for set systems (also known as Test Cover and
Discriminating Code) was introduced in the 1960s [28] and widely studied from
a combinatorial point of view [1, 2, 6, 21] as well as from the algorithmic
perspective for the settings of classical, approximation and parameterized
algorithms [8, 11, 27]. The associated graph problem is called Identifying
Code [22] and is also extensively studied (see [25] for an online bibliography
with almost 500 references as of January 2022); geometric versions of
Separation have been studied as well [10, 17, 19]. The Separation problem is
also closely related to the VC Dimension problem [31] which is very important
in the context of machine learning. In VC Dimension, for a given set system
$(V,\mathcal{S})$, one is looking for a (large) set $X$ of vertices that is
_shattered_ , that is, for every possible subset of $X$, there is a set of
$\mathcal{S}$ whose trace on $X$ is the subset. This can be seen as ”perfectly
separating” a subset of $\mathcal{S}$ using $X$; see [4] for more details on
this connection.

#### Structure of the paper.

We start with the algorithmic results on Red-Blue Separation in Section 2. We
then present the bounds on $\operatorname{max-sep_{RB}}$ in Section 3 and the
hardness result for Max Red-Blue Separation in Section 4. We conclude in
Section 5.

##  2 Complexity and algorithms for Red-Blue Separation

We will prove some algorithmic results for Red-Blue Separation by reducing to
or from the following problems.

Set Cover Input: A set of elements $U$, a family $\mathcal{S}$ of subsets of
$U$ and an integer $k$. Question: Does their exist a cover
$\mathcal{C}\subseteq\mathcal{S}$, with $|\mathcal{C}|\leq k$ such that
$\bigcup_{C\in\mathcal{C}}C=U$?
---

Dominating Set Input: A graph $G=(V,E)$ and an integer $k$. Question: Does
there exist a set $D\subseteq V$ of size $k$ with $\forall v\in V,N[v]\cap
D\neq\emptyset$?
---

###  2.1 Hardness

######  Theorem 1.

Red-Blue Separation cannot be approximated within a factor of
$(1-\epsilon)\cdot\ln n$ for any $\epsilon>0$ even when the smallest color
class has size $1$ and the input is a split graph of order $n$, unless P = NP.
Moreover, Red-Blue Separation is W[2]-hard when parameterized by the solution
size together with the size of the smallest color class, even on split graphs.

###### Proof.

For an instance $((U,\mathcal{S}),k)$ of Set-Cover, we construct in polynomial
time an instance $((G,c),k)$ of Red-Blue Separation where $G$ is a split graph
and one color class has size 1. The statement will follow from the hardness of
approximating Min Set Cover proved in [12], and from the fact that Set Cover
is W[2]-hard when parameterized by the solution size [13].

We create the graph $(G,c)$ by first creating vertices corresponding to all
the sets and the elements. We connect a vertex $u_{i}$ corresponding to an
element $i\in U$ to a vertex $v_{j}$ corresponding to a set
$S_{j}\in\mathcal{S}$ if $u_{i}\in S_{j}$. We color all these vertices blue.
We add two isolated blue vertices $b$ and $b^{\prime}$. We connect all the
vertices of type $u_{i}\in U$ to each other. Also, we add a red vertex $r$ and
connect all vertices $u_{i}\in U$ to $r$. Now, note that the vertices
$U\cup\\{r\\}$ form a clique whereas the vertices $v_{j}$ along with $b$ and
$b^{\prime}$ form an independent set. Thus, our constructed graph $(G,c)$ with
the coloring $c$ is a split graph. See Figure 2.

Figure 2: Reduction from Set Cover to Red-Blue Separation of Theorem 1. Vertex
$r$ is red, the others are blue.

######  Claim 1.1.

$\mathcal{S}$ has a set cover of size $k$ if and only if $G$ has a red-blue
separating set of size at most $k+1$.

_Proof of claim._ Let $\mathcal{C}$ be a set cover of $(U,\mathcal{S})$ of
size $k$. We construct a red-blue separating set $S$ of $(G,c)$ of size at
most $k+1$ as follows. For each set $s_{j}\in\mathcal{S}$ selected in the set
cover $\mathcal{C}$, we choose the corresponding vertex $v_{j}$ in $S$. Also
include the vertex $r$ in $S$. Observe that some blue vertices may have the
empty code and the red vertex has itself as the code. Also, the vertices
$u_{i}$ are dominated by the vertices $v_{j}$ and have some unique code
different from $r$. Therefore, $S$ is a separating set of $(G,c)$ of size at
most $k+1$.

Conversely, consider a red-blue separating set $S$ of $(G,c)$ of size
$k^{\prime}$. Since the vertices $U\cup\\{r\\}$ form a clique, choosing any
vertex from this set will not separate any two vertices of the clique. Let us
assume that the red vertex $r$ of $(G,c)$ gets the empty code. But then, we
have the two isolated blue vertices, one of which also gets the empty code.
Thus, the red vertex has to be selected. But $r$, being part of the clique,
has to be separated from the blue vertices. Thus, we have to choose vertices
from the independent set to separate the blue vertices of the clique from $r$.
So, we dominate the blue vertices of the clique by using the vertices in the
independent set, which gives our set cover of size at most $k^{\prime}-1=k$.
($\Box$)
This completes the proof of the theorem. ∎

######  Theorem 2.

Red-Blue Separation is NP-hard for bipartite planar sub-cubic graphs of girth
at least 12 when the color classes have almost the same size.

###### Proof.

We reduce from Dominating Set, which is NP-hard for bipartite planar sub-cubic
graphs with girth at least 12 that contain some degree-2 vertices [32]. We
reduce any instance $(G,k)$ of Dominating Set to an instance
$((H,c),k^{\prime})$ of Red-Blue Separation, where $k^{\prime}=k+1$ and the
number of red and blue vertices in $c$ differ by at most 2.

Figure 3: Reduction from Dominating Set to Red-Blue Separation of Theorem 2.
Vertices $v_{B}$ and $u_{4}$ are blue, the others are red.

#### Construction.

We create two disjoint copies of $G$ namely $H_{B}$ and $H_{R}$ and color all
vertices of $H_{B}$ blue and all vertices of $H_{R}$ red. Select an arbitrary
vertex $v$ of degree 2 in $G$ (we may assume such a vertex exists in $G$ by
the reduction of [32]) and look at its corresponding vertices $v_{R}\in
V(H_{R})$ and $v_{B}\in V(H_{B})$. We connect $v_{R}$ and $v_{B}$ with the
head of the path $u_{1},u_{2},u_{3},u_{4}$ as shown in Figure 3. The tail of
the path, i.e. the vertex $u_{4}$, is colored blue and the remaining three
vertices $u_{1},u_{2}$ and $u_{3}$ are colored red. Our final graph $H$ is the
union of $H_{R},H_{B}$ and the path $u_{1},u_{2},u_{3},u_{4}$ and the coloring
$c$ as described. Note that if $G$ is a connected bipartite planar sub-cubic
graph of girth at least $g$, then so is $H$ (since $v$ was selected as a
vertex of degree 2). We make the following claim.

######  Claim 2.1.

The instance $(G,k)$ is a YES-instance of Dominating Set if and only if
$\operatorname{sep_{RB}}(H,c)\leq k^{\prime}=k+1$.

_Proof of claim._ $(\implies)$ Let $D$ be a dominating set of $G$ of size $k$.
We construct a red-blue separating set $S$ of $(H,c)$ of size at most $k+1$ as
follows. For each vertex in $D$, include its corresponding vertex in $H_{R}$
in $S$. Also include in $S$, the vertex $u_{2}\in V(H)$. Observe that all blue
vertices have the empty code and all red vertices have some non-empty code.
Therefore $S$ is a separating set of $(H,c)$ of size at most $k+1$.

$(\impliedby)$ Consider a red-blue separating set $S$ of $(H,c)$ of size
$k^{\prime}$. Let us assume that the red vertices of $(H,c)$ did not get the
empty code. The argument when the blue vertices do not get the empty code is
similar. Then, the set $S$ also dominates
$V(H_{R})\cup\\{u_{1},u_{2},u_{3}\\}$. Since $u_{3}$ can only be dominated by
a vertex $x$ in $\\{u_{2},u_{3},u_{4}\\}$, the vertices in $V(H_{R})$ are
dominated by $S^{\prime}=S\setminus\\{x\\}$. If $S^{\prime}=S^{\prime}\cap
V(H_{G})$ then the set $D$ formed by choosing the corresponding vertices of
$S^{\prime}$ in $G$ is a dominating set of size $k=k^{\prime}-1$. Otherwise,
$S^{\prime}\setminus\\{u_{1}\\}=S^{\prime}\cap V(H_{R})$, and the set $D$
formed by choosing the corresponding vertices of
$S^{\prime}\setminus\\{u_{1}\\}$ in $G$ is a dominating set of $G$ of size
$k=k^{\prime}-1$. ($\Box$)
This completes the proof of the theorem. ∎

In the previous reduction, we could choose any class of instances for which
Dominating Set is known to be NP-hard. We could also simply take two copies of
the original graph and obtain a coloring with two equal color class sizes (but
then we obtain a disconnected instance). In contrast, in the geometric
setting, the problem is fixed-parameter-tractable when parameterized by the
size of the smallest color class [3], and by the solution size [23]. It is
also 2-approximable [5].

We can also provide another reduction, as follows.

######  Theorem 3.

Red-Blue Separation is NP-hard even when the input is a subcubic planar
bipartite graph of girth at least 12 and the size of the smallest color class
is $k+1$.

###### Proof.

We reduce from Dominating Set.

Dominating Set is NP-hard when the input graph is a subcubic planar bipartite
graph of girth at least 12 [32]. We reduce an instance $(G,k)$ of the
Dominating Set to an instance $((H,c_{k+1}),k)$ of Red-Blue Separation where
$c_{k+1}$ is a coloring of $H$ with the minimum color class being of size at
most $k+1$.

Figure 4: Construction from an instance of Dominating Set to an instance of
Red-Blue Separation where size of the smaller color class is bounded. The
square vertices are blue, the round ones are red.

#### Construction.

Without loss of generality let us assume the smaller sized color class to be
red. For $H$ we create a copy $G_{H}$ of $G$ with all its vertices colored
blue and an independent set $I$ of size $k+1$ all its vertices colored red
vertices. We now make the following claim.

######  Claim 3.1.

$(G,k)$ is a YES-instance of Dominating Set if and only if $((H,c_{k+1}),k)$
is a YES-instance of Red-Blue Separation.

_Proof of claim._ ($\implies$) Let $D$ be a dominating set of $G$. We
construct a red-blue separating set of $(H,c_{k+1})$ by selecting the
corresponding vertices of $D$ in $G_{H}$. Since $D$ is a dominating set of
$G$, all blue vertices receive a non-empty code. The red vertices on the other
hand receive the empty code and we have a valid separating set.

($\impliedby$) Let $(H,c_{k+1})$ have a separating set $C$ of size at most
$k$. Since there are $k+1$ independent red vertices, there will be at least
one red vertex which receives the empty code. So, in order for $C$ to be a
valid separating set, all blue vertices must receive some non-empty code. This
implies that $C\cap V(G_{H})$ is a dominating set of $G_{H}$ of size at most
$k$ and which implies a dominating set of $G$ of size at most $k$. ($\Box$)

This completes the proof. ∎

###  2.2 Positive algorithmic results

We start with a reduction to Set Cover implying an approximation algorithm.

Figure 5: A reduction instance from Red-Blue Separation of $(G,c)$ (where the
square vertices are blue, the round ones are red) to Set Cover of
$(U,\mathcal{S})$. The separating set in the colored graph $(G,c)$ and the
corresponding set cover in the set system $(U,{\cal S})$ has been highlighted.

######  Proposition 4.

Red-Blue Separation has a polynomial-time $(2\ln n)$-factor approximation
algorithm, where $n$ is the input graph’s order.

###### Proof.

We reduce Red-Blue Separation to Set Cover. Let $((G,c),k)$ be an input
instance of Red-Blue Separation. We reduce it to an instance
$((U,\mathcal{S}),k)$ of Set Cover. For each red-blue vertex pair $(r,b)$ in
$G$, create an element in $U$. For each vertex $v$ in $G$ create a set in
$\mathcal{S}$ with elements $(r,b)$ in $U$ such that $v$ is in the closed
neighborhood of exactly one of $r$ and $b$ in $G$. See Figure 5. Observe that
a set cover $\mathcal{C}$ of size $k$ corresponds to a separating set $S$ of
size at most $k$ and vice versa. The greedy algorithm for Set Cover has an
approximation factor of $\ln|U|+1$. Since, in our case $|U|\leq n^{2}/4$, the
resulting approximation factor for Red-Blue Separation is at most
$\ln(n^{2}/4)+1\leq 2\ln n$. ∎

######  Proposition 5.

Let $(G,c)$ be a red-blue colored triangle-free and twin-free graph with the
two color classes $R$ and $B$. Then, $\operatorname{sep_{RB}}(G,c)\leq
3\min\\{|R|,|B|\\}$.

###### Proof.

Without loss of generality, we assume $|R|\leq|B|$. We construct a red-blue
separating set $S$ of $(G,c)$. First, we add all red vertices to $S$. It
remains to separate every red vertex from its blue neighbors. If a red vertex
$v$ has at least two neighbors, we add (any) two such neighbors to $S$. Since
$G$ is triangle-free, no blue neighbor of $v$ is in the closed neighborhood of
both these neighbors of $v$, and thus $v$ is separated from all its neighbors
(see vertex $v_{1}$ in Figure 6). If $v$ had only one neighbor $w$, and it was
blue, then we separate $w$ from $v$ by adding one arbitrary neighbor of $w$
(other than $v$) to $S$. Since $G$ is triangle-free, $v$ and $w$ are separated
(see vertex $v_{2}$ in Figure 6). Thus, we have built a red-blue separating
set $S$ of size at most $3|R|$.∎

Figure 6: Illustration of Proposition 5: here $v_{1}$ has just one blue
neighbor hence $w_{1}$ is added in $S$. $v_{2}$’s neighbors $w_{2}$ and
$w_{3}$ are also included in $S$. The square vertices are blue, the round ones
are red. Figure 7: Illustration of Proposition 6: the two cases when the
vertices $v$ and $w$ are (a) not adjacent and (b) adjacent. The square
vertices are blue, the round ones are red.

######  Proposition 6.

Let $(G,c)$ be a red-blue colored twin-free graph with maximum degree
$\Delta\geq 3$. Then,
$\operatorname{sep_{RB}}(G,c)\leq\Delta\min\\{|R|,|B|\\}$.

###### Proof.

Without loss of generality, let us assume $|R|\leq|B|$. We construct a red-
blue separating set $S$ of $(G,c)$. Let $v$ be any red vertex. If there is a
blue vertex $w$ whose closed neighborhood contains all neighbors of $v$ ($w$
could be a neighbor of $v$), we add both $v$ and $w$ to $S$ (see Figure 7(a)).
If $v$ is adjacent to $w$, since they cannot be twins, there must be a vertex
$z$ that can separate $v$ and $w$; we add $z$ to $S$ (see Figure 7(b)). Now,
$v$ is separated from every blue vertex in $G$.

If such a vertex $w$ does not exist, then we add all neighbors of $v$ to $S$.
Now again, $v$ is separated from every vertex of $G$. Thus, we have built a
red-blue separating set $S$ of size at most $\Delta|R|$. ∎

The previous propositions imply that Red-Blue Separation can be solved in XP
time for the parameter ”size of a smallest color class” on triangle-free
graphs and on graphs of bounded degree (by a brute-force search algorithm).
This is in contrast with the fact that in general graphs, it remains hard even
when the smallest color class has size 1 by Theorem 1.

######  Theorem 7.

Red-Blue Separation on graphs whose vertices belong to the color classes $R$
and $B$ can be solved in time $O(n^{3\min\\{|R|,|B|\\}})$ on triangle-free
graphs and in time $O(n^{\Delta\min\\{|R|,|B|\\}})$ on graphs of maximum
degree $\Delta$.

##  3 Extremal values and bounds for $\operatorname{max-sep_{RB}}$

We denote by $\operatorname{sep}(G)$ the smallest size of a (non-colored)
separating set of $G$, that is, a set that separates _all_ pairs of vertices.
We will use the relation $\operatorname{max-
sep_{RB}}(G)\leq\operatorname{sep}(G)$, which clearly holds for every twin-
free graph $G$.

###  3.1 Lower bounds for general graphs

We can have a large twin-free colored graph with solution size 2 (for example,
in a large blue path with a single red vertex, two vertices suffice). We show
that in every twin-free graph, there is always a coloring that requires a
large solution.

######  Theorem 8.

For any twin-free graph $G$ of order $n\geq 1$ and $n\not\in\\{8,9,16,17\\}$,
we have $\operatorname{max-sep_{RB}}(G)\geq\lfloor\log_{2}(n)\rfloor$.

###### Proof.

Let $G$ be a twin-free graph of order $n$ with $\operatorname{max-
sep_{RB}}(G)=k$. There are $2^{n}$ different red-blue colorings of $G$. For
each such coloring $c$, we have $\operatorname{sep_{RB}}(G,c)\leq k$. Consider
the set of vertex subsets of $G$ which are separating sets of size $k$ for
some red-blue colorings of $G$. Notice that each red-blue coloring has a
separating set of cardinality $k$. There are at most ${n\choose k}\leq n^{k}$
such sets.

Consider such a separating set $S$ and consider the set $I(S)$ of subsets
$S^{\prime}$ of $S$ for which there exists a vertex $v$ of $G$ with $N[v]\cap
S=S^{\prime}$. Let $i_{S}$ be the number of these subsets: we have $i_{S}\leq
2^{|S|}\leq 2^{k}$. If $S$ is a separating set for $(G,c)$, then all vertices
having the same intersection between their closed neighborhood and $S$ must
receive the same color by $c$. Thus, there are at most $2^{i_{S}}\leq
2^{2^{k}}$ red-blue colorings of $G$ for which $S$ is a separating set. Hence,
we have

$\begin{array}[]{rcl}2^{n}&\leq&\binom{n}{k}2^{2^{k}}\text{, which implies}\\\
2^{n}&\leq&n^{k}2^{2^{k}}\text{, which implies}\\\
n&\leq&k\log_{2}(n)+2^{k}\end{array}$

We now claim that this implies that $k\geq\log_{2}(n-\log_{2}(n)\log_{2}(n))$.
Suppose to the contrary that this is not the case, then we would obtain:

$\begin{array}[]{rcl}n&<&\log_{2}(n-\log_{2}(n)\log_{2}(n))\log_{2}(n)+n-\log_{2}(n)\log_{2}(n)\\\
n&<&\log_{2}(n)\log_{2}(n)+n-\log_{2}(n)\log_{2}(n)\end{array}$

And thus $n<n$, a contradiction. Since $k$ is an integer, we actually have
$k\geq\lceil\log_{2}(n-\log_{2}(n)\log_{2}(n))\rceil$. To conclude, one can
check that whenever $n\geq 70$, we have
$\lceil\log_{2}(n-\log_{2}(n)\log_{2}(n))\rceil\geq\lfloor\log_{2}(n)\rfloor$.
Moreover, if we compute values for $2^{n}-\binom{n}{k}2^{2^{k}}$ when $1\leq
n\leq 69$ and $k=\lfloor\log_{2}(n)\rfloor-1$, then we observe that this is
negative only when $n\in\\{8,9,16,17\\}$. Thus, $\lfloor\log_{2}(n)\rfloor$ is
a lower bound for $\operatorname{max-sep_{RB}}(G)$ as long as
$n\not\in\\{8,9,16,17\\}$. ∎

The bound of Theorem 8 is tight for infinitely many values of $n$.

######  Proposition 9.

For any integers $k\geq 1$ and $n=2^{k}$, there exists a graph $G$ of order
$n$ with $\operatorname{max-sep_{RB}}(G)=k$.

###### Proof.

We build $G$ as follows. Let $S=\\{s_{1},\ldots,s_{k}\\}$ be a set of $k$
vertices. Let $T$ be another set of vertices (disjoint from $S$). For every
subset $S^{\prime}$ of $S$ of size at least $2$, we add a vertex
$v_{S^{\prime}}$ to $T$ and we join it to all vertices of $S^{\prime}$ and
$T$. The set $T$ induces a clique. Finally, we add an isolated vertex
$v_{\emptyset}$ to $G$. To see that $\operatorname{max-sep_{RB}}(G)\leq k$,
notice that $S$ is a separating set of $G$ (regardless of the coloring).

If $k=1$, the coloring with $s_{1}$ Red and $v_{\emptyset}$ Blue shows that
$\operatorname{max-sep_{RB}}(G)\geq 1$.

If $k=2$, color $s_{1}$ and $s_{2}$ Red and $v_{\\{1,2\\}}$ and
$v_{\emptyset}$ Blue. To separate $v_{\\{1,2\\}}$ from $s_{1}$ (respectively
$s_{2}$), $s_{2}$ must belong to any separating set (respectively $s_{1}$),
which shows that $\operatorname{max-sep_{RB}}(G)\geq 2$.

If $k\geq 3$, color $v_{S}$ Blue and the other vertices Red. For each subset
$S^{\prime}$ of $S$ with $|S^{\prime}|=k-1$, in order to separate $v_{S}$ from
$v_{S^{\prime}}$, any separating set needs to contain $s_{i}$ where
$\\{s_{i}\\}=S\setminus S^{\prime}$. This shows that $\operatorname{max-
sep_{RB}}(G)\geq k$. ∎

We next relate parameter $\operatorname{max-sep_{RB}}$ to other graph
parameters.

######  Theorem 10.

Let $G$ be a graph on $n$ vertices. Then,
$\operatorname{sep}(G)\leq\min\\{\lceil\log_{2}(n)\rceil\cdot\operatorname{max-
sep_{RB}}(G),\lceil\log_{2}(\Delta(G)+1)\rceil\cdot\operatorname{max-
sep_{RB}}(G)+\gamma(G)\\}$, where $\gamma(G)$ is the domination number of $G$
and $\Delta(G)$ its maximum degree.

###### Proof.

Let $G$ be a graph on $2^{k-1}+1\leq n\leq 2^{k}$ vertices for some integer
$k$. We denote each vertex by a different $k$-length binary word
$x_{1}x_{2}\cdots x_{k}$ where each $x_{i}\in\\{0,1\\}$. Moreover, we give $k$
different red-blue colorings $c_{1},\dots,c_{k}$ such that vertex
$x_{1}x_{2}\cdots x_{k}$ is red in coloring $c_{i}$ if and only if $x_{i}=0$
and blue otherwise. For each $i$, let $S_{i}$ be an optimal red-blue
separating set of $(G,c_{i})$. We have $|S_{i}|\leq\operatorname{max-
sep_{RB}}(G)$ for each $i$. Let $S=\bigcup_{i=1}^{k}S_{i}$. Now, $|S|\leq
k\cdot\operatorname{max-
sep_{RB}}(G)=\lceil\log_{2}(n)\rceil\cdot\operatorname{max-sep_{RB}}(G)$. We
claim that $S$ is a separating set of $G$. Assume to the contrary that for two
vertices $x=x_{1}x_{2}\cdots x_{k}$ and $y=y_{1}y_{2}\cdots y_{k}$, $N[x]\cap
S=N[y]\cap S$. For some $i$, we have $y_{i}\neq x_{i}$. Thus, in coloring
$c_{i}$, vertices $x$ and $y$ have different colors and hence, there is a
vertex $s\in c_{i}$ such that $s\in N[y]\triangle N[x]$, a contradiction which
proves the first bound.

Let $S$ be an optimal red-blue separating set for such a coloring $c$ and let
$D$ be a minimum-size dominating set in $G$; $S\cup D$ is also a red-blue
separating set for coloring $c$. At most $\Delta(G)+1$ vertices of $G$ may
have the same closed neighborhood in $D$. Thus, we may again choose
$\lceil\log_{2}(\Delta(G)+1)\rceil$ colorings and optimal separating sets for
these colorings, each coloring (roughly) halving the number of vertices having
the same vertices in the intersection of separating set and their closed
neighborhoods. Since each of these sets has size at most $\operatorname{max-
sep_{RB}}(G)$, we get the second bound. ∎

We do not know whether the previous bound is reached, but as seen next, there
are graphs $G$ such that $\operatorname{sep}(G)=2\operatorname{max-
sep_{RB}}(G)$.

######  Proposition 11.

Let $G=K_{k_{1},\dots,k_{t}}$ be a complete $t$-partite graph for $t\geq 2$,
$k_{i}\geq 5$ odd for each $i$. Then $\operatorname{sep}(G)=n-t$ and
$\operatorname{max-sep_{RB}}(G)=(n-t)/2$.

###### Proof.

Let us have $t$ parts $G_{1},\dots,G_{t}$ with vertex sets
$V(G_{i})=\\{v^{i}_{1},\dots,v^{i}_{k_{i}}\\}$. Let $c$ be such a coloring in
$G$ that $\operatorname{sep_{RB}}(G,c)=\operatorname{max-sep_{RB}}(G)$.
Observe that $S$ is a separating set in $G$ if and only if $|S\cap
V(G_{i})|\geq k_{i}-1$. Indeed, if we have $v^{i}_{j},v^{i}_{h}\not\in S$,
then $N[v^{i}_{j}]\cap S=N[v^{i}_{h}]\cap S$ since
$N(v^{i}_{j})=N(v^{i}_{h})$. Moreover, each vertex in $S$ is separated from
vertices not in $S$ and each vertex in $V(G_{i})$ is separated from vertices
in $V(G_{j})$. Thus, $\operatorname{sep}(G)=n-t$.

Next we form a red-blue separating set $S^{\prime}$ for coloring $c$. For each
part, we choose to set $S^{\prime}$ every vertex which has the less common
color in that part (however, we choose at least two vertices to $S^{\prime}$
from each part). Observe that
$|S^{\prime}|\leq\sum_{i=1}^{t}\frac{k_{i}-1}{2}=(n-t)/2$. Moreover as above,
we can see that $S^{\prime}$ is a red-blue separating set with the help of
fact that if $v^{i}_{j}\not\in S^{\prime}$ and $v^{i}_{h}\not\in S^{\prime}$,
then $v^{i}_{j}$ and $v^{i}_{h}$ have the same color.

Finally, we show that $\operatorname{max-sep_{RB}}(G)\geq(n-t)/2$. Observe
that if we have $u,v\in V(G_{i})$ and $u,v\not\in S$, then $N[u]\cap
S=N[v]\cap S$. Thus, any two vertices $u,v\in V(G_{i})\setminus S$ must have
the same color. If each part has $(k_{i}+1)/2$ red vertices and $(k_{i}-1)/2$
blue vertices, then we require at least $\sum_{i=1}^{t}(k_{1}-1)/2=(n-t)/2$
vertices in $S$.∎

###  3.2 Upper bound for general graphs

We will use the following classic theorem in combinatorics to show that we can
always spare one vertex in the solution of Max Red-Blue Separation.

######  Theorem 12 (Bondy’s Theorem [2]).

Let $V$ be an $n$-set with a family
$\mathcal{A}=\\{\mathcal{A}_{1},\mathcal{A}_{2},\ldots,\mathcal{A}_{n}\\}$ of
$n$ distinct subsets of $V$. There is an $(n-1)$-subset $X$ of $V$ such that
the sets $\mathcal{A}_{1}\cap X,\mathcal{A}_{2}\cap X,\mathcal{A}_{3}\cap
X,\ldots,\mathcal{A}_{n}\cap X$ are still distinct.

######  Corollary 13.

For any twin-free graph $G$ on $n$ vertices, we have $\operatorname{max-
sep_{RB}}(G)\leq\operatorname{sep}(G)\leq n-1$.

###### Proof.

Regardless of the coloring, by Bondy’s theorem, we can always find a set of
size $n-1$ that separates _all_ pairs of vertices. ∎

This bound is tight for every even $n$ for complements of _half-graphs_
(studied in the context of identifying codes in [15]).

######  Definition 14 (Half-graph [14]).

For any integer $k\geq 1$, the _half-graph_ $H_{k}$ is the bipartite graph on
vertex sets $\\{v_{1},\ldots,v_{k}\\}$ and $\\{w_{1},\ldots,w_{k}\\}$, with an
edge between $v_{i}$ and $w_{j}$ if and only if $i\leq j$.

The complement $\overline{H_{k}}$ of $H_{k}$ thus consists of two cliques
$\\{v_{1},\ldots,v_{k}\\}$ and $\\{w_{1},\ldots,w_{k}\\}$ and with an edge
between $v_{i}$ and $w_{j}$ if and only if $i>j$.

######  Proposition 15.

For every $k\geq 1$, we have $\operatorname{max-
sep_{RB}}(\overline{H_{k}})=2k-1$.

###### Proof.

The upper bound follows from Corollary 13.

Consider the red-blue coloring $c$ such that $v_{i}$ is Blue whenever $i$ is
odd and Red, otherwise. If $k$ is odd, $w_{i}$ is Red whenever $i$ is odd and
Blue, otherwise. If $k$ is even, $w_{i}$ is Blue whenever $i$ is odd and Red,
otherwise.

For any integer $i$ between $1$ and $k-1$, $v_{i}$ and $v_{i+1}$ have
different colors and can only be separated by $w_{i}$. Likewise, $w_{i}$ and
$w_{i+1}$ have different colors and can only be separated by $v_{i+1}$. This
shows that $\\{w_{1},\ldots,w_{k-1}\\}$ and $\\{v_{2},\ldots,v_{k}\\}$ must
belong to any separating set of $(\overline{H_{k}},c)$. Finally, consider
$w_{1}$ and $v_{k}$. They also have different colors and can only be separated
by either $v_{1}$ or $w_{k}$. This shows that we need at least $n-1$ vertices
in any separating set. ∎

###  3.3 Upper bound for trees

We will now show that a much better upper bound holds for trees.

Degree-1 vertices are called leaves and the set of leaves of the tree $T$ is
$L(T)$. Vertices adjacent to leaves are called support vertices, and the set
of support vertices of $T$ is denoted $S(T)$. We denote $\ell(T)=|L(T)|$ and
$s(T)=|S(T)|$. The set of support vertices with exactly $i$ adjacent leaves is
denoted $S_{i}(T)$ and the set of leaves adjacent to support vertices in
$S_{i}(T)$ is denoted $L_{i}(T)$. Observe that $|L_{1}(T)|=|S_{1}(T)|$.
Moreover, let $L_{+}(T)=L(T)\setminus L_{1}(T)$ and $S_{+}(T)=S(T)\setminus
S_{1}(T)$. We denote the sizes of these four types of sets by
$s_{i}(T),\ell_{i}(T),s_{+}(T)$ and $\ell_{+}(T)$, respectively.

For trees, we can show the following result, which is in contrast with the
situation for general graphs (or even split graphs, as highlighted by Theorem
1).

######  Theorem 16.

Let $T$ be a tree on $n\geq 3$ vertices and let $c$ be a coloring with exactly
one red (or blue) vertex. We have $\operatorname{sep_{RB}}(T,c)\leq 2$.

###### Proof.

Let $T$ be a tree on at least three vertices with coloring $c$ such that there
is exactly one red vertex $v\in V(T)$.

Let us assume first that $v\not\in L(T)$. Thus, $v$ has at least two neighbors
$w$ and $u$. If we now include $w$ and $u$ in the separating set $S$, then $v$
is the only vertex in $T$ which has two adjacent vertices in $S$ and hence,
$S$ is a red-blue separating set in $T$ for coloring $c$.

On the other hand, if $v\in L(T)$, $u\in N(v)$ and $w\in
N(u)\setminus\\{v\\}$, then $S=\\{v,w\\}$ is a red-blue separating set in $T$
for coloring $c$, and $\operatorname{sep_{RB}}(T,c)\leq 2.$ ∎

To prove our upper bound for trees, we need Theorems 17 and 18.

Figure 8: Construction of $C_{1}$ from $C_{1}^{\prime}$ where the boxed
elements represent members of the set.

######  Theorem 17.

For any tree $T$ of order $n\geq 5$, we have $\operatorname{max-
sep_{RB}}(T)\leq\frac{n+s(T)}{2}$.

###### Proof.

Observe that the claim holds for stars (select the vertices of the smallest
color class among the leaves, and at least two leaves). Thus, we assume that
$s(T)\geq 2$. Let $c$ be a coloring of $T$ such that $\operatorname{max-
sep_{RB}}(T)=\operatorname{sep_{RB}}(T,c)$.

We build two separating sets $C_{1}$ and $C_{2}$; the idea is that one of them
is small. We choose a non-leaf vertex $x$ and add to the first set
$C_{1}^{\prime}$ every vertex at odd distance from $x$ and every leaf. If
there is a support vertex $u\in S_{1}(T)\cap C_{1}^{\prime}$ and an adjacent
leaf $v\in L_{1}(T)\cap N(u)$, we create a separating set $C_{1}$ from
$C_{1}^{\prime}$ by shifting the vertex away from leaf $v$ to some vertex
$w\in N(u)\setminus L(T)$. We construct in a similar manner sets
$C_{2}^{\prime}$ and $C_{2}$, except that we add the vertices at even distance
from $x$ to $C_{2}^{\prime}$ (including $x$ itself) and do the shifting when
$u\in S_{1}(T)$ has even distance to $x$. Sets $C_{1}$ and $C_{2}$ have been
previously considered in [16, Theorem 6]. See Figure 8.

Figure 9: Illustration of various cases for $C_{1}$ in Claim 17.1.

######  Claim 17.1.

Both $C_{1}$ and $C_{2}$ are separating sets.

_Proof of claim._ Let us first consider set $C_{1}$. See Figure 9 for helpful
illustrations of different cases we go through in the following arguments. Let
us first show that each leaf $v\in L(T)$ is separated from all other vertices
by $C_{1}$. Let $u\in N(v)$ be the adjacent support vertex. If $d(x,v)$ is
odd, then $v\in C_{1}$ and $|N(u)\cap C_{1}|\geq 2$. Hence, $v$ is separated
from every other vertex. If $d(v,x)$ is even and $v\in L_{+}(T)$, then $v\in
C_{1}$ and $|N[u]\cap C_{1}|\geq 3$. Hence, $v$ is again separated from other
vertices. If $d(v,x)$ is even and $v\in L_{1}(T)$, then $v\not\in C_{1}$,
$u\in C_{1}$ and $|N[u]\cap C_{1}|\geq 2$ due to the shift when we form
$C_{1}$ from $C_{1}^{\prime}$. If we have $N[w]\cap C_{1}=\\{u\\}$ for some
$w\neq u$ and $w\not\in L(T)$, then $d(w,x)$ is even and we have $|N[w]\cap
C_{1}|\geq 2$, a contradiction. Thus, any leaf $v$ is separated from each
other vertex.

Let us then consider a vertex $w\not\in L(T)$ with odd distance $d(w,x)$, then
$w\in C_{1}$. Moreover, each neighbor $u\in N(w)$ has even distance to $x$ and
is either a leaf which is separated from $w$ or has at least two neighbors
with odd distances to $x$ and hence, $|C_{1}\cap N(u)|\geq 2$ and $u$ is
separated from $w$. Finally, if $w\not\in L(T)$ and $d(w,x)$ is even, then
$w\not\in C_{1}^{\prime}$ and $|N(w)\cap C_{1}|\geq 2$. Since there are no
$3$-cycles nor $4$-cycles in a tree, $w$ is separated from all other vertices.

The proof that also $C_{2}$ is a separating set is similar. We only swap evens
and odds. Hence, the claim follows. ($\Box$)

Let us denote by $NS_{3}(T)$ a smallest set of vertices in $T$ such that for
each vertex $v\in S_{3}(T)$ which has $N(v)\cap S_{+}(T)=\emptyset$, we have
at least one vertex $u\in N(v)\setminus L(T)$ in $NS_{3}(T)$ (such a set
exists since $T$ is not a star).

Figure 10: Comparison of the sets $C_{1}^{\prime}$ and $C_{2}^{\prime}$ where
the vertices highlighted in green belong to the sets
$C^{\prime}_{1}\setminus(L(T)\cup S_{+}(T)\cup NS_{3}(T))$ and
$C^{\prime}_{2}\setminus(L(T)\cup S_{+}(T)\cup NS_{3}(T))$, respectively.

We assume that out of the two sets $C_{1}^{\prime}$ and $C_{2}^{\prime}$,
$C_{a}^{\prime}$ ($a\in\\{1,2\\}$) has less vertices among the vertices in
$V(T)\setminus(L(T)\cup S_{+}(T)\cup NS_{3}(T))$. In particular, it contains
at most half of those vertices and we have $|C_{a}^{\prime}\setminus(L(T)\cup
S_{+}(T)\cup NS_{3}(T))|\leq(n-\ell(T)-s_{+}(T)-|NS_{3}(T)|)/2$. In Figure 10,
a comparison of the sets $C_{1}^{\prime}$ and $C_{2}^{\prime}$ is shown. Next,
we will construct set $C$ from $C_{a}^{\prime}$. Let us start by having each
vertex in $C_{a}^{\prime}$ be in $C$. Let us then, for each support vertex
$u\in S_{+}(T)$, remove from $C$ every adjacent leaf $w\in L_{+}(T)\cap N(u)$
such that $w$ is in the more common color class within the vertices in
$N(u)\cap L_{+}(T)$ in coloring $c$. We then add some vertices to $C$ as
follows. For $u\in S_{i}(T)$, $i\geq 4$, we add $u$ to $C$ and some leaves so
that there are at least two vertices in $N(u)\cap C$. We have at most
$|L(T)\cap N[u]|/2+1$ vertices in $C\cap(N[u]\cap L(T)\cup\\{u\\})$.

For $i=3$, we add $u$ and any $v\in NS_{3}(T)\cap N(u)\setminus C$, depending
on which one already belongs to $C$. Then, if all leaves in $N(u)$ have the
same color, we add one of them to $C$. Hence, we have $|C\cap(L_{3}(T)\cup
NS_{3}(T))|/s_{3}(T)\leq 2$.

Finally, for $i=2$, if the two leaves have same color and $u\not\in
C_{a}^{\prime}$, we add $u$ and one of the two leaves to $C$. If the two
leaves have the same color and $u\in C_{a}^{\prime}$, we add a non-leaf
neighbor of $u$ to $C$. If the leaves have different colors, one of them, say
$v$, has the same color as $u$. We add $u$ to $C$ and shift the vertex in $C$
in the leaves so that $v$ is in $C$. We added at most two vertices to $C$ in
this case. Notice that now we have $S_{+}(T)\subseteq C$.

Each time, we added to $C$ at most half of the considered vertices in $N(u)$,
and at most one other additional vertex. After these changes, we shift some
vertices in $C$ away from $L_{1}(T)$ the same way we built $C_{a}$ from
$C_{a}^{\prime}$. As $|C_{a}^{\prime}\setminus(L(T)\cup S_{+}(T)\cup
NS_{3}(T))|\leq(n-\ell(T)-s_{+}(T)-|NS_{3}(T)|)/2$, we get:

$\displaystyle|C|$
$\displaystyle\leq\frac{n-\ell(T)-s_{+}(T)-|NS_{3}(T)|}{2}+\ell_{1}(T)+\frac{\ell_{+}(T)+|NS_{3}(T)|}{2}+s_{+}(T)$
$\displaystyle=\frac{n+\ell_{1}(T)+s_{+}(T)}{2}=\frac{n+s(T)}{2}.$

######  Claim 17.2.

$C$ is a red-blue separating set for coloring $c$.

_Proof of claim._ Since $C_{a}$ is a separating set and $C_{a}\setminus
C\subseteq L_{+}(T)$, if two vertices $w,v$ are not separated by $C$, then
they were separated by a leaf in $L_{+}(T)$ in $C_{a}$. Moreover, there exists
a support vertex $u\in S_{+}(T)$ such that $v,w\in N[u]$. Recall that
$S_{+}(T)\subseteq C$ and hence, $u\in C$. If $w$ and $v$ are both leaves,
then they have the same color and do not need to be separated. In the
following, we go through all the other possibilities for $w$ and $v$.

Assume first that $w,v\not\in L(T)$ and $d(w,v)=1$ and let us say, without
loss of generality, that $d(w,x)$ is of such parity that $w\in C_{a}^{\prime}$
(and $w\in C$). Notice that we have $w=u$ or $v=u$ in this case. Moreover,
since there are no cycles in $T$, the parities of $d(w,x)$ and $d(v,x)$
differ. Thus, there exists some vertex $b\in N(v)\setminus N[w]$ such that the
parity of $d(b,x)$ equals to the parity of $d(w,x)$. Thus, $b\in
C_{a}^{\prime}$. If $b$ is not a leaf, then $b\in C$ and $b$ separates $w$ and
$v$. Thus, $b\in L(T)$. However, if $b\in L_{1}(T)$, then $b\in C$ and if
$b\in L_{+}(T)$, then $v\in S_{+}(T)$ and there exists a leaf in $C$ adjacent
to $v$ separating $v$ and $w$, a contradiction. When $d(w,v)=2$, neither of
$w$ or $v$ are in $C$ since they cannot be separated. Again, we can find some
vertex $b$ in $C$ that will separate them as in the previous case.

Moreover, since there are no cycles in $T$, the parities of $d(w,x)$ and
$d(v,x)$ differ. Thus, there exists some vertex $b\in N(v)\setminus N[w]$ such
that the parity of $d(b,x)$ equals to the parity of $d(w,x)$. If $b$ is not a
leaf, then $b\in C$ and $b$ separates $w$ and $v$. Thus, $b\in L(T)$. However,
if $b\in L_{1}(T)$, then $b\in C$ and if $b\in L_{+}(T)$, then $v\in S_{+}(T)$
and there exists a leaf in $C$ adjacent to $v$ separating $v$ and $w$, a
contradiction. When $d(w,v)\geq 2$, we notice that this case cannot occur
since $v,w\in N[u]$ and at least one of these two vertices is adjacent to a
leaf in $N(u)$.

Finally, we have the case where exactly one of the two vertices is a leaf, let
us say $v\in L(T)$ and since $v\in N(u)$, we have $v\in L_{+}(T)$. Assume
first that $d(v,w)=2$. Thus, $v,w\not\in C$. However, then we again have $b\in
C$ such that $b\in N(w)\setminus\\{u\\}$, either due to the parity of $d(x,b)$
or because $b$ is a leaf. As the last case we have $u=w$ and $v\in
L_{+}(T)\cap N(u)$. If $u\not\in C_{a}^{\prime}$, then, by parity, $u$ has an
adjacent non-leaf vertex in $C$ since $T$ is not a star. On the other hand, if
$u\in C_{a}^{\prime}$, then if $u\in S_{2}(T)$ and the two leaves have the
same color, there is again a non-leaf neighbor in $C$. If $u\in S_{2}(T)$ and
the two leaves have different colors, then there is a leaf of the same color,
in $N(u)$, as $u$ which is in $C$. If $u\in S_{3}(T)$, then $u$ has a non-leaf
neighbor in $NS_{3}(T)\cap C$ or in $S_{+}(T)\cap C$. If $u\in S_{i}(T)$ for
$i\geq 4$, then $u$ has at least two adjacent leaves which are in $C$. Hence,
$w$ and $v$ are either separated or they have the same color. ($\Box$)

This completes the proof of the theorem. ∎

The upper bound of Theorem 17 is tight. Consider, for example, a path on eight
vertices. Also, the trees presented in Proposition 20 are within $1/2$ from
this upper bound. In the following theorem, we offer another upper bound for
trees which is useful when the number of support vertices is large. Following
theorem has been previously considered for total dominating identifying codes
(under term differentiating-total dominating set) in [20].

######  Theorem 18.

For any tree $T$ of order $n\geq 5$, $\operatorname{sep}(T)\leq n-s(T)$.

###### Proof.

Let us choose for each support vertex $u\in S(T)$ exactly one adjacent leaf
$v\in L(T)$ and say that these vertices form the set $S^{\prime}$. Next, we
form the separating set $S=V(T)\setminus S^{\prime}$. Notice that
$|S|=n-s(T)$. In the following, we show that $S$ is a separating set in $T$.

Observe that if $v\not\in S$, then $v$ is a leaf and no support vertex has two
adjacent leaves which do not belong to $S$. Thus, vertices which do not belong
to $S$ are pairwise separated. Since $S^{\prime}\subseteq L(T)$, $T[S]$ is a
connected induced subgraph of $T$. Moreover, as $n\geq 5$, we have $|N[w]\cap
S|\geq 2$ for each vertex $w\in S$. Thus, vertices in $S$ are separated from
vertices which are not in $S$. Finally, any two vertices $w,w^{\prime}\in S$
are separated since $|V(T[S])|\geq 3$; hence, each closed neighborhood is
unique in $T[S]$. ∎

The following corollary is a direct consequence of Theorems 17 and 18. Indeed,
we have $\operatorname{max-sep_{RB}}(T)\leq\min\\{n-s(T),(n+s(T))/2\\}$.

######  Corollary 19.

For any tree $T$ of order $n\geq 5$, we have $\operatorname{max-
sep_{RB}}(T)\leq\frac{2n}{3}$.

We next show that Corollary 19 (and Theorem 17) is not far from tight.

######  Proposition 20.

For any $k\geq 1$, there is a tree $T$ of order $n=5k+1$ with
$\operatorname{max-sep_{RB}}(T)=\frac{3(n-1)}{5}=\frac{n+s(T)-1}{2}$.

###### Proof.

Consider the tree $T$ formed by taking $k$ disjoint copies
$P^{1},\ldots,P^{k}$ of a path of order $6$ and identifying one endpoint of
each path into one single vertex $x$. We consider the coloring that colors $x$
red, and all other vertices are colored red-blue-red… following the
bipartition of the tree. Let $v^{i}_{1},\ldots,v^{i}_{5}$ be the vertices of
$P^{i}$ distinct from $x$, where $x$ is adjacent to $v^{i}_{1}$. In order to
separate $v^{i}_{5}$ from $v^{i}_{4}$, we need $v^{i}_{3}$ in any red-blue
separating set. To separate $v^{i}_{4}$ from $v^{i}_{3}$, we need either
$v^{i}_{2}$ or $v^{i}_{5}$. To separate $v^{i}_{3}$ from $v^{i}_{2}$, we need
either $v^{i}_{1}$ or $v^{i}_{4}$. Thus, we need at least three vertices of
$P^{i}$ in any red-blue separating set, which shows that $\operatorname{max-
sep_{RB}}(T)\geq 3k$. To see that $\operatorname{max-sep_{RB}}(T)\leq 3k$, one
can see that the set consisting of all vertices
$v_{1}^{i},v_{3}^{i},v_{5}^{i}$ separates all pairs of vertices. Finally,
since $s(T)=k$ and $n-1=5k$, we get that
$\frac{n+s(T)-1}{2}=3k=\frac{3(n-1)}{5}$. ∎

##  4 Algorithmic results for Max Red-Blue Separation

The problem Max Red-Blue Separation does not seem to be naturally in the class
NP (it is in the second level of the polynomial hierarchy). Nevertheless, we
show that it is NP-hard.

######  Theorem 21.

Max Red-Blue Separation is NP-hard even for graphs of maximum degree 12.

###### Proof.

We reduce from the following NP-hard version of 3-SAT [29].

3-SAT-2l Input: A set of $m$ clauses $C=\\{c_{1},\ldots,c_{m}\\}$ each with at
most three literals, over $n$ Boolean variables $X=\\{x_{1},\ldots,x_{n}\\}$,
and each literal appears at most twice. Question: Is there an assignment of
$X$ where each clause has a true literal?
---

#### Construction:

Given an instance $\sigma$ of 3-SAT-2l with $m$ clauses and $n$ variables, we
create an instance $(H,k)$ of Max Red-Blue Separation, where $k=4m+9n$. We
first explain the construction of a domination gadget.

A _domination gadget_ on vertices $v_{1}$ and $v_{2}$, denoted by
$H(v_{1},v_{2})$, consists of 16 vertices including $v_{1}$ and $v_{2}$. This
gadget will ensure that $v_{1},v_{2}$ are dominated by the local solution of
the gadget (and thus, separated from the rest of the graph). See Figure 11 for
reference. The vertices $v_{1}$ and $v_{2}$ may be connected to each other or
to some other vertices outside the domination gadget as represented by the
dashed edges incident to them. Both $v_{1}$ and $v_{2}$ are also connected to
the vertices $u_{1}$ to $u_{4}$ as shown in the figure. Next we have a clique
$K_{10}$ consisting of the vertices
$\\{p_{1},p_{2},\ldots,p_{6},q_{1},q_{2},\ldots,q_{4}\\}$. Every vertex
$p_{i}$ is connected to a unique pair of vertices from
$\\{u_{1},u_{2},u_{3},u_{4}\\}$ and every vertex $q_{j}$ is connected to a
unique triple of vertices from $\\{u_{1},u_{2},u_{3},u_{4}\\}$. For example in
the figure we have $p_{4}$ connected with the pair of vertices $u_{2}$ and
$u_{3}$ and $q_{3}$ connected with the triplet of vertices $u_{1},u_{3}$ and
$u_{4}$.

Figure 11: A domination gadget on vertices $v_{1}$ and $v_{2}$ and its
schematic representation.

The graph $H$ consists of one _variable gadget_ per variable and one _clause
gadget_ per clause. The variable gadget for a variable $x$ consists of the
graph $H(x^{a},x^{b})$ and $H(x,\overline{x})$ with additional edges
$(x^{a},x^{b}),(x^{a},x)$ and $(x^{a},\overline{x})$. The clause gadget for a
clause $C=(x\lor\overline{y}\lor z)$ (say) is $H(c^{a},c^{b})$, where $c^{a}$
is connected to the vertices $c^{b},x,\overline{y}$ and $z$. See Figure 12 for
an illustration. Observe that since each literal can appear at most twice
therefore, the maximum degree of $H$ is 12, determined by the $q_{i}$’s in
each domination gadget.

Figure 12: Variable and clause gadgets.

Let us illustrate an example instance for the reduction (see Figure 13). In
this example, we have the formula as $(\overline{w}\lor\overline{x}\lor
y)\land(x\lor\overline{y}\lor z)$. Thus, we have two clauses
$c_{1}=\overline{w}\lor\overline{x}\lor y$ and $c_{2}=x\lor\overline{y}\lor z$
and four variables $w,x,y$ and $z$. Corresponding to each clause and each
variable, we have a clause gadget and a variable gadget respectively (as
described earlier). The domination gadget attached with both the clause and
variable gadgets is shown below to increase readability. We have shown one
possible coloring in this instance with a large solution size.

Figure 13: An example to show the reduction from 3-SAT-2l to Max Red-Blue
Separation. The square vertices are blue, the round ones are red.

######  Claim 21.1.

$\operatorname{max-sep_{RB}}(H)=\operatorname{sep}(H)$.

_Proof of claim._ It is clear that $\operatorname{max-
sep_{RB}}(H)\leq\operatorname{sep}(H)$, since any set that separates _all_
pairs of vertices also separates all red-blue pairs, for any possible
coloring.

We will now prove that $\operatorname{sep}(H)\leq\operatorname{max-
sep_{RB}}(H)$ by providing a specific coloring, and showing that for this
coloring, any (optimal) solution also separates all pairs of vertices.

Consider a coloring $c$ of $H$, where for each domination gadget
$H(v_{1},v_{2})$, all $p_{i}$’s are colored blue and all $q_{j}$’s are colored
red, or vice versa. For each variable $x$, the vertices $x^{a}$ and $x^{b}$
are given different colors. For each clause $C$, the vertices $c^{a}$ and
$c^{b}$ are also colored differently. The rest of the vertices are colored
arbitrarily.

Consider a (minimum) red-blue separating set $S$ of $H$ with respect to the
coloring $c$. For each domination gadget $H(v_{1},v_{2})$, the vertices
$u_{1}$ to $u_{4}$ must be included in $S$. This is because for each $u_{h}\in
H(v_{1},v_{2})$, there exist $p_{i},q_{j}\in H(v_{1},v_{2})$ such that
$N[p_{i}]\triangle N[q_{j}]=\\{u_{h}\\}$, where $\triangle$ denotes the
symmetric difference between two sets. Since $p_{i}$ and $q_{j}$ are given
different colors, $u_{h}$ is the only vertex which separates them and has to
be included in $S$.

Observe that, for each variable $x$, the vertices $u_{1}$ to $u_{4}$ of the
domination gadget $H(x^{a},x^{b})$ separate the vertices $x^{a}$ and $x^{b}$
from the rest of $H$. Therefore, they only need to be separated between
themselves. The same reasoning holds for the vertices $x$ and $\overline{x}$,
for each variable $x$, as well as for the vertices $c^{a}$ and $c^{b}$, for
each clause $C$.

For each variable $x$, at least one of the vertices $x$ or $\overline{x}$ must
be included in $S$ in order to separate the vertices $x^{a}$ and $x^{b}$ as
they are colored differently. This also separates vertices $x$ and
$\overline{x}$, if they are assigned different colors. For each clause
$C=(x\lor\overline{y}\lor z)$ (say), at least one of the vertices
$x,\overline{y}$ or $z$ needs to be included in $S$ (if not already included)
in order to separate the vertices $c^{a}$ and $c^{b}$ as they are also colored
differently. The set $S$ must contain a subset of vertices from the set
$\\{x,\overline{x}\mid x\in X\\}$ which separates the vertices $y^{a}$ and
$y^{b}$ for all variables $y$, and the vertices $c^{a}$ and $c^{b}$ for all
clauses $C$.

Since the size of set $S$ is minimum, it is a minimum red-blue separating set
of $H$ with respect to the coloring $c$. We will now show that $S$ is also a
separating set of (uncolored) $H$. Observe that for each domination gadget
$H(v_{1},v_{2})$, the vertices from $u_{1}$ to $u_{4}$ (which are in $S$)
separate all (uncolored) $p_{i}$’s and $q_{j}$’s from the rest of the vertices
in $H$. This is because the intersection of the set
$\\{u_{1},u_{2},u_{3},u_{4}\\}$ and the closed neighborhood of each $p_{i}$ or
$q_{j}$ is unique. The vertices $u_{1}$ to $u_{4}$ are also separated from the
remaining vertices.

Also, since the vertices $u_{1}$ to $u_{4}$ are included in $S$ for all
domination gadgets of $H$, therefore going by the previous explanation we only
need to separate the vertex pairs $(x^{a},x^{b}),(x,\overline{x})$ and
$(c^{a},c^{b})$. But the construction of $S$ is such that all these pairs of
vertices are already separated by $S$. Therefore $S$ is also a separating set
of $H$. This proves our claim. ($\Box$)

######  Claim 21.2.

If $\sigma$ is satisfiable, $\operatorname{sep}(H)=k$ and otherwise,
$\operatorname{sep}(H)>k$, where $k=4m+9n$.

_Proof of claim._ Consider a separating set $S$ of $H$. For each domination
gadget $H(v_{1},v_{2})$, the vertices $u_{1}$ to $u_{4}$ must be included in
$S$ as these are the only vertices which can separate all the $p_{i}$’s and
$q_{j}$’s of $H(v_{1},v_{2})$ and themselves. Also, for each variable $x$, one
of the vertices $x$ or $\overline{x}$ must also be included in $S$ in order to
separate $x^{a}$ and $x^{b}$. Thus, a total of $4(m+2n)+n=4m+9n$ vertices are
needed in $S$. This implies that $\operatorname{sep}(H)\geq k=4m+9n$.

If $\sigma$ is satisfiable, then with respect to a satisfying assignment, we
include for each variable $x$, the vertex $x$ if it is assigned true, or the
vertex $\overline{x}$, if it is assigned false. These vertices also separate
$c^{a}$ and $c^{b}$ for all clauses $C$. Therefore, $S$ is a separating set of
$H$ and $\operatorname{sep}(H)=k$.

On the contrary, if $\sigma$ is not satisfiable, then $S$ is not a separating
set of $H$ as there exists some clause $C$ for which $c^{a}$ and $c^{b}$ are
not separated. Since all vertices in $S$ are necessary to be included, any
separating set of $H$ is a strict superset of $S$, and
$\operatorname{sep}(H)>k$. ($\Box$)

From Claim 21.1 and Claim 21.2 it follows that $\sigma$ is satisfiable if and
only if $\operatorname{max-sep_{RB}}(H)\leq k=4m+9n$. Since the maximum degree
of $H$ is 12 and 3-SAT-2l is NP-hard, Max Red-Blue Separation is also NP-hard
for graphs with maximum degree 12. ∎

We can use Theorem 10 and a reduction to Set Cover to show the following
algorithmic result.

######  Theorem 22.

Max Red-Blue Separation can be approximated within a factor of $O(\ln^{2}n)$
on graphs of order $n$ in polynomial time.

###### Proof.

Let $A$ be a polynomial-time ($2\ln n+1$)-approximation algorithm for the
Separation problem [18]. For any graph $G$, let $S(G)$ denote the separating
set returned by $A$ on the input graph $G$. Using Theorem 10, we have

$\displaystyle|S(G)|$ $\displaystyle\leq(2\ln n+1)\cdot\operatorname{sep}(G)$
$\displaystyle\leq(2\ln n+1)\cdot\lceil\log n\rceil\cdot\operatorname{max-
sep_{RB}}(G)$

Hence, algorithm $A$ is a polynomial-time $O(\ln^{2}n)$-approximation
algorithm for Max Red-Blue Separation. ∎

##  5 Conclusion

We have initiated the study of Red-Blue Separation and Max Red-Blue Separation
on graphs, problems which seem natural given the interest that their geometric
version has gathered, and the popularity of its ”non-colored” variants
Identifying Code on graphs or Test Cover on set systems.

When the coloring is part of the input, the solution size of Red-Blue
Separation can be as small as 2, even for large instances; however, we have
seen that this is not possible for Max Red-Blue Separation since
$\operatorname{max-sep_{RB}}(G)\geq\lfloor\log_{2}(n)\rfloor$ for twin-free
graphs of order $n$. Moreover, $\operatorname{max-sep_{RB}}(G)$ can be as
large as $n-1$ in general graphs, yet, on trees, it is at most $2n/3$ (we do
not know if this is tight, or if the upper bound of $3n/5$, which would be
best possible, holds). However, the upper bound of Theorem 17, which is based
on the number of support vertices, is tight for trees. It would also be
interesting to see if other interesting upper or lower bounds can be shown for
other graph classes.

We have shown that
$\operatorname{sep}(G)\leq\lceil\log_{2}(n)\rceil\cdot\operatorname{max-
sep_{RB}}(G)$. Is it true that $\operatorname{sep}(G)\leq 2\operatorname{max-
sep_{RB}}(G)$? As we have seen, this would be tight.

We have also shown that Max Red-Blue Separation is NP-hard, yet it does not
naturally belong to NP. Is the problem actually hard for the second level of
the polynomial hierarchy?

## References

  * [1] B. Bollobás and A. D. Scott. On separating systems. _European Journal of Combinatorics_ 28:1068–1071, 2007.
  * [2] J. A. Bondy. Induced subsets. _Journal of Combinatorial Theory, Series B_ 12(2):201–202, 1972.
  * [3] É. Bonnet, P. Giannopoulos and M. Lampis. On the parameterized complexity of red-blue points separation. _Journal of Computational Geometry_ 10(1):181–206, 2019.
  * [4] N. Bousquet, A. Lagoutte, Z. Li, A. Parreau and S. Thomassé. Identifying codes in hereditary classes of graphs and VC-dimension. _SIAM Journal on Discrete Mathematics_ 29(4):2047–2064, 2015.
  * [5] G. Cǎlinescu, A. Dumitrescu, H. J. Karloff and P. Wan. Separating points by axis-parallel lines. _International Journal Of Computational Geometry & Applications_ 15(6):575–590, 2005.
  * [6] E. Charbit, I. Charon, G. Cohen, O. Hudry and A. Lobstein. Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity. _Advances in Mathematics of Communications_ 2(4):403–420, 2008.
  * [7] B. S. Chlebus and S. H. Nguyen. On finding optimal discretizations for two attributes. Proceedings of the 1st International Conference on Rough Sets and Current Trends in Computing (RSCTC 1998). _Lecture Notes in Computer Science_ 1424:537–544, 1998.
  * [8] R. Crowston, G. Gutin, M. Jones, G. Muciaccia and A. Yeo. Parameterizations of test cover with bounded test sizes. _Algorithmica_ 74(1):367–384, 2016.
  * [9] S. R. Dev, S. Dey, F. Foucaud, R. Klasing and T. Lehtilä. The Red-Blue Separation problem on graphs. Proceedings of the 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022). _Lecture Notes in Computer Science_ 13270:285–298, 2022.
  * [10] S. Dey, F. Foucaud, S. C. Nandy and A. Sen. Discriminating codes in geometric setups. Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020). _Leibniz International Proceedings in Informatics_ 181, 24:1–24:16, 2020.
  * [11] K. M. J. De Bontridder, B. V. Halldórsson, M. M. Halldórsson, C. A. J. Hurkens, J. K. Lenstra, R. Ravi and L. Stougie. Approximation algorithms for the test cover problem. _Mathematical Programming Series B_ 98:477–491, 2003.
  * [12] I. Dinur and D. Steurer. Analytical approach to parallel repetition. _ACM Symposium on Theory of computing_ , 46:624–633, 2014.
  * [13] R. G. Downey and M. R. Fellows. _Parameterized Complexity_. Springer Verlag, 1999.
  * [14] P. Erdős. Some combinatorial, geometric and set theoretic problems in measure theory. In _Measure Theory Oberwolfach 1983_ , pp. 321–327. Springer, 1984.
  * [15] F. Foucaud, E. Guerrini, M. Kovše, R. Naserasr, A. Parreau and P. Valicov. Extremal graphs for the identifying code problem. _European Journal of Combinatorics_ 32(4):628–638, 2011.
  * [16] F. Foucaud and T. Lehtilä. Revisiting and improving upper bounds for identifying codes. _SIAM Journal on Discrete Mathematics_ 36(4):2619–2634, 2022.
  * [17] V. Gledel and A. Parreau. Identification of points using disks. _Discrete Mathematics_ 342:256–269, 2019.
  * [18] S. Gravier, R. Klasing and J. Moncel. Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs. _Algorithmic Operations Research_ 3(1):43–50, 2008.
  * [19] S. Har-Peled and M. Jones. On separating points by lines. _Discrete and Computational Geometry_ 63:705–730, 2020.
  * [20] T. W. Haynes, M. A. Henning and J. Howard. Locating and total dominating sets in trees. _Discrete Applied Mathematics_ 154(8):1293–1300, 2006.
  * [21] M. A. Henning and A. Yeo. Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs. _Graphs and Combinatorics_ 30(4):909–932, 2014.
  * [22] M. G. Karpovsky, K. Chakrabarty and L. B. Levitin. On a new class of codes for identifying vertices in graphs. _IEEE Transactions on Information Theory_ 44:599–611, 1998.
  * [23] S. Kratsch, T. Masařík, I. Muzi, M. Pilipczuk and M. Sorge. Optimal discretization is fixed-parameter tractable. Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pp. 1702-1719, 2021.
  * [24] J. Kujala and T. Elomaa. Improved algorithms for univariate discretization of continuous features. Proceedings of the 11th European Conference on Princi ples and Practice of Knowledge Discovery in Database (PKDD 2007). _Lecture Notes in Computer Science_ 4702:188–199, 2007.
  * [25] A. Lobstein. Watching systems, identifying, locating-dominating and discriminating codes in graphs: a bibliography. https://www.lri.fr/~lobstein/debutBIBidetlocdom.pdf
  * [26] N. Misra, H. Mittal and A. Sethia. Red-blue point separation for points on a circle. Proceedings of the 32nd Canadian Conference on Computational Geometry (CCCG 2020), pp. 266–272, 2020.
  * [27] B. M. E. Moret and H. D. Shapiro. On minimizing a set of tests. _SIAM Journal of Scientifical and Statistical Computation_ 6(4):983–1003, 1985.
  * [28] A. Rényi. On random generating elements of a finite Boolean algebra. _Acta Scientiarum Mathematicarum Szeged_ 22:75–81, 1961.
  * [29] C. A. Tovey. A simplified NP-complete satisfiability problem. _Discrete Applied Mathematics_ 8(1):85–89, 1984.
  * [30] R. Ungrangsi, A. Trachtenberg and D. Starobinski. An implementation of indoor location detection systems based on identifying codes. _Proceedings of Intelligence in Communication Systems, INTELLCOMM 2004_. _Lecture Notes in Computer Science_ 3283:175–189, 2004.
  * [31] V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. _Theory of Probability & Its Applications_ 16(2):264–280, 1971.
  * [32] I. E. Zvervich and V. E. Zverovich. An induced subgraph characterization of domination perfect graphs. _Journal of Graph Theory_ 20(3):375–395, 1995.