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

Article

10.1016/j.ipl.2022.106315

Department of Theoretical Computer Science

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.

Proceedings paper

Department of Theoretical Computer Science

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.

Article

10.1142/S0218195921500072

Department of Theoretical Computer Science

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.

Proceedings paper

10.4230/LIPIcs.ESA.2022.22

Department of Theoretical Computer Science

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.

Proceedings paper

10.1007/978-3-030-86838-3_22

Department of Theoretical Computer Science

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.

Proceedings paper

10.1007/978-3-030-92702-8_2

Department of Theoretical Computer Science

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.

Proceedings paper

10.1007/978-3-030-92931-2_15

Department of Theoretical Computer Science

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 .

Proceedings paper

10.1007/978-3-030-68766-3_7

Department of Theoretical Computer Science

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$.

Proceedings paper

10.1007/978-3-030-67899-9_15

Department of Theoretical Computer Science

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$.

Proceedings paper

10.1007/978-3-030-19955-5_6

Department of Theoretical Computer Science

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. \]

Proceedings paper

10.1007/978-3-030-30806-3_4

Department of Theoretical Computer Science

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.

Proceedings paper

10.1007/978-3-319-72453-9_28

Department of Theoretical Computer Science

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.