Eduard Eiben

AIJ Journal 2026 Journal Article

A structural complexity analysis of synchronous dynamical systems

• Eduard Eiben
• Robert Ganian
• Thekla Hamm
• Viktoriia Korchemna

AAAI Conference 2026 Conference Paper

Dividing Indivisible Items for the Benefit of All: It Is Hard to Be Fair Without Social Awareness

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith
• Dušan Knop
• Šimon Schierreich

In standard fair division models, we assume that all agents are selfish. However, in many scenarios, division of resources has a direct impact on the whole group or even society. Therefore, we study fair allocations of indivisible items that, at the same time, maximize social impact. In this model, each agent is associated with two additive functions that define their value and social impact for each item. The goal is to allocate items so that the social impact is maximized while maintaining some fairness criterion. We reveal that the complexity of the problem heavily depends on whether the agents are socially aware, i.e., they take into consideration the social impact functions. For socially unaware agents, we prove that the problem is NP-hard for a variety of fairness notions, and that it is tractable only for very restricted cases, e.g., if for every agent valuation equals social impact and it is binary. On the other hand, social awareness allows for fair allocations that maximize social impact, and such allocations can be computed in polynomial time. Interestingly, the problem becomes again intractable as soon as the definition of social awareness is relaxed.

AAAI Conference 2026 Short Paper

Network Restoration Games with Quotas (Student Abstract)

• Philip Bogaars
• Argyrios Deligkas
• Eduard Eiben
• Michail Fasoulakis

In a game of Network Restoration Games With Quotas, there is an underlying graph where a subset of its edges have to be restored by a set of agents. Each agent has a creation cost for each such edge, a traversal cost for every edge of the graph, and in addition they have a quota on the number of edges they have to restore. Then, given a set of edges that fulfill the quota, the cost of an agent is the cost of creating these edges, plus the cost of reaching them, i.e., the traversal cost. We prove that any cost-minimizing allocation is swap-stable, i.e., there is no profitable exchange of edges between any pair of agents, but computing one is hard even on trees. We complement this by designing an algorithm that finds a swap-stable allocation on trees in polynomial time and we quantify its cost against the optimal one.

AAAI Conference 2025 Conference Paper

Balanced and Fair Partitioning of Friends

• Argyrios Deligkas
• Eduard Eiben
• Stavros D. Ioannidis
• Dušan Knop
• Šimon Schierreich

In the recently introduced model of fair partitioning of friends, there is a set of agents located on the vertices of an underlying graph that indicates the friendships between the agents. The task is to partition the graph into k balanced-sized groups, keeping in mind that the value of an agent for a group is equal to the number of edges they have in that group. The goal is to construct partitions that are "fair", i.e., no agent would like to replace an agent in a different group. We generalize the standard model by considering utilities for the agents that are beyond binary and additive. Having this as our foundation, our contribution is threefold: (a) we adapt several fairness notions that have been developed in the fair division literature to our setting; (b) we give several existence guarantees supported by polynomial-time algorithms; (c) we initiate the study of the computational (and parameterized) complexity of the model and provide an almost complete landscape of the (in)tractability frontier for our fairness concepts.

IJCAI Conference 2025 Conference Paper

EF1 and EFX Orientations

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith
• Viktoriia Korchemna

We study the problem of finding fair allocations -- EF1 and EFX -- of indivisible goods with orientations. In an orientation, every agent gets items from their own predetermined set. For EF1, we show that EF1 orientations always exist when agents have monotone valuations, via a pseudopolynomial-time algorithm. This surprisingly positive result is the main contribution of our paper. We complement this result with a comprehensive set of scenarios where our algorithm, or a slight modification of it, finds an EF1 orientation in polynomial time. For EFX, we focus on the recently proposed graph instances, where every agent corresponds to a vertex on a graph and their allowed set of items consists of the edges incident to their vertex. It was shown that finding an EFX orientation is NP-complete in general. We prove that it remains intractable even when the graph has a vertex cover of size 8, or when we have a multigraph with only 10 vertices. We essentially match these strong negative results with a fixed-parameter tractable algorithm that is virtually the best someone could hope for.

AAAI Conference 2025 Conference Paper

How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs

