Author name cluster

Ondřej Suchý

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

AIJ Journal 2023 Journal Article

Hedonic diversity games: A complexity picture with more than two colors

Robert Ganian
Thekla Hamm
Dušan Knop
Šimon Schierreich
Ondřej Suchý

Hedonic diversity games are a variant of the classical hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly targeted the case with two diversity classes (represented as colors in the model) and provided some initial complexity-theoretic and existential results concerning Nash and individually stable outcomes. Here, we design new algorithms accompanied with lower bounds which provide a comprehensive parameterized-complexity picture for computing Nash and individually stable outcomes with respect to the most natural parameterizations of the problem. Crucially, our results hold for general hedonic diversity games where the number of colors is not necessarily restricted to two, and show that—apart from two trivial cases—a necessary condition for tractability in this setting is that the number of colors is bounded by the parameter. Moreover, for the special case of two colors we resolve an open question asked in previous work (Boehmer and Elkind, AAAI 2020).

Details DOI

AAAI Conference 2022 Short Paper

Balancing the Spread of Two Opinions in Sparse Social Networks (Student Abstract)

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

We propose a new discrete model for simultaneously spreading two opinions within a social network inspired by the famous TARGET SET SELECTION problem. We are given a social network, a seed-set of agents for each opinion, and two thresholds per agent. The first threshold represents the willingness of an agent to adopt an opinion if she has no opinion at all, while the second threshold states the readiness to acquire a second opinion arriving. The goal is to add as few agents as possible to the initial seed-sets such that, once the process started with these seed-set stabilises, each agent has either both opinions or none. We perform an initial study of its computational complexity. It is not surprising that the problem is NP-hard even in quite restricted settings. Therefore, we investigate the complexity of the problem from the parametrized point-of-view with special focus on sparse networks, which appears often in practice. Among other things, we show that the proposed problem is in FPT if we parametrize by the vertex cover number of the underlying graph.

PDF Details

AAAI Conference 2022 Conference Paper

Hedonic Diversity Games: A Complexity Picture with More than Two Colors

Robert Ganian
Thekla Hamm
Dušan Knop
Šimon Schierreich
Ondřej Suchý

Hedonic diversity games are a variant of the classical Hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly targeted the case with two diversity classes (represented as colors in the model) and provided some initial complexitytheoretic and existential results concerning Nash and individually stable outcomes. Here, we design new algorithms accompanied with lower bounds which provide a complete parameterized-complexity picture for computing Nash and individually stable outcomes with respect to the most natural parameterizations of the problem. Crucially, our results hold for general Hedonic diversity games where the number of colors is not necessarily restricted to two, and show that—apart from two trivial cases—a necessary condition for tractability in this setting is that the number of colors is bounded by the parameter. Moreover, for the special case of two colors we resolve an open question posed in previous work.

PDF Details

I&C Journal 2015 Journal Article

A refined complexity analysis of degree anonymization in graphs

Sepp Hartung
André Nichterlein
Rolf Niedermeier
Ondřej Suchý

Motivated by a strongly growing interest in graph anonymization, we study the NP-hard Degree Anonymity problem asking whether a graph can be made k-anonymous by adding at most a given number of edges. Herein, a graph is k-anonymous if for every vertex in the graph there are at least k − 1 other vertices of the same degree. Our algorithmic results shed light on the performance quality of a popular heuristic due to Liu and Terzi [ACM SIGMOD 2008]; in particular, we show that the heuristic provides optimal solutions if “many” edges need to be added. Based on this, we develop a polynomial-time data reduction yielding a polynomial-size problem kernel for Degree Anonymity parameterized by the maximum vertex degree. In terms of parameterized complexity analysis, this result is in a sense tight since we also show that the problem is already NP-hard for H-index three, implying NP-hardness for smaller parameters such as average degree and degeneracy.

Details DOI

AAAI Conference 2012 Conference Paper

A Multivariate Complexity Analysis of Lobbying in Multiple Referenda

Robert Bredereck
Jiehua Chen
Sepp Hartung
Rolf Niedermeier
Ondřej Suchý
Stefan Kratsch

We extend work by Christian et al. [Review of Economic Design 2007] on lobbying in multiple referenda by first providing a more fine-grained analysis of the computational complexity of the NP-complete LOBBYING problem. Herein, given a binary matrix, the columns represent issues to vote on and the rows correspond to voters making a binary vote on each issue. An issue is approved if a majority of votes has a 1 in the corresponding column. The goal is to get all issues approved by modifying a minimum number of rows to all-1-rows. In our multivariate complexity analysis, we present a more holistic view on the nature of the computational complexity of LOBBYING, providing both (parameterized) tractability and intractability results, depending on various problem parameterizations to be adopted. Moreover, we show non-existence results concerning efficient and effective preprocessing for LOB- BYING and introduce natural variants such as RESTRICTED LOBBYING and PARTIAL LOBBYING.

PDF Details