Encompassing Computer Science Workshop 2015

Solving an NP hard problem of finding independent dominating sets of minimum cardinality for hypercube graphs of size 2^n with n=2^r-1

Not scheduled

Description

Let G = (V, E) be a hypercube of dimension n, that is, |V| = 2^n where V=GF(2)^n. There is an edge between u,v in G if the Hamming distance between u and v is one, i.e., d_H(u,v)=1. A subset S of V is said to dominate G if every node in V \S is adjacent to at least one node in S. Furthermore, if no two elements in S (that dominates G) are adjacent in G, then S is called an independent dominating set (IDS). The problem of finding minimum cardinality of S has been proved to be NP hard for arbitrary graphs and for hypercube graphs there are some greedy algorithms that give good estimates for the minimum cardinality of S, being closed to the lower bound. Using the Hamming codes and a simple modification technique applied to so-called root Boolean functions we derive the exact value (in a constructive way thus specifying a portion of these sets) of the minimum cardinality when n=2^r-1, for r >1.