Constant factor approximation for tracking paths and fault tolerant feedback vertex set
Autoři
Rok
2023
Publikováno
Discrete Optimization. 2023, 47 ISSN 1572-5286.
Typ
Článek
Pracoviště
Anotace
Consider a vertex-weighted graph G with a source s and a target t. TRACKING PATHS requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from s to t is unique. In this work, we derive a factor 6-approximation algorithm for TRACKING PATHS in weighted graphs and a factor 4-approximation algorithm if the input is unweighted. This is the first constant factor approximation for this problem. While doing so, we also study approximation of the closely related r-FAULT TOLERANT FEEDBACK VERTEX SET problem. There, for a fixed integer r and a given vertex-weighted graph G, the task is to find a minimum weight set of vertices intersecting every cycle of G in at least r+1 vertices. We give a factor O(r) approximation algorithm for r-FAULT TOLERANT FEEDBACK VERTEX SET if r is a constant.
Polynomial kernels for tracking shortest paths
Autoři
Rok
2023
Publikováno
Information Processing Letters. 2023, 179(1), ISSN 1872-6119.
Typ
Článek
Pracoviště
Anotace
Given an undirected graph G = (V , E), vertices s,t ∈ V , and an integer k, Tracking
Shortest Paths requires deciding whether there exists a set of k vertices T ⊆ V such
that for any two distinct shortest paths between s and t, say P1 and P2, we have
T ∩ V (P1) != T ∩ V (P2). In this paper, we give the first polynomial size kernel for the
problem. Specifically we show the existence of a kernel with O(k2) vertices and edges in
general graphs and a kernel with O(k) vertices and edges in planar graphs for the Tracking Paths in DAG problem. This problem admits a polynomial parameter transformation to Tracking Shortest Paths, and this implies a kernel with O(k4) vertices and edges for Tracking Shortest Paths in general graphs and a kernel with O(k2) vertices and edges in planar graphs. Based on the above we also give a single exponential algorithm for Tracking Shortest Paths in planar graphs.
Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set
Autoři
Rok
2021
Publikováno
Approximation and Online Algorithms - 19th International Workshop, WAOA 2021, Lisbon, Portugal, September 6-10, 2021, Revised Selected Papers. Springer, Cham, 2021. p. 23-38. Lecture Notes in Computer Science (LNCS). vol. 12982. ISSN 0302-9743. ISBN 978-3-030-92701-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
Consider a vertex-weighted graph G with a source s and a target t. Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from s to t is unique. In this work, we derive a factor 66-approximation algorithm for Tracking Paths in weighted graphs and a factor 4-approximation algorithm if the input is unweighted. This is the first constant factor approximation for this problem. While doing so, we also study approximation of the closely related r -Fault Tolerant Feedback Vertex Set problem. There, for a fixed integer r and a given vertex-weighted graph G, the task is to find a minimum weight set of vertices intersecting every cycle of G in at least r+1 vertices. We give a factor O(r^2) approximation algorithm for r -Fault Tolerant Feedback Vertex Set if r is a constant.
On the m-eternal Domination Number of Cactus Graphs
Autoři
Blažej, V.; Křišťan, J.; Valla, T.
Rok
2019
Publikováno
Reachability Problems. Springer, Cham, 2019. p. 33-47. ISSN 0302-9743. ISBN 978-3-030-30805-6.
Typ
Stať ve sborníku
Pracoviště
Anotace
Given a graph $G$, guards are placed on vertices of $G$.
Then vertices are subject to an infinite sequence of attacks
so that each attack must be defended by a guard moving from a neighboring vertex.
The m-eternal domination number is the minimum number of guards such that
the graph can be defended indefinitely.
In this paper we study the m-eternal domination number of cactus graphs,
that is, connected graphs where each edge lies in at most two cycles,
and we consider three variants of the m-eternal domination number:
first variant allows multiple guards to occupy a single vertex,
second variant does not allow it, and in the third variant additional ``eviction'' attacks must be defended.
We provide a new upper bound for the m-eternal domination number of cactus graphs,
and for a subclass of cactus graphs called
Christmas cactus graphs, where each vertex lies in at most two cycles,
we prove that these three numbers are equal.
Moreover, we present a linear-time algorithm for computing them.