Knights and Liars on Graphs

Paul Tabatabai and Dieter P. Gruber Polymer Competence Center Leoben GmbH Roseggerstraße 12 8700 Leoben Austria

                paul.tabatabai@pccl.at
                 dieter.gruber@pccl.at

Abstract

We discuss the Knights and Liars problem, which is the problem of maximizing the number of red vertices in a red-blue-coloring of the vertices on a square grid, such that for each red vertex, exactly half of its neighbors are red, and for each blue vertex, not exactly half of its neighbors are red. We discuss the generalization of the problem to arbitrary graphs and discuss three integer programming formulations, by which we give results for grid graphs, torus grid graphs, triangular grid graphs, and graphs corresponding to the transitive closure of the boolean lattice. We give a full combinatorial treatment for two-dimensional grid graphs whose shorter interval-size is less than seven. We further prove that the decision version of the generalized problem is NP-complete.

1 Introduction and definitions

The Knights and Liars problem was the topic of the mathematical competition Mathematical Marathon 140, which Letsko [11] organized. Letsko [11] has compiled an interesting summary of the results obtained by multiple contributors of the competition and added the corresponding sequence \underline{A289362} to the On-Line Encyclopedia of Integer Sequences (OEIS) [12]. The problem is a beautiful mathematical recreation and we find it fitting to introduce it in the following, riddle-esque way, which has been adapted slightly from Letsko’s comment on his OEIS entry.

Consider a finite square grid, on each point of which there is either a knight or a liar. A knight always speaks the truth, a liar always lies. All occupants of the grid make the same statement: “Exactly half of my (horizontal and vertical) neighbors are knights.” What is the maximum possible number of knights on the grid?

We give a more general problem definition, generalizing the Knights and Liars problem to arbitrary graphs.

Definition 1. For a (simple and undirected) graph G, call a vertex 2-coloring (we will call the colors red and blue) red-balanced if for each red vertex v, exactly half of v’s neighbors are red and if for each blue vertex w, not exactly half of w’s neighbors are red. We define the Knights and Liars number kl(G) to be the maximum number of red vertices in a red-balanced coloring of G.

The Knights and Liars number of a graph is well-defined, because every graph has at least one red-balanced coloring, namely the coloring, where all isolated vertices are red and all other vertices are blue.

The main focus of this paper is on grid graphs. In Definition 2, we define grid graphs formally and introduce some notation.

Definition 2. For d ≥ 2, let k_{1}, k_{2}, …, k_{d} ≥ 1 be integers. The grid graph (or just grid) G_{k_{1},...,k_{d}} is the graph whose vertex set is [k_{1}] × [k_{2}] × ⋯ × [k_{d}] and in which two vertices form an edge if they differ in exactly one coordinate and if the absolute difference in this coordinate is one. We call d the dimension of the grid and call the integers k_{i} the intervalsizes of the grid. Sometimes it is convenient notation to identify the grid graph with its vertex set and to write [k_{1}] × ⋯ × [k_{d}] instead of G_{k_{1},...,k_{d}}. If all interval-sizes are equal, say k_{1} = ⋯ = k_{d} = n, we may write [n]^{d} to denote the graph G_{n,...,n}.

If a vertex x = (x_{1}, …, x_{d}) has at least one coordinate j with x_{j} ∈ {1, k_{j}}, we say x belongs to the outer shell of G_{k_{1},...,k_{d}}. For d = 2, we call the outer shell the border of the grid. A vertex that does not belong to the outer shell is called interior vertex.

By thinking of knights as red vertices and liars as blue vertices, the original problem is equivalent to asking what the value of kl(G_{n,n}) is. Table 1 corresponds to the sequence \underline{A289362} and lists all currently known Knights and Liars numbers kl(G_{n,n}). The bold entries are our contribution. Figures 2 and 1 show red-balanced colorings of the grids G_{n,n} with the maximum possible number of red vertices for 4 ≤ n ≤ 18. We computed these colorings using the integer programming approach described in Section 4.1. For visibility reasons, edges are not drawn and blue vertices are drawn at a smaller size.

\begin{matrix}n & kl(G_{n,n}) & n & kl(G_{n,n}) & n & kl(G_{n,n}) \\ 1 & 1 & 7 & 10 & 13 & 58 \\ 2 & 0 & 8 & 16 & 14 & 68 \\ 3 & 0 & 9 & 28 & 15 & 88 \\ 4 & 4 & 10 & 32 & 16 & 98 \\ 5 & 8 & 11 & 40 & 17 & 110 \\ 6 & 10 & 12 & 46 & 18 & 126 \end{matrix}

Table 1: All known Knights and Liars numbers for two-dimensional square grid graphs.

kl(G_{4,4}) = 4  kl(G_{5,5}) = 8  kl(G_{6,6}) = 10

kl(G_{7,7}) = 10  kl(G_{8,8}) = 16  kl(G_{9,9}) = 28

kl(G_{10,10}) = 32  kl(G_{11,11}) = 40  kl(G_{12,12}) = 46

kl(G_{13,13}) = 58  kl(G_{14,14}) = 68  kl(G_{15,15}) = 88

Figure 1: Red-balanced colorings of G_{n,n} with the maximum possible number of red vertices for n = 4, …, 15.

kl(G_{16,16}) = 98  kl(G_{17,17}) = 110  kl(G_{18,18}) = 126

Figure 2: Red-balanced colorings of G_{n,n} with the maximum possible number of red vertices for n = 16, 17, and 18.

We will also be interested in torus grid graphs, which can be thought of as grid graphs in which the neighborhood relation allows for wrap-around at the borders of the grid. We define torus grid graphs formally in Definition 3.

Definition 3. For d ≥ 2, let k_{1}, k_{2}, …, k_{d} ≥ 1 be integers. The torus grid graph Tor_{k_{1},...,k_{d}} is the graph whose vertex set is [k_{1}] × [k_{2}] × ⋯ × [k_{d}] and in which two vertices form an edge if they differ in exactly one coordinate j and if the absolute difference in this coordinate is either 1 or k_{j} −1. We call d the dimension and the integers k_{i} the interval-sizes of Tor_{k_{1},...,k_{d}}.

Note that in contrast to grid graphs, d-dimensional torus grid graphs are 2d-regular.

1.1 Relation to the maximum density still life problem

The Knights and Liars problem on two-dimensional grid graphs is related to the maximum density still life (MDSL) problem. In Definition 4, we define Conway’s [1] Game of Life and still lifes. The wording is inspired by the definition given by Chu and Stuckey [4].

Definition 4 (Conway’s Game of Life and still lifes). Conway’s Game of Life is played on an infinite grid over discrete time steps. At each time step, each cell (vertex) has exactly one of the states alive or dead. The state of a cell c at time step t + 1 is determined by the number of live (orthogonal and diagonal) neighbors of c at time step t:

1. If c has exactly two live neighbors at time step t, then the state of c does not change at time step t + 1.

2. If c has exactly three live neighbors at time step t, then c is alive at time step t + 1.

3. If c has at least four or at most one live neighbors at time step t, then c is dead at time step t + 1.

If the above rules do not modify the state of any cell, the state of the grid is called a still life.

