54 citations · 152 across the 16 of their papers we have counts for
13 papers · 1 filter
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet +6
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Cliq…
The Longest Run Subsequence Problem: Further Complexity Results
Riccardo Dondi, Florian Sikora
Longest Run Subsequence is a problem introduced recently in the context of the scaffolding phase of genome assembly (Schrinner et al., WABI 2020). The problem asks for a maximum le…
On the complexity of Broadcast Domination and Multipacking in digraphs
Florent Foucaud, Benjamin Gras, Anthony Perez +1
We study the complexity of the two dual covering and packing distance-based problems Broadcast Domination and Multipacking in digraphs. A dominating broadcast of a digraph is a…
Weighted Upper Edge Cover: Complexity and Approximability
Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jerome Monnot +1
Optimization problems consist of either maximizing or minimizing an objective function. Instead of looking for a maximum solution (resp. minimum solution), one can find a minimum m…
Token Sliding on Split Graphs
Rémy Belmonte, Eun Jung Kim, Michael Lampis +3
We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked i…
Covering with Clubs: Complexity and Approximability
Riccardo Dondi, Giancarlo Mauri, Florian Sikora +1
Finding cohesive subgraphs in a network is a well-known problem in graph theory. Several alternative formulations of cohesive subgraph have been proposed, a notable example being $…
Parameterized and Approximation Complexity of Partial VC Dimension
Cristina Bazgan, Florent Foucaud, Florian Sikora
We introduce the problem Partial VC Dimension that asks, given a hypergraph and integers and , whether one can select a set of vertices of $H…
Finding Disjoint Paths on Edge-Colored Graphs: More Tractability Results
Riccardo Dondi, Florian Sikora
The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph (called MaxCDP) has been recently introduced in literature, motivated by appli…
Parameterized Complexity and Approximation Issues for the Colorful Components Problems
Riccardo Dondi, Florian Sikora
The quest for colorful components (connected components where each color is associated with at most one vertex) inside a vertex-colored graph has been widely considered in the last…
The Graph Motif problem parameterized by the structure of the input graph
Édouard Bonnet, Florian Sikora
The Graph Motif problem was introduced in 2006 in the context of biological networks. It consists of deciding whether or not a multiset of colors occurs in a connected subgraph of…
On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
Faisal N. Abu-Khzam, Édouard Bonnet, Florian Sikora
In the Maximum Common Induced Subgraph problem (henceforth MCIS), given two graphs and , one looks for a graph with the maximum number of vertices being both an induced…
Complexity of Grundy coloring and its variants
Edouard Bonnet, Florent Foucaud, Eun Jung Kim +1
The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity o…
Parameterized Approximability of Maximizing the Spread of Influence in Networks
Cristina Bazgan, Morgan Chopin, André Nichterlein +1
In this paper, we consider the problem of maximizing the spread of influence through a social network. Given a graph with a threshold value~ attached to each vertex~, th…