Constrained ear decompositions in graphs and digraphs

Frédéric Havet 1 Nicolas Nisse 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Ear decompositions of graphs are a standard concept related to several major problems in graph theory like the Traveling Salesman Problem. For example, the Hamiltonian Cycle Problem, which is notoriously N P-complete, is equivalent to deciding whether a given graph admits an ear decomposition in which all ears except one are trivial (i.e. of length 1). On the other hand, a famous result of Lovász states that deciding whether a graph admits an ear decomposition with all ears of odd length can be done in polynomial time. In this paper, we study the complexity of deciding whether a graph admits an ear decomposition with prescribed ear lengths. We prove that deciding whether a graph admits an ear decomposition with all ears of length at most is polynomial-time solvable for all fixed positive integer. On the other hand, deciding whether a graph admits an ear decomposition without ears of length in F is N P-complete for any finite set F of positive integers. We also prove that, for any k ≥ 2, deciding whether a graph admits an ear decomposition with all ears of length 0 mod k is N P-complete. We also consider the directed analogue to ear decomposition, which we call handle decomposition, and prove analogous results : deciding whether a digraph admits a handle decomposition with all handles of length at most is polynomial-time solvable for all positive integer ; deciding whether a digraph admits a handle decomposition without handles of length in F is N P-complete for any finite set F of positive integers (and minimizing the number of handles of length in F is not approximable up to n(1 −)); for any k ≥ 2, deciding whether a digraph admits a handle decomposition with all handles of length 0 mod k is N P-complete. Also, in contrast with the result of Lovász, we prove that deciding whether a digraph admits a handle decomposition with all handles of odd length is N P-complete. Finally, we conjecture that, for every set A of integers, deciding whether a digraph has a handle decomposition with all handles of length in A is N P-complete, unless there exists h ∈ N such that A = {1, · · · , h}.
Type de document :
Rapport
[Research Report] Inria - Sophia Antipolis. 2018
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01798795
Contributeur : Nicolas Nisse <>
Soumis le : mercredi 23 mai 2018 - 22:55:59
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : vendredi 24 août 2018 - 23:06:43

Fichier

oddEarDec.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01798795, version 1

Collections

Citation

Frédéric Havet, Nicolas Nisse. Constrained ear decompositions in graphs and digraphs. [Research Report] Inria - Sophia Antipolis. 2018. 〈hal-01798795〉

Partager

Métriques

Consultations de la notice

173

Téléchargements de fichiers

68