Other life-variants, and their corresponding still lifes can be defined by varying the number of possible states, the definition of neighborhood, and the cell rules. The density problem for Conway’s Game of Life on the infinite grid was solved by Elkies [7], who proved that the largest possible density of a still life in Conway’s Game of Life is 1/2. The finite version of this problem is defined in Definition 5.

Definition 5. The (n × n) maximum density still life (MDSL) problem asks for the largest possible density (or maximum possible number) of live cells in an n × n sub-region of a still life, such that all cells outside of the region are dead.

Formulating the Knights and Liars problem on two-dimensional grid graphs in terms of still lifes leads to the following set of cell rules, where only orthogonal neighborhood is considered:

1. If c has exactly two live neighbors at time step t, then c is alive at time step t + 1.

2. If c does not have exactly two live neighbors at time step t, then c is dead at time step t + 1.

The problem of finding the value kl(G_{n+2,n+2}) is the same as the n × n MDSL problem for the above cell rules, i.e., asking for the maximum number of live cells in an n × n sub-region of a still life with respect to the above rules, such that all cells outside of the region are dead. This holds, because in any red-balanced coloring of a finite grid (with side-lengths at least 3), all vertices on the border of the grid are blue (this important fact is discussed in more detail in Section 2). This means that the red-balanced colorings of finite grids (with side-lengths at least 3) are exactly the red-blue-colorings such that

1. every red interior vertex has exactly two red neighbors,

2. every blue interior vertex does not have exactly two red neighbors, and

3. all vertices on the border are blue.

The first two requirements correspond to the still life conditions. The third requirement corresponds to the requirement that all cells outside of the interior (non-border) region are dead and can not become alive. To see this, note that cells outside of the interior region have at most one orthogonal neighbor in the interior region.

Chu and Stuckey [4] solved the MDSL problem for Conway’s Game of Life for all values of n. They used different approaches for various ranges of n. For n ≤ 50, they used a constraint programming formulation in which they re-formulated the problem in terms of wastage, by assigning a wastage-score to each possible 3 × 3 pattern within a still life and proving that minimizing the total wastage is equivalent to maximizing the number of live cells. It remains open whether a similar re-formulation is possible for the Knights and Liars Problem (see Section 6 for a list of open problems). Chu and Stuckey [4] further list some previous computational techniques in the literature that have been used to attack the MDSL problem. Among those, we mention Bosch [2], who computed values for the MDSL problem for Conway’s Game of Life by using two integer programming formulations. Bosch [3] used integer programming to find maximum density still lifes for two other life variants. In Section 4.1 we discuss three integer program formulations IP1, IP2 and IP3 for computing values of the Knights and Liars problem. The formulation IP1 is a re-discovery of ideas used by Bosch [2], and IP3 has been adapted from Bosch [2], after the authors learned about this related work.

2 Upper bounds and trivially blue vertices

In the examples shown in Figures and 1 and 2, all vertices on the borders of the grids are blue. This is not by chance: For m, n ≥ 3, the border vertices of the grid G_{m,n} are blue in any red-balanced coloring. The degree-three vertices on the border each have three neighbors— an odd number—and must therefore be blue. The corner vertices of the grid must also be blue, because the majority of their neighbors (two out of two) have degree three and are blue by the previous argument. In fact, the generalization of this property holds for all grids. We prove this in Lemma 6.

Lemma 6. Let G = [k_{1}] × ⋯ × [k_{d}] be the grid graph of dimension d with interval-sizes k_{1}, …, k_{d} ≥ 3. Then, in any red-balanced coloring of G, all vertices of the outer shell of G are blue.

Proof. In this proof we say a vertex is blue to mean that it is blue in any red-balanced coloring of G. For a vertex x = (x_{1}, …, x_{d}) of G, and for each 1 ≤ i ≤ d, we define

δ(x_{i}) := min(x_{i} − 1, k_{i} − x_{i})

to be the distance of x_{i} to the end-point of the interval [k_{i}] that is closer to x_{i}. We further define dz(x) to be the number of indices i such that the distance δ(x_{i}) is zero. Note that the vertices x for which dz(x) > 0 are exactly the vertices of the outer shell of G, and that each vertex x has exactly 2d − dz(x) neighbors in G. It follows that the vertices in the set

S_{odd} := {x ∈ V (G) | dz(x) is odd}

have an odd number of neighbors in G and are thus blue. For d = 1, the set S_{odd} is the outer shell of G. For d ≥ 2, it remains to show that the vertices x for which dz(x) ≥ 2 is even are blue. We prove this for the case where d ≥ 3 is odd (the argument for even d is similar). For n ≥ 1, we define

S_{n} := {x ∈ V (G) | ∑_{i=1}^{d} δ(x_{i}) = n and dz(x) ≥ 2 is even} .

Let M be the largest integer such that S_{M} is non-empty (M is the sum of the d − 2 largest values ⌊k_{i}/2⌋). We prove by induction that for every 1 ≤ n ≤ M, all vertices in S_{n} are blue.

Let x = (x_{1}, …, x_{d}) be a vertex in S_{1}. We have dz(x) = d − 1 and δ(x_{j}) = 1 for exactly one index j. It follows that x has 2d − dz(x) = d + 1 neighbors, out of which d are in S_{odd}. The strict majority of neighbors of x is in S_{odd}, and it follows that x is blue.

Now let 2 ≤ n ≤ M. Assume that all vertices in S_{n−1} are blue. If S_{n} is empty, the assertion holds. Otherwise let x = (x_{1}, …, x_{d}) be a vertex in S_{n}. The vertex x has dz(x) ≥ 2 neighbors in S_{odd}. For each index i with δ(x_{i}) = ⌊k_{i}/2⌋ (this is the maximum value δ(x_{i}) can take), the vertex x has two neighbors in S_{n−1}. For each index i with δ(x_{i}) = 1, the vertex x has one neighbor in S_{odd}, and one neighbor in S_{n+1}. For each index i with 2 ≤ δ(x_{i}) ≤ ⌊k_{i}/2⌋ − 1, the vertex x has one neighbor in S_{n−1} and one neighbor in S_{n+1}. We showed that the strict majority of neighbors of x is in S_{odd} ∪ S_{n−1}, and it follows that x is blue.

The proof for even d works by starting the induction from the set S_{0} instead of from S_{1}.

For two-dimensional square grid graphs, Letsko [11] gives the bound kl(G_{n,n}) < \frac{2}{3}n^{2}. We use Letsko’s argument for this bound to show a tight version of the bound for regular graphs.

Proposition 7. For a regular graph G, we have the upper bound

kl(G) ≤ \frac{2}{3} |V (G)| .

Proof. Let k denote the degree of the vertices in G (i.e., G is k-regular). Consider a redbalanced coloring of G in which exactly r vertices are red. For each vertex v of G, let N_{red}(v) denote the number of red neighbors of v in this coloring. Since every vertex of G has k neighbors, we have

kr = ∑_{v∈V (G)} N_{red}(v).

Each red vertex has exactly k/2 red neighbors and each blue vertex has at most k red neighbors, giving the bound

kr = ∑_{v∈V (G)} N_{red}(v) ≤ r\frac{k}{2} + (|V (G)| − r) k,

from which the proposition follows.

