, a digraph is a handle decomposition in which all handles have length in A. Note that an A-ear-decomposition (resp. A-handle-decomposition) of a graph (resp. digraph) can be seen as an ear decomposition (resp. handle decomposition) with no ear (resp. handle) with length in A. In view of all our results

, A-Ear-Decomposition Input: A graph G. Question: Does G admit an A-ear-decomposition ?

A. , Question: Does D admit an A-handle-decomposition ? It would be nice to characterize the graphs (resp. digraphs) for which A-Ear-Decomposition (resp. A-Handle-Decomposition) is polynomial-time solvable. Below is an easy lemma, Decomposition Input: A digraph D

J. Cheriyan, A. Sebö, and Z. Szigeti, Improving on the 1.5-approximation of a smallest 2-edge connected spanning subgraph, SIAM J. Discrete Math, vol.14, issue.2, pp.170-180, 2001.

N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Graduate School of Industrial Administration, 1976.

A. Frank, Conservtive weightings and ear-decompositions of graphs, Combinatorica, vol.13, pp.65-81, 1993.

M. R. Garey, D. S. Johnson, and L. Stockmeyer, Some simplified NP-complete graph problems, Theor. Comput. Sci, vol.1, issue.3, pp.237-267, 1976.
DOI : 10.1016/0304-3975(76)90059-1
URL : https://doi.org/10.1016/0304-3975(76)90059-1

A. Shayan-oveis-gharan, M. Saberi, and . Singh, A randomized rounding approach to the traveling salesman problem, Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS '11, pp.550-559, 2011.

S. Khuller and U. Vishkin, Biconnectivity approximations and graph carvings, Journal of the ACM, vol.41, issue.2, pp.214-235, 1994.
DOI : 10.1145/129712.129786

H. Klauck, On the hardness of global and local approximation, Algorithm Theory-SWAT'96, pp.88-99, 1996.

L. Lovász, A note on factor-critical graphs, Studia Sci. Math. Hungar, vol.7, pp.279-280, 1972.

T. Mömke and O. Svensson, Approximating graphic TSP by matchings, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp.560-569, 2011.

M. Mucha, 13 9-approximation for Graphic TSP. Theory of Computing Systems, vol.55, pp.640-657, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00678172

H. E. Robbins, A theorem on graphs with an application to a problem on traffic control, Amer. Math. Mon, vol.46, pp.281-283, 1939.

A. Seb?-o and J. Vygen, Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs, Combinatorica, 2014.

A. Vetta, Approximating the minimum strongly connected subgraph via a matching lower bound, Proc. 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.417-426, 2001.