PhD defense: Algorithmic Graph Problems - From Computer Networks to Graph Embeddings
Date: February 27, 2009 (Friday) at 13:00
Martin Wahlén defends his thesis "Algorithmic Graph Problems - From Computer Networks to Graph Embeddings"
Opponent:
Fedor Fomin
Abstract:
This dissertation is a contribution to the knowledge of the
computational complexity of discrete combinatorial problems.
1. The first problem that we consider is to compute the maximum
independent set of a box graph, that is, given a set of orthogonal
boxes in the plain compute the largest subset such that no boxes in the
subset overlap. We provide a exp(O(sqrt(n) log n)) time algorithm for
this problem and give a exp(Omega(sqrt(n))) bound unless the
Exponential Time Hypothesis (ETH) is false.
2. Next, we consider the problem of computing the Hadwiger number of a
graph G. The Hadwiger number is the largest h such that the complete
graph on h vertices, Kh, is a minor of G. We also study the related
problem of computing the maximum homeomorphic clique. That is,
determining the largest h such that Kh is a topological minor of G. We
give upper and lower bounds for the approximability of these problems.
For the fixed-vertex subgraph homeomorphism problem we provide an
exponential time exact algorithm.
3. Then we study broadcasting in geometric multi-hop radio networks by
using analysis techniques from computational complexity. We attempt to
minimize the total power consumption of broadcasting a message from a
source node to all the other nodes in the network. We also study the
number of rounds required to broadcast a message in a known geometric
radio network. We also show that an h-hop broadcasting scheme, in a
model that does not account for interference, requiring E energy can be
simulated in h log y rounds using O(E) energy in a model that does,
where y denotes the ratio between the maximum and the minimum Euclidean
distance between nodes in the network.
4. Finally, we establish lower bounds on the computational complexity of
counting problems; in particular we study the Tutte polynomial and the
permanent under a counting version of the ETH (#ETH). The Tutte
polynomial is related to determining the failure probability for
computer networks by its relation to the reliability polynomial. We
consider the problem of computing the Tutte polynomial in a point
(x,y), and show that for multigraphs with m adjacent vertex pairs the
problem requires time exp(Omega(m)), in many points, under the #ETH. We
also show that computing the permanent of a n * n matrix with m nonzero
entries requires time exp(Omega(m)), under the #ETH.
Room: E:1406
Last modified Dec 9, 2011 12:57 pm by Mikael.Antic@cs.lth.se
0261