Ondřej Suchý

Dušan Knop, Šimon Schierreich, Ondřej Suchý

Inspired by the famous Target Set Selection problem, we propose a new discrete model to simultaneously spread two opinions within a social network and perform an initial study of its complexity. Here, we are given a social network, a seed-set of agents for each opinion, two thresholds for each agent, a budget, and a number of rounds. The first threshold represents the willingness of an agent to adopt an opinion if the agent has no opinion at all, while the second threshold states the willingness to acquire a second opinion if the agent already has one. The goal is to add at most budget-many agents to the initial seed-sets such that the process started with these extended seed-sets stabilizes within the given number of rounds, with each agent having either both opinions or none. That is, our goal is to ensure that the spread of opinions is balanced. We show that the problem is NP-hard, and thus we study the problem from the perspective of parameterized complexity. In particular, we show that the problem is FPT when parameterized by the number of rounds, the maximum threshold, and the treewidth combined. This algorithm also applies to the combined parameter, the treedepth and the maximum threshold. Finally, we show that the problem is FPT when parameterized by the vertex cover number, the $3$-path vertex cover number, or the vertex integrity of the input network alone. To complement our tractability results, we show that the problem is W[1]-hard with respect to a) the sizes of the initial seed-sets and the feedback-vertex set number combined, even if all thresholds are bounded by a constant, and b) the budget, the 4-path vertex cover number, and the feedback-vertex set number combined, even if every activation process stabilizes in at most 4 rounds.

Václav Blažej, J. Pascal Gollin, Tomáš Hons et al.

The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bounded tree-independence number have strong structural and algorithmic properties, but the parameter can be unbounded even in quite restricted classes. In particular, the presence of an induced biclique $K_{\ell,\ell}$ forces tree-independence number at least $\ell$. This leads to the question whether large induced bicliques are the only obstruction to bounded tree-independence number in natural hereditary classes. A conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht states that for all positive integers $t$ and $\ell$, every $\{P_t,K_{\ell,\ell}\}$-free graph has bounded tree-independence number. We prove this conjecture for $t=5$ by showing that every $\{P_5,K_{\ell,\ell}\}$-free graph has tree-independence number at most $4\ell$. We also obtain related bounds for the weaker parameter of $α$-degeneracy.