Controlling the Spread of Two Secrets in Diverse Social Networks (Student Abstract)
Authors
Blažej, V.; Knop, D.; Schierreich, Š.
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 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.
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.
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
Blažej, V.; Křišťan, J.; Valla, T.
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
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.