Algorithmic Graph Problems - From Computer Networks to Graph Embeddings

Martin Wahlén

    Research output: ThesisDoctoral Thesis (compilation)

    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 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.
    Original languageEnglish
    QualificationDoctor
    Awarding Institution
    Supervisors/Advisors
    • Lingas, Andrzej, Supervisor
    • Husfeldt, Thore, Supervisor
    Award date2009 Feb 27
    Print ISBNs978-91-628-7684-5
    Publication statusPublished - 2009

    Bibliographical note

    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

    ---

    Subject classification (UKÄ)

    • Computer Science

    Keywords

    • Approximation Algorithms
    • Exact Algorithms
    • Time Complexity
    • Broadcasting

    Fingerprint

    Dive into the research topics of 'Algorithmic Graph Problems - From Computer Networks to Graph Embeddings'. Together they form a unique fingerprint.

    Cite this