We give some examples of graphs for which Proposition 7 holds with equality. For twodimensional torus grid graphs whose interval-sizes m and n are both multiples of three, we have kl(Tor_{m,n}) = \frac{2}{3}mn. A corresponding coloring can be constructed by tiling the 3 × 3 pattern whose main diagonal vertices are blue, and whose other vertices are red. Figure 3 shows a coloring of the torus grid graph Tor_{12,27} constructed this way.

Figure 3: A red-balanced coloring of the torus grid graph Tor_{12,27} in which the ratio of red vertices is 2/3.

Similarly, by tiling the same 3 × 3 pattern, the infinite two-dimensional grid graph can also be colored such that the ratio of red vertices is 2/3. This pattern and its optimality was also known to Elkies [7], who proved that if X is a subset of the infinite (4-neighborhood) grid such that every x ∈ X has at most two neighbors in X, then X has density at most 2/3.

The Knights and Liars number of the complete tri-partite graph K_{n,n,n} on 3n vertices is 2n. In the corresponding coloring, all vertices of one of the partition sets of K_{n,n,n} are blue, and the vertices of the other two partition sets are red.

As remarked by the anonymous referee, the bound in Proposition 7 is tight for the line graph L(G) of every cubic graph G that admits a perfect matching. To obtain a red-balanced coloring that colors two thirds of the vertices of L(G) red, take a perfect matching M of G, and color all vertices of L(G) corresponding to M blue, and all other vertices red. Figure 4 shows such a coloring of the line graph of the Petersen graph.

Figure 4: A red-balanced coloring of the line graph of the Petersen graph, in which 10 out of 15 vertices are red.

Because of Lemma 6, it is possible to generalize Letsko’s [11] argument for the bound kl(G_{n,n}) < \frac{2}{3}n^{2} to arbitrary grid graphs, and by doing a slightly more involved calculation, we obtain a bound that is an improvement for the special case of two-dimensional square grid graphs.

Proposition 8. Let G = [k_{1}] × ⋯ × [k_{d}] be the grid graph of dimension d with interval-sizes k_{1}, …, k_{d} ≥ 3. Then

kl(G) ≤ \frac{2}{3} ∏_{i=1}^{d} (k_{i} − 2) + \frac{2}{3d} ∑_{i=1}^{d} ∏_{j≠i}(k_{j} − 2).

Proof. Consider a red-balanced coloring of G in which exactly r vertices are red. For each vertex v of G, let N_{red}(v) denote the number of red neighbors of v in this coloring. Since every red vertex has 2d neighbors in G (this follows from Lemma 6), we have

2dr = ∑_{v∈V (G)} N_{red}(v).

Every red vertex has exactly d red neighbors and every blue vertex in the interior of G has at most 2d red neighbors. Since all red vertices are in the interior of the grid, the number of blue vertices in the interior of the grid is ∏_{i=1}^{d} (k_{i} − 2) − r. Every (blue) vertex x = (x_{1}, …, x_{d}) of the outer shell for which x_{j} ∈ {1, k_{d}} for exactly one index j, can have at most one red neighbor. There are ∑_{i=1}^{d} 2 ∏_{j≠i}(k_{j} − 2) such vertices in the outer shell of G. All other vertices of the outer shell only have neighbors in the outer shell (which can not be red). From these arguments we obtain the bound

2dr = ∑_{v∈V (G)} N_{red}(v) ≤ dr + 2d (∏_{i=1}^{d} (k_{i} − 2) − r) + ∑_{i=1}^{d} 2 ∏_{j≠i}(k_{j} − 2),  (1)

from which the proposition follows.

For the case of two-dimensional square grids, Proposition 8 is the bound

kl(G_{n,n}) ≤ \frac{2}{3}n^{2} − 2n + \frac{4}{3} for n ≥ 3,

which is tight for n = 4 and n = 5. For large n, we can get close to a red-vertex ratio of 2/3, in the following sense: Letsko [11] gives a construction by Sergei Polovinkin, showing that for every 0 < α < 2/3, there exists a natural number n_{α} such that kl(G_{n_{α},n_{α}}) ≥ αn_{α}^{2}.

We proved in Lemma 6 that the vertices of the outer shell of a grid graph are blue in any red-balanced coloring. The main argument we used in the proof was that if the majority of neighbors of a vertex x is blue in any red-balanced coloring, the vertex x must also be blue in any red-balanced coloring. This immediately leads to the following simple method for finding vertices that are blue in any red-balanced coloring for arbitrary graphs G. First, let B_{0} be the set of odd-degree vertices of G. Then, iteratively for i ≥ 1, define B_{i} as the union of B_{i−1} and the set of vertices of G whose strict majority of neighbors is in B_{i−1}. Stop as soon as B_{j} = B_{j−1} for some j ≥ 1 and call the resulting set the trivially blue vertices of G. For two-dimensional grid graphs, B_{0} is the set of degree-three vertices of the border of the grid and B_{1} is the set of all border vertices (including corner vertices).

Graphs consisting only of trivially blue vertices have Knights and Liars number zero. Examples of such graphs are the following:

• Graphs in which every vertex has an odd number of neighbors, such as the complete graph on an even number of vertices and hypercubes of odd dimension.

• The star graph S_{k} for k ≥ 3.

• Grid graphs in which at least one interval-size is three.

• Rooted trees with the property that each vertex in the second-to-last level has at least two leaves.

Trivially blue vertices can be thought of as vertices that must be colored blue “for simple reasons”. In fact, there are graphs without trivially blue vertices whose Knights and Liars number is zero. Figure 5 shows an example of a 4-regular graph on eight vertices for which only the all-blue coloring is red-balanced.

Figure 5: A 4-regular graph G with kl(G) = 0.

3 Results for grids G_{m,n} with m ≤ 6

We discuss the Knights and Liars problem for the non-square grid graph G_{m,n} for m ≤ 6. For m = 1, the grid is a path. In a path with a red-balanced coloring, red vertices can only appear in pairs of consecutive positions. Two such pairs must be separated by exactly one blue vertex. The end-points of the path have degree one and must be blue. It follows that kl(P_{3k+1}) = 2k for k ≥ 1, and kl(P_{n}) = 0 for all other n ≥ 2. Figure 6 shows a red-balanced coloring of the path on 16 vertices.

Figure 6: A red-balanced coloring of the path P_{16} with ten red vertices.

For m = 2, only the four corner vertices of the grid have even degree. For n ≥ 3, coloring the corner vertices of G_{2,n} red leads to a red-balanced coloring, and it follows that kl(G_{2,n}) = 4 for all n ≥ 3. For m = 3, we have kl (G_{3,n}) = 0 for all n, because G_{3,n} consists of trivially blue vertices only.

We show that for 4 ≤ m ≤ 6, finding a red-balanced coloring with the maximum number of red vertices is equivalent to a packing problem. For m = 4 (and n ≥ 4), in a red-balanced coloring of G_{4,n}, the only possible connected subgraph formed by red vertices are 4-cycles of interior vertices of the grid. The border vertices of the grid must be blue, and each pair of neighboring 4-cycles must be separated by at least two columns of blue vertices. This can be viewed as each 4-cycle being enclosed by at least one of its own blue columns on both its left and its right. Thus, for every four columns in the grid, we can color four vertices red and it follows that for all n ≥ 4, we have

