|
|
Parameterized Approximations of Directed Steiner Networks
Koreček, Martin ; Feldmann, Andreas Emil (vedoucí práce) ; Marx, Dániel (oponent)
Instance problému orientované Steinerovy sítě (zkracováno na DSN podle anglického názvu) je tvořena orientovaným grafem G s cenami hran a k tzv. "terminálními" páry vrcholů. Cílem je najít podgraf G s minimální cenou, ve kterém je každý terminální pár propojen cestou. Toto zobecňuje několik NP-těžkých problémů. Terminální páry indukují takzvaný "vzorový graf", orientovaný graf na podmnožině vrcholů G. V této práci se zabýváme problémem DSN omezeným na určité třídy vzorových grafů. Ví se, že optimum lze najít v FPT čase pro některé třídy, a že to není možné pro všechny ostatní třídy, za předpokladu že FPT ̸= W[1]. To vede na otázku, jak dobře lze ony těžké třídy aproximovat v FPT čase. Doká- žeme, že pro ně neexistuje FPT aproximační schéma na základě silnějšího předpokladu, Gap-ETH hypotézy. Poté ukážeme algoritmy s konstantním aproximačním faktorem pro speciální třídy vzorových grafů. 1
|
|
|
Parameterized Algorithms for 2-Edge Connected Steiner Subgraphs
Sami, Sasha ; Feldmann, Andreas Emil (vedoucí práce) ; Chitnis, Rajesh (oponent)
In the weighted Minimum 2-Edge Connected Steiner Subgraph (2-ECSS) problem, the input is a simple undirected edge-weighted graph. The task is to find a subgraph with the least cost (sum of weights of edges), such that for each pair of vertices u, v from a distinguished subset (called terminals), there exist at least two edge-disjoint u-v paths in the subgraph. We give a ran- domized XP algorithm, parameterized by the number of terminals, for weighted Minimum 2-ECSS in case of uniform edge weights, at the heart of which lies the randomized algorithm by Bj¨orklund, Husfeldt, and Taslaman (SODA 2012), for finding a shortest cycle through a given subset of vertices. A close variant of weighted Minimum 2-ECSS is the weighted Minimum 2-Edge Connected Steiner Multi-subgraph (2-ECSM) problem. In weighted Min- imum 2-ECSM, the solution subgraph can use multiple copies of each edge in the input graph, paying separately for each copy. We show that weighted Minimum 2-ECSM is polynomially equivalent to a problem called Bi-directed Strongly Connected Steiner Subgraph (BI-SCSS), for which an FPT algorithm is known due to Chitnis et al. (TALG 2021). We show that by combining the results of Jord'an (Discret. Appl. Math. 2001) and Feldmann et al. (SOSA 2022), one can obtain an FPT algorithm for weighted Minimum 2-ECSM...
|
|
|
Algorithms for Low Highway Dimension Graphs
Vu, Tung Anh ; Feldmann, Andreas Emil (vedoucí práce) ; Lampis, Michail (oponent)
V této práci navrhneme algoritmy pro problém k-Supplier with Outliers. V síti dostaneme zadanou množinu dodavatelů a množinu klientů. Cílem je vybrat k doda- vatelů tak, aby vzdálenost mezi každým obslouženým klientem a nejbližším vybraným dodavatelem byla co nejmenší. Je dovoleno ponechat některé klienty neobsloužené. Max- imální počet klientů, které nemusíme obsloužit, je dán na vstupu. Jelikož k-Supplier with Outliers má mnoho využití v logistice, soustředíme se na parametry, které jsou vhodné pro dopravní sítě. Zabýváme se grafy s malou highway dimension, která byla zavedena Abrahamem et al. [SODA 2010] a grafy s malou doubling dimension. Je známo, že za předpokladu P ̸= NP nelze pro žádné kladné ε problém k-Sup- plier with Outliers (3 − ε)-aproximovat. Problém k-Supplier with Outliers je W[1]-těžký pro grafy s konstantní doubling dimension a highway dimension. Oba tyto těžkostní výsledky překonáme pomocí paradigmatu parametrizovaných aproximačních algoritmů. V případě highway dimension navrhneme (1 + ε)-aproximační algoritmus pro jakéko- liv kladné ε pracující v čase f(k, p, h, ε) · nO(1) , kde p je povolený počet klientů, které nemusíme obsloužit, h je highway dimension grafu na vstupu a f je nějaká vyčíslitelná funkce. V případě doubling dimension navrhneme (1 + ε)-aproximační algoritmus pro...
|
|
| |
|
|
Strongly Connected Steiner Subgraphs with small number of Steiner vertices
Kemény, Tamás Dávid ; Feldmann, Andreas Emil (vedoucí práce) ; Suchý, Ondřej (oponent)
Title: Strongly Connected Steiner Subgraphs with Small Number of Steiner Vertices Author: Tamás Dávid Kemény Department: Department of Applied Mathematics Supervisor: Dr. Andreas Emil Feldmann, Department of Applied Mathematics Abstract: Two well-established methods of dealing with hard optimization problems have been to develop approximation and parameterized algorithms. Recent results have shown that for some problems, it is only by combining these two approaches, into so-called pa- rameterized approximation algorithms, that we are able to efficiently find solutions that are of reasonable quality. This is the viewpoint from which we study the problem known as the Strongly Connected Steiner Subgraph problem, where a set of terminal vertices of an edge-weighted directed graph needs to be strongly-connected in the cheapest way possible. Keywords: Strongly Connected Steiner Subgraphs, Parameterized Algorithms, Approxi- mation Algorithms, Bidirected Graphs iii
|
|
|
Structural properties of graphs and eficient algorithms: Problems Between Parameters
Knop, Dušan ; Fiala, Jiří (vedoucí práce) ; Niedermeier, Rolf (oponent) ; Feldmann, Andreas Emil (oponent)
Strukturální vlastnosti grafů a efektivní algoritmy: Problémy separující parametry Dušan Knop Parametrizovaná složitost se v přůběhu posledních dvou dekád stala jednou z nejvýznamějších oblastí výpočetní složitosti. Strukturální vlastnosti grafů (také nazývané grafové šířky) hrají dnes centrální roli jak v teorii grafů tak v návrhu (parametrizovaných) algoritmů. V těto práci za pomoci studia konkrétních problémů poukazujeme na souvislost strukturálních vlastností grafů a možnosti získání parametrizovaného algoritmu. Předvádíme proto parametrizované algo- ritmy a těžkostní redukce pro problémy Target Set Selection, Minimum Length Bounded Cut a další. Vstupem problému Minimum Length Bounded Cut je graf, dva jeho vrcholy (zdroj a stok) a kladné celé číslo L. Úkolem pak je naleznout minimální množinu hran po jejímž odebrání bude vzdálenost mezi zdrojem a stokem více než L. Ukazujeme, že je možné naleznout optimální řešení pro tento problém algoritmem s časem běhu f(k)n, kde f je vyčíslitelná funkce a k je tree-depth n vrcholového grafu na vstupu. Naopak takovýto algoritmus nemůže existovat pro parametr tree-width (pokud FPT ̸= W[1]). V současné době je jen velmi málo známých problémů s touto vlastností....
|
host ::
RSS.