Finding a family of simple circuits in graphs with~vertex semidegrees bounded by~$k$

A. A. Medvedev

Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 85-94.

Résumé

We study the algorithmic complexity of finding a family of simple circuits passing every vertice of a digraph with semidegree bounded by $k$. The problem is considered in two variants: as a search and as an optimization problem. Parametrically polynomial solvability of the problem is proved in both variants, Algorithms with complexity $O(nk^2 + n\log_{2}n)$, $O(n(k^2 + k) + n\log_{2}n)$ and $O(n)$ for various types of constraints are proposed, where $n$ is the number of digraph vertices.

Détail

Keywords: digraphs, search problems, optimization, parametrical complexity, polynomial solvability.
Mots-clés : simple circuits, P class

Bibliographie

[1] Karp R. M., “Reducibility among combinatorial problems”, Complexity of Computer Computations, The IBM Research Symposia Series, eds. R. E. Miller, J. W. Thatcher, J. D. Bohlinger, Springer, Boston, 1972, 85–103 | MR

[2] Akiyama T., Nisizeki T., and Saito N., “NP-completeness of the Hamiltonian cycle problem for bipartite graphs”, J. Inform. Processing, 3:2 (1981), 73–76 | MR

[3] Itai A., Papadimitiou Ch., and Szwarcfiter J., “Hamiltonian paths in grid graphs”, SIAM J. Computing, 4:11 (1982), 676–686 | DOI | MR

[4] Buro M., “Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs”, LNCS, 2063, 2000, 250–261 | MR

[5] Plesńik J., “The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two”, Inform. Process. Lett., 8:4 (1979), 199–201 | DOI | MR | Zbl

[6] Chiba N. and Nishizeki T., “The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs”, J. Algorithms, 10:2 (1989), 187–211 | DOI | MR | Zbl

[7] Dirac G. A., “Some theorems on abstract graphs”, Proc. London Math. Soc., 2:3 (1952), 69–81 | DOI | MR | Zbl

[8] Ore O., “Note on Hamiltonian circuits”, American Math. Monthly, 67 (1960), 55 | DOI | MR | Zbl

[9] Ghouila-Houri A., “Une condition suffisante d'existence d'un circuit Hamiltonien”, Comptes Rendus de l'Académie des Science Paris, 251 (1960), 495–497 (in French) | MR | Zbl

[10] Woodall D., “Sufficient conditions for cycles in digraphs”, Proc. London Math. Soc., 24 (1972), 739–755 | DOI | MR | Zbl

[11] Christofides D., Keevash P., Kühn D., and Osthus D., “A semi-exact degree condition for Hamiltonian cycles in digraphs”, SIAM J. Discrete Math., 24:3 (2010), 709–756 | DOI | MR | Zbl

[12] Keevash P., Kühn D., and Osthus D., “An exact minimum degree condition for Hamiltonian cycles in oriented graphs”, J. London Math. Soc., 79:1 (2009), 144–166 | DOI | MR | Zbl

[13] Kelly L., Kühn D., and Osthus D., “A Dirac-type result on Hamiltonian cycles in oriented graphs”, Combinatorics, Probability and Computing, 17:5 (2008), 689–709 | DOI | MR | Zbl

[14] Björklund A., Husfeldt T., and Khanna S., “Approximating longest directed paths and cycles”, Automata, Languages and Programming, 3142 (2004), 222–233 | DOI | MR | Zbl

[15] Gabow H. N. and Nie S., “Finding long paths, cycles and circuits”, LNCS, 5369, 2008, 752–763 | MR | Zbl

[16] Zamfirescu T., “On longest paths and circuits in graphs”, Mathematica Scandinavica, 38 (1976), 211–239 | DOI | MR | Zbl

[17] Kharari F., Teoriya grafov, Editorial URSS, M., 2003, 296 pp.

[18] Medvedev A. A., “Finding a family of simple circuits in an digraph with semidegree bound 2”, Intellektual'nyye Sistemy. Teoriya i Prilozheniya, 26:3 (2022), 150–164 (in Russian)

[19] Kuhn H. W., “Variants of the Hungarian method for assignment problems”, Naval Research Logistics Quarterly, 3 (1956), 253–258 | DOI | MR | Zbl