# Ing. Václav Blažej, Ph.D.

- +420224357987
- vaclav.blazej@fit.cvut.cz
- TH:A-1222

### Polynomial kernels for tracking shortest paths

Authors

Year

2023

Published

Information Processing Letters. 2023, 179(1), ISSN 1872-6119.

Type

Article

Departments

Annotation

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.

### Controlling the Spread of Two Secrets in Diverse Social Networks (Student Abstract)

Authors

Year

2022

Published

Proceedings of the 36th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2022. p. 12919-12920. ISSN 2159-5399. ISBN 978-1-57735-876-3.

Type

Proceedings paper

Departments

Annotation

nformation diffusion in social networks is a well-studied concept in social choice theory. We propose the study of the diffusion of two secrets in a heterogeneous environment from the complexity perspective, that is, there are two different networks with the same set of agents (e.g., the structure of the set of followers might be different in two distinct social networks). Formally, our model combines two group identification processes for which we do have independent desiderata---either constructive, where we would like a given group of agents to be exposed to a secret, or destructive, where a given group of agents should not be exposed to a secret. To be able to reach these targets, we can either delete an agent or introduce a previously latent agent. Our results are mostly negative---all of the problems are NP-hard. Therefore, we propose a parameterized study with respect to the natural parameters, the number of influenced agents, the size of the required/protected agent sets, and the duration of the diffusion process. Most of the studied problems remain W[1]-hard even for a combination of these parameters. We complement these results with nearly optimal XP algorithms.

### On Edge-Length Ratios of Partial 2-Trees

Authors

Blažej, V.; Fiala, J.; Liotta, G.

Year

2022

Published

International Journal of Computational Geometry & Applications. 2022, 31(02n03), 141-162. ISSN 0218-1959.

Type

Article

Departments

Annotation

The edge-length ratio of a planar straight-line drawing of a graph is the maximum ratio between the lengths of any two of its edges. When the edges to be considered in the ratio are required to be adjacent, the ratio is called local edge-length ratio. The (local) edge-length ratio of a graph 𝐺 is the infimum over all (local) edge-length ratios in the planar straight-line drawings of 𝐺. We prove that the edge-length ratio of the 𝑛-vertex 2-trees is Ω(log 𝑛), which proves a conjecture by Lazard et al. [TCS 770, 2019, pp. 88–94] and complements an upper bound by Borrazzo and Frati [JoCG 11(1), 2020, pp. 137–155].
We also prove that every partial 2-tree admits a planar straight-line drawing whose local edge-length ratio is at most 4+𝜀 for any arbitrarily small 𝜀>0.

### On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations

Authors

Year

2022

Published

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.

Type

Proceedings paper

Departments

Annotation

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.

### Bears with Hats and Independence Polynomials

Authors

Blažej, V.; Dvořák, P.; Opler, M.

Year

2021

Published

Graph-Theoretic Concepts in Computer Science. Cham: Springer, 2021. p. 283-295. Lecture Notes in Computer Science. vol. 12911. ISSN 0302-9743. ISBN 978-3-030-86837-6.

Type

Proceedings paper

Departments

Annotation

Consider the following hat guessing game. A bear sits on each vertex of a graph G, and a demon puts on each bear a hat colored by one of h colors. Each bear sees only the hat colors of his neighbors. Based on this information only, each bear has to guess g colors and he guesses correctly if his hat color is included in his guesses. The bears win if at least one bear guesses correctly for any hat arrangement.
We introduce a new parameter—fractional hat chromatic number 𝜇̂, arising from the hat guessing game. The parameter 𝜇̂ is related to the hat chromatic number which has been studied before. We present a surprising connection between the hat guessing game and the independence polynomial of graphs. This connection allows us to compute the fractional hat chromatic number of chordal graphs in polynomial time, to bound fractional hat chromatic number by a function of maximum degree of G, and to compute the exact value of 𝜇̂ of cliques, paths, and cycles.

### Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set

Authors

Year

2021

Published

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.

Type

Proceedings paper

Departments

Annotation

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.

### Non-homotopic Loops with a Bounded Number of Pairwise Intersections

Authors

