Graph and Hypergraph Decompositions for Exact Algorithms

Show full item record

Permalink

http://urn.fi/URN:ISBN:978-952-10-9639-6
Title: Graph and Hypergraph Decompositions for Exact Algorithms
Author: Korhonen, Janne
Contributor: University of Helsinki, Faculty of Science, Department of Computer Science
Helsinki Institute for Information Technology HIIT
Thesis level: Doctoral dissertation (article-based)
Abstract: This thesis studies exact exponential and fixed-parameter algorithms for hard graph and hypergraph problems. Specifically, we study two techniques that can be used in the development of such algorithms: (i) combinatorial decompositions of both the input instance and the solution, and (ii) evaluation of multilinear forms over semirings. In the first part of the thesis we develop new algorithms for graph and hypergraph problems based on techniques (i) and (ii). While these techniques are independently both useful, the work presented in this part is largely characterised by their joint application. That is, combining results from different pieces of the decompositions often takes the from of multilinear form evaluation task, and on the other hand, decompositions offer the basic structure for dynamic-programming-style algorithms for the evaluation of multilinear forms. As main positive results of the first part, we give algorithms for three different problem families. First, we give a fast evaluation algorithm for linear forms defined by a disjointness matrix of small sets. This can be applied to obtain faster algorithms for counting maximum-weight objects of small size, such as k-paths in graphs. Second, we give a general framework for exponential-time algorithms for finding maximum-weight subgraphs of bounded tree-width, based on the theory of tree decompositions. Besides basic combinatorial problems, this framework has applications in learning Bayesian network structures. Third, we give a fixed-parameter algorithm for finding unbalanced vertex cuts, that is, vertex cuts that separate a small number of vertices from the rest of the graph. In the second part of the thesis we consider aspects of the complexity theory of linear forms over semirings, in order to better understand technique (ii). Specifically, we study how the presence of different algebraic catalysts in the ground semiring affects the complexity. As the main result, we show that there are linear forms that are easy to compute over semirings with idempotent addition, but difficult to compute over rings, unless the strong exponential time hypothesis fails.Yksi tietojenkäsittelytieteen perustavista tavoitteista on tehokkaiden algoritmien kehittäminen. Teoreettisesta näkökulmasta algoritmia yleensä pidetään tehokkaana mikäli sen ajoaika riippuu polynomisesti syötteen koosta. On kuitenkin laskennallisia ongelmia, joihin ei ole olemassa polynomiaikaisia algoritmeja. Esimerkiksi NP-kovia ongelmia ei voi ratkaista polynomisessa ajassa, mikäli yleinen vaativuusolettamus P ≠ NP pitää paikkansa. Tästä huolimatta haluaisimme kuitenkin usein ratkaista tällaisia vaikeita ongelmia. Kaksi yleistä lähestymistapaa vaikeiden, polynomisessa ajassa ratkeamattomien ongelmien tarkkaan ratkaisemiseen on (i) eksponentiaalinen algoritmiikka ja (ii) parametrisoitu algoritmiikka. Eksponentiaaliaikaisessa algoritmiikassa kehitetään algoritmeja, joiden ajoaika on edelleen eksponentiaalinen syötteen koon suhteen, mutta jotka välttävät koko ratkaisuavaruuden läpikäynnin; toisin sanoen, kyse on vähemmän eksponentiaalisten algoritmien kehittämisestä. Parametrisoitu algoritmiikka puolestaan pyrkii eristämään eksponentiaaliaikaisen riippuvuuden ajoajassa syötteen koosta riippumattomaan parametriin. Tässä väitöstyössä esitetään eksponentiaaliaikaisia ja parametrisoituja algoritmeja erinäisten vaikeiden verkko- ja hyperverkko-ongelmien tarkkaan ratkaisemiseen. Esitetyt algoritmit perustuvat kahteen algoritmiseen tekniikkaan: (i) monilineaarimuotojen evaluoiminen yli erilaisten puolirengaiden ja (ii) kombinatoristen hajotelmien käyttö. Algoritmien lisäksi työssä tarkastellaan näihin tekniikoihin liittyviä vaativuusteoreettisia kysymyksiä, mikä auttaa ymmärtämään tekniikoiden rajoituksia ja toistaiseksi hyödyntämättömiä mahdollisuuksia.
URI: URN:ISBN:978-952-10-9639-6
http://hdl.handle.net/10138/42429
Date: 2014-01-16
Subject: tietojenkäsittelytiede
Rights: This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
xmlui.dri2xhtml.METS-1.0.item-accessrights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
graphand.pdf 1.040Mb PDF View/Open

This item appears in the following Collection(s)

Show full item record