54 citations · 152 across the 16 of their papers we have counts for
25 papers
Monte Carlo Graph Coloring
Tristan Cazenave, Benjamin Negrevergne, Florian Sikora
Graph Coloring is probably one of the most studied and famous problem in graph algorithms. Exact methods fail to solve instances with more than few hundred vertices, therefore, a l…
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…
Scaling up graph homomorphism for classification via sampling
Paul Beaujean, Florian Sikora, Florian Yger
Feature generation is an open topic of investigation in graph machine learning. In this paper, we study the use of graph homomorphism density features as a scalable alternative to…
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…
Grundy Coloring & friends, Half-Graphs, Bicliques
Pierre Aboulker, Édouard Bonnet, Eun Jung Kim +1
The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order , the smallest available color. The problem Grundy Coloring asks how many colors…
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…
Extension of vertex cover and independent set in some classes of graphs and generalizations
Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikolaei +2
We consider extension variants of the classical graph problems Vertex Cover and Independent Set. Given a graph and a vertex set , it is asked if there exis…
On the Complexity of Solution Extension of Optimization Problems
Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikolaei +2
The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating min…
Parameterized Orientable Deletion
Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis +2
A graph is -orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most . -orientability is a well-studied concept with close…
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 $…
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim +2
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 shortest way to visit all metro lines in a city
Florian Sikora
What if a tourist, a train addict, Dr. Sheldon Cooper, somebody who likes to waste time wants to visit all metro lines or carriages in a given network in a minimum number o…
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…
A note on Edge Isoperimetric Numbers and Regular Graphs
Edouard Bonnet, Florian Sikora
This note resolves an open problem asked by Bezrukov in the open problem session of IWOCA 2014. It shows an equivalence between regular graphs and graphs for which a sequence of in…
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 Inapproximability of Target Set Selection and Generalizations
Cristina Bazgan, Morgan Chopin, André Nichterlein +1
In this paper, we consider the Target Set Selection problem: given a graph and a threshold value for any vertex of the graph, find a minimum size vertex-subset to "act…
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…
Some results on more flexible versions of Graph Motif
Romeo Rizzi, Florian Sikora
The problems studied in this paper originate from Graph Motif, a problem introduced in 2006 in the context of biological networks. Informally speaking, it consists in deciding if a…