Václav Blažej

TCS Journal 2026 Journal Article

A parameterized perspective of all-colors

• Václav Blažej
• Satyabrata Jana
• Peter Strulo

In this paper, we study the All-Colors problem: given a graph G each of whose vertices is equipped with a button and assigned a color value from the set { 0, 1, …, m − 1 } and an integer k, can we reach color value 1 ( mod m ) on every vertex of G by pressing the button at most k times. The rule we follow is the following: if a button of a corresponding vertex is pressed one time, then the color values of the vertex and its neighbors are incremented by 1. This problem is known to be NP -hard on bipartite graphs even when m = 2 [Theor. Comput. Sci. , 2007], although linear time solvable on trees [SIAM J. Comput. , 2004]. In this work, we study this problem in the realm of parameterized complexity with respect to several parameters. In particular, we show the following for All-Colors. • W[1] -hard when parameterized by solution size ( k ). • FPT algorithm parameterized by solution size + maximum degree. • FPT algorithm parameterized by tree width, clique-width. • NP -hard on sub-cubic planar graphs.

EUMAS Conference 2025 Conference Paper

Controlling the Spread of Two Secrets in Diverse Social Networks

• Václav Blažej
• Dušan Knop
• Šimon Schierreich

AAAI Conference 2023 Conference Paper

The Parameterized Complexity of Network Microaggregation

• Václav Blažej
• Robert Ganian
• Dušan Knop
• Jan Pokorný
• Šimon Schierreich
• Kirill Simonov

Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameterizations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network.

AAAI Conference 2022 Short Paper

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

• Václav Blažej
• Dušan Knop
• Šimon Schierreich

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