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 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 $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:
https://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, E-building, Ole Römers väg 3
- defense date
- 2009-02-27 13:00:00
- ISBN
- 978-91-628-7684-5
- language
- English
- LU publication?
- yes
- id
- 2c48f14e-f134-4373-8be4-2a4cc0a61dae (old id 1001274)
- date added to LUP
- 2016-04-04 09:13:36
- date last changed
- 2018-11-21 20:51:38
@phdthesis{2c48f14e-f134-4373-8be4-2a4cc0a61dae,
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 fixed-vertex subgraph homeomorphism problem we provide an exponential time exact algorithm.<br/><br>
<br/><br>
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 <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 = {{978-91-628-7684-5}},
keywords = {{Approximation Algorithms; Exact Algorithms; Time Complexity; Broadcasting}},
language = {{eng}},
school = {{Lund University}},
title = {{Algorithmic Graph Problems - From Computer Networks to Graph Embeddings}},
year = {{2009}},
}