• Argyrios Deligkas
• Michelle Döring
• Eduard Eiben
• Tiger-Lily Goldsmith
• George Skretas
• Georg Tennigkeit

Logistics and transportation networks require a large amount of resources to realise necessary connections between locations and minimizing these resources is a vital aspect of planning research. Since such networks have dynamic connections that are only available at specific times, intricate models are needed to portray them accurately. In this paper, we study the problem of minimizing the number of resources needed to realise a dynamic network, using the temporal graphs model. In a temporal graph, edges appear at specific points in time. Given a temporal graph and a natural number k, we ask whether we can cover every temporal edge exactly once using at most k temporal journeys; in a temporal journey consecutive edges have to adhere to the order of time. We conduct a thorough investigation of the complexity of the problem with respect to four dimensions: (a) whether the type of the temporal journey is a walk, a trail, or a path; (b) whether the chronological order of edges in the journey is strict or non-strict; (c) whether the temporal graph is directed or undirected; (d) whether the start and end points of each journey are given. We almost completely resolve the complexity of these problems and provide dichotomies for each of them with respect to k.

AAMAS Conference 2025 Conference Paper

Parameterized Algorithms for Multiagent Pathfinding on Trees

• Argyrios Deligkas
• Eduard Eiben
• Robert Ganian
• Iyad Kanj
• M. S. Ramanujan

The classical Multiagent Pathfinding problem has been extensively studied not only within the artificial intelligence research community, but also by scholars in the areas of theoretical computer science and computational geometry. The problem asks for a minimum-makespan schedule that routes 𝑘 agents (or robots) from their starting points to their destinations in a graph, while avoiding collisions, and is known to be NP-hard even on the fundamental class of trees. In this article we present two fixed parameter algorithms parameterized by 𝑘: the first yields a collision-free schedule on trees whose makespan deviates from the optimum by at most an additive polynomial function of 𝑘, and the second solves Multiagent Pathfinding optimally on the class of irreducible trees, i. e. , trees with no vertices of degree 2. Both results rely on novel tools and insights into the properties of optimal schedules.

AAAI Conference 2025 Conference Paper

The Complexity of Extending Fair Allocations of Indivisible Goods

• Argyrios Deligkas
• Eduard Eiben
• Robert Ganian
• Tiger-Lily Goldsmith
• Stavros D. Ioannidis

We initiate the study of computing envy-free allocations of indivisible items in the extension setting, i.e., when some part of the allocation is fixed and the task is to allocate the remaining items. In view of the NP-hardness of the problem, we investigate whether - and under which conditions - one can obtain fixed-parameter algorithms for computing a solution in settings where most of the allocation is already fixed. Our results provide a broad complexity-theoretic classification of the problem which includes: (a) fixed-parameter algorithms tailored to settings with few distinct types of agents or items; (b) lower bounds which exclude the generalization of these positive results to more general settings. We conclude by showing that - unlike when computing allocations from scratch - the non-algorithmic question of whether more relaxed EF1 or EFX allocations exist can be completely resolved in the extension setting.

SODA Conference 2024 Conference Paper

Determinantal Sieving

• Eduard Eiben
• Tomohiro Koana
• Magnus Wahlström

IJCAI Conference 2024 Conference Paper

Individual Rationality in Topological Distance Games Is Surprisingly Hard

• Argyrios Deligkas
• Eduard Eiben
• Dušan Knop
• Šimon Schierreich

In the recently introduced topological distance games, strategic agents need to be assigned to a subset of vertices of a topology. In the assignment, the utility of an agent depends on both the agent's inherent utilities for other agents and its distance from them on the topology. We study the computational complexity of finding individually-rational outcomes; this notion is widely assumed to be the very minimal stability requirement and requires that the utility of every agent in a solution is non-negative. We perform a comprehensive study of the problem's complexity, and we prove that even in very basic cases, deciding whether an individually-rational solution exists is intractable. To reach at least some tractability, one needs to combine multiple restrictions of the input instance, including the number of agents and the topology and the influence of distant agents on the utility.

AAAI Conference 2024 Conference Paper

Learning Small Decision Trees for Data of Low Rank-Width

