On the complexity of Independent Dominant with Obligations in graphs - Université Clermont Auvergne Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2020

On the complexity of Independent Dominant with Obligations in graphs

Résumé

A subset D ⊆ V of a graph G = (V, E) is an independent (or stable) dominant if D is independent and dominates all the vertices of V. An instance of the Independent Dominant with Obligation (IDO) problem is a graph G = (V, E) and a partition of V denoted Π (each subset of Π is called an obligation). The distinction is that vertices can only be added obligation by obligation, instead of one by one. In this context D is a solution for (G, Π) if and only if D is an independent dominant respecting these obligations Π. We show that determining if a solution exists for the IDO problem is N P-complete, even if the graph is a path and all the obligations are stable and are all of size λ ≥ 2, or if there are √ N stable obligations each of size √ N or if the properties of obligations depend on the number N of vertices of the graph. We further introduce the Partially Independent Dominant with Obligation problem in which we relax the constraint of dominating every vertex. We show that determining if there is a stable set respecting the obligations dominating at least 3 √ N − 2 vertices (with N the number of vertices of the graph) is N P-complete even if the graph is a path and obligations are stable. On the positive side, we construct in polynomial time a solution dominating at least 2 √ N − 1 vertices if obligations are stable.
Fichier principal
Vignette du fichier
Article_IDO_HAL.pdf (172.11 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02946979 , version 1 (23-09-2020)
hal-02946979 , version 2 (09-01-2021)

Identifiants

  • HAL Id : hal-02946979 , version 1

Citer

Christian Laforest, Timothée Martinod. On the complexity of Independent Dominant with Obligations in graphs. [Research Report] LIMOS (UMR CNRS 6158), université Clermont Auvergne, France. 2020. ⟨hal-02946979v1⟩
273 Consultations
225 Téléchargements

Partager

Gmail Facebook X LinkedIn More