Blažej, V.; Opler, M.; Šileikis, M.; Valtr, P.

Year

2021

Published

Graph Drawing and Network Visualization. Cham: Springer, 2021. p. 210-222. Lecture Notes in Computer Science. vol. 12868. ISSN 1611-3349. ISBN 978-3-030-92931-2.

Type

Proceedings paper

Departments

Annotation

Let 𝑉𝑛 be a set of n points in the plane and let 𝑥∉𝑉𝑛. An x-loop is a continuous closed curve not containing any point of 𝑉𝑛. We say that two x-loops are non-homotopic if they cannot be transformed continuously into each other without passing through a point of 𝑉𝑛. For 𝑛=2, we give an upper bound 𝑒𝑂(𝑘√) on the maximum size of a family of pairwise non-homotopic x-loops such that every loop has fewer than k self-intersections and any two loops have fewer than k intersections. The exponent 𝑂(𝑘‾‾√) is asymptotically tight. The previous upper bound 2(2𝑘)4 was proved by Pach et al. [6]. We prove the above result by proving the asymptotic upper bound 𝑒𝑂(𝑘√) for a similar problem when 𝑥∈𝑉𝑛, and by proving a close relation between the two problems .

### On the Edge-Length Ratio of 2-Trees

Authors

Blažej, V.; Fiala, J.; Liotta, G.

Year

2021

Published

Graph Drawing and Network Visualization. Cham: Springer, 2021. p. 85-98. Lecture Notes in Computer Science. vol. 12590. ISSN 0302-9743. ISBN 978-3-030-68765-6.

Type

Proceedings paper

Departments

Annotation

We study planar straight-line drawings of graphs that minimize the ratio between the length of the longest and the shortest edge. We answer a question of Lazard et al. [Theor. Comput. Sci. {\bf 770} (2019), 88--94] and, for any given constant $r$, we provide a $2$-tree which does not admit a planar straight-line drawing with a ratio bounded by $r$. When the ratio is restricted to adjacent edges only, we prove that any $2$-tree admits a planar straight-line drawing whose edge-length ratio is at most $4 + \varepsilon$ for any arbitrarily small $\varepsilon > 0$, hence the upper bound on the local edge-length ratio of partial $2$-trees is $4$.

### On the Intersections of Non-homotopic Loops

Authors

Blažej, V.; Opler, M.; Šileikis, M.; Valtr, P.

Year

2021

Published

Algorithms and Discrete Applied Mathematics. Cham: Springer, 2021. p. 196-205. Lecture Notes in Computer Science. vol. 12601. ISSN 0302-9743. ISBN 978-3-030-67898-2.

Type

Proceedings paper

Departments

Annotation

Let $V = \{v_1, \dots, v_n\}$ be a set of $n$ points in the plane and let $x \in V$. An \emph{$x$-loop} is a continuous closed curve not containing any point of $V$, except of passing exactly once through the point $x$. We say that two $x$-loops are \emph{non-homotopic} if they cannot be transformed continuously into each other without passing through a point of $V$. For $n=2$, we give an upper bound $2^{O(k)}$ on the maximum size of a family of pairwise non-homotopic $x$-loops such that every loop has fewer than $k$ self-intersections and any two loops have fewer than $k$ intersections. This result is inspired by a very recent result of Pach, Tardos, and T\'oth who proved the upper bounds $2^{16k^4}$ for the slightly different scenario when $x\not\in V$.

### On Induced Online Ramsey Number of Paths, Cycles, and Trees

Authors

Blažej, V.; Dvořák, P.; Valla, T.

Year

2019

Published

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.

Type

Proceedings paper

Departments

Annotation

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

Authors

Year

2019

Published

Reachability Problems. Springer, Cham, 2019. p. 33-47. ISSN 0302-9743. ISBN 978-3-030-30805-6.

Type

Proceedings paper

Departments

Annotation

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

Authors

Year

2017

Published

Mathematical Aspects of Computer and Information Sciences. Cham: Springer International Publishing, 2017. p. 333-348. Lecture Notes in Computer Science. vol. 10693. ISSN 0302-9743. ISBN 978-3-319-72452-2.

Type

Proceedings paper

Departments

Annotation

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.