• Konrad K. Dabrowski
• Eduard Eiben
• Sebastian Ordyniak
• Giacomo Paesani
• Stefan Szeider

We consider the NP-hard problem of finding a smallest decision tree representing a classification instance in terms of a partially defined Boolean function. Small decision trees are desirable to provide an interpretable model for the given data. We show that the problem is fixed-parameter tractable when parameterized by the rank-width of the incidence graph of the given classification instance. Our algorithm proceeds by dynamic programming using an NLC decomposition obtained from a rank-width decomposition. The key to the algorithm is a succinct representation of partial solutions. This allows us to limit the space and time requirements for each dynamic programming step in terms of the parameter.

AAAI Conference 2024 Conference Paper

The Complexity of Fair Division of Indivisible Items with Externalities

• Argyrios Deligkas
• Eduard Eiben
• Viktoriia Korchemna
• Šimon Schierreich

We study the computational complexity of fairly allocating a set of indivisible items under externalities. In this recently-proposed setting, in addition to the utility the agent gets from their bundle, they also receive utility from items allocated to other agents. We focus on the extended definitions of envy-freeness up to one item (EF1) and of envy-freeness up to any item (EFX), and we provide the landscape of their complexity for several different scenarios. We prove that it is NP-complete to decide whether there exists an EFX allocation, even when there are only three agents, or even when there are only six different values for the items. We complement these negative results by showing that when both the number of agents and the number of different values for items are bounded by a parameter the problem becomes fixed-parameter tractable. Furthermore, we prove that two-valued and binary-valued instances are equivalent and that EFX and EF1 allocations coincide for this class of instances. Finally, motivated from real-life scenarios, we focus on a class of structured valuation functions, which we term agent/item-correlated. We prove their equivalence to the "standard" setting without externalities. Therefore, all previous results for EF1 and EFX apply immediately for these valuations.

AAMAS Conference 2024 Conference Paper

The Parameterized Complexity of Welfare Guarantees in Schelling Segregation

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith

Schelling’s model considers 𝑘 types of agents each of whom needs to select a vertex on an undirected graph, where every agent prefers neighboring agents of the same type. We are motivated by a recent line of work that studies solutions that are optimal with respect to notions related to the welfare of the agents. We explore the parameterized complexity of computing such solutions. We focus on the well-studied notions of social welfare (WO) and Pareto optimality (PO), alongside the recently proposed notions of group-welfare optimality (GWO) and utility-vector optimality (UVO), both of which lie between WO and PO. Firstly, we focus on the fundamental case where 𝑘 = 2 and there are 𝑟 red agents and 𝑏 blue agents. We show that all solution-notions we consider are intractable even when 𝑏 = 1 and that they do not admit an FPT algorithm when parameterized by 𝑟 and 𝑏, unless FPT = W[1]. In addition, we show that WO and GWO remain intractable even on cubic graphs. We complement these negative results with an FPT algorithm parameterized by 𝑟, 𝑏 and the maximum degree of the graph. For the general case with 𝑘 types of agents, we prove that for any of the notions we consider the problem remains hard when parameterized by 𝑘 for a large family of graphs that includes trees. We accompany these negative results with an XP algorithm parameterized by 𝑘 and the treewidth of the graph.

TCS Journal 2024 Journal Article

The parameterized complexity of welfare guarantees in Schelling segregation

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith

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.

AAMAS Conference 2023 Conference Paper

Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith
• George Skretas

We consider the influence maximization problem over a temporal graph, where there is a single fixed source. We deviate from the standard model of influence maximization, where the goal is to choose the set of most influential vertices. Instead, in our model we are given a fixed vertex, or source, and the goal is to find the best time steps to transmit so that the influence of this vertex is maximized. We frame this problem as a spreading process that follows a variant of the susceptible-infected-susceptible (SIS) model and we focus on three objective functions. In the MaxSpread objective, the goal is to maximize the total number of vertices that get infected at least once. In the MaxViral objective, the goal is to maximize the number of vertices that are infected at the same time step. Finally, in MaxViralTstep, the goal is to maximize the number of vertices that are infected at a given time step. We perform a thorough complexity theoretic analysis for these three objectives over three different scenarios: (1) the unconstrained setting where the source can transmit whenever it wants; (2) the window-constrained setting where the source has to transmit at either a predetermined, or a shifting window; (3) the periodic setting where the temporal graph has a small period. We prove that all of these problems, with the exception of MaxSpread for periodic graphs, are intractable even for very simple underlying graphs.

