Publikation:

Leveraging Path Structures in NP-hard Graph Problems

Lade...
Vorschaubild

Dateien

Beck_2-109cjzlrh54eg3.pdf
Beck_2-109cjzlrh54eg3.pdfGröße: 9.52 MBDownloads: 26

Datum

2022

Autor:innen

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

DOI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Dissertation
Publikationsstatus
Published

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)
004 Informatik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690BECK, Moritz, 2022. Leveraging Path Structures in NP-hard Graph Problems [Dissertation]. Konstanz: Universität Konstanz
BibTex
@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&lt;sub&gt;P&lt;/sub&gt; 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&lt;sub&gt;P&lt;/sub&gt; . 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>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

October 10, 2022
Hochschulschriftenvermerk
Konstanz, Univ., Diss., 2022
Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen