5 papers
Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy
Argyrios Deligkas, Eduard Eiben, Robert Ganian +2
We study the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of …
Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems
Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan
Given a simple connected undirected graph G = (V, E), a set X \subseteq V(G), and integers k and p, STEINER SUBGRAPH EXTENSION problem asks if there exists a set S \supseteq X with…
On the Parameterized Complexity of Eulerian Strong Component Arc Deletion
Václav Blažej, Satyabrata Jana, M. S. Ramanujan +1
In this paper, we study the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure…
Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
Christian Komusiewicz, Diptapriyo Majumdar
Enumeration kernelization was first proposed by Creignou et al. [TOCS 2017] and was later refined by Golovach et al. [JCSS 2022] into two different variants: fully-polynomial enume…
Packing Short Cycles
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +6
Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of v…