G. , E. , and ?. V. ,

, Since P uv is flippable, we have ? D Puv (u, v) ? k. By Lemma 74, this is equivalent to ? D (u, v) ? 1 ? k and thus we can conlude that ? D (u, v) > k. Now suppose that ? D (u, v) > k and let us prove that the pair (u, v) is flippable, i.e., D Puv is karc-connected, i.e., for all u , v we have ? D Puv (u v ) ? k, By Lemma, vol.74, issue.2

, Consider another path P uv from u to v and let us show that like P uv , it is a flippable path, Again, by Lemma, vol.74, issue.1

, Let D be k-connected

, there exists at least k + 1 disjoint paths from u to v in D, if and only if the procedure of reversing a path from u to v can be applied k + 1 times. Hence, a simple algorithm consists in finding a directed path P uv in D, reverse it and iterate in D Puv . We have ? D (u, v) > k if and only if this procedure can be applied k + 1 times. Each execution is a BFS, which yields the claimed running time, Proof. By Lemma, vol.74

?. Reverse and F. Pvu,

(. Enods, F. Pvu, and . {v},

, Function Reverse +, p.22

+. Reverse and F. Puv,

(. Enods, F. Puv, E. ?-{v}-;-g-=-(v, and F. , The function EnODS(D,F ) enumerates the k-connected outdegree sequences coinciding with D on F . Furthermore, Algorithm 21 enumerates all k-connected outdegree sequences of G exactly once and with a delay in O

, We prove the completeness of the described algorithm, then we show that there is no redundancy and finally we analyse its complexity

, ) outputs ? + D and the proposition holds. Consider now the case |V \ F | > 0 and let v ? V \ F be the next vertex. By induction EnODS(D,F ? {v}) enumerates every k-connected outdegree sequence coinciding with D on F ? {v} exactly once. We have to show that Reverse +, Completeness We show the first part of the proposition by induction on |V \ F |. If |V \ F | = 0, then EnODS

, On the other hand, it is easy to see that a graph G admits a 2-acyclic orientation if and only if G is the cover graph of a poset. The corresponding recognition problem is NP-complete [16] and the proof can be extended to show that testing whether G admits a k-acyclic orientation is NP-complete for any k ? 2. Using [26, Theorem 13] one can show that enumerating k-acyclic orientations (as well as k-vertex connected orientations for k > 2) are DelNP-hard under D-reductions and IncNP-hard under I-reduction. Since with an NP-oracle one can decide if a given partial orientation extends to one of these types, a flashlight backtrack search algorithm like Algorithm 14 yields that the above problems can be solved with a polynomial number of calls of an NP-oracle. Thus these problems are in the class DelNP (and a fortiori IncNP), and therefore are indeed complete in both settings, Efficient enumeration of k-arc-connected orientations in graphs kn 2 m) by Iwata and Kobayashi in [62] and Lovász's result which yields a running time in O

O. Aichholzer, J. Cardinal, T. Huynh, K. Knauer, T. Mütze et al., Flip distances between graph orientations, Graph-Theoretic Concepts in Computer Science -45th International Workshop, WG 2019, pp.120-134, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02436272

T. Aittokallio and B. Schwikowski, Graph-based methods for analysing networks in cell biology, Briefings in Bioinformatics, vol.7, issue.3, pp.243-255, 2006.

D. Avis and K. Fukuda, Reverse search for enumeration, Discrete Applied Mathematics, vol.65, issue.1-3, pp.21-46, 1996.

G. Bagan, A. Durand, and E. Grandjean, On acyclic conjunctive queries and constant delay enumeration, Computer Science Logic, 21st International Workshop, pp.208-222, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00195010

J. Bang-jensen, J. Huang, and X. Zhu, Completing orientations of partially oriented graphs, Journal of Graph Theory, vol.87, issue.3, pp.285-304, 2018.

A. Bar-noy, R. Bar-yehuda, A. Freund, J. Naor, and B. Schieber, A unified approach to approximating resource allocation and scheduling, Journal of the ACM, vol.48, issue.5, pp.1069-1090, 2001.

V. C. Barbosa and J. L. Szwarcfiter, Generating all the acyclic orientations of an undirected graph, Information Processing Letters, vol.72, issue.1, pp.71-74, 1999.

O. Bernardi, Tutte polynomial, subgraphs, orientations and sandpile model: New connections via embeddings, Electronic Journal of Combinatorics, vol.15, issue.1, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00117268

H. L. Bodlaender, T. Kloks, and D. Kratsch, Treewidth and pathwidth of permutation graphs, SIAM Journal on Discrete Mathematics, vol.8, issue.4, pp.606-616, 1995.

F. Boesch and R. Tindell, Robbins' theorem for mixed multigraphs, The American Mathematical Monthly, vol.87, issue.9, pp.716-719, 1980.

M. Bonamy, O. Defrain, M. Heinrich, and J. Raymond, Enumerating minimal dominating sets in triangle-free graphs, STACS 2019, vol.16, p.12, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02181721

A. Bondy and U. S. Murty, Graph Theory. Graduate Texts in Mathematics, 2008.

E. Boros, V. Gurvich, L. Khachiyan, and K. Makino, Generating partial and multiple transversals of a hypergraph, Automata, Languages and Programming, 27th International Colloquium, pp.588-599, 2000.

E. Boros and K. Makino, , 2016.

E. Brehm, 3-orientations and Schnyder-3-tree-decompositions, 2000.

G. Brightwell, On the complexity of diagram testing, Order, vol.10, issue.4, pp.297-303, 1993.

M. R. Bussieck and M. E. Lübbecke, The vertex set of a 0/1-polytope is strongly p-enumerable, Computational Geometry, vol.11, issue.2, pp.103-109, 1998.

F. R. Chung, M. R. Garey, and R. E. Tarjan, Strongly connected orientations of mixed multigraphs, Networks, vol.15, issue.4, pp.477-484, 1985.

A. Conte, Enumeration Algorithms for Real-World Networks: Efficiency and Beyond, 2018.

A. Conte, R. Grossi, A. Marino, and R. Rizzi, Efficient enumeration of graph orientations with sources, Discrete Applied Mathematics, vol.246, pp.22-37, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01609009

A. Conte, R. Grossi, A. Marino, R. Rizzi, and L. Versari, Directing Road Networks by Listing Strong Orientations, pp.83-95, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01388476

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second Edition, 2001.

J. Couturier, P. Heggernes, P. Van't-hof, and D. Kratsch, Minimal dominating sets in graph classes: Combinatorial bounds and enumeration, Theoretical Computer Science, vol.487, pp.82-94, 2013.
URL : https://hal.archives-ouvertes.fr/hal-02332232

J. Couturier, R. Letourneur, and M. Liedloff, On the number of minimal dominating sets on some graph classes, Theoretical Computer Science, vol.562, pp.634-642, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01105097

N. Creignou and J. Hébrard, On generating all solutions of generalized satisfiability problems, Informatique Théorique et Applications, vol.31, issue.6, pp.499-511, 1997.

N. Creignou, M. Kröll, R. Pichler, S. Skritek, and H. Vollmer, On the complexity of hard enumeration problems, Language and Automata Theory and Applications -11th International Conference, pp.183-195, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01786350

W. H. Cunningham and A. Frank, A primal-dual algorithm for submodular flows, Mathematics of Operations Research, vol.10, issue.2, pp.251-262, 1985.

O. D. De-gevigney, On frank's conjecture on k-connected orientations. CoRR, abs/1212, vol.4086, 2012.

A. Durand and E. Grandjean, First-order queries on structures of bounded degree are computable with constant delay, ACM Transactions on Computational Logic, vol.8, issue.4, p.21, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00195016

G. Ehrlich, Loopless algorithms for generating permutations, combinations, and other combinatorial configurations, Journal of the ACM, vol.20, issue.3, pp.500-513, 1973.

T. Eiter and G. Gottlob, Identifying the minimal transversals of a hypergraph and related problems, SIAM Journal on Computing, vol.24, issue.6, pp.1278-1304, 1995.

S. Even, A. Pnueli, and A. Lempel, Permutation graphs and transitive graphs, Journal of the ACM, vol.19, issue.3, pp.400-410, 1972.

M. Fellows, G. Fricke, S. Hedetniemi, and D. Jacobs, The private neighbor cube, SIAM Journal on Discrete Mathematics, vol.7, pp.41-47, 1994.

S. Felsner, Lattice structures from planar graphs, Electronic Journal of Combinatorics, vol.11, issue.1, 2004.

S. Felsner, Rectangle and square representations of planar graphs, Thirty essays on geometric graph theory, pp.213-248, 2013.

S. Felsner, H. Schrezenmaier, and R. Steiner, Equiangular polygon contact representations, Graph-Theoretic Concepts in Computer Science -44th International Workshop, pp.203-215, 2018.

S. Felsner, H. Schrezenmaier, and R. Steiner, Pentagon contact representations, The Electronic Journal of Combinatorics, vol.25, issue.3, 2018.

F. V. Fomin, F. Grandoni, A. V. Pyatkin, and A. A. Stepanov, Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications, ACM Transactions on Algorithms, vol.5, issue.1, p.17, 2008.

A. Frank, An algorithm for submodular functions on graphs, Annals of Discrete Mathematics, vol.16, pp.97-120, 1982.

A. Frank, A note on k-strongly connected orientations of an undirected graph, Discrete Mathematics, vol.39, issue.1, pp.103-104, 1982.

A. Frank, Submodular flows. Progress in Combinatorial Optimization, pp.147-165, 1984.

A. Frank, Applications of submodular functions, Surveys in combinatorics, pp.85-136, 1993.

H. N. Gabow, A framework for cost-scaling algorithms for submodular flow problems, 34th Annual Symposium on Foundations of Computer Science, pp.449-458, 1993.

H. N. Gabow, Efficient splitting off algorithms for graphs, Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC '94, pp.696-705, 1994.

H. N. Gabow, Centroids, representations, and submodular flows, Journal of Algorithms, vol.18, issue.3, pp.586-628, 1995.

P. Gara and R. Frank, Gray codes from antimatroids, Order, vol.10, issue.3, pp.239-252, 1993.

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

P. M. Gilmer and R. A. Litherland, The duality conjecture in formal knot theory, Osaka Journal of Mathematics, vol.23, issue.1, pp.229-247, 1986.

E. Gioan, Enumerating degree sequences in digraphs and a cycle-cocycle reversing system, European Journal of Combinatorics, vol.28, issue.4, pp.1351-1366, 2007.
URL : https://hal.archives-ouvertes.fr/lirmm-00154515

P. M. Gleiss, J. Leydold, P. C. Godsil, G. Royle, and F. Stadler, Circuit bases of strongly connected digraphs, Discussiones Mathematicae, Graph Theory, vol.23, issue.2, pp.241-260, 2003.

C. Godsil and G. Royle, Algebraic graph theory, vol.207, 2001.

P. A. Golovach, P. Heggernes, M. M. Kanté, D. Kratsch, S. H. Saether et al., Outputpolynomial enumeration on graphs of bounded (local) linear mim-width, Algorithmica, vol.80, issue.2, pp.714-741, 2018.
URL : https://hal.archives-ouvertes.fr/hal-02083480

P. A. Golovach, P. Heggernes, and D. Kratsch, Enumerating minimal connected dominating sets in graphs of bounded chordality, Theoretical Computer Science, vol.630, pp.63-75, 2016.

P. A. Golovach, D. Kratsch, and M. Y. Sayadi, Enumeration of maximal irredundant sets for claw-free graphs, Theoretical Computer Science, vol.754, pp.3-15, 2019.

M. C. Golumbic, Interval graphs and related topics. Discrete Mathematics, vol.55, pp.113-121, 1985.

D. Gonçalves, B. Lévêque, and A. Pinlou, Triangle contact representations and duality. Discrete and Computational Geometry, An International Journal of Mathematics and Computer Science, vol.48, issue.1, pp.239-254, 2012.

D. Gunopulos, R. Khardon, H. Mannila, and H. Toivonen, Data mining, hypergraph transversals, and machine learning, Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp.209-216, 1997.

M. Habib, R. Medina, L. Nourine, and G. Steiner, Efficient algorithms on distributive lattices, Discrete Applied Mathematics, vol.110, issue.2, pp.169-187, 2001.
URL : https://hal.archives-ouvertes.fr/hal-01765516

S. T. Hedetniemi and R. C. Laskar, Topics on Domination, 1991.

M. A. Henning and A. Yeo, Total Domination in Graphs, 2013.

H. Hosoya, Topological index. a newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bulletin of The Chemical Society of Japan -BULL CHEM SOC JPN, vol.44, pp.2332-2339, 1971.

S. Iwata and Y. Kobayashi, An algorithm for minimum cost arc-connectivity orientations, Algorithmica, vol.56, issue.4, pp.437-447, 2010.

D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis, On generating all maximal independent sets, Information Processing Letters, vol.27, issue.3, pp.119-123, 1988.

M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine, Enumeration of minimal dominating sets and variants, Fundamentals of Computation Theory -18th International Symposium, pp.298-309, 2011.

M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine, On the enumeration of minimal dominating sets and related notions, SIAM Journal on Discrete Mathematics, vol.28, issue.4, pp.1916-1929, 2014.

M. M. Kanté, V. Limouzy, A. Mary, L. Nourine, and T. Uno, On the enumeration and counting of minimal dominating sets in interval and permutation graphs, Algorithms and Computation -24th International Symposium, pp.339-349, 2013.

R. M. Karp, Reducibility among combinatorial problems, 50 Years of Integer Programming 1958-2008 -From the Early Years to the State-of-the-Art, pp.219-241, 2010.

L. G. Khachiyan, E. Boros, K. M. Elbassioni, V. Gurvich, and K. Makino, On the complexity of some enumeration problems for matroids, SIAM Journal on Discrete Mathematics

S. Klamt, U. Haus, and F. J. Theis, Hypergraphs and cellular networks, PLoS Computational Biology, vol.5, issue.5, 2009.

D. J. Kleitman and K. J. Winston, Forests and score vectors, Combinatorica, vol.1, issue.1, pp.49-54, 1981.

U. Knauer and K. Knauer, Algebraic graph theory. Morphisms, monoids and matrices (to appear). 2nd revised and extended edition, vol.41, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02436201

D. E. Knuth, Fascicle 2: Generating All Tuples and Permutations (Art of Computer Programming), vol.4, 2005.

P. C. Lam and H. Zhang, A distributive lattice on the set of perfect matchings of a plane bipartite graph, Order, vol.20, issue.1, pp.13-29, 2003.

L. C. Lau and C. K. Yung, Efficient edge splitting-off algorithms maintaining all-pairs edgeconnectivities, SIAM Journal on Discrete Mathematics, vol.42, issue.3, pp.1185-1200, 2013.

L. Lovász, Combinatorial Problems and Exercises, 1979.

C. L. Lucchesi and S. L. Osborn, Candidate keys for relations, Journal of Computer and System Sciences, vol.17, issue.2, pp.270-279, 1978.

K. Makino and T. Uno, New algorithms for enumerating all maximal cliques, Algorithm Theory -SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, pp.260-272, 2004.

A. Marino, Algorithms for biological graphs: Analysis and enumeration, Bulletin of the EATCS, vol.114, 2014.

A. Mary, Enumération des dominants minimaux d'un graphe, 2013.

A. Mary and Y. Strozecki, Efficient enumeration of solutions produced by closure operations, Discrete Mathematics and Theoretical Computer Science, vol.21, issue.3, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01388505

N. Megiddo, On the complexity of linear programming, Advances in Economic Theory: Fifth World Congress, 1987.

K. Menger, Zur allgemeinen kurventheorie, Fundamental Mathematics, pp.96-115, 1927.

C. S. Nash-williams, On orientations, connectivity and odd-vertex-pairings in finite graphs, Canadian Journal of Mathematics, vol.12, pp.555-567, 1960.

J. B. Orlin, Max flows in O(nm) time, or better, Proceedings of the 45th annual ACM symposium on theory of computing, STOC '13, pp.765-774, 2013.

J. Propp, Lattice structure for orientations of graphs, 2002.

E. Rémila, The lattice structure of the set of domino tilings of a polygon, Theoretical Computer Science, vol.322, issue.2, pp.409-422, 2004.

H. E. Robbins, A theorem on graphs, with an application to a problem of traffic control, The American Mathematical Monthly, vol.46, issue.5, pp.281-283, 1939.

M. Rospocher, On the computational complexity of enumerating certificates of NP problems, 2006.

J. Schmidt, Enumeration: Algorithms and Complexity, 2009.

A. Schrijver, Theory of linear and integer programming. Wiley-Interscience series in Discrete Mathematics and optimization, 1999.

A. Schrijver, Combinatorial Optimization -Polyhedra and Efficiency, 2003.

N. Z. Shor and V. I. Gershivich, Family of algorithms for solving convex programming problems, Cybernetics and Systems Analysis, vol.15, issue.4, pp.502-508, 1979.

M. B. Squire, Generating the acyclic orientations of a graph, Journal of Algorithms, vol.26, issue.2, pp.275-290, 1998.

É. Tardos, C. A. Tovey, and M. A. Trick, Layered augmenting path algorithms, Mathematics of Operations Research, vol.11, issue.2, pp.362-370, 1986.

C. Thomassen, Strongly 2-connected orientations of graphs, Journal of Combinatorial Theory, Series B, vol.110, pp.67-78, 2015.

W. P. Thurston, Conway's tiling groups, American Mathematical Monthly, vol.97, issue.8, pp.757-773, 1990.

L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science, vol.8, pp.189-201, 1979.

P. Wan and D. Du, Connected Dominating Set : Theory and Applications

J. Wu and H. Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M 1999), pp.7-14, 1999.

P. Zhang, E. A. Schon, S. G. Fischer, E. Cayanis, J. Weiss et al., An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA, Computer Applications in the Biosciences, vol.10, issue.3, pp.309-317, 1994.

G. M. Ziegler, Lectures on polytopes, 1995.