kl (G_{4,n}) = 4 ⌊\frac{n}{4}⌋ .

Figure 7 shows a red-balanced coloring of the grid G_{4,15} with the maximum possible number of red vertices.

Figure 7: A red-balanced coloring of the grid G_{4,15} with 12 red vertices.

For m = 5 (and n ≥ 5), we can argue similarly as in the case m = 4, but now three different red-colored structures are possible. The possible sub-colorings are shown in Figure 8. Note that for m = 5, a cycle of red vertices enclosing more than two blue vertices can not occur in a red-balanced coloring, because there is a blue vertex with two red and two blue neighbors in this pattern.

Figure 8: The three possible patterns of red vertices (up to vertical symmetry of the first pattern) in a red-balanced coloring the grid G_{5,n}.

The three possible configurations contribute 4, 8, and 10 red vertices, respectively. The problem can thus be solved by maximizing 4x+8y+10z such that x, y and z are nonnegative integers with 4x + 5y + 6z ≤ n.

For m = 6 (and n ≥ 6), the relevant configurations are shown in Figure 9.

Figure 9: The two relevant patterns (up to vertical shifts of the first pattern) of red vertices in a red-balanced coloring the grid G_{6,n}.

The remaining possible patterns—an 8-cycle of blue vertices enclosing a blue vertex and a rotated version of the 10-cycle from the case m = 5—are strictly worse than the 10-cycle pattern and can thus be ignored. Note that two vertically shifted 4-cycles of red vertices can now neighbor each other with just a single blue column separating them, but the resulting pattern is strictly worse than the 10-cycle pattern and can thus be ignored as well. For n ≥ 6, we have

kl(G_{6,n}) = \begin{cases}10k + 4, & if n = 5k + 4; \\ 10k, & if n = 5k + r, where r ≤ 3. \end{cases}

The problem is more difficult for m, n ≥ 7. Figures 10 and 11 show examples of redbalanced colorings with the maximum number of red vertices for grids with m = 7 and m = 8.

Figure 10: A coloring of G_{7,32} with the maximum possible number of red vertices.

Figure 11: A coloring of G_{8,32} with the maximum possible number of red vertices.

4 Exact values for the Knights and Liars problem

In this section, we discuss integer programming formulations for computing a red-balanced coloring with the maximum possible number of red vertices for arbitrary graphs. We were especially interested in computing Knights and Liars numbers for graph classes with highly regular structures and consisting of few trivially blue vertices. In addition to the newly obtained Knights and Liars numbers for square grids, we give results for non-square and higher-dimensional grid graphs, torus grid graphs, triangular grid graphs, and graphs corresponding to the transitive closure of the boolean lattice.

4.1 Integer programming formulations

Let G be a (simple and undirected) graph. For a vertex v of G, let N(v) denote the set of neighbors of v in G and write deg(v) for the degree of v in G. Let V_{even}(G) and V_{odd}(G) denote the set of vertices of even, and odd degree of G, respectively.

For each vertex v of G, we define a binary variable x_{v} encoding whether v is colored red. Vertices of odd degree must be colored blue:

x_{v} = 0 for each v ∈ V_{odd}(G)  (2)

If a vertex of even degree is red, exactly half of its neighbors must be red:

x_{v} = 1 implies ∑_{w∈N(v)} x_{w} = \frac{deg(v)}{2} for each v ∈ V_{even}(G)  (3)

We say a vertex of even degree has high saturation if the strict majority of its neighbors is red and that is has low saturation if the strict minority of its neighbors is red. If a vertex of even degree is blue, it must have either high or low saturation:

x_{v} = 0 implies ( ∑_{w∈N(v)} x_{w} ≥ \frac{deg(v)}{2} + 1 or ∑_{w∈N(v)} x_{w} ≤ \frac{deg(v)}{2} − 1)  (4)
for each v ∈ V_{even}(G)

There are multiple ways to model (4) as a set of linear integer constraints. In the first approach, we introduce binary variables H_{v} and L_{v} for every vertex v of even degree in G. These variables are used to imply that a vertex has high or low saturation, respectively. The implication (4) is equivalent to the conjunction of the implications (5)–(7).

x_{v} = 0 implies H_{v} + L_{v} = 1 for each v ∈ V_{even}(G).  (5)
H_{v} = 1 implies ∑_{w∈N(v)} x_{w} ≥ \frac{deg(v)}{2} + 1 for each v ∈ V_{even}(G).  (6)

L_{v} = 1 implies ∑_{w∈N(v)} x_{w} ≤ \frac{deg(v)}{2} − 1 for each v ∈ V_{even}(G).  (7)

We model the implications (3) and (5)–(7) as linear inequalities, resulting in the integer program IP1. It is easy to see that (3) is equivalent to the conjunction of (9) and (10), that (5) is equivalent to the conjunction of (11) and (12), and that (6) and (7) are equivalent to (13) and (14), respectively.

(IP1) max. ∑_{v∈V (G)} x_{v}
subject to x_{v} = 0  for each v ∈ V_{odd}(G). (8)
∑_{w∈N(v)} x_{w} ≤ deg(v) − \frac{deg(v)}{2}x_{v}  for each v ∈ V_{even}(G). (9)

∑_{w∈N(v)} x_{w} ≥ \frac{deg(v)}{2}x_{v}  for each v ∈ V_{even}(G). (10)
H_{v} + L_{v} ≤ 1 + x_{v}  for each v ∈ V_{even}(G). (11)
H_{v} + L_{v} ≥ 1 − x_{v}  for each v ∈ V_{even}(G). (12)
∑_{w∈N(v)} x_{w} ≥ (\frac{deg(v)}{2} + 1) H_{v}  for each v ∈ V_{even}(G). (13)

∑_{w∈N(v)} x_{w} ≤ deg(v) − (\frac{deg(v)}{2} + 1) L_{v}  for each v ∈ V_{even}(G). (14)
H_{v}, L_{v} ∈ {0, 1}  for each v ∈ V_{even}(G). (15)
x_{v} ∈ {0, 1}  for each v ∈ V (G).

Note that the constraint (11) can optionally be dropped, because (5) can be replaced by

x_{v} = 0 implies H_{v} + L_{v} ≥ 1 for each v ∈ V_{even}(G).

Bosch [2] gives integer programming formulations for solving instances of the maximum density still life problem for Conway’s Game of Life. The integer programming formulation IP1 is a re-discovery of ideas used by Bosch. Bosch uses constraints similar to (9)–(10) and (12)–(14) to model the cell rules in Conway’s Game of Life. Bosch does not use the optional constraint. To obtain the Knights and Liars equivalent closest to Bosch’s formulation, all occurrences of the auxiliary variables H_{v} and L_{v} in IP1 are replaced by their negations 1−H_{v} and 1 − L_{v} respectively. This can be viewed as x_{v} = 0 forcing at least one of L_{v} or H_{v} to be zero, H_{v} = 0 forcing ∑_{w∈N(v)} x_{w} ≥ \frac{deg(v)}{2} + 1, and L_{v} = 0 forcing ∑_{w∈N(v)} x_{w} ≤ \frac{deg(v)}{2} − 1.

We give an alternative integer programming formulation IP2, which uses only a single auxiliary variable for each vertex of even degree to model the or in (4).

