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.
On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations
Autoři
Rok
2022
Publikováno
30th Annual European Symposium on Algorithms (ESA 2022). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2022. p. 22:1-22:16. Leibniz International Proceedings in Informatics (LIPIcs). vol. 244. ISSN 1868-8969. ISBN 978-3-95977-247-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today’s computation, we employ one of the most successful models of such precomputation - the kernelization. Within this framework, we focus on Traveling Salesperson Problem (TSP) and some of its generalizations.
We provide a kernel for TSP with size polynomial in either the feedback edge set number or the size of a modulator to constant-sized components. For its generalizations, we also consider other structural parameters such as the vertex cover number and the size of a modulator to constant-sized paths. We complement our results from the negative side by showing that the existence of a polynomial-sized kernel with respect to the fractioning number, the combined parameter maximum degree and treewidth, and, in the case of {Subset TSP}, modulator to disjoint cycles (i.e., the treewidth two graphs) is unlikely.
Průvodce labyrintem algoritmů, 2. rozšířené vydání
Autoři
Mareš, M.; Valla, T.
Rok
2022
Publikováno
Praha: CZ.NIC, z.s.p.o., 2022. ISBN 978-80-88168-66-9.
Typ
Kniha
Pracoviště
Automorphisms of the cube n^d
Autoři
Dvořák, P.; Valla, T.
Rok
2021
Publikováno
Discrete Mathematics. 2021, 2021(344(3)), ISSN 0012-365X.
Typ
Článek
Pracoviště
Anotace
Consider a hypergraph n^d where the vertices are points of the d-dimensional cube [n]^d and the edges are all sets of n points such that they are in one line. We study the structure of the group of automorphisms of n^d, i.e., permutations of points of [n]^d preserving the edges. In this paper we provide a complete characterization. Moreover, we consider the Colored Cube Isomorphism problem of deciding whether for two colorings of the vertices of n^d there exists an automorphism of n^d preserving the colors. We show that this problem is GI-complete.
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.
Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem
Typ
Stať ve sborníku
Pracoviště
Anotace
We consider the subgraph isomorphism problem where, given two graphs G (source graph) and F (pattern graph), one is to decide whether there is a (not necessarily induced) subgraph of G isomorphic to F. While many practical heuristic algorithms have been developed for the problem, as pointed out by McCreesh et al. [JAIR 2018], for each of them there are rather small instances which they cannot cope. Therefore, developing an alternative approach that could possibly cope with these hard instances would be of interest. A seminal paper by Alon, Yuster and Zwick [J. ACM 1995] introduced the color coding approach to solve the problem, where the main part is a dynamic programming over color subsets and partial mappings. As with many exponential-time dynamic programming algorithms, the memory requirements constitute the main limiting factor for its usage. Because these requirements grow exponentially with the treewidth of the pattern graph, all existing implementations based on the color coding principle restrict themselves to specific pattern graphs, e.g., paths or trees. In contrast, we provide an efficient implementation of the algorithm significantly reducing its memory requirements so that it can be used for pattern graphs of larger treewidth. Moreover, our implementation not only decides the existence of an isomorphic subgraph, but it also enumerates all such subgraphs (or given number of them). We provide an extensive experimental comparison of our implementation to other available solvers for the problem.
On Induced Online Ramsey Number of Paths, Cycles, and Trees
Autoři
Blažej, V.; Dvořák, P.; Valla, T.
Rok
2019
Publikováno
The 14th International Computer Science Symposium in Russia. Springer, Cham, 2019. p. 60-69. Lecture Notes in Computer Science. vol. 11532. ISSN 0302-9743. ISBN 978-3-030-19954-8.
Typ
Stať ve sborníku
Pracoviště
Anotace
An online Ramsey game is a game between Builder and
Painter, alternating in turns.
They are given a fixed graph $H$ and a an infinite set of independent vertices $G$.
In each round Builder draws a new edge in $G$ and Painter colors it either red or blue.
Builder wins if after some finite round there is a monochromatic
copy of the graph $H$, otherwise Painter wins.
The online Ramsey number $\widetilde{r}(H)$ is the minimum number of rounds such that Builder can
force a monochromatic copy of $H$ in $G$.
This is an analogy to the size-Ramsey number $\overline{r}(H)$
defined as the minimum number such that there exists graph $G$ with $\overline{r}(H)$ edges
where for any edge two-coloring $G$ contains a monochromatic copy of $H$.
In this extended abstract, we introduce the concept of induced online Ramsey numbers:
the induced online Ramsey number $\overline{r}_{ind}(H)$ is the minimum number of rounds Builder
can force an induced monochromatic copy of $H$ in $G$.
We prove asymptotically tight bounds on the induced online Ramsey numbers of paths,
cycles and two families of trees.
Moreover, we provide a result analogous to Conlon [On-line Ramsey Numbers, SIAM J. Discr. Math. 2009],
showing that there is an infinite family of trees $T_1,T_2,\dots$, $|T_i|<|T_{i+1}|$ for $i\ge1$, such that
\[
\lim_{i\to\infty} \frac{\widetilde{r}(T_i)}{\overline{r}(T_i)} = 0.
\]
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.
A Simple Streaming Bit-parallel Algorithm for Swap Pattern Matching
Typ
Stať ve sborníku
Pracoviště
Anotace
The pattern matching problem with swaps is to find all occurrences of a pattern in a text while allowing the pattern to swap adjacent symbols.
The goal is to design fast matching algorithm that takes advantage of the bit parallelism of bitwise machine instructions
and has only streaming access to the input.
We introduce a new approach to solve this problem based on the graph theoretic model and compare its performance to previously known algorithms.
We also show that an approach using deterministic finite automata cannot achieve similarly efficient algorithms.
Furthermore, we describe a fatal flaw in some of the previously published algorithms based on the same model.
Finally, we provide experimental evaluation of our algorithm on real-world data.
Průvodce labyrintem algoritmů
Autoři
Valla, T.; Mareš, M.
Rok
2017
Publikováno
Praha: CZ.NIC, z.s.p.o., 2017. ISBN 978-80-88168-19-5.
Typ
Kniha
Pracoviště
Automorphisms of the Cube n^d
Autoři
Valla, T.; Dvořák, P.
Rok
2016
Publikováno
Computing and Combinatorics - 22nd International Conference. Wien: Springer, 2016. p. 405-416. Lecture notes in computer science. vol. 9797. ISSN 0302-9743. ISBN 978-3-319-42633-4.
Typ
Stať ve sborníku
Pracoviště
Anotace
Consider a hypergraph $H_n^d$ where the vertices are points
of the $d$-dimensional combinatorial cube $n^d$ and the edges
are all sets of $n$ points such that they are in one line.
We study the structure of the group of automorphisms of $H_n^d$,
i.e., permutations of points of $n^d$ preserving the edges.
In this paper we provide a complete characterization.
Moreover, we consider the {\ColoredCube} problem
of deciding whether for two colorings of the vertices of $H_n^d$
there exists an automorphism of $H_n^d$ preserving the colors.
We show that this problem is $\GI$-complete.
On the Tree Search Problem with Non-uniform Costs
Autoři
Valla, T.; Cicalese, F.; Keszegh, B.; Lidický, B.; Pálvölgyi, D.
Rok
2016
Publikováno
Theoretical Computer Science. 2016, 647 22-32. ISSN 0304-3975.
Typ
Článek
Pracoviště
Anotace
Searching in partially ordered structures has been considered in the context of
information retrieval and efficient tree-like indices, as well as in hierarchy
based knowledge representation.
In this paper we focus on tree-like partial orders and consider the problem of
identifying an initially unknown vertex in a tree by asking edge queries:
an edge query $e$ returns the component of $T-e$ containing the vertex sought for,
while incurring some known cost $c(e)$.
The Tree Search Problem with Non-Uniform Cost is the following:
given a tree $T$ on $n$ vertices, each edge having an associated cost,
construct a strategy that minimizes the total cost of the identification in the worst case.
Finding the strategy guaranteeing the minimum possible cost is an NP-complete
problem already for input trees of degree 3 or diameter 6.
The best known approximation guarantee was an $O(\log n/\log \log \log n)$-approximation
algorithm of [Cicalese et al. TCS 2012].
We improve upon the above results both from the algorithmic and the
computational complexity point of view:
We provide a novel algorithm that provides an $O(\frac{\log n}{\log \log n})$-approximation
of the cost of the optimal strategy.
In addition, we show that finding an optimal strategy is
NP-hard even when the input tree is a spider of diameter 6, i.e., at most one vertex has
degree larger than 2.
On the Tree Search Problem with Non-uniform Costs
Autoři
Valla, T.; Cicalese, F.; Keszegh, B.; Lidicky, B.; Pálvölgyi, D.
Rok
2016
Publikováno
Graph-Theoretic Concepts in Computer Science - 41st International Workshop. Munich: Springer, 2016. p. 90-102. Lecture Notes in Computer Science. vol. 9224. ISSN 0302-9743. ISBN 978-3-662-53173-0.
Typ
Stať ve sborníku
Pracoviště
Anotace
Searching in partially ordered structures has been considered in the context of
information retrieval and efficient tree-like indices, as well as in hierarchy
based knowledge representation.
In this paper we focus on tree-like partial orders and consider the problem of
identifying an initially unknown vertex in a tree by asking edge queries:
an edge query $e$ returns the component of $T-e$ containing the vertex sought for,
while incurring some known cost $c(e)$.
The Tree Search Problem with Non-Uniform Cost is the following:
given a tree $T$ on $n$ vertices, each edge having an associated cost,
construct a strategy that minimizes the total cost of the identification in the worst case.
Finding the strategy guaranteeing the minimum possible cost is an NP-complete
problem already for input trees of degree 3 or diameter 6.
The best known approximation guarantee was an $O(\log n/\log \log \log n)$-approximation
algorithm of [Cicalese et al. TCS 2012].
We improve upon the above results both from the algorithmic and the
computational complexity point of view:
We provide a novel algorithm that provides an $O(\frac{\log n}{\log \log n})$-approximation
of the cost of the optimal strategy.
In addition, we show that finding an optimal strategy is
NP-hard even when the input tree is a spider of diameter 6, i.e., at most one vertex has
degree larger than 2.
LP-Based Covering Games with Low Price of Anarchy
Autoři
Piliouras, G.; Valla, T.; Végh, L.
Rok
2015
Publikováno
Theory of Computing Systems. 2015, 57(1), 238-260. ISSN 1432-4350.
Typ
Článek
Pracoviště
Anotace
We design a new class of vertex and set cover games, where the price of anarchy
bounds match the best known constant factor approximation guarantees for the
centralized optimization problems for linear and also for submodular costs.
This is in contrast to all previously studied covering games, where the price
of anarchy grows linearly with the size of the game. Both the game design and
the price of anarchy results are based on structural properties of the linear
programming relaxations. For linear costs we also exhibit simple best response
dynamics that converge to Nash equilibria in linear time.
On the Computational Complexity and Strategies of Online Ramsey Theory
Autoři
Dvořák, P.; Valla, T.
Rok
2015
Publikováno
Electronic Notes in Discrete Mathematics. Amsterdam: Elsevier Science Publishers B.V., 2015. pp. 729-736. ISSN 1571-0653.
Typ
Stať ve sborníku
Pracoviště
Anotace
An online Ramsey game $(G,H)$ is a game between Builder and
Painter, alternating in turns. In each round Builder draws an edge
and Painter colors it either red or blue. Builder wins if after some round there is a monochromatic
copy of the graph $H$, otherwise Painter is the winner.
The rule for Builder is that after each his move the resulting graph must belong to the class of graphs $G$.
In this abstract we investigate the computational complexity of the related decision problem
and we show that it is PSPACE-complete.
Moreover, we study a generalization of online Ramsey game for hypergraphs
and we provide a result showing that Builder wins the online Ramsey game
for the case when $G$ and $H$ are $3$-uniform hyperforests and $H$ is $1$-degenerate.
On the Geometric Ramsey Number of Outerplanar Graphs
Autoři
Cibulka, J.; Gao, P.; Krčál, M.; Valla, T.; Valtr, P.
Rok
2015
Publikováno
Discrete & Computational Geometry. 2015, 53(1), 64-79. ISSN 0179-5376.
Typ
Článek
Pracoviště
Anotace
We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on 2n vertices are bounded by O(n^3) and O(n^10) , in the convex and general case, respectively. We then apply similar methods to prove an nO(log(n)) upper bound on the Ramsey number of a path with n ordered vertices.
The guarding game is E-complete
Autoři
Šámal, R.; Valla, T.
Rok
2014
Publikováno
Theoretical Computer Science. 2014, 521 92-106. ISSN 0304-3975.
Typ
Článek
Pracoviště
Anotace
The guarding game is a game in which several cops try to guard a region in a (directed or undirected) graph against Robber. Robber and the cops are placed on the vertices of the graph; they take turns in moving to adjacent vertices (or staying), cops inside the guarded region, Robber on the remaining vertices (the robber-region). The goal of Robber is to enter the guarded region at a vertex with no cop on it. The problem is to determine whether for a given graph and given number of cops the cops are able to prevent Robber from entering the guarded region. Fomin et al. (2011) [7] proved that the problem is NP-complete when the robber-region is restricted to a tree. Further they prove that is it PSPACE-complete when the robber-region is restricted to a directed acyclic graph, and they ask about the problem complexity for arbitrary graphs. In this paper we prove that the problem is E-complete for arbitrary directed graphs.
WALTZ: A Strong Tzaar-Playing Program
Autoři
Valla, T.; Veselý, P.
Rok
2014
Publikováno
Computer Games. Cham: Springer International Publishing AG, 2014. pp. 81-96. Communications in Computer and Information Science. ISSN 1865-0929. ISBN 978-3-319-05427-8.
Typ
Stať ve sborníku
Pracoviště
Anotace
Tzaar is an abstract strategy two-player game, which has recently gained popularity in the gaming community and has won several awards. There are some properties, most notably the high branching factor, that make Tzaar hard for computers. We developed Waltz, a strong Tzaar-playing program, using enhanced variants of Alpha-beta and Proof-number Search based algorithms. After many tests with computer opponents and a year of deployment on a popular board-gaming portal, we conclude that Waltz can defeat all available computer programs and even strong human players. In this paper we describe Waltz, its performance and an enhancement of Proof-number Search developed for Waltz that can be also used in other domains than Tzaar.
Polynomial Bounds on Geometric Ramsey Numbers of Ladder Graphs
Autoři
Cibulka, J.; Gao, P.; Krčál, M.; Valla, T.; Valtr, P.
Rok
2013
Publikováno
The Seventh European Conference on Combinatorics, Graph Theory and Applications. Milano: Springer, 2013. pp. 171-176. Publications of the Scuola Normale Superiore. ISBN 978-88-7642-474-8.
Typ
Stať ve sborníku
Pracoviště
Anotace
We prove polynomial upper bounds of geometric Ramsey numbers of
pathwidth-$2$ outerplanar triangulations in both convex and general cases.
We also prove that the geometric Ramsey numbers of the ladder graph on $2n$ vertices
are bounded by $O(n^{3})$ and $O(n^{10})$, in the convex and general case, respectively.
We then apply similar methods to prove an $n^{O(log(n))}$ upper bound
on the Ramsey number of a path with $n$ ordered vertices.
The biased odd cycle Game
Autoři
Ferber, A.; Glebov, R.; Krivelevich, M.; Liu, H.; Palmer, C.; Valla, T.; Vizer, M.
Rok
2013
Publikováno
Electronic Journal of Combinatorics (E-JC),. 2013, 20(20(2)), ISSN 1077-8926.
Typ
Článek
Pracoviště
Anotace
In this paper we consider biased Maker-Breaker games played on the
edge set of a given graph $G$. We prove that for every $delta>0$
and large enough $n$, there exists a constant $k$ for which if
$delta(G)geq delta n$ and $chi(G)geq k$, then Maker can build
an odd cycle in the $(1:b)$ game for $b=Oleft(frac{n}{log^2
n}right)$. We also consider the analogous game where Maker and
Breaker claim vertices instead of edges. This is a special case of
the following well known and notoriously difficult problem due to
Duffus, {L}uczak and R"{o}dl: is it true that for any positive
constants $t$ and $b$, there exists an integer $k$ such that for
every graph $G$, if $chi(G)geq k$, then Maker can build a graph
which is not $t$-colorable, in the $(1:b)$ Maker-Breaker game played
on the vertices of $G$?
LP-based Covering games with low Price of Anarchy
Autoři
Valla, T.; Végh, L.; Piliouras, G.
Rok
2012
Publikováno
Lecture Notes in Computer Science. Berlin: Springer, 2012. pp. 184-197. ISBN 978-3-642-35310-9.
Typ
Stať ve sborníku
Pracoviště
Anotace
We design a new class of vertex and set cover games, where the price of anarchy
bounds match the best known constant factor approximation guarantees for the
centralized optimization problems for linear and also for submodular costs.
This is in contrast to all previously studied covering games, where the price
of anarchy grows linearly with the size of the game. Both the game design and
the price of anarchy results are based on structural properties of the linear
programming relaxations. For linear costs we also exhibit simple best-response
dynamics that converge to Nash equilibria in linear time.