1 citations · 1 across the 13 of their papers we have counts for
18 papers
Temporal Path Covers: Dilworth Properties and Parameterized Complexity
Lapo Cioni, Sotiris Kanellopoulos, Edouard Nemery +3
The Temporal Path Cover (TPC) and Temporally Disjoint Path Cover (TDPC) problems were introduced by [Chakraborty, Dailly, Foucaud, Klasing, MFCS '24] as the natural temporal analog…
Improved Learning with Structure: Fine-Grained Complexity of Minimum Consistent Subset
Robert Ganian, Manolis Vasilakis, Simon Wietheger
Instance selection is a vital technique for mitigating the computational bottlenecks of nearest-neighbor classification in large-scale supervised clustering. A classical theoretica…
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…
Parameterized Capacitated Vertex Cover Revisited
Michael Lampis, Manolis Vasilakis
Capacitated Vertex Cover is a generalization of Vertex Cover where we seek a set of vertices covering all edges, but with the added constraint that for each vertex we are given…
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…
Structural Parameters for Steiner Orientation
Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos +3
We consider the \textsc{Steiner Orientation} problem, where we are given as input a mixed graph and a set of demand pairs , . The goal is to ori…
Parameterized Critical Node Cut Revisited
Dušan Knop, Nikolaos Melissinos, Manolis Vasilakis
We study how to sparsify connectivity in graphs under a tight deletion budget. Given a graph and integers , Critical Node Cut (CNC) asks whether we can delete at mos…
Broadcasting under Structural Restrictions
Yudai Egami, Tatsuya Gima, Tesshu Hanaka +7
In the Telephone Broadcast problem we are given a graph with a designated source vertex . Our goal is to transmit a message, which is initially known only to ,…
Exact Algorithms for Distance to Unique Vertex Cover
Foivos Fioravantes, Dušan Knop, Nikolaos Melissinos +2
Horiyama et al. (AAAI 2024) studied the problem of generating graph instances that possess a unique minimum vertex cover under specific conditions. Their approach involved pre-assi…
Structural Parameterizations for Induced and Acyclic Matching
Michael Lampis, Manolis Vasilakis
We revisit the (structurally) parameterized complexity of Induced Matching and Acyclic Matching, two problems where we seek to find a maximum independent set of edges whose endpoin…
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 Maximum Node-Disjoint Paths
Michael Lampis, Manolis Vasilakis
We revisit the Maximum Node-Disjoint Paths problem, the natural optimization version of Node-Disjoint Paths, where we are given a graph , pairs of vertices and…
Parameterized Vertex Integrity Revisited
Tesshu Hanaka, Michael Lampis, Manolis Vasilakis +1
Vertex integrity is a graph parameter that measures the connectivity of a graph. Informally, its meaning is that a graph has small vertex integrity if it has a small separator whos…
Bandwidth Parameterized by Cluster Vertex Deletion Number
Tatsuya Gima, Eun Jung Kim, Noleen Köhler +2
Given a graph and an integer , Bandwidth asks whether there exists a bijection from to such that $\max_{\{u, v \} \in E(G)} | π(u) - π(v)…
Structural Parameterizations for Two Bounded Degree Problems Revisited
Michael Lampis, Manolis Vasilakis
We revisit two well-studied problems, Bounded Degree Vertex Deletion and Defective Coloring, where the input is a graph and a target degree and we are asked either to edit…
Parameterized Max Min Feedback Vertex Set
Michael Lampis, Nikolaos Melissinos, Manolis Vasilakis
Given a graph and an integer , Max Min FVS asks whether there exists a minimal set of vertices of size at least whose deletion destroys all cycles. We present several re…
Approximating Subset Sum Ratio via Partition Computations
Giannis Alonistiotis, Antonis Antonopoulos, Nikolaos Melissinos +3
We present a new FPTAS for the Subset Sum Ratio problem, which, given a set of integers, asks for two disjoint subsets such that the ratio of their sums is as close to as possi…
Faster Algorithms for -Subset Sum and Variations
Antonis Antonopoulos, Aris Pagourtzis, Stavros Petsalakis +1
We present new, faster pseudopolynomial time algorithms for the -Subset Sum problem, defined as follows: given a set of positive integers and targets $t_1, \ldots, t…