, We denote by A the set N \ A, and for any positive integer k we set kA = {k × a | a ? A}. An A-ear-decomposition of a graph is an ear decomposition in which all ears have length in A. Similarly, an A-handle-decomposition of 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, Let A be a set of positive integers

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

A. Input, 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

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. Garey, D. Johnson, and L. Stockmeyer, Some simplified NP-complete graph problems, Theor. Comput. Sci, vol.1, issue.3, pp.237-267, 1976.

S. O. Gharan, A. Saberi, and M. 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.

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, Graphic TSP. Theory of Computing Systems, vol.13, pp.640-657, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00678172

H. 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? 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.