Computation of Treespan. A Generalization of Bandwidth to Treelike Structures
Abstract
Motivated by a search game, Fomin, Heggernes and Telle [Algorithmica, 2005]
defined the graph parameter treespan, a generalization of the well studied
parameter bandwidth. Treespan is the maximum number of appearances of
a vertex in an ordered tree decomposition, i.e. a tree decomposition intro-
ducing at most one new vertex in each bag. In this thesis, we investigate the
computational tractability of the problem Treespan, which aims to decide
whether the treespan of a given graph is at most a given integer k. First we
introduce a new perspective to the problem, with an equivalent parameter
which we call adjacencyspan. It provides, in our opinion, a clearer under-
standing of the nature of the problem.
We provide structural results related to adjacencyspan, and combine these
with dynamic programming to solve Treespan in polynomial time for fixed
values of k and hence prove the problem to be in XP. Fomin et al. [Al-
gorithmica, 2005] asked whether Treespan is polynomial time solvable for
trees of degree higher than 3 as their final open problem. We solve this
problem by proving Treespan to be polynomial time solvable for trees of
bounded maximum degree d, for every fixed d. In the area of fixed parame-
ter tractability we give a polynomial kernel for Treespan parameterized by
both the required treespan and the vertex cover number of the input graph.
It is a classical result, first proven by Lenstra [Mathematics of Operations
Research, 1983], that p-Integer Linear Programming Feasibility is
fixed parameter tractable. In his book Invitation to Fixed-Parameter Al-
gorithms", Niedermeier specifically asks for more applications of this result.
In this thesis we provide another application by using it to obtain a fixed
parameter tractable algorithm for Treespan parameterized by the vertex
cover number.
The thesis do not only have theoretical implications, but we give algorithms
that by far outperform previously known algorithms in practical terms.
Publisher
The University of BergenCollections
Copyright the author. All rights reserved