Author name cluster

Thekla Hamm

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.

19 papers

2 author rows

AIJ Journal 2026 Journal Article

A structural complexity analysis of synchronous dynamical systems

Eduard Eiben
Robert Ganian
Thekla Hamm
Viktoriia Korchemna

Synchronous dynamic systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product adoption. We study the three most notable problems in synchronous dynamic systems: whether the system will transition to a target configuration from a starting configuration, whether the system will reach convergence from a starting configuration, and whether the system is guaranteed to converge from every possible starting configuration. While all three problems were known to be intractable in the classical sense, we initiate the study of their exact boundaries of tractability from the perspective of structural parameters of the network by making use of the more fine-grained parameterized complexity paradigm. As our first result, we consider treewidth - as the most prominent and ubiquitous structural parameter - and show that all three problems remain intractable even on instances of constant treewidth. We complement this negative finding with fixed-parameter algorithms for the former two problems parameterized by treedepth, a well-studied restriction of treewidth. While it is possible to rule out a similar algorithm for convergence guarantee under treedepth, we conclude with a fixed-parameter algorithm for this last problem when parameterized by treedepth and the maximum in-degree.

Details DOI

AAAI Conference 2026 Conference Paper

Edge-Binary Public Goods Games

Thekla Hamm
Paloma T. de Lima

Binary networked public goods games model situations in which players can choose whether to participate in an action at some cost which benefits players in their immediate vicinity within some typically social or infrastructural network. An important underlying assumption for this model is that participation in an action impacts the entire vicinity of participating players. However, there are numerous natural settings in which participation influences only a subset of the neighbors and is in fact more "interaction-specific''. In this work, we introduce a type of game that is more appropriate in such settings. We initiate the investigation of these games, by studying the complexity of deciding existence of their Nash equilibria in general and with respect to well-motivated structural restrictions on the network. The outcome is a comprehensive understanding of the complexity of computing Nash equilibria with respect to any combination of three natural properties of the network structure.

PDF Details DOI

AAAI Conference 2023 Conference Paper

A Structural Complexity Analysis of Synchronous Dynamical Systems

Eduard Eiben
Robert Ganian
Thekla Hamm
Viktoriia Korchemna

Synchronous dynamical systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product adoption. We study the three most notable problems in synchronous dynamical systems: whether the system will transition to a target configuration from a starting configuration, whether the system will reach convergence from a starting configuration, and whether the system is guaranteed to converge from every possible starting configuration. While all three problems were known to be intractable in the classical sense, we initiate the study of their exact boundaries of tractability from the perspective of structural parameters of the network by making use of the more fine-grained parameterized complexity paradigm. As our first result, we consider treewidth - as the most prominent and ubiquitous structural parameter - and show that all three problems remain intractable even on instances of constant treewidth. We complement this negative finding with fixed-parameter algorithms for the former two problems parameterized by treedepth, a well-studied restriction of treewidth. While it is possible to rule out a similar algorithm for convergence guarantee under treedepth, we conclude with a fixed-parameter algorithm for this last problem when parameterized by treedepth and the maximum in-degree.

PDF Details DOI

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

TARK Conference 2023 Conference Paper

Maximizing Social Welfare in Score-Based Social Distance Games

Robert Ganian
Thekla Hamm
Dusan Knop
Sanjukta Roy 0001
Simon Schierreich
Ondrej Suchý 0001

Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function u that took into account distances in a given social network. In this paper, we consider a non-normalized score-based definition of social distance games where the utility function u_v depends on a generic scoring vector v, which may be customized to match the specifics of each individual application scenario. As our main technical contribution, we establish the tractability of computing a welfare-maximizing partitioning of the agents into coalitions on tree-like networks, for every score-based function u_v. We provide more efficient algorithms when dealing with specific choices of u_v or simpler networks, and also extend all of these results to computing coalitions that are Nash stable or individually rational. We view these results as a further strong indication of the usefulness of the proposed score-based utility function: even on very simple networks, the problem of computing a welfare-maximizing partitioning into coalitions remains open for the originally considered canonical function u.

Details DOI

AIJ Journal 2023 Journal Article

Parameterized complexity of envy-free resource allocation in social networks

Eduard Eiben
Robert Ganian
Thekla Hamm
Sebastian Ordyniak

We consider the classical problem of allocating indivisible resources among agents in an envy-free (and, where applicable, proportional) way. Recently, the basic model was enriched by introducing the concept of a social network which allows to capture situations where agents might not have full information about the allocation of all resources. We initiate the study of the parameterized complexity of these resource allocation problems by considering natural parameters which capture structural properties of the network and similarities between agents and resources. In particular, we show that even very general fragments of the considered problems become tractable as long as the social network has constant treewidth or clique-width. We complement our results with matching lower bounds which show that our algorithms cannot be substantially improved.

Details DOI

AIJ Journal 2022 Journal Article

An efficient algorithm for counting Markov equivalent DAGs

Robert Ganian
Thekla Hamm
Topi Talvitie