(IP2) max. ∑_{v∈V (G)} x_{v}
subject to (8), (9), (10)
∑_{w∈N(v)} x_{w} ≤ (\frac{deg(v)}{2} − 1) + (\frac{deg(v)}{2} + 1) (A_{v} + x_{v}) for each v ∈ V_{even}(G). (16)

∑_{w∈N(v)} x_{w} ≥ (\frac{deg(v)}{2} + 1) (A_{v} − x_{v})  for each v ∈ V_{even}(G). (17)

A_{v} ∈ {0, 1}  for each v ∈ V_{even}(G).
x_{v} ∈ {0, 1}  for each v ∈ V (G).

The constraint (16) models

(x_{v} = 0 and A_{v} = 0) implies ∑_{w∈N(v)} x_{w} ≤ (\frac{deg(v)}{2} − 1) for each v ∈ V_{even}(G),

and the constraint (17) models

(x_{v} = 0 and A_{v} = 1) implies ∑_{w∈N(v)} x_{w} ≥ (\frac{deg(v)}{2} + 1) for each v ∈ V_{even}(G).

Bosch [2] gives another a way to model (the Game of Life still life equivalent of) (4), which uses no auxiliary variables, but has—depending on the degrees of the vertices of G—a large number of constraints. We call the Knights and Liars equivalent of this idea IP3.

(IP3) max. ∑_{v∈V (G)} x_{v}
subject to (8), (9), (10)
− x_{v} + ∑_{w∈S} x_{w} − ∑_{w∈N(v)\S} x_{w} ≤ \frac{deg(v)}{2} − 1  for each v ∈ V_{even}(G)
and each S ⊂ N(v) with |S| = \frac{deg(v)}{2}. (18)
x_{v} ∈ {0, 1}  for each v ∈ V (G).

The constraint (18) models that for each subset S ⊂ N(v) with |S| = deg(v)/2, x_{v} = 1 implies that S can not be exactly the set of all red neighbors of v.

Benchmarking the solving speed using the formulations IP1, IP2 and IP3 and the impact of negating the auxiliary variables and/or using the optional constraint in IP1 is difficult, because solvers are very sensitive to small structural changes, even such changes as adding the constraints in different order. However, IP3 seems to be not well suited for graphs with large degrees, for which IP1 and IP2 perform significantly better.

Python programs for generating and solving the above integer programming formulations are available at the first author’s Github repository [13]. We give implementations using both the official Python-API gurobipy of the commercial state-of-the art MIP solver Gurobi [9], as well as COIN-OR’s [5] library python-mip, which allows to use the open source solver CBC, which is also maintained by COIN-OR. The repository also contains integer programs that use Gurobi’s ability to natively model implications as indicator constraints. The repository is a living collection of formulations and approaches to the Knights and Liars problem and will be continuously updated.

Optionally, the concept of trivially blue vertices discussed in Section 2 can be used to adapt the above formulations. The set of constraints x_{v} = 0 for each v ∈ V_{odd}(G) can be replaced by the set of constraints x_{v} = 0 for each trivially blue vertex v, and all other constraints need only be specified for vertices that are not trivially blue.

4.2 Results

As mentioned in Section 1, we managed to calculate the new Knights and Liars numbers kl(G_{16,16}) = 98, kl(G_{17,17}) = 110 and kl(G_{18,18}) = 126. These numbers were added to \underline{A289362} by the first author. Using a desktop computer equipped with an AMD 3700X processor and 32 gigabytes of memory, calculating kl(G_{17,17}) using IP1 took approximately six hours, and finding kl(G_{18,18}) took approximately six days.

For 16 ≤ n ≤ 18, the Gurobi solver instance found red-balanced colorings with the maximum possible number of red vertices relatively quickly, and spent most of the computation time proving optimality. For this reason, we believe that the colorings we found for n = 19 and n = 20 are best possible. The colorings—which are certificates for kl(G_{19,19}) ≥ 144 and kl(G_{20,20}) ≥ 160—are shown in Figure 12.

kl(G_{19,19}) ≥ 144  kl(G_{20,20}) ≥ 160

Figure 12: Red-balanced colorings of G_{19,19} and G_{20,20}. We conjecture that these colorings have the maximum possible number of red vertices.

We calculated Knights and Liars numbers and lower bounds for the two-dimensional grid graph G_{m,n} for 7 ≤ m ≤ n ≤ 20. Our results are listed in Table 2. The case min{m, n} ≤ 6 is discussed in Section 3.

We calculated Knights and Liars numbers for the grid graph [n]^{d} for small values of n and d. The corresponding Knights and Liars numbers and lower bounds are listed in Table 3. Note that the grid graphs [2]^{d} are the d-dimensional hypercubes. The hypercubes of odd dimension consist of vertices of odd degree only and thus their Knights and Liars number is zero. For the 8-dimensional hypercube, we obtained the bound 72 ≤ kl([2]^{8}) ≤ 165. A red-balanced coloring of the 4-dimensional hypercube is shown in Figure 13.

\begin{matrix}m/n & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ 7 & 10 & 12 & 14 & 20 & 20 & 20 & 22 & 24 & 30 & 30 & 30 & 32 & 34 & 40 \\ 8 & - & 16 & 26 & 26 & 30 & 30 & 38 & 38 & 40 & 40 & 50 & 52 & 52 & 56 \\ 9 & - & - & 28 & 30 & 32 & 34 & 40 & 40 & 44 & 52 & 54 & 56 & 60 & 64 \\ 10 & - & - & - & 32 & 36 & 42 & 44 & 46 & 50 & 52 & 58 & 62 & 64 & 70 \\ 11 & - & - & - & - & 40 & 42 & 50 & 52 & 54 & 60 & 64 & 68 & 70 & 80 \\ 12 & - & - & - & - & - & 46 & 52 & 62 & 62 & 68 & 74 & 78 & 82 & 86 \\ 13 & - & - & - & - & - & - & 58 & 64 & 68 & 76 & 80 & 86 & 92 & 98 \\ 14 & - & - & - & - & - & - & - & 68 & 74 & 80 & 88 & 92 & 96 & ≥ 104 \\ 15 & - & - & - & - & - & - & - & - & 88 & 90 & 96 & 104 & 108 & ≥ 116 \\ 16 & - & - & - & - & - & - & - & - & - & 98 & 106 & 112 & ≥ 120 & ≥ 124 \\ 17 & - & - & - & - & - & - & - & - & - & - & 110 & 120 & ≥ 126 & ≥ 132 \\ 18 & - & - & - & - & - & - & - & - & - & - & - & 126 & ≥ 134 & ≥ 140 \\ 19 & - & - & - & - & - & - & - & - & - & - & - & - & ≥ 144 & ≥ 150 \\ 20 & - & - & - & - & - & - & - & - & - & - & - & - & - & ≥ 160 \end{matrix}

Table 2: Knights and Liars numbers and lower bounds for G_{m,n} for 7 ≤ m ≤ n ≤ 20.

n  1 2 3 4 5  6  7  8  9  10
kl([n]^{3}) 1 0 0 8 16  24  64 112 ≥ 160 ≥ 216
kl([n]^{4}) 1 6 0 16 16 168 ≥ 256 ?  ?  ?
kl([n]^{5}) 1 0 0 32 128 ≥ 256  ?  ?  ?  ?
kl([n]^{6}) 1 40 0 64 512  ?  ?  ?  ?  ?

