Perfect codes, NP-completeness, and towers of Hanoi graphs
By: Paul Cull, Ingrid Nelson.
Contributors: Nelson, Ingrid.; Oregon State University. Dept. of Computer Science.
Series: Technical report -- 98-20-01.; Technical report (Oregon State University. Dept. of Computer Science) -- 98-20-01.
Publisher: Oregon State University, Dept. of Computer Science
Published: 1998
Place of publication: Corvallis, OR
Language: eng
Number of pages: 26
Subjects: Error-correcting codes (Information theory); Graph theory.
Description: The set of codewords for a standard error-correcting code can be viewed as subset of the vertices of a hypercube. Two vertices are adjacent in a hypercube exactly when their Hamming distance is 1. A code is a perfect-error-correcting code if no two codewords are adjacent and every non-codeword is adjacent to exactly one codeword. Since such a code can be described using only vertices and adjacency, the definition applies to general graphs rather than only to hypercubes. How does one decide if a graph can support a perfect 1-error-correcting code? The obvious way to show that such a code exists is to display the code. On the other hand, it seems difficult to show that a graph does not support such a code. We show that this intuition is correct by showing that to determine if a graph has a perfect 1-error-correcting code is an NP-complete problem. The proof is by reduction from 3-SAT. To show that perfect codes in graphs is not vacuous, we give an infinite family of graphs so that each graph in the family has a perfect 1-error-correcting code. Our graphs are based on the Towers of Hanoi puzzle, so that, each vertex is a configuration of the puzzle and two vertices are adjacent when they are one legal move apart. We give a recursive construction which determines which vertices are codewords. There is a natural correspondence between the hypercube vertices and the binary strings, and there is a natural correspondence between Tower of Hanoi configuration and ternary strings. Our recursive construction also species which ternary strings are codewords. We characterize the codewords as the set of ternary strings with an even number of 1's and an even number of 2's. As part of this characterization, we show that there is essentially one perfect 1-error-correcting code for each n. There is a unique code when n is even, but the code is only unique up to a permutation of 0, 1, and 2 when n is odd. We show that error-correction can be accomplished by a finite state machine which passes over the ternary string twice, and that this machine is fixed independent of the length of the string. Encoding and decoding are the mappings between integers and codewords, and vice-versa. While algorithms for such mappings can be derived directly from the recursive construction, we show that encoding/decoding can be carried out by multiplication/division by 4 and error-correction. So error-correction, encoding, and decoding can all be done in time theta (n) for code strings of length n in these codes.
Notes: Cover title.

Includes bibliographical references (leaves [25]-[26]).

Also issued online.