We consider the problem of counting the number of DAGs which are Markov equivalent, i. e. , which encode the same conditional independencies between random variables. The problem has been studied, among others, in the context of causal discovery, and it is known that it reduces to counting the number of so-called moral acyclic orientations of certain undirected graphs, notably chordal graphs. Our main empirical contribution is a new algorithm which outperforms previously known exact algorithms for the considered problem by a significant margin. On the theoretical side, we show that our algorithm is guaranteed to run in polynomial time on a broad cubic-time recognisable class of chordal graphs, including interval graphs.

Details DOI

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

IJCAI Conference 2022 Conference Paper

The Complexity of Envy-Free Graph Cutting

Argyrios Deligkas
Eduard Eiben
Robert Ganian
Thekla Hamm
Sebastian Ordyniak

We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, every agent must be assigned a connected piece of this graph, and the fairness notion considered is the classical envy freeness. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph. While the problem remains NP-hard even for instances with 2 agents, we provide a dichotomy characterizing the complexity of the problem when the number of agents is constant based on structural properties of the graph. For the latter case, we design a polynomial-time algorithm when the graph has a constant number of edges.

PDF Details DOI

ICML Conference 2022 Conference Paper

The Complexity of k-Means Clustering when Little is Known

Robert Ganian
Thekla Hamm
Viktoriia Korchemna
Karolina Okrasa
Kirill Simonov

In the area of data analysis and arguably even in machine learning as a whole, few approaches have been as impactful as the classical k-means clustering. Here, we study the complexity of k-means clustering in settings where most of the data is not known or simply irrelevant. To obtain a more fine-grained understanding of the tractability of this clustering problem, we apply the parameterized complexity paradigm and obtain three new algorithms for k-means clustering of incomplete data: one for the clustering of bounded-domain (i. e. , integer) data, and two incomparable algorithms that target real-valued data. Our approach is based on exploiting structural properties of a graphical encoding of the missing entries, and we show that tractability can be achieved using significantly less restrictive parameterizations than in the complementary case of few missing entries.

Details

AAAI Conference 2022 Conference Paper

The Complexity of Temporal Vertex Cover in Small-Degree Graphs

Thekla Hamm
Nina Klobas
George B. Mertzios
Paul G. Spirakis

Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems TEM- PORAL VERTEX COVER (or TVC) and SLIDING-WINDOW TEMPORAL VERTEX COVER (or ∆-TVC for time-windows of a fixed-length ∆) have been established as natural extensions of the classic VERTEX COVER problem on static graphs with connections to areas such as surveillance in sensor networks. In this paper we initiate a systematic study of the complexity of TVC and ∆-TVC on sparse graphs. Our main result shows that for every ∆ ≥ 2, ∆-TVC is NP-hard even when the underlying topology is described by a path or a cycle. This resolves an open problem from literature and shows a surprising contrast between ∆-TVC and TVC for which we provide a polynomial-time algorithm in the same setting. To circumvent this hardness, we present a number of exact and approximation algorithms for temporal graphs whose underlying topologies are given by a path, that have bounded vertex degree in every time step, or that admit a small-sized temporal vertex cover.

PDF Details

AAAI Conference 2021 Conference Paper

The Complexity of Object Association in Multiple Object Tracking

Robert Ganian
Thekla Hamm
Sebastian Ordyniak

Object association, i. e. , the identification of which observations correspond to the same object, is a central task for the area of multiple object tracking. Two prominent models capturing this task have been introduced in the literature: the Lifted Multicut model and the more recent Lifted Paths model. Here, we carry out a detailed complexity-theoretic study of the problems arising from these two models that is aimed at complementing previous empirical work on object association. We obtain a comprehensive complexity map for both models that takes into account natural restrictions to instances such as possible bounds on the number of frames, number of tracked objects and branching degree, as well as less explicit structural restrictions such as having bounded treewidth. Our results include new fixed-parameter and XP algorithms for the problems as well as hardness proofs which altogether indicate that the Lifted Paths problem exhibits a more favorable complexity behavior than Lifted Multicut.

PDF Details

IJCAI Conference 2021 Conference Paper

The Parameterized Complexity of Connected Fair Division

Argyrios Deligkas
Eduard Eiben
Robert Ganian
Thekla Hamm
Sebastian Ordyniak

We study the Connected Fair Division problem (CFD), which generalizes the fundamental problem of fairly allocating resources to agents by requiring that the items allocated to each agent form a connected subgraph in a provided item graph G. We expand on previous results by providing a comprehensive complexity-theoretic understanding of CFD based on several new algorithms and lower bounds while taking into account several well-established notions of fairness: proportionality, envy-freeness, EF1 and EFX. In particular, we show that to achieve tractability, one needs to restrict both the agents and the item graph in a meaningful way. We design (XP)-algorithms for the problem parameterized by (1) clique-width of G plus the number of agents and (2) treewidth of G plus the number of agent types, along with corresponding lower bounds. Finally, we show that to achieve fixed-parameter tractability, one needs to not only use a more restrictive parameterization of G, but also include the maximum item valuation as an additional parameter.

