Lund University Publications

LUND UNIVERSITY LIBRARIES

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)
author
supervisor
opponent
• Professor Fomin, Fedor, Institutt for informatikk, University of Bergen
organization
publishing date
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)
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},
language     = {eng},
school       = {Lund University},
title        = {Algorithmic Graph Problems - From Computer Networks to Graph Embeddings},
year         = {2009},
}

```