Hardness Results and Approximation Algorithms for Discrete Optimization Problems with Conditional and Unconditional Forbidden Vertices

Francois Delbot (1) , Christian Laforest (2) , Raksmey Phan (2)

1 RO - Recherche Opérationnelle
2 LIMOS - Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes

In this paper we study and solve new variants of classical graph problems (vertex cover, dominating set, Steiner tree). We add constraints of incompatibilities between vertices that can be conditional or unconditional. This capture the impossibility for certain vertices or pairs of vertices of been into a solution. In the first part, we consider a graph with unconditional forbidden vertices. An instance of the problem is a graph, a set F of Forbidden vertices and a set R of Required vertices. We prove that constructing a minimal size vertex cover or connected vertex cover or dominating set or Steiner tree, containing all R and no vertex of F can be 2-approximated (when there exists one, that is polynomial to determine). We also show that it is N P-complete to determine whether there is an independent dominating set (containing R and no vertex of F). In the second part, we carry on the conditional case that is expressed by conflicts that are a set of pairs of vertices that cannot be both into a solution. An instance is then a graph G and a set C of conflicts. We first study the question to know whether there is a vertex cover of G containing no conflict of C and if the answer is positive to construct one of minimal size. We reduce that to 2-SAT and we show that the first question can be answered with a polynomial time algorithm. We show that the second problem is N P-complete but can be 2-approximated. We also prove that it is N P-complete to decide if there exists a connected vertex cover, an (independent) dominating set or a Steiner tree with no conflict of C.

Domaines: Informatique [cs]

Francois Delbot, Christian Laforest, Raksmey Phan. Hardness Results and Approximation Algorithms for Discrete Optimization Problems with Conditional and Unconditional Forbidden Vertices. [Research Report] LIP6 - Laboratoire d'Informatique de Paris 6; LIMOS; Univerisité Paris X Nanterre; Univerité Blaise Pascal, Clermont-Ferrand. 2016. ⟨hal-01257820⟩