Structural parameterizations of hard graph problems
Item
-
Title
-
Structural parameterizations of hard graph problems
-
Identifier
-
d_2009_2013:5c40a621ec47:11267
-
identifier
-
11356
-
Creator
-
Lampis, Michail,
-
Contributor
-
Amotz Bar-Noy
-
Date
-
2011
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer science | Computational Complexity | Graph Algorithms | Parameterized Complexity
-
Abstract
-
In traditional computational complexity we measure algorithm running times as functions of one variable, the size of the input. Though in this setting our goal is usually to design polynomial-time algorithms, most interesting graph problems are unfortunately believed to require exponential time.;Parameterized complexity theory refines this by introducing a second variable, called the parameter, which is supposed to quantify the "hardness" of each specific instance. The goal now becomes to confine the combinatorial explosion to the parameter, by designing an algorithm that runs in time polynomial in the size of the input, though inevitably exponential in the parameter. This will allow us to tackle instances where the parameter value is much more modest than the input size, which will happen often if the parameter is chosen well.;In this work we deal with parameterized versions of intractable graph problems. Our focus will be structural parameterizations, meaning that the parameters we choose will be measures which attempt to quantify the complexity of a graph. The most important such measure in the literature is treewidth, a notion which quantifies how "tree-like" a graph is. Here, we will consider parameterizations by treewidth, but also by alternative measures of graph complexity such as vertex cover, or maximum degree.;Our results move in two directions: First, we study the computational complexity of structural parameterizations of several specific problems. In this vein we show hardness results for Maximum Path Coloring parameterized by measures such as treewidth and maximum degree; we present algorithms for two parameterizations of Vertex Cover; and we present algorithms and hardness results for three different parameterizations of the modal satisfiability problem.;Second, we study the algorithmic properties of structural parameters not with respect to a specific problem, but with respect to whole classes of problems. For undirected graphs we present algorithmic meta-theorems which show that large classes of problems are tractable when parameterized by vertex cover or max-leaf number. Our results strengthen a famous theorem due to Courcelle, for these special cases. For directed graphs we give hardness results for Hamiltonian Circuit and Max Di Cut which apply to essentially all the definitions of directed treewidth which have appeared in the literature, showing that none of them is as algorithmically potent as (undirected) treewidth.
-
Type
-
dissertation
-
Source
-
2009_2013.csv
-
degree
-
Ph.D.
-
Program
-
Computer Science