IJCAI Conference 2023 Conference Paper

Complexity of Efficient Outcomes in Binary-Action Polymatrix Games and Implications for Coordination Problems

• Argyrios Deligkas
• Eduard Eiben
• Gregory Gutin
• Philip Neary
• Anders Yeo

We investigate the difficulty of finding economically efficient solutions to coordination problems on graphs. Our work focuses on two forms of coordination problem: pure-coordination games and anti-coordination games. We consider three objectives in the context of simple binary-action polymatrix games: (i) maximizing welfare, (ii) maximizing potential, and (iii) finding a welfare-maximizing Nash equilibrium. We introduce an intermediate, new graph-partition problem, termed MWDP, which is of independent interest, and we provide a complexity dichotomy for it. This dichotomy, among other results, provides as a corollary a dichotomy for Objective (i) for general binary-action polymatrix games. In addition, it reveals that the complexity of achieving these objectives varies depending on the form of the coordination problem. Specifically, Objectives (i) and (ii) can be efficiently solved in pure-coordination games, but are NP-hard in anti-coordination games. Finally, we show that objective (iii) is NP-hard even for simple non-trivial pure-coordination games.

MFCS Conference 2023 Conference Paper

Finding a Highly Connected Steiner Subgraph and its Applications

• Eduard Eiben
• Diptapriyo Majumdar
• M. S. Ramanujan 0001

Given a (connected) undirected graph G, a set X ⊆ V(G) and integers k and p, the Steiner Subgraph Extension problem asks whether there exists a set S ⊇ X of at most k vertices such that G[S] is a p-edge-connected subgraph. This problem is a natural generalization of the well-studied Steiner Tree problem (set p = 1 and X to be the terminals). In this paper, we initiate the study of Steiner Subgraph Extension from the perspective of parameterized complexity and give a fixed-parameter algorithm (i. e. , FPT algorithm) parameterized by k and p on graphs of bounded degeneracy (removing the assumption of bounded degeneracy results in W-hardness). Besides being an independent advance on the parameterized complexity of network design problems, our result has natural applications. In particular, we use our result to obtain new single-exponential FPT algorithms for several vertex-deletion problems studied in the literature, where the goal is to delete a smallest set of vertices such that: (i) the resulting graph belongs to a specified hereditary graph class, and (ii) the deleted set of vertices induces a p-edge-connected subgraph of the input graph.

IJCAI Conference 2023 Conference Paper

Learning Small Decision Trees with Large Domain

• Eduard Eiben
• Sebastian Ordyniak
• Giacomo Paesani
• Stefan Szeider

One favors decision trees (DTs) of the smallest size or depth to facilitate explainability and interpretability. However, learning such an optimal DT from data is well-known to be NP-hard. To overcome this complexity barrier, Ordyniak and Szeider (AAAI 21) initiated the study of optimal DT learning under the parameterized complexity perspective. They showed that solution size (i. e. , number of nodes or depth of the DT) is insufficient to obtain fixed-parameter tractability (FPT). Therefore, they proposed an FPT algorithm that utilizes two auxiliary parameters: the maximum difference (as a structural property of the data set) and maximum domain size. They left it as an open question of whether bounding the maximum domain size is necessary. The main result of this paper answers this question. We present FPT algorithms for learning a smallest or lowest-depth DT from data, with the only parameters solution size and maximum difference. Thus, our algorithm is significantly more potent than the one by Szeider and Ordyniak as it can handle problem inputs with features that range over unbounded domains. We also close several gaps concerning the quality of approximation one obtains by only considering DTs based on minimum support sets.

IJCAI Conference 2023 Conference Paper

Minimizing Reachability Times on Temporal Graphs via Shifting Labels

• Argyrios Deligkas
• Eduard Eiben
• George Skretas

