{"id":{"repo_id":"helsinki","oai_identifier":"oai:helda.helsinki.fi:10138/42429"},"canonical_url":"https://search.dev.ndltd.org/etd/helsinki/oai:helda.helsinki.fi:10138/42429","repository":{"repo_id":"helsinki","name":"University of Helsinki","base_url":"https://helda.helsinki.fi/server/oai/request"},"display":{"title":"Graph and Hypergraph Decompositions for Exact Algorithms","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Korhonen, Janne"],"institution":"Helsingin yliopisto","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-01-16","date_published":"2014-01-16","updated_at":"2026-08-21T22:21:56Z","subjects":["tietojenkäsittelytiede"],"languages":["eng"],"rights":["Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.","This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.","Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10138/42429","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"source_record":{"url":"https://helda.helsinki.fi/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Ahelda.helsinki.fi%3A10138%2F42429","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Korhonen, Janne"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-01-03T09:55:29Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-01-06","2014-01-03T09:55:29Z"]},{"key":"dc:date.issued","label":"Date","values":["2014-01-16"]},{"key":"dc:publisher","label":"Institution","values":["Helsingin yliopisto","Helsingfors universitet","University of Helsinki"]},{"key":"dc:type.dcmitype","label":"Dc Type Dcmitype","values":["Text"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["tietojenkäsittelytiede"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.","This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.","Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10138/42429"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Graph and Hypergraph Decompositions for Exact Algorithms"]}]}],"canonical_facts":{"dc:creator":["Korhonen, Janne"],"dc:date.accessioned":["2014-01-03T09:55:29Z"],"dc:date.available":["2014-01-06","2014-01-03T09:55:29Z"],"dc:date.issued":["2014-01-16"],"dc:description.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."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/10138/42429"],"dc:language.iso":["eng"],"dc:publisher":["Helsingin yliopisto","Helsingfors universitet","University of Helsinki"],"dc:rights":["Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.","This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.","Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden."],"dc:subject":["tietojenkäsittelytiede"],"dc:title":["Graph and Hypergraph Decompositions for Exact Algorithms"],"dc:type.dcmitype":["Text"]},"updated_at":"2026-08-21T22:21:56Z"}