A. Agarwal and M. Charikar, Konstantin Makarychev, and Yury Makarychev. o( ( log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems, 37th Annual ACM Symposium on Theory of Computing, pp.573-581, 2005.

H. Alpert, Rank numbers of grid graphs, Discrete Mathematics, vol.310, issue.23, pp.3103324-3333, 2010.
DOI : 10.1016/j.disc.2010.07.022

D. Angluin, Inference of Reversible Languages, Journal of the ACM, vol.29, issue.3, pp.741-765, 1982.
DOI : 10.1145/322326.322334

A. Bar-noy, Ordered coloring of grids and related graphs, Theoretical Computer Science, vol.444, pp.40-51, 2012.
DOI : 10.1016/j.tcs.2012.04.036

J. Barát, Directed Path-width and Monotonicity in Digraph Searching, Graphs and Combinatorics, vol.22, issue.2, pp.161-172, 2006.
DOI : 10.1007/s00373-005-0627-y

D. Berwanger, A. Dawar, P. Hunter, S. Kreutzer, and J. Obdrzálek, The dag-width of directed graphs, Journal of Combinatorial Theory, Series B, vol.102, issue.4, pp.900-923, 2012.
DOI : 10.1016/j.jctb.2012.04.004

A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, The traveling salesman problem in bounded degree graphs, ACM Transactions on Algorithms, vol.8, issue.2, p.18, 2012.
DOI : 10.1145/2151171.2151181

L. Hans, J. R. Bodlaender, H. Gilbert, T. Hafsteinsson, and . Kloks, Approximating treewidth, pathwidth , frontsize, and shortest elimination tree, Journal of Algorithms, vol.18, issue.2, pp.238-255, 1995.

J. Chen, Y. Liu, S. Lu, O. Barry, I. Sullivan et al., A fixed-parameter algorithm for the directed feedback vertex set problem, Journal of the ACM, vol.55, issue.5, 2008.

C. Lawrence and . Eggan, Transition graphs and the star height of regular events, pp.385-397, 1963.

C. Stanley, J. W. Eisenstat, and . Liu, The theory of elimination trees for sparse unsymmetric matrices, SIAM Journal on Matrix Analysis and Applications, vol.26, issue.3, pp.686-705, 2005.

V. Fedor, D. Fomin, and . Kratsch, Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series, 2010.

R. Ganian, P. Hlinen´yhlinen´y, J. Kneis, A. L. Obdrzálek, and P. Rossmanith, On Digraph Width Measures in Parameterized Algorithmics, 4th International Workshop on Parameterized and Exact Computation, pp.185-197, 2009.
DOI : 10.1007/978-3-642-11269-0_15

R. Michael, D. S. Garey, and . Johnson, Computers and Intractability: A Guide to the Theory of NP- Completeness. A Series of Books in the Mathematical Sciences, 1979.

H. Gruber, Digraph complexity measures and applications in formal language theory, Mathematical and Engineering Methods in Computer Science, pp.60-67, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00990597

H. Gruber, On balanced separators, treewidth, and cycle rank, Journal of Combinatorics, vol.3, issue.4
DOI : 10.4310/JOC.2012.v3.n4.a5

H. Gruber and M. Holzer, Finite Automata, Digraph Connectivity, and Regular Expression Size, 35th International Colloquium on Automata, Languages and Programming (Part II), pp.39-50, 2008.
DOI : 10.1007/978-3-540-70583-3_4

K. Hashiguchi, Algorithms for determining relative star height and star height, Information and Computation, vol.78, issue.2, pp.124-169, 1988.
DOI : 10.1016/0890-5401(88)90033-8

M. Holzer and M. Kutrib, NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES, International Journal of Foundations of Computer Science, vol.14, issue.06, pp.1087-1102, 2003.
DOI : 10.1142/S0129054103002199

E. John, J. D. Hopcroft, and . Ullman, Introduction to Automata Theory, Languages and Computation, Series in Computer Science, 1979.

P. Hunter, LIFO-Search on Digraphs: A Searching Game for Cycle-Rank, 18th International Symposium on Fundamentals of Computation Theory, pp.217-228, 2011.
DOI : 10.1006/jctb.1993.1027

B. Harry, I. Hunt, and D. J. Rosenkrantz, Computational parallels between the regular and context-free languages, SIAM Journal on Computing, vol.7, issue.1, pp.99-114, 1978.

S. Kintali, N. Kothari, and A. Kumar, Approximation algorithms for directed width parameters Available online as arXiv:1107, 2011.

D. Kirsten, On the complexity of the relative inclusion star height problem, Advances in Computer Science and Engineering, vol.5, issue.3, pp.173-211, 2010.

S. Kreutzer and S. Ordyniak, Digraph decompositions and monotonicity in digraph searching, Theoretical Computer Science, vol.412, issue.35, pp.4688-4703, 2011.
DOI : 10.1016/j.tcs.2011.05.003

M. Lampis, G. Kaouri, and V. Mitsou, On the algorithmic effectiveness of digraph decompositions and complexity measures, Discrete Optimization, vol.8, issue.1, pp.129-138, 2011.
DOI : 10.1016/j.disopt.2010.03.010

R. Mcnaughton, The loop complexity of pure-group events, Information and Control, vol.11, issue.1-2, pp.167-176, 1967.
DOI : 10.1016/S0019-9958(67)90481-0

R. Mcnaughton, The loop complexity of regular events, Information Sciences, vol.1, issue.3, pp.305-328, 1969.
DOI : 10.1016/S0020-0255(69)80016-2

J. Ne?et?il, P. Ossona, and . Mendez, Tree-depth, subgraph coloring and homomorphism bounds, European Journal of Combinatorics, vol.27, issue.6, pp.1022-1041, 2006.
DOI : 10.1016/j.ejc.2005.01.010

S. Venkatesh-raman, S. Saurabh, and . Sikdar, Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques, Theory of Computing Systems, vol.41, issue.3, pp.563-587, 2007.
DOI : 10.1007/s00224-007-1334-2

I. Razgon, Computing minimum directed feedback vertex set in O * (1.9977 n ), Proceedings of the 10th Italian Conference on Theoretical Computer Science, pp.70-81, 2007.

N. Robertson and P. D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, Journal of Algorithms, vol.7, issue.3, pp.309-322, 1986.
DOI : 10.1016/0196-6774(86)90023-4

A. Mohammad and . Safari, D-Width: A more natural measure for directed tree width, 30th International Symposium on Mathematical Foundations of Computer Science, pp.745-756, 2005.

R. Schreiber, A New Implementation of Sparse Gaussian Elimination, ACM Transactions on Mathematical Software, vol.8, issue.3, pp.256-276, 1982.
DOI : 10.1145/356004.356006

B. Schwikowski and E. Speckenmeyer, On enumerating all minimal solutions of feedback problems, Discrete Applied Mathematics, vol.117, issue.1-3, pp.253-265, 2002.
DOI : 10.1016/S0166-218X(00)00339-5

J. Von and . Gathen, Irreducibility of multivariate polynomials, Journal of Computer and System Sciences, vol.31, issue.2, pp.225-264, 1985.

C. Appendix and . Instance, A digraph G and an integer k

. Good-news, Approximable within O((log n) 3/2 ) in polynomial time (Thm. 13) Exact solution can be computed in time O * (1.9129 n ) for digraphs with maximum outdegree at most 2; and for unbounded outdegree in time O *

. Good-news, For digraphs with maximum outdegree at most 2, exact solution can be computed in time O * (1.9129 n ) (Thm. 17); and in time O * (1.9977 n ) for unbounded outdegree

. Good-news, Approximable within O((log n) 3/2 ) in polynomial time (Thm. 21) Exact solution can be computed in time O * (1.9129 n ) for binary alphabets; and for unbounded alphabet size in time O *

. Bad and . News, NP-complete; NP-hardness holds already for binary alphabets (Thm

. Good-news, Problem is decidable [20]. Exact solution can be computed within exponential space and doubly exponential time

. Bad and . News, NP-hard, already for binary alphabets (Thm. 23) Problem is PSPACE-hard if input given by an nondeterministic finite automaton in place of a deterministic one