Table 3: Knights and Liars numbers for higher-dimensional grids.

Figure 13: A red-balanced coloring of the 4-dimensional hypercube with six red vertices.

We give some Knights and Liars numbers for two-dimensional torus grid graphs in Table 4. As discussed in Section 1, two-dimensional torus grid graphs whose interval-sizes are both multiples of three admit a red-balanced coloring in which two thirds of all vertices are red. The corresponding Knights and Liars numbers are marked in bold.

\begin{matrix}m/n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ 1 & 1 & 0 & 2 & 0 & 0 & 4 & 0 & 0 & 6 & 0 & 0 & 8 & 0 & 0 & 10 & 0 & 0 & 12 \\ 2 & - & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & - & - & 6 & 4 & 5 & 12 & 7 & 14 & 18 & 18 & 20 & 24 & 24 & 26 & 30 & 30 & 32 & 36 \\ 4 & - & - & - & 6 & 6 & 12 & 10 & 20 & 12 & 18 & 16 & 24 & 18 & 32 & 22 & 40 & 24 & 38 \\ 5 & - & - & - & - & 15 & 10 & 12 & 14 & 15 & 30 & 18 & 20 & 22 & 24 & 45 & 28 & 29 & 30 \\ 6 & - & - & - & - & - & 24 & 14 & 28 & 36 & 36 & 40 & 48 & 48 & 52 & 60 & 60 & 64 & 72 \\ 7 & - & - & - & - & - & - & 22 & 20 & 29 & 29 & 32 & 32 & 36 & 63 & 46 & 46 & 50 & 58 \\ 8 & - & - & - & - & - & - & - & 40 & 42 & 36 & 46 & 60 & 48 & 64 & 70 & 80 & 74 & 84 \\ 9 & - & - & - & - & - & - & - & - & 54 & 54 & 60 & 72 & 72 & 78 & 90 & 90 & 96 & 108 \\ 10 & - & - & - & - & - & - & - & - & - & 60 & 46 & 72 & 64 & 68 & 90 & 82 & 82 & 108 \\ 11 & - & - & - & - & - & - & - & - & - & - & 77 & 80 & 70 & 86 & 100 & 92 & 106 & 120 \\ 12 & - & - & - & - & - & - & - & - & - & - & - & 96 & 96 & 104 & 120 & 120 & 128 & 144 \\ 13 & - & - & - & - & - & - & - & - & - & - & - & - & 104 & 88 & 120 & ≥ 102 & ≥ 110 & 144 \\ 14 & - & - & - & - & - & - & - & - & - & - & - & - & - & 126 & 130 & 128 & 138 & 156 \\ 15 & - & - & - & - & - & - & - & - & - & - & - & - & - & - & 150 & 150 & 160 & 180 \\ 16 & - & - & - & - & - & - & - & - & - & - & - & - & - & - & - & 160 & ≥ 152 & 180 \\ 17 & - & - & - & - & - & - & - & - & - & - & - & - & - & - & - & - & 187 & 192 \\ 18 & - & - & - & - & - & - & - & - & - & - & - & - & - & - & - & - & - & 216 \end{matrix}

Table 4: Knights and Liars numbers and lower bounds for Tor_{m,n} for 3 ≤ m ≤ n ≤ 18.

We also calculated Knights and Liars numbers and lower bounds for the three-dimensional torus grid graphs Tor_{n,n,n} for 1 ≤ n ≤ 5. The numbers are listed in Table 5.

\begin{matrix}n & kl(Tor_{n,n,n}) \\ 1 & 0 \\ 2 & 0 \\ 3 & 18 \\ 4 & 40 \\ 5 & ≥ 52 \end{matrix}

Table 5: Knights and Liars numbers for the three-dimensional torus grid graphs Tor_{n,n,n} for n = 1, …, 5

For n ≥ 1, let T_{n} denote the triangular grid graph. The triangular grid graph T_{n} is the graph whose vertices are the triples (i, j, k) with i, j, k ≥ 0 and i + j + k = n and whose edges are the pairs of vertices whose sum of absolute differences of coordinates is two [14, Ex. 8.3.22, pp. 390–391]. We calculated the Knights and Liars numbers kl(T_{n}) for 1 ≤ n ≤ 100 and observed that kl(T_{n}) is equal to \underline{A007980}(n) for these values of n. Table 6 lists the first 40 Knights and Liars numbers of the triangular grid graphs. The sequence \underline{A007980} is defined as the expansion of

\frac{1 + x^{2}}{(1 − x)^{2}(1 − x^{3})}

and has a multitude of other interpretations. For all n ≥ 1, we have \underline{A007980}(n) = ⌈\frac{(n+1)(n+2)}{3}⌉, as given by Paul Boddington on the OEIS page of the sequence. For all n ≤ 100, we found red-balanced colorings with the maximum possible number of red vertices, in which every blue vertex has red neighbors only, leading to the aesthetically pleasing pattern shown in the left coloring of Figure 14. For some n, we searched for—and found—alternative redbalanced colorings with the maximum possible number of red vertices, for which there are blue vertices with blue neighbors. The right coloring of Figure 14 is an example of such a coloring.

Figure 14: Two different red-balanced colorings of the triangular grid graph T_{16} with the maximum possible number of red vertices.

n kl(T_{n}) n kl(T_{n}) n kl(T_{n}) n kl(T_{n}) n kl(T_{n})
1  2  9  37 17 114 25 234 33 397
2  4  10 44 18 127 26 252 34 420
3  7  11 52 19 140 27 271 35 444
4 10 12 61 20 154 28 290 36 469
5 14 13 70 21 169 29 310 37 494
6 19 14 80 22 184 30 331 38 520
7 24 15 91 23 200 31 352 39 547
8 30 16 102 24 217 32 374 40 574

Table 6: Knights and Liars numbers for triangular grid graphs T_{n} for 1 ≤ n ≤ 40.

For n ≥ 1, let B_{n} denote the undirected graph corresponding to the transitive closure of the boolean lattice. The set of vertices of B_{n} is the powerset of {1, …, n} and two sets A ≠ B form an edge if A ⊂ B or B ⊂ A. Table 7 lists the Knights and Liars numbers of B_{n} for 1 ≤ n ≤ 6. Figure 15 shows the 34 red vertices in the red-balanced coloring of B_{6} we found. We omit curly brackets and commas to make the representation more compact. We were not able to find a red-balanced coloring of B_{7} with at least one red vertex. It remains open whether kl(B_{7}) > 0.

\begin{matrix}n & kl(B_{n}) \\ 1 & 0 \\ 2 & 0 \\ 3 & 6 \\ 4 & 0 \\ 5 & 18 \\ 6 & 34 \end{matrix}

Table 7: Knights and Liars numbers kl(B_{n}) for n = 1, …, 6

1 2 3 4 5 13 16 24 25 34 56 123 125 135 145 146 156 234 235 236 246 346 456 1236 1245 1246 1345 2356 3456 12346 12356 12456 13456 23456

Figure 15: The 34 red vertices in a best-possible red-balanced coloring of B_{6}.

