From the 1 of 14 linked papers with an AI index.
14 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…
Temporal Path Covers: Dilworth Properties and Parameterized Complexity
Lapo Cioni, Sotiris Kanellopoulos, Edouard Nemery +3
The Minimum Temporal Path Cover (TPC) and Minimum Temporally Disjoint Path Cover (TDPC) problems were introduced by [Chakraborty, Dailly, Foucaud, Klasing, MFCS '24]. Both were sho…
Faster Parameterized Broadcasting
Ãdouard Bonnet, Carl Feghali, Manolis Vasilakis
Given a connected graph and a source , what is the smallest number of rounds necessary for all vertices of to receive a message initially only held by , wher…
EF(X) Orientations: A Parameterized Complexity Perspective
Sotiris Kanellopoulos, Edouard Nemery, Christos Pergaminelis +2
The concept of fair orientations in graphs was introduced by Christodoulou, Fiat, Koutsoupias, and Sgouritsa in 2023, naturally modeling fair division scenarios in which resources…
Parameterized Spanning Tree Congestion
Michael Lampis, Valia Mitsou, Edouard Nemery +3
In this paper we study the Spanning Tree Congestion problem, where we are given a graph and are asked to find a spanning tree of minimum maximum congestion. Here, the…
Parameterized Capacitated Vertex Cover Revisited
Michael Lampis, Manolis Vasilakis
Capacitated Vertex Cover is the hard-capacitated variant of Vertex Cover: given a graph, a capacity for every vertex, and an integer , the task is to select at most vertices…