Data reduction for connected dominating set
Navid Imani · Summit (Simon Fraser University) · 2008
Computationally difficult problems are ubiquitous. Although, sometimes approximations come in handy, accuracy is often a must and hence complexity of optimization seems unavoidable. The classical viewpoint to the complexity considers the instant size as the only factor for computing its hardness, but while dealing with hard problems, many input instances consist of easy parts and other parts that form the hard core of the problem. Therefore, it seems reasonable that before starting a cost-intensive algorithm, a polynomial-time preprocessing phase is executed in order to shrink the instance to the hard core kernel. In fixed-parameter algorithms, this is known as data reduction to a problem kernel. In this thesis, we study data reduction for the connected dominating set problem. In particular, we introduce a set of data reduction rules for the connected dominating set problem and prove that the problem admits a linear-size kernel in planar graphs.