Algorithmic Graph Problems  From Computer Networks to Graph Embeddings
(2009) 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... (More)  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. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1001274
 author
 Wahlén, Martin ^{LU}
 supervisor

 Andrzej Lingas ^{LU}
 Thore Husfeldt ^{LU}
 opponent

 Professor Fomin, Fedor, Institutt for informatikk, University of Bergen
 organization
 publishing date
 2009
 type
 Thesis
 publication status
 published
 subject
 keywords
 Approximation Algorithms, Exact Algorithms, Time Complexity, Broadcasting
 pages
 157 pages
 defense location
 E:1406, Ebuilding, Ole Römers väg 3
 defense date
 20090227 13:00
 ISSN
 16501268
 ISBN
 9789162876845
 language
 English
 LU publication?
 yes
 id
 2c48f14ef13443738be42a4cc0a61dae (old id 1001274)
 date added to LUP
 20090204 08:34:47
 date last changed
 20160919 08:45:00
@phdthesis{2c48f14ef13443738be42a4cc0a61dae, abstract = {This dissertation is a contribution to the knowledge of the computational complexity of discrete combinatorial problems. <br/><br> <br/><br> 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.<br/><br> <br/><br> 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.<br/><br> <br/><br> 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 <br/><br> 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.<br/><br> <br/><br> 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 <br/><br> 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.}, author = {Wahlén, Martin}, isbn = {9789162876845}, issn = {16501268}, keyword = {Approximation Algorithms,Exact Algorithms,Time Complexity,Broadcasting}, language = {eng}, pages = {157}, school = {Lund University}, title = {Algorithmic Graph Problems  From Computer Networks to Graph Embeddings}, year = {2009}, }