PDF Details DOI

MFCS Conference 2020 Conference Paper

Extending Nearly Complete 1-Planar Drawings in Polynomial Time

Eduard Eiben
Robert Ganian
Thekla Hamm
Fabian Klute
Martin Nöllenburg

The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph G, a connected subgraph H of G and a drawing H of H, the extension problem asks whether H can be extended into a drawing of G while maintaining some desired property of the drawing (e. g. , planarity). In their breakthrough result, Angelini et al. [ACM TALG 2015] showed that the extension problem is polynomial-time solvable when the aim is to preserve planarity. Very recently we considered this problem for partial 1-planar drawings [ICALP 2020], which are drawings in the plane that allow each edge to have at most one crossing. The most important question identified and left open in that work is whether the problem can be solved in polynomial time when H can be obtained from G by deleting a bounded number of vertices and edges. In this work, we answer this question positively by providing a constructive polynomial-time decision algorithm.

Details

AAAI Conference 2020 Conference Paper

Parameterized Complexity of Envy-Free Resource Allocation in Social Networks

Eduard Eiben
Robert Ganian
Thekla Hamm
Sebastian Ordyniak

We consider the classical problem of allocating resources among agents in an envy-free (and, where applicable, proportional) way. Recently, the basic model was enriched by introducing the concept of a social network which allows to capture situations where agents might not have full information about the allocation of all resources. We initiate the study of the parameterized complexity of these resource allocation problems by considering natural parameters which capture structural properties of the network and similarities between agents and items. In particular, we show that even very general fragments of the considered problems become tractable as long as the social network has bounded treewidth or bounded clique-width. We complement our results with matching lower bounds which show that our algorithms cannot be substantially improved.

PDF Details

IJCAI Conference 2020 Conference Paper

Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP

Jiehua Chen
Robert Ganian
Thekla Hamm

We investigate the following many-to-one stable matching problem with diversity constraints (SMTI-DIVERSE): Given a set of students and a set of colleges which have preferences over each other, where the students have overlapping types, and the colleges each have a total capacity as well as quotas for individual types (the diversity constraints), is there a matching satisfying all diversity constraints such that no unmatched student-college pair has an incentive to deviate? SMTI-DIVERSE is known to be NP-hard. However, as opposed to the NP-membership claims in the literature [Aziz et al. , AAMAS 2019; Huang, SODA 2010], we prove that it is beyond NP: it is complete for the complexity class Σ^P_2. In addition, we provide a comprehensive analysis of the problem’s complexity from the viewpoint of natural restrictions to inputs and obtain new algorithms for the problem.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

The Complexity Landscape of Resource-Constrained Scheduling

Robert Ganian
Thekla Hamm
Guillaume Mescoff

The Resource-Constrained Project Scheduling Problem (RCPSP) and its extension via activity modes (MRCPSP) are well-established scheduling frameworks that have found numerous applications in a broad range of settings related to artificial intelligence. Unsurprisingly, the problem of finding a suitable schedule in these frameworks is known to be NP-complete; however, aside from a few results for special cases, we have lacked an in-depth and comprehensive understanding of the complexity of the problems from the viewpoint of natural restrictions of the considered instances. In the first part of our paper, we develop new algorithms and give hardness-proofs in order to obtain a detailed complexity map of (M)RCPSP that settles the complexity of all 1024 considered variants of the problem defined in terms of explicit restrictions of natural parameters of instances. In the second part, we turn to implicit structural restrictions defined in terms of the complexity of interactions between individual activities. In particular, we show that if the treewidth of a graph which captures such interactions is bounded by a constant, then we can solve MRCPSP in polynomial time.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Title

Robert Ganian
Thekla Hamm
Topi Talvitie

We consider the problem of counting the number of DAGs which are Markov-equivalent, i. e. , which encode the same conditional independencies between random variables. The problem has been studied, among others, in the context of causal discovery, and it is known that it reduces to counting the number of so-called moral acyclic orientations of certain undirected graphs, notably chordal graphs. Our main empirical contribution is a new algorithm which outperforms previously known exact algorithms for the considered problem by a signiﬁcant margin. On the theoretical side, we show that our algorithm is guaranteed to run in polynomial time on a broad class of chordal graphs, including interval graphs.

PDF Details

MFCS Conference 2019 Conference Paper

Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth

Eduard Eiben
Robert Ganian
Thekla Hamm
O-joung Kwon

We develop a framework for applying treewidth-based dynamic programming on graphs with "hybrid structure", i. e. , with parts that may not have small treewidth but instead possess other structural properties. Informally, this is achieved by defining a refinement of treewidth which only considers parts of the graph that do not belong to a pre-specified tractable graph class. Our approach allows us to not only generalize existing fixed-parameter algorithms exploiting treewidth, but also fixed-parameter algorithms which use the size of a modulator as their parameter. As the flagship application of our framework, we obtain a parameter that combines treewidth and rank-width to obtain fixed-parameter algorithms for Chromatic Number, Hamiltonian Cycle, and Max-Cut.

Details