Physical Zero-knowledge Proofs for Flow Free, Hamiltonian Cycles, and Many-to-many k-disjoint Covering Paths

Abstract

In this paper we describe protocols which use a standard deck of cards to provide a perfectly sound zero-knowledge proof for Hamiltonian cycles and Flow Free puzzles. The latter can easily be extended to provide a protocol for a zero-knowledge proof of many-to-many k-disjoint path coverings.