Thekla Hamm

Thekla Hamm, Bart M. P. Jansen, Faezeh Motiei

We study generalizations of the Steiner Tree problem motivated by the design of power networks. While Steiner Tree asks for a single minimum-cost tree connecting given terminal vertices, a power network typically consists of multiple trees, each connecting a subset of the terminals, to avoid electrical overloads. The cost of installing depends on both the cable lengths and the cost of digging underground trenches for putting the cables where the digging costs can be shared. These leads to variants of Steiner Tree where the goal is to compute a minimum-cost set of Steiner trees with a common root, that together connect all terminals while balancing the power demand of the terminals in each tree. Two important variants arise depending on whether the network is intended for low-voltage or high-voltage power. In the low-voltage case, power loss imposes a bound on the maximum depth of each tree, while no such restriction applies in the high-voltage case. We study the parameterized complexity of several power network design problems, parameterized by the number of terminals. While Steiner Tree is fixed-parameter tractable under this parameterization, most of our variants are W[1]-hard. For low-voltage networks, we present an XP-algorithm for planar inputs based on structural bounds on the treewidth of solution subgraphs. We also give a reduction from Grid Tiling showing tightness under ETH. The XP-algorithm extends to the high-voltage setting and general graphs, albeit at a cost in the running time. For high-voltage networks, we show the problem remains W[1]-hard even on planar graphs. Finally, we explore a variant of the cost model for sharing digging costs in which both problems become fixed-parameter tractable.

Argyrios Deligkas, Eduard Eiben, Robert Ganian et al.

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.

Eduard Eiben, Robert Ganian, Thekla Hamm et al.

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.