zbMATH — the first resource for mathematics

Quasi-hamiltonian paths in semicomplete multipartite digraphs. (English) Zbl 1262.05095
Summary: A quasi-hamiltonian path in a semicomplete multipartite digraph \(D\) is a path which visits each maximal independent set (also called a partite set) of \(D\) at least once. This is a generalization of a hamiltonian path in a tournament.
In this paper we investigate the complexity of finding a quasi-hamiltonian path, in a given semicomplete multipartite digraph, from a prescribed vertex \(x\) to a prescribed vertex \(y\) as well as the complexity of finding a quasi-hamiltonian path whose end vertices belong to a given set of two vertices \(\{ x,y\} \). While both of these problems are polynomially solvable for semicomplete digraphs (here all maximal independent sets have size one), we prove that the first problem is NP-complete and describe a polynomial algorithm for the latter problem.

05C45 Eulerian and Hamiltonian graphs
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI
[1] Ailon, N.; Charikar, M.; Newman, A., Aggregating inconsistent information: ranking and clustering, (Proc. STOC’05: The 37th Annual ACM Symp. on Theory of Computing, (2005), ACM Press), 684-693 · Zbl 1192.90252
[2] Alon, N.; Yuster, R.; Zwick, U., Color-coding, J. Assoc. Comput. Mach., 42, 844-856, (1995) · Zbl 0885.68116
[3] Bang-Jensen, J.; Gutin, G., Generalizations of tournaments: a survey, J. Graph Theory, 28, 171-202, (1998) · Zbl 0920.05033
[4] Bang-Jensen, J.; Gutin, G., Digraphs: theory, algorithms and applications, (2009), Springer-Verlag London · Zbl 1170.05002
[5] Bang-Jensen, J.; Gutin, G.; Huang, J., Weakly Hamiltonian-connected ordinary multipartite tournaments, 14th British Combinatorial Conference (Keele, 1993), Discrete Math., 138, 1-3, 63-74, (1995) · Zbl 0834.05027
[6] Bang-Jensen, J.; Gutin, G.; Yeo, A., A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs, J. Graph Theory, 29, 111-132, (1998) · Zbl 0916.05049
[7] Bang-Jensen, J.; Manoussakis, Y.; Thomassen, C., A polynomial algorithm for Hamiltonian-connectedness in semicomplete digraphs, J. Algor., 13, 1, 114-127, (1992) · Zbl 0749.68057
[8] Bang-Jensen, J.; Thomassen, C., A polynomial algorithm for the 2-path problem for semicomplete digraphs, SIAM J. Discrete Math., 5, 366-376, (1992) · Zbl 0759.05041
[9] Charbit, P.; Thomassé, S.; Yeo, A., The minimum feedback arc set problem is NP-hard for tournaments, Combin. Probab. Comput., 16, 1-4, (2007) · Zbl 1120.05038
[10] V. Conitzer, Computing Slater rankings using similarities among candidates, in: 21st National Conference on Artificial Intelligence, AAAI-06, 2006, pp. 613-619.
[11] Guo, Y.; Lu, M.; Surmacs, M., Weakly quasi-Hamiltonian-set-connected multipartite tournaments, Discrete Appl. Math., 160, 10-11, 1561-1566, (2012) · Zbl 1243.05140
[12] Gutin, G., Finding a longest path in a complete multipartite digraph, SIAM J. Discrete Math., 6, 270-273, (1993) · Zbl 0773.05071
[13] Speckenmeyer, E., On feedback problems in digraphs, (Proc. 15th WG, Lect. Notes Comput. Sci., vol. 411, (1989), Springer), 218-231 · Zbl 0768.68181
[14] Tewes, M.; Volkmann, L., Vertex deletion and cycles in multipartite tournaments, 16th British Combinatorial Conference (London, 1997), Discrete Math., 197/198, 769-779, (1999) · Zbl 0939.05046
[15] Thomassen, C., Hamiltonian-connected tournaments, J. Combin. Theory Ser. B, 28, 2, 142-163, (1980) · Zbl 0435.05026
[16] Volkmann, L., Spanning multipartite tournaments of semicomplete multipartite digraphs, Ars Combin., 58, 271-278, (2001) · Zbl 1065.05047
[17] Yeo, A., One-diregular subgraphs in semicomplete multipartite digraphs, J. Graph Theory, 24, 2, 175-185, (1997) · Zbl 0865.05045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.