8 papers
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…
The Computational Complexity of Positive Non-Clashing Teaching in Graphs
Robert Ganian, Liana Khazaliya, Fionn Mc Inerney +1
We study the classical and parameterized complexity of computing the positive non-clashing teaching dimension of a set of concepts, that is, the smallest number of examples per con…
The Parameterized Complexity Landscape of the Unsplittable Flow Problem
Robert Ganian, Mathis Rocton, Daniel Unterberger
We study the well-established problem of finding an optimal routing of unsplittable flows in a graph. While by now there is an extensive body of work targeting the problem on graph…
Twin-Width Meets Feedback Edges and Vertex Integrity
Jakub Balabán, Robert Ganian, Mathis Rocton
The approximate computation of twin-width has attracted significant attention already since the moment the parameter was introduced. A recently proposed approach (STACS 2024) towar…
Computing the degreewidth of a digraph is hard
Pierre Aboulker, Nacim Oijid, Robin Petit +2
Given a digraph, an ordering of its vertices defines a backedge graph, namely the undirected graph whose edges correspond to the arcs pointing backwards with respect to the order.…
Computing Twin-Width Parameterized by the Feedback Edge Number
Jakub Balabán, Robert Ganian, Mathis Rocton
The problem of whether and how one can compute the twin-width of a graph -- along with an accompanying contraction sequence -- lies at the forefront of the area of algorithmic mode…
Polynomial kernels for edge modification problems towards block and strictly chordal graphs
Maël Dumas, Anthony Perez, Mathis Rocton +1
We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph and an integer and seeks to…