Graph separators - a parameterized view

DSpace Repository


Dokumentart: Report
Date: 2001
Source: WSI ; 2001 ; 8
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Sonstige - Informations- und Kognitionswissenschaften
DDC Classifikation: 004 - Data processing and computer science
Keywords: Tübingen / Wilhelm-Schickard-Institut für Informatik
Other Keywords:
planar graph problems , fixed parameter tractability , parameterized complexity , graph separators , divide and conquer algorithms
Show full item record


Graph separation is a well-known tool to make (hard) graph problems accessible to a divide and conquer approach. We show how to use graph separator theorems in combination with (linear) problem kernels in order to develop fixed parameter algorithms for many well-known NP-hard (planar) graph problems. We coin the key notion of glueable select&verify graph problems and derive from that a prospective way of easily check wether a planar graph problem will allow for a fixed parameter algorithm of running time. Besides we introduce the novel cocept of "problem cores" that might serve as an alternative to problem kernels for devising parameterized algorithms. One of the main contributions of the paper is to exactly compute the base c of the exponential term and its dependence on the various parameters specified by the employed separator theorem and the underlying graph problem. We discuss several strategies to improve on the involved constant c. Our findings also give rise to studying further refinements of the complexity class FTP of fixed parameters tractable problems.

This item appears in the following Collection(s)