Knights and Liars on Graphs
Paul Tabatabai and Dieter P. Gruber
Polymer Competence Center Leoben GmbH
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.
Full version: pdf,
(Concerned with sequences
Received July 19 2020; revised versions received March 21 2021; April 26 2021.
Published in Journal of Integer Sequences,
April 26 2021.
Journal of Integer Sequences home page