From the 1 of 23 linked papers with an AI index.
23 papers
Improved Learning with Structure: Fine-Grained Complexity of Minimum Consistent Subset
Robert Ganian, Manolis Vasilakis, Simon Wietheger
The paper investigates the Minimum Consistent Subset problem, providing faster treewidth‑parameterized algorithms for both weighted and unweighted graphs and proving matching lower…
Two-Layer Drawings with a Tree on Top: Vertex Splits and Fixed-Parameter Algorithms
Alexander Firbas, Robert Ganian, Sylvain Meunier +1
Two-layer drawings of bipartite graphs place the vertices of each part on one of two parallel lines and draw the edges as straight-line links. Traditionally, the optimization goal…
A Fixed-Parameter Algorithm for Extending Upward Planar Drawings
Vera Chekan, Robert Ganian, Viktoriia Korchemna
An upward planar drawing of a directed acyclic graph is a planar drawing where every edge is pointed upward from its tail to head. Upward planar drawings are among the most natural…
New Complexity-Theoretic Frontiers of Tractability for Neural Network Training
Cornelius Brand, Robert Ganian, Mathis Rocton
In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networ…
Computing Twin-Width via Treedepth and Vertex Integrity
Robert Ganian, Mathis Rocton
Twin-width is a graph parameter that has become central to explaining the fixed-parameter tractability of first-order model checking across many graph classes. Despite its algorith…
Coordinated Motion Planning is FPT on Discretized Simple Polygons
Argyrios Deligkas, Eduard Eiben, Robert Ganian +1
In the coordinated motion planning problem, we are given a graph together with the starting and destination vertices of robots. At each time step, any subset of robots may move…