Even Kernels

Abstract

Given a graph $G = (V,E)$, an even kernel is a nonempty independent subset $V' \subseteq V$, such that every vertex of $G$ is adjacent to an even number (possibly 0) of vertices in $V'$. It is proved that the question of whether a graph has an even kernel is NP-complete. The motivation stems from combinatorial game theory. It is known that this question is polynomial if $G$ is bipartite. We also prove that the question of whether there is an even kernel whose size is between two given bounds, in a given bipartite graph, is NP-complete. This result has applications in coding and set theory.