5 papers
(In)approximability of Maximum Minimal FVS
Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei +2
We study the approximability of the NP-complete \textsc{Maximum Minimal Feedback Vertex Set} problem. Informally, this natural problem seems to lie in an intermediate space between…
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…
How Bad is the Freedom to Flood-It?
Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi +2
Fixed-Flood-It and Free-Flood-It are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is…