We study how we can accelerate the spreading of information in temporal graphs via shifting operations; a problem that captures real-world applications varying from information flows to distribution schedules. In a temporal graph there is a set of fixed vertices and the available connections between them change over time in a predefined manner. We observe that, in some cases, shifting some connections, i. e. , advancing or delaying them, can decrease the time required to reach from some vertex (source) to another vertex. We study how we can minimize the maximum time a set of sources needs to reach every vertex, when we are allowed to shift some of the connections. If we restrict the allowed number of changes, we prove that, already for a single source, the problem is NP-hard, and W[2]-hard when parameterized by the number of changes. Then we focus on unconstrained number of changes. We derive a polynomial-time algorithm when there is one source. When there are two sources, we show that the problem becomes NP-hard; on the other hand, we design an FPT algorithm parameterized by the treewidth of the graph plus the lifetime of the optimal solution, that works for any number of sources. Finally, we provide polynomial-time algorithms for several graph classes.

AIJ Journal 2023 Journal Article

Parameterized complexity of envy-free resource allocation in social networks

• Eduard Eiben
• Robert Ganian
• Thekla Hamm
• Sebastian Ordyniak

TCS Journal 2023 Journal Article

Preference swaps for the stable matching problem

• Eduard Eiben
• Gregory Gutin
• Philip R. Neary
• Clément Rambaud
• Magnus Wahlström
• Anders Yeo

ICML Conference 2023 Conference Paper

The Computational Complexity of Concise Hypersphere Classification

• Eduard Eiben
• Robert Ganian
• Iyad A. Kanj
• Sebastian Ordyniak
• Stefan Szeider

Hypersphere classification is a classical and foundational method that can provide easy-to-process explanations for the classification of real-valued as well as binary data. However, obtaining an (ideally concise) explanation via hypersphere classification is much more difficult when dealing with binary data as opposed to real-valued data. In this paper, we perform the first complexity-theoretic study of the hypersphere classification problem for binary data. We use the fine-grained parameterized complexity paradigm to analyze the impact of structural properties that may be present in the input data as well as potential conciseness constraints. Our results include not only stronger lower bounds but also a number of new fixed-parameter algorithms for hypersphere classification of binary data, which can find an exact and concise explanation when one exists.

AAMAS Conference 2023 Conference Paper

The Parameterized Complexity of Welfare Guarantees in Schelling Segregation

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith

Schelling’s model considers 𝑘 types of agents each of whom needs to select a vertex on an undirected graph, where every agent prefers neighbor agents of the same type. We are motivated by a recent line of work that studies solutions that are optimal with respect to notions related to the welfare of the agents. We explore the parameterized complexity of computing such solutions. We focus on the well-studied notions of social welfare and Pareto optimality, alongside the recently proposed notions of group-welfare optimality and utility-vector optimality.

IJCAI Conference 2022 Conference Paper

Parameterized Complexity of Hotelling-Downs with Party Nominees

• Argyrios Deligkas
• Eduard Eiben
• Tiger-Lily Goldsmith

We study a generalization of the Hotelling-Downs model through the lens of parameterized complexity. In this model, there is a set of voters on a line and a set of parties that compete over them. Each party has to choose a nominee from a set of candidates with predetermined positions on the line, where each candidate comes at a different cost. The goal of every party is to choose the most profitable nominee, given the nominees chosen by the rest of the parties; the profit of a party is the number of voters closer to their nominee minus its cost. We examine the complexity of deciding whether a pure Nash equilibrium exists for this model under several natural parameters: the number of different positions of the candidates, the discrepancy and the span of the nominees, and the overlap of the parties. We provide FPT and XP algorithms and we complement them with a W[1]-hardness result.

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.

SODA Conference 2021 Conference Paper

EPTAS for k -means Clustering of Affine Subspaces

• Eduard Eiben
• Fedor V. Fomin
• Petr A. Golovach
• William Lochet
• Fahad Panolan
• Kirill Simonov

We consider a generalization of the fundamental k -means clustering for data with incomplete or corrupted entries. When data objects are represented by points in ℝ d, a data point is said to be incomplete when some of its entries are missing or unspecified. An incomplete data point with at most Δ unspecified entries corresponds to an axis-parallel affine subspace of dimension at most Δ, called a Δ-point. Thus we seek a partition of n input Δ-points into k clusters minimizing the k -means objective. For Δ = 0, when all coordinates of each point are specified, this is the usual k -means clustering. We give an algorithm that finds an (1 + ∊ )-approximate solution in time f ( k, ∊, Δ) · n 2 · d for some function f of k, ∊, and Δ only.

