|
|
Parameterized Approximations of Directed Steiner Networks
Koreček, Martin ; Feldmann, Andreas Emil (advisor) ; Marx, Dániel (referee)
An instance of the Directed Steiner Network (DSN) problem consists of a directed graph G with edge costs, and k so called "terminal" vertex pairs. The task is to find a minimum-cost subgraph of G in which all terminal pairs are connected by a path. This generalizes several NP-hard problems. The terminal pairs induce the so called "pattern graph", a digraph on a subset of vertices of G. We investigate the DSN problem restricted to certain classes of pattern graphs. It has been shown that the optimum may be found for certain classes in FPT time parameterized by k, and that this is impossible for all other classes of graphs, assuming FPT ̸= W[1]. This leads to the question whether the hard classes may be approximated in FPT time. We prove that no FPT approximation scheme may exist for any of the W[1]-hard classes, based on a stronger hypothesis, the Gap-ETH. We then give FPT algorithms with constant approximation guarantees for special classes of pattern graphs. 1
|
|
|
Parameterized Algorithms for 2-Edge Connected Steiner Subgraphs
Sami, Sasha ; Feldmann, Andreas Emil (advisor) ; Chitnis, Rajesh (referee)
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 (advisor) ; Lampis, Michail (referee)
In this work we develop algorithms for the k-Supplier with Outliers problem. In a network, we are given a set of suppliers and a set of clients. The goal is to choose k suppliers so that the distance between every served client and its nearest supplier is minimized. Clients that are not served are called outliers and the number of allowed outliers is given on input. As k-Supplier with Outliers has numerous applications in logistics, we focus on parameters which are suitable for transportation networks. We study graphs with low highway dimension, which was proposed by Abraham et al. [SODA 2010], and low doubling dimension. It is known that unless P = NP, k-Supplier with Outliers does not admit a (3 − ε)-approximation algorithm for any constant ε > 0. The k-Supplier with Outliers problem is W[1]-hard on graphs of constant doubling dimension for parame- ters k and highway dimension. We overcome both of these barriers through the paradigm of parameterized approximation algorithms. In the case of highway dimension, we develop a (1 + ε)-approximation algorithm for any ε > 0 with running time f(k, p, h, ε) · nO(1) where p is the number of allowed outliers, h is the highway dimension of the input graph, and f is some computable function. In the case of doubling dimension, we develop a (1 + ε)-approximation...
|
|
| |
|
|
Strongly Connected Steiner Subgraphs with small number of Steiner vertices
Kemény, Tamás Dávid ; Feldmann, Andreas Emil (advisor) ; Suchý, Ondřej (referee)
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ří (advisor) ; Niedermeier, Rolf (referee) ; Feldmann, Andreas Emil (referee)
Structural Properties of Graphs and Eficient Algorithms: Problems Between Parameters Dušan Knop Parameterized complexity became over last two decades one of the most impor- tant subfield of computational complexity. Structural graph parameters (widths) play important role both in graph theory and (parameterized) algoritmh design. By studying some concrete problems we exhibit the connection between struc- tural graph parameters and parameterized tractability. We do this by examining tractability and hardness results for the Target Set Selection, Minimum Length Bounded Cut, and other problems. In the Minimum Length Bounded Cut problem we are given a graph, source, sink, and a positive integer L and the task is to remove edges from the graph such that the distance between the source and the sink exceeds L in the resulting graph. We show that an optimal solution to the Minimum Length Bounded Cut problem can be computed in time f(k)n, where f is a computable function and k denotes the tree-depth of the input graph. On the other hand we prove that (under assumption that FPT ̸= W[1]) no such algorithm can exist if the parameter k is the tree-width of the input graph. Currently only few such problems are known. The Target Set Selection problem exibits the same phenomenon for the vertex cover number and...
|
guest ::
