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 plane compute the largest subset such that no boxes in the subset overlap. We provide an $mathtt{exp}(O(sqrt nlog n))$time algorithm for this problem and give an $mathtt{exp}(Omega(sqrt n))$ bound unless the {em 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, $K_h,$ 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 $K_h$ is a topological minor of $G$. We give upper and lower bounds for the approximability of these problems. For the fixedvertex subgraph homeomorphism problem we provide an exponential time exact algorithm.
3. Then we study broadcasting in geometric multihop 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 $cal E$ energy can be simulated in $hlog psi$ rounds using $O(cal E)$ energy in a model that does, where $psi$ 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 $bar m$ adjacent vertex pairs the problem requires time $mathtt{exp}(Omega(bar m)),$ in many points, under the #ETH. We also show that computing the permanent of a $n imes n$ matrix with $bar m$ nonzero entries requires time $mathtt{exp}(Omega(bar m))$,} under the #ETH.
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 plane compute the largest subset such that no boxes in the subset overlap. We provide an $mathtt{exp}(O(sqrt nlog n))$time algorithm for this problem and give an $mathtt{exp}(Omega(sqrt n))$ bound unless the {em 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, $K_h,$ 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 $K_h$ is a topological minor of $G$. We give upper and lower bounds for the approximability of these problems. For the fixedvertex subgraph homeomorphism problem we provide an exponential time exact algorithm.
3. Then we study broadcasting in geometric multihop 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 $cal E$ energy can be simulated in $hlog psi$ rounds using $O(cal E)$ energy in a model that does, where $psi$ 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 $bar m$ adjacent vertex pairs the problem requires time $mathtt{exp}(Omega(bar m)),$ in many points, under the #ETH. We also show that computing the permanent of a $n imes n$ matrix with $bar m$ nonzero entries requires time $mathtt{exp}(Omega(bar m))$,} under the #ETH.
Original language  English 

Qualification  Doctor 
Awarding Institution  
Supervisors/Advisors 

Award date  2009 Feb 27 
Print ISBNs  9789162876845 
Publication status  Published  2009 
Bibliographical note
Defence detailsDate: 20090227
Time: 13:00
Place: E:1406, Ebuilding, Ole Römers väg 3
External reviewer(s)
Name: Fomin, Fedor
Title: Professor
Affiliation: Institutt for informatikk, University of Bergen

Subject classification (UKÄ)
 Computer Science
Keywords
 Approximation Algorithms
 Exact Algorithms
 Time Complexity
 Broadcasting