AIJ Journal 2021 Journal Article

The complexity landscape of decompositional parameters for ILP: Programs with few global variables and constraints

• Pavel Dvořák
• Eduard Eiben
• Robert Ganian
• Dušan Knop
• Sebastian Ordyniak

AAAI Conference 2021 Conference Paper

The Parameterized Complexity of Clustering Incomplete Data

• Eduard Eiben
• Robert Ganian
• Iyad Kanj
• Sebastian Ordyniak
• Stefan Szeider

We study fundamental clustering problems for incomplete data. Specifically, given a set of incomplete d-dimensional vectors (representing rows of a matrix), the goal is to complete the missing vector entries in a way that admits a partitioning of the vectors into at most k clusters with radius or diameter at most r. We give tight characterizations of the parameterized complexity of these problems with respect to the parameters k, r, and the minimum number of rows and columns needed to cover all the missing entries. We show that the considered problems are fixed-parameter tractable when parameterized by the three parameters combined, and that dropping any of the three parameters results in parameterized intractability. A byproduct of our results is that, for the complete data setting, all problems under consideration are fixed-parameter tractable parameterized by k + r.

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.

MFCS Conference 2020 Conference Paper

A Polynomial Kernel for 3-Leaf Power Deletion

• Jungho Ahn
• Eduard Eiben
• O-joung Kwon
• Sang-il Oum

For a non-negative integer 𝓁, a graph G is an 𝓁-leaf power of a tree T if V(G) is equal to the set of leaves of T, and distinct vertices v and w of G are adjacent if and only if the distance between v and w in T is at most 𝓁. Given a graph G, 3-Leaf Power Deletion asks whether there is a set S ⊆ V(G) of size at most k such that G\S is a 3-leaf power of some treeT. We provide a polynomial kernel for this problem. More specifically, we present a polynomial-time algorithm for an input instance (G, k) to output an equivalent instance (G', k') such that k'≤ k and G' has at most O(k^14) vertices.

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.

AAAI Conference 2020 Conference Paper

Manipulating Districts to Win Elections: Fine-Grained Complexity

• Eduard Eiben
• Fedor Fomin
• Fahad Panolan
• Kirill Simonov

Gerrymandering is a practice of manipulating district boundaries and locations in order to achieve a political advantage for a particular party. Lewenberg, Lev, and Rosenschein [AAMAS 2017] initiated the algorithmic study of a geographically-based manipulation problem, where voters must vote at the ballot box closest to them. In this variant of gerrymandering, for a given set of possible locations of ballot boxes and known political preferences of n voters, the task is to identify locations for k boxes out of m possible locations to guarantee victory of a certain party in at least districts. Here integers k and are some selected parameter. It is known that the problem is NP-complete already for 4 political parties and prior to our work only heuristic algorithms for this problem were developed. We initiate the rigorous study of the gerrymandering problem from the perspectives of parameterized and fine-grained complexity and provide asymptotically matching lower and upper bounds on its computational complexity. We prove that the problem is W[1]-hard parameterized by k + n and that it does not admit an f(n, k) · mo( √ k) algorithm for any function f of k and n only, unless the Exponential Time Hypothesis (ETH) fails. Our lower bounds hold already for 2 parties. On the other hand, we give an algorithm that solves the problem for a constant number of parties in time (m + n)O( √ k).

AAAI Conference 2020 Conference Paper

On the Problem of Covering a 3-D Terrain

• Eduard Eiben
• Isuru Godage
• Iyad Kanj
• Ge Xia

We study the problem of covering a 3-dimensional terrain by a sweeping robot that is equipped with a camera. We model the terrain as a mesh in a way that captures the elevation levels of the terrain; this enables a graph-theoretic formulation of the problem in which the underlying graph is a weighted plane graph. We show that the associated graph problem is NP-hard, and that it admits a polynomial time approximation scheme (PTAS). Finally, we implement two heuristic algorithms based on greedy approaches and report our findings.

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.

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.

AAAI Conference 2019 Conference Paper

