Publikation: Leveraging Path Structures in NP-hard Graph Problems
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
There is a multitude of practically relevant graph problems, for example asking for efficient route plans, strategically placed facilities or nicely drawn graphs. Unfortunately, most of those problems are NP-hard, that is, in general it is not possible to efficiently solve large instances to optimality. In this thesis we study ways to tackle such problems in practice. To build upon structure found in graphs, we focus on graph problems that use the notion of shortest paths, in the problem statement or utilized in a solution method. We combine theoretical approaches with practical methods in order to design, analyze and implement data structures and algorithms that work well in practice and also give theoretical guarantees. In particular we give approximation algorithms, focusing on simple ones because they are easier to analyze and implement. Our methodology includes, among other techniques, designing simple algorithms, especially greedy algorithms, computing lower and upper bounds on the optimum value of an instance and evaluating the implemented algorithms on suitable benchmark graphs. The main part of the thesis is divided into four parts, corresponding to four problems.
We first consider the problem of finding small Concatenated k-Path Covers. A Path Concatenation is a set of connected paths satisfying some additional properties. Given a graph G and parameters p, k ∈ N, the goal is to find a minimum set C of nodes (called cover) such that every Path Concatenation of p paths, of total size k, contains at least one node in C. If we fix p = 1 we get the k-Path Cover problem which has been proven to be NP-hard and even APX-hard. We analyze the so-called VC-dimension of these path structures, giving lower and upper bounds, which gets us a O(log OPT)-approximation algorithm for constant p. Additionally, we design a greedy algorithm that is better in practice. We determine instance-based lower bounds by computing sets of non-overlapping Path Concatenations and use these to evaluate the greedy algorithm on various benchmark graphs.
Second, we want to determine places for facilities that should be far apart from each other, we call them Remote Locations. The NP-hard Remote-P problem takes an optimization problem P and strives to place k node facilities such that the corresponding optimization function fP is maximized. In contrast to previous literature we do not assume the graph to be complete and metric, introducing two new cost functions suitable for this setting. We present two greedy algorithms that are applicable for a wide range of functions fP . For the first one, we show that it provides a 6-approximation. For the other one, we obtain the result that it solves the problem exactly on trees, which we use to compute instance-based upper bounds on the optimum solution value. These bounds are used to evaluate the quality of the greedy algorithms in practice. We tested the algorithms on different types of benchmarks, including road networks and proximity graphs.
The third part studies how to find Grid Embeddings. For a given graph with positive edges weights, we want to determine if it is possible to embed this graph in the plane such that every edge has the prescribed length and is drawn either horizontally or vertically. If so, we give such an embedding in form of node coordinates. We design data structures and a backtracking algorithm to answer this question that is considerably sped up by a greedy preprocessing method. We demonstrate with experiments on self-generated grids, among others, the applicability and scalability of our approach.
Lastly, we study Edge Center Selection. There we seek to choose k edges in a graph such that either the maximum distance to these facilities (“centers”) is as small as possible or the maximum distance on shortest paths between facilities is minimized. We analyze four variants of this problem, most of which we prove to be NP-hard, and even determine one problem variant to be not approximable to any factor. We analyze two algorithms. We introduce a parameter ψ to measure an upper bound on the deviation from the triangle inequality and prove various approximation guarantees (constant or depending on ψ) under different assumptions about the graph instances. Several algorithms and heuristics are evaluated on benchmark graphs and we find that the best algorithm mainly depends on how large k is.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
BECK, Moritz, 2022. Leveraging Path Structures in NP-hard Graph Problems [Dissertation]. Konstanz: Universität KonstanzBibTex
@phdthesis{Beck2022Lever-70858, year={2022}, title={Leveraging Path Structures in NP-hard Graph Problems}, author={Beck, Moritz}, address={Konstanz}, school={Universität Konstanz} }
RDF
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/70858"> <dc:language>eng</dc:language> <dc:creator>Beck, Moritz</dc:creator> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/70858"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2024-09-30T05:42:04Z</dc:date> <dc:contributor>Beck, Moritz</dc:contributor> <dcterms:abstract>There is a multitude of practically relevant graph problems, for example asking for efficient route plans, strategically placed facilities or nicely drawn graphs. Unfortunately, most of those problems are NP-hard, that is, in general it is not possible to efficiently solve large instances to optimality. In this thesis we study ways to tackle such problems in practice. To build upon structure found in graphs, we focus on graph problems that use the notion of shortest paths, in the problem statement or utilized in a solution method. We combine theoretical approaches with practical methods in order to design, analyze and implement data structures and algorithms that work well in practice and also give theoretical guarantees. In particular we give approximation algorithms, focusing on simple ones because they are easier to analyze and implement. Our methodology includes, among other techniques, designing simple algorithms, especially greedy algorithms, computing lower and upper bounds on the optimum value of an instance and evaluating the implemented algorithms on suitable benchmark graphs. The main part of the thesis is divided into four parts, corresponding to four problems. We first consider the problem of finding small Concatenated k-Path Covers. A Path Concatenation is a set of connected paths satisfying some additional properties. Given a graph G and parameters p, k ∈ N, the goal is to find a minimum set C of nodes (called cover) such that every Path Concatenation of p paths, of total size k, contains at least one node in C. If we fix p = 1 we get the k-Path Cover problem which has been proven to be NP-hard and even APX-hard. We analyze the so-called VC-dimension of these path structures, giving lower and upper bounds, which gets us a O(log OPT)-approximation algorithm for constant p. Additionally, we design a greedy algorithm that is better in practice. We determine instance-based lower bounds by computing sets of non-overlapping Path Concatenations and use these to evaluate the greedy algorithm on various benchmark graphs. Second, we want to determine places for facilities that should be far apart from each other, we call them Remote Locations. The NP-hard Remote-P problem takes an optimization problem P and strives to place k node facilities such that the corresponding optimization function f<sub>P</sub> is maximized. In contrast to previous literature we do not assume the graph to be complete and metric, introducing two new cost functions suitable for this setting. We present two greedy algorithms that are applicable for a wide range of functions f<sub>P</sub> . For the first one, we show that it provides a 6-approximation. For the other one, we obtain the result that it solves the problem exactly on trees, which we use to compute instance-based upper bounds on the optimum solution value. These bounds are used to evaluate the quality of the greedy algorithms in practice. We tested the algorithms on different types of benchmarks, including road networks and proximity graphs. The third part studies how to find Grid Embeddings. For a given graph with positive edges weights, we want to determine if it is possible to embed this graph in the plane such that every edge has the prescribed length and is drawn either horizontally or vertically. If so, we give such an embedding in form of node coordinates. We design data structures and a backtracking algorithm to answer this question that is considerably sped up by a greedy preprocessing method. We demonstrate with experiments on self-generated grids, among others, the applicability and scalability of our approach. Lastly, we study Edge Center Selection. There we seek to choose k edges in a graph such that either the maximum distance to these facilities (“centers”) is as small as possible or the maximum distance on shortest paths between facilities is minimized. We analyze four variants of this problem, most of which we prove to be NP-hard, and even determine one problem variant to be not approximable to any factor. We analyze two algorithms. We introduce a parameter ψ to measure an upper bound on the deviation from the triangle inequality and prove various approximation guarantees (constant or depending on ψ) under different assumptions about the graph instances. Several algorithms and heuristics are evaluated on benchmark graphs and we find that the best algorithm mainly depends on how large k is.</dcterms:abstract> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2024-09-30T05:42:04Z</dcterms:available> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:issued>2022</dcterms:issued> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dcterms:title>Leveraging Path Structures in NP-hard Graph Problems</dcterms:title> <dc:rights>terms-of-use</dc:rights> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/70858/4/Beck_2-109cjzlrh54eg3.pdf"/> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/70858/4/Beck_2-109cjzlrh54eg3.pdf"/> </rdf:Description> </rdf:RDF>