5 The Knights and Liars problem is NP-complete

Let KL be the decision problem of deciding whether a given graph has a red-balanced coloring in which at least k vertices are red. In order to make this section self-contained, we repeat the definition of red-balanced. A red-balanced coloring of a graph G is a mapping f : V (G) → {red, blue}, such that for each red vertex, exactly half of its neighbors are red, and for each blue vertex, not exactly half of its neighbors are red.

KL

Instance: A graph G and an integer k.
Question: Does a red-balanced coloring of G with at least k red vertices exist?

In Theorem 9, we prove that KL is NP-complete. To show NP-hardness we will give a polynomial-time reduction from the exact cover by 3-sets (X3C) problem—which Karp [10] proved to be NP-complete—to KL.

X3C

Instance: A set U whose cardinality is a multiple of three, and a set F of 3-subsets of

U.

Question: Does a family S ⊆ F with ˙⋃_{D∈S}D = U exist?

Theorem 9. The decision problem KL is NP-complete.

Proof. Clearly, whether a given coloring is red-balanced can be verified in polynomial time, and it follows that KL is in NP. To show that KL is NP-hard, we give a polynomial-time reduction from X3C to KL.

Let (U, F) be a problem instance of X3C. We will define a problem instance (G, k) of KL, such that X3C(U, F) has an affirmative answer if and only if KL(G, k) does.

Construction of the KL instance. We construct an instance (G, k) for KL, by starting from the empty graph G. In this proof we will call vertices of degree one leaves and all other vertices inner vertices. In figures sketching parts of the construction, we will depict leaf vertices of G as blue, because they must be blue in any red-balanced coloring of G.

Let T be the graph consisting of a cycle of length three, in which each vertex is connected to three leaf vertices. For every 3-set X ∈ F, we add a copy T_{X} of T to G and identify each element a ∈ X with a unique inner vertex of T_{X}, by giving the name (a, X) to that vertex. Figure 16 depicts this construction.

Figure 16: For each X ∈ F, we add a copy T_{X} of the graph T to G.

Let M = max{|U|, |F|}. We define LC (short for “large cycle”) to be the graph consisting of a cycle of M^{2} +3M vertices, in which one of the vertices is connected to three leaf vertices, and all other vertices are connected to two leaf vertices. For each u ∈ U, we add a copy LC_{u} of LC to G. Figure 17 depicts this construction.

For each u ∈ U, we add an auxiliary vertex Z_{u} to G. This vertex acts as an intermediate connection point between LC_{u} and each of the subgraphs T_{X} for which u ∈ X. We add an edge between the three-leaf-vertex of LC_{u} and Z_{u}. We add edges between Z_{u} and each of the vertices (u, X^{(1)}), …, (u, X^{(m)}), where X^{(1)}, …, X^{(m)} are the 3-sets containing u. Note that Z_{u} has exactly one neighbor in each of the subgraphs T_{X^{(1)}}, …, T_{X^{(m)}}. If 1 ≤ m ≤ 2, we connect 3 − m new leaf vertices to Z_{u}. If m ≥ 3, we add m − 3 copies of the graph K_{2} to G and add edges between Z_{u} and one of the vertices of each copy of K_{2}. Figure 18 sketches this construction for the case m ≥ 3.

Figure 17: For each u ∈ U, we add a copy LC_{u} of the graph LC to G. The graph LC consists of M^{2} + 3M inner vertices.

Figure 18: Sketch showing how the subgraph LC_{u} is connected to each of the subgraphs T_{X^{(1)}}, …, T_{X^{(m)}} for the case m ≥ 3.

We count the number of inner vertices of G that are not part of a copy of LC and show that this number is strictly bounded from above by M^{2} + 3M. For each X ∈ F, there are three inner vertices in the subgraph T_{X}. For each u ∈ U, the vertex Z_{u} is an inner vertex, and is connected to at most |F| − 3 copies of K_{2} (this upper bound is reached when u is member of every set in F), each having an inner vertex in G. The number of inner vertices not part of a copy of LC is thus bounded by

3|F| + |U| · (|F| − 2) < M^{2} + 3M.  (19)

We set k = |U| · (M^{2} + 3M). The motivation behind this choice of k is that a red-balanced coloring of G can only have at least k red vertices if all inner vertices of all copies of LC in G are colored red. This is explained in more detail in the second part of the proof.

Equivalence of the problem instances. We claim that G admits a red-balanced coloring with at least k red vertices, if and only if (U, F) has an exact 3-cover.

In any red-balanced coloring of G, the inner vertices of a copy of LC are monochromatic (all blue or all red). To see this, note that if an inner vertex of a copy of LC is red, then both its inner-vertex-neighbors must be red as well. By the same argument, the inner vertices of a copy of T are monochromatic in any red-balanced coloring.

First, consider the case where an exact 3-cover S for the instance (U, F) exists. We construct a red-balanced coloring of G with more than k red vertices. We color all leaves blue. For every u ∈ U, we color Z_{u} and all inner vertices of LC_{u} red. For every set X ∈ S, we color all inner vertices of T_{X} red and for every set X ∈ F \S, we color all inner vertices of T_{X} blue. If u is member of at least three sets in F, the vertex Z_{u} is connected to a number of copies of K_{2}. In each such copy of K_{2}, we color the vertex connected to Z_{u} red.

The number of red vertices in this coloring exceeds k, because there are k = |U| · (M^{2} + 3M) red vertices within the copies of LC alone. We show that this coloring is redbalanced, by checking every inner vertex of G.

• For each u ∈ U, the two-leaf inner vertices of LC_{u} are red and have two red neighbors (adjacent inner vertices in LC_{u}) and two blue neighbors (leaves). The three-leaf inner vertex of LC_{u} is red and has three red neighbors (the vertex Z_{u} and two adjacent inner vertices in LC_{u}) and three blue neighbors (leaves).

• For each u ∈ U, let X^{(1)}, … X^{(m)} be the 3-sets containing u. The vertex Z_{u} is red. If 1 ≤ m ≤ 2, Z_{u} has two red neighbors (the three-leaf-vertex of LC_{u} and (u, X), where X ∈ S is the unique set in S containing u) and two blue neighbors (3 − m leaves and the m − 1 vertices (u, X) for which X ∉ S). If m ≥ 3, Z_{u} has m − 1 red neighbors (m − 3 vertices in the copies of K_{2} connected to Z_{u}, the three-leaf-vertex of LC_{u} and (u, X), where X ∈ S is the unique set in S containing u) and m − 1 blue neighbors (the vertices (u, X) for which X ∉ S).

• Each inner vertex (u, X) for which u ∈ X ∈ S, is red and has three red neighbors (the vertex Z_{u} and two adjacent inner vertices in T_{X}) and three blue neighbors (leaves). Each inner vertex (u, X) for which u ∈ X ∉ S, is blue and has one red neighbor (the vertex Z_{u}) and five blue neighbors (three leaves and two adjacent inner vertices in T_{X}).

Next, consider the case where G has a red-balanced coloring with at least k red vertices. We show that the sets X ∈ F for which the inner vertices of the subgraph T_{X} are (all) red in this coloring form an exact 3-cover of F.