Solving Integer Quadratic Programming via Explicit and Structural Restrictions

• Eduard Eiben
• Robert Ganian
• Dusan Knop
• Sebastian Ordyniak

We study the parameterized complexity of Integer Quadratic Programming under two kinds of restrictions: explicit restrictions on the domain or coefficients, and structural restrictions on variable interactions. We argue that both kinds of restrictions are necessary to achieve tractability for Integer Quadratic Programming, and obtain four new algorithms for the problem that are tuned to possible explicit restrictions of instances that we may wish to solve. The presented algorithms are exact, deterministic, and complemented by appropriate lower bounds.

NeurIPS Conference 2019 Conference Paper

The Parameterized Complexity of Cascading Portfolio Scheduling

• Eduard Eiben
• Robert Ganian
• Iyad Kanj
• Stefan Szeider

Cascading portfolio scheduling is a static algorithm selection strategy which uses a sample of test instances to compute an optimal ordering (a cascading schedule) of a portfolio of available algorithms. The algorithms are then applied to each future instance according to this cascading schedule, until some algorithm in the schedule succeeds. Cascading algorithm scheduling has proven to be effective in several applications, including QBF solving and the generation of ImageNet classification models. It is known that the computation of an optimal cascading schedule in the offline phase is NP-hard. In this paper we study the parameterized complexity of this problem and establish its fixed-parameter tractability by utilizing structural properties of the success relation between algorithms and test instances. Our findings are significant as they reveal that in spite of the intractability of the problem in its general form, one can indeed exploit sparseness or density of the success relation to obtain non-trivial runtime guarantees for finding an optimal cascading schedule.

IJCAI Conference 2018 Conference Paper

A Structural Approach to Activity Selection

• Eduard Eiben
• Robert Ganian
• Sebastian Ordyniak

The general task of finding an assignment of agents to activities under certain stability and rationality constraints has led to the introduction of two prominent problems in the area of computational social choice: Group Activity Selection (GASP) and Stable Invitations (SIP). Here we introduce and study the Comprehensive Activity Selection Problem, which naturally generalizes both of these problems. In particular, we apply the parameterized complexity paradigm, which has already been successfully employed for SIP and GASP. While previous work has focused strongly on parameters such as solution size or number of activities, here we focus on parameters which capture the complexity of agent-to-agent interactions. Our results include a comprehensive complexity map for CAS under various restrictions on the number of activities in combination with restrictions on the complexity of agent interactions.

AAAI Conference 2018 Conference Paper

Improved Results for Minimum Constraint Removal

• Eduard Eiben
• Jonathan Gemmell
• Iyad Kanj
• Andrew Youngdahl

Given a set of obstacles and two designated points in the plane, the MINIMUM CONSTRAINT REMOVAL problem asks for a minimum number of obstacles that can be removed so that a collision-free path exists between the two designated points. It is a well-studied problem in both robotic motion planning and wireless computing that has been shown to be NP-hard in various settings. In this work, we extend the study of MINIMUM CONSTRAINT REMOVAL. We start by presenting refined NP-hardness reductions for the two cases: (1) when all the obstacles are axes-parallel rectangles, and (2) when all the obstacles are line segments such that no three intersect at the same point. These results improve on existing results in the literature. As a byproduct of our NP-hardness reductions, we prove that, unless the Exponential-Time Hypothesis (ETH) fails, MIN- IMUM CONSTRAINT REMOVAL cannot be solved in subexponential time 2o(n), where n is the number of obstacles in the instance. This shows that significant improvement on the brute-force 2O(n) -time algorithm is unlikely. We then present a subexponential-time algorithm for instances of MINIMUM CONSTRAINT REMOVAL in which the number of obstacles that overlap at any point is constant; the algorithm runs in time 2O( √ N), where N is the number of the vertices in the auxiliary graph associated with the instance of the problem. We show that significant improvement on this algorithm is unlikely by showing that, unless ETH fails, MIN- IMUM CONSTRAINT REMOVAL with bounded overlap number cannot be solved in time 2o( √ N). We describe several exact algorithms and approximation algorithms that leverage heuristics and discuss their performance in an extensive empirical simulation.

