On the complexity of finding large odd induced subgraphs and odd colorings - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Algorithmica Année : 2021

On the complexity of finding large odd induced subgraphs and odd colorings

Ignasi Sau

Résumé

We study the complexity of the problems of finding, given a graph G, a largest induced subgraph of G with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition V (G). We call these parameters mos(G) and χ odd (G), respectively. We prove that deciding whether χ odd (G) ≤ q is polynomial-time solvable if q ≤ 2, and NP-complete otherwise. We provide algorithms in time 2 O(rw) •n O(1) and 2 O(q•rw) •n O(1) to compute mos(G) and to decide whether χ odd (G) ≤ q on n-vertex graphs of rank-width at most rw, respectively, and we prove that the dependency on rank-width is asymptotically optimal under the ETH. Finally, we give some tight bounds for these parameters on restricted graph classes or in relation to other parameters.
Fichier principal
Vignette du fichier
Odd-final.pdf (1.08 Mo) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-03374591 , version 1 (12-10-2021)

Identifiants

Citer

Rémy Belmonte, Ignasi Sau. On the complexity of finding large odd induced subgraphs and odd colorings. Algorithmica, 2021, 83 (8), pp.2351-2373. ⟨10.1007/s00453-021-00830-x⟩. ⟨lirmm-03374591⟩
60 Consultations
57 Téléchargements

Altmetric

Partager

More