Because of the bound (19), and because each copy of LC is monochromatic, all inner vertices of each copy of LC are red (if a copy of LC was blue, there would not be enough inner vertices of G left to exceed k red vertices in G). It follows that, in particular, for each u ∈ U, the three-leaf vertex of LC_{u} is red. This further implies that Z_{u} is red (because the three-leaf vertex of LC_{u} has an equal number of red and blue neighbors). Let again X^{(1)}, …, X^{(m)} denote the sets containing u. If m ≥ 3, the vertex Z_{u} is connected to 3 − m copies of K_{2}. The inner vertices of these copies are red, because they have one blue neighbor (a leaf) and one red neighbor (the vertex Z_{u}).

We show that exactly one of the vertices (u, X^{(1)}), …, (u, X^{(m)}) is red. Since Z_{u} is red, Z_{u} has an equal number of red and blue neighbors. We count the red and blue neighbors of Z_{u}, excluding the vertices (u, X^{(1)}), …, (u, X^{(m)}):

• If m = 1, the vertex Z_{u} has two blue neighbors (two leaf vertices) and one red neighbor (the three-leaf vertex in LC_{u}).

• If m = 2, the vertex Z_{u} has one blue neighbor (a leaf vertex) and one red neighbor (the three-leaf vertex in LC_{u}).

• If m ≥ 3, the vertex Z_{u} has no blue neighbors and m − 2 red neighbors (the three-leaf vertex in LC_{u} and m − 3 in the the copies of K_{2} connected to Z_{u}).

In all cases, for Z_{u} to have an equal number of red and blue neighbors, exactly one of the vertices (u, X^{(1)}), …, (u, X^{(m)}) must be red.

It follows from the fact that for each X ∈ F, the inner vertices of T_{X} are monochromatic, that exactly one of the subgraphs T_{X^{(1)}}, …, T_{X^{(m)}} has red inner vertices. This means that for each u ∈ U, there exists exactly one set X ∈ F with u ∈ X, such that the inner vertices of T_{X} are red. It follows that the family of sets X for which the inner vertices of T_{X} are red form an exact 3-cover of (U, F).

Gonzales [8] showed that the exact cover by 3-sets problem remains NP-complete when restricted such that each element from the ground set appears in exactly three 3-sets. It follows from the construction in the proof of Theorem 9, that the decision problem KL remains NP-complete when restricted to graphs with maximum degree six.

Dyer and Frieze [6] showed that Planar X3C (i.e., X3C restricted such that the bipartite incidence graph between universe set U and set family F is planar) is NP-complete. It follows that KL remains NP-complete when restricted to planar graphs. This observation is due to Wulf [15].

6 Open problems and questions

We give a number of open problems and questions we encountered, which we hope will spark interest for future research on this topic.

1. Chu [4] computed values of the maximum density still life problem for small n by re-formulating the problem in terms of assigning wastage-scores to all possible 3 × 3 sub-patterns in a still life. Is a similar formulation possible for the Knights and Liars problem on square grids?

2. The decision problem discussed in Section 5 remains NP-complete when restricted to planar graphs and graphs with maximum degree six. Investigate for which other graph classes the problem remains NP-complete. Is the case k = 1—i.e., the problem of deciding whether a graph has a red-balanced coloring with at least one red vertex— NP-complete (suggested by the anonymous referee)? Is the problem restricted to subgraphs of (two-dimensional) grid graphs NP-complete (suggested by Stefan Lendl)? Is the chromatic number or chromatic index related to the hardness of the problem?

3. In Section 4.2 we observed that the sequence of Knights and Liars numbers of the triangular grid graphs equals the sequence \underline{A007980} for the initial 100 values. Find a nice argument to show that this holds for all n ≥ 1.

4. Study the generalization of the Knights and Liars problem to directed graphs, in which the directed Knights and Liars number is the maximum number of red vertices in a red-blue coloring such that for each red vertex, exactly half of its out-neighbors are red, and for each blue vertex, not exactly half of its out-neighbors are red. One can also ask for an edge-orientation of an undirected graph, such that the directed Knights and Liars number is maximized.

5. For the 8-dimensional hypercube Q_{8} = [2]^{8}, we were not able to determine the value of kl(Q_{8}). It would be of interest to see whether combinatorial arguments can be used to improve the bound 72 ≤ kl(Q_{8}) ≤ 165, which we obtained using the integer programming techniques described in Section 4.1.

6. We were not able to find a non-trivial red-balanced coloring (i.e., a coloring with at least one red vertex) of the graph B_{7} (defined in Section 4.2). Does such a coloring exist?

7. In Section 1 we gave an example of a 4-regular graph on eight vertices with Knights and Liars number zero. Do arbitrarily large connected k-regular graphs with Knights and Liars number zero exist for all k ≥ 2?

7 Acknowledgments

We would like to thank the anonymous referee for their helpful comments and suggestions and for pointing us towards related literature in the field of still lifes. Without these comments this paper would not be complete.

References

[1] E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 2: Games in Particular, Academic Press, 1982.

[2] R. Bosch, Integer programming and Conway’s Game of Life, SIAM Rev. 41 (1999), 594– 604.

[3] R. Bosch, Maximum density stable patterns in variants of Conway’s Game of Life, Oper. Res. Lett. 27 (2000), 7–11.

[4] G. Chu and P. J. Stuckey, A complete solution to the maximum density still life problem, Artificial Intelligence 184-185 (2012), 1–16.

[5] The COIN-OR Foundation, Computational Infrastructure for Operations Research

   (COIN-OR), 2020, https://www.coin-or.org.

[6] M. E. Dyer and A. M. Frieze, Planar 3DM is NP-complete, J. Algorithms 7 (1986), 174–184.

[7] N. D. Elkies, The still-life density problem and its generalizations, in P. Engel and H. Syta, eds., Voronoi’s Impact on Modern Science, Book I, Institute of Math., Kyiv, 1998, pp. 228–253.

[8] T. F. Gonzalez, Clustering to minimize the maximum intercluster distance, Theoret. Comput. Sci. 38 (1985), 293–306.

[9] Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual, 2021,

   https://www.gurobi.com.

[10] R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thatcher, eds., Complexity of Computer Computations, Plenum Press, 1972, pp. 85–103.

[11] V. Letsko, Mathematical Marathon 140, Volgograd State Pedagogical University, 2020,

   http://www-old.fizmat.vspu.ru/doku.php?id=marathon:problem_140.

[12] OEIS Foundation Inc. (2020), The On-Line Encyclopedia of Integer Sequences,

   https://oeis.org.

[13] P. Tabatabai, Knights and Liars, Github repository, 2021,

   https://github.com/tabatabai/knights-and-liars.

[14] D. B. West, Introduction to Graph Theory, Second edition, Prentice Hall, 2000.

[15] L. Wulf, Personal communication, 2021.

2010 Mathematics Subject Classification: Primary 05C15; Secondary 00A08, 90C10, 68Q25, 68Q80. Keywords: coloring, partition, grid, graph, maximization, integer programming, computational complexity, NP-completeness, cellular automata.

(Concerned with sequences \underline{A007980} and \underline{A289362}.)

Received July 19 2020; revised versions received March 21 2021; April 26 2021. Published in Journal of Integer Sequences, April 26 2021.

Return to Journal of Integer Sequences home page.