Skip to Main content Skip to Navigation
New interface
Journal articles

Constrained ear decompositions in graphs and digraphs

Frédéric Havet 1 Nicolas Nisse 1 
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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}.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01798795
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Monday, July 15, 2019 - 11:03:42 AM
Last modification on : Thursday, August 4, 2022 - 4:58:26 PM

File

oddEarDec-final.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Frédéric Havet, Nicolas Nisse. Constrained ear decompositions in graphs and digraphs. Discrete Mathematics and Theoretical Computer Science, 2019, vol. 21 no. 4, ⟨10.23638/DMTCS-21-4-3⟩. ⟨hal-01798795v3⟩

Share

Metrics

Record views

288

Files downloads

1353