Algorithmic Graph Problems - From Computer Networks to Graph Embeddings

Martin Wahlén

    Forskningsoutput: AvhandlingDoktorsavhandling (sammanläggning)


    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.
    Tilldelande institution
    • Lingas, Andrzej, handledare
    • Husfeldt, Thore, handledare
    Tilldelningsdatum2009 feb. 27
    ISBN (tryckt)978-91-628-7684-5
    StatusPublished - 2009

    Bibliografisk information

    Defence details

    Date: 2009-02-27
    Time: 13:00
    Place: E:1406, E-building, Ole Römers väg 3

    External reviewer(s)

    Name: Fomin, Fedor
    Title: Professor
    Affiliation: Institutt for informatikk, University of Bergen


    Ämnesklassifikation (UKÄ)

    • Datavetenskap (datalogi)


    Utforska forskningsämnen för ”Algorithmic Graph Problems - From Computer Networks to Graph Embeddings”. Tillsammans bildar de ett unikt fingeravtryck.

    Citera det här