IJCAI Conference 2018 Conference Paper

Unary Integer Linear Programming with Structural Restrictions

• Eduard Eiben
• Robert Ganian
• Dušan Knop
• Sebastian Ordyniak

Recently a number of algorithmic results have appeared which show the tractability of Integer Linear Programming (ILP) instances under strong restrictions on variable domains and/or coefficients (AAAI 2016, AAAI 2017, IJCAI 2017). In this paper, we target ILPs where neither the variable domains nor the coefficients are restricted by a fixed constant or parameter; instead, we only require that our instances can be encoded in unary. We provide new algorithms and lower bounds for such ILPs by exploiting the structure of their variable interactions, represented as a graph. Our first set of results focuses on solving ILP instances through the use of a graph parameter called clique-width, which can be seen as an extension of treewidth which also captures well-structured dense graphs. In particular, we obtain a polynomial-time algorithm for instances of bounded clique-width whose domain and coefficients are polynomially bounded by the input size, and we complement this positive result by a number of algorithmic lower bounds. Afterwards, we turn our attention to ILPs with acyclic variable interactions. In this setting, we obtain a complexity map for the problem with respect to the graph representation used and restrictions on the encoding.

MFCS Conference 2017 Conference Paper

Lossy Kernels for Hitting Subgraphs

• Eduard Eiben
• Danny Hermelin
• M. S. Ramanujan 0001

In this paper, we study the Connected H-hitting Set and Dominating Set problems from the perspective of approximate kernelization, a framework recently introduced by Lokshtanov et al. [STOC 2017]. For the Connected H-hitting set problem, we obtain an \alpha-approximate kernel for every \alpha>1 and complement it with a lower bound for the natural weighted version. We then perform a refined analysis of the tradeoff between the approximation factor and kernel size for the Dominating Set problem on d-degenerate graphs and provide an interpolation of approximate kernels between the known d^2-approximate kernel of constant size and 1-approximate kernel of size k^{O(d^2)}.

IJCAI Conference 2017 Conference Paper

Solving Integer Linear Programs with a Small Number of Global Variables and Constraints

• Pavel Dvořák
• Eduard Eiben
• Robert Ganian
• Dušan Knop
• Sebastian Ordyniak

Integer Linear Programming (ILP) has a broad range of applications in various areas of artificial intelligence. Yet in spite of recent advances, we still lack a thorough understanding of which structural restrictions make ILP tractable. Here we study ILP instances consisting of a small number of ``global'' variables and/or constraints such that the remaining part of the instance consists of small and otherwise independent components; this is captured in terms of a structural measure we call fracture backdoors which generalizes, for instance, the well-studied class of N-fold ILP instances. Our main contributions can be divided into three parts. First, we formally develop fracture backdoors and obtain exact and approximation algorithms for computing these. Second, we exploit these backdoors to develop several new parameterized algorithms for ILP; the performance of these algorithms will naturally scale based on the number of global variables or constraints in the instance. Finally, we complement the developed algorithms with matching lower bounds. Altogether, our results paint a near-complete complexity landscape of ILP with respect to fracture backdoors.

MFCS Conference 2017 Conference Paper

Towards a Polynomial Kernel for Directed Feedback Vertex Set

• Benjamin Bergougnoux
• Eduard Eiben
• Robert Ganian
• Sebastian Ordyniak
• M. S. Ramanujan 0001

In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008]; since then, the existence of a polynomial kernel for this problem has become one of the largest open problems in the area of parameterized algorithmics. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlying undirected graph. We provide two main contributions: a polynomial kernel for this problem on general instances, and a linear kernel for the case where the input digraph is embeddable on a surface of bounded genus.

MFCS Conference 2016 Conference Paper

A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion

• Eduard Eiben
• Robert Ganian
• O-joung Kwon

Vertex deletion problems ask whether it is possible to delete at most k vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years, the parameterized complexity of vertex deletion to a plethora of graph classes has been systematically researched. Here we present the first single-exponential fixed-parameter algorithm for vertex deletion to distance-hereditary graphs, a well-studied graph class which is particularly important in the context of vertex deletion due to its connection to the graph parameter rank-width. We complement our result with matching asymptotic lower bounds based on the exponential time hypothesis.