×

Algorithms for finding maximum transitive subtournaments. (English) Zbl 1342.90164

Summary: The problem of finding a maximum clique is a fundamental problem for undirected graphs, and it is natural to ask whether there are analogous computational problems for directed graphs. Such a problem is that of finding a maximum transitive subtournament in a directed graph. A tournament is an orientation of a complete graph; it is transitive if the occurrence of the arcs \(xy\) and \(yz\) implies the occurrence of \(xz\). Searching for a maximum transitive subtournament in a directed graph \(D\) is equivalent to searching for a maximum induced acyclic subgraph in the complement of \(D\), which in turn is computationally equivalent to searching for a minimum feedback vertex set in the complement of \(D\). This paper discusses two backtrack algorithms and a Russian doll search algorithm for finding a maximum transitive subtournament, and reports experimental results of their performance.

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks

Software:

CLIP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon N (1998) On the capacity of digraphs. Eur J Combin 19:1-5 · Zbl 0894.05031
[2] Bang-Jensen J, Gutin G (2001) Digraphs: theory, algorithms and applications. Springer, London · Zbl 0958.05002
[3] Berghammer R, Fronk A (2006) Exact computation of minimum feedback vertex sets with relational algebra. Fund Inform 70:301-316 · Zbl 1110.68093
[4] Bomze IM, Budinich M, Pardalos PM, Pelillo M (1999) The maximum clique problem. In: Du D-Z, Pardalos PM (eds) Handbook of combinatorial optimization, supplement vol A. Kluwer, Dordrecht, pp 1-74 · Zbl 1253.90188
[5] Brazdil PB, Soares C (2000) A comparison of ranking methods for classification algorithm selection. In: López de Mántanas R, Plaza E (eds) Machine learning: ECML 2000, LNCS vol 1810. Springer, Berlin, pp 63-74
[6] Butenko S, Wilhelm WE (2006) Clique-detection models in computational biochemistry and genomics. Eur J Oper Res 173:1-17 · Zbl 1125.92025
[7] Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper Res Lett 9:375-382 · Zbl 0711.90080
[8] Chakradhar ST, Balakrishnan A, Agrawal VD (1995) An exact algorithm for selecting partial scan flip-flops. J Electron Test Theory Appl 7:83-93
[9] Cong J, Smith M (1993) A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design. In: Proceedings of the 30th international design automation conference. ACM, New York, pp 755-760
[10] Dechter R (2003) Constraint processing. Morgan Kaufmann, San Francisco · Zbl 1057.68114
[11] Funke M, Reinelt G (1996) A polyhedral approach to the feedback vertex set problem. In: Cunningham WH, McCormick ST, Queyranne M (eds) Integer programming and combinatorial optimization, LNCS vol 1084. Springer, Berlin, pp 445-459 · Zbl 1415.90063
[12] Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H Freeman, San Francisco · Zbl 0411.68039
[13] Gargano L, Körner J, Vaccaro U (1992) Qualitative independence and Sperner problems for directed graphs. J Combin Theory Ser A 61:173-192 · Zbl 0765.05007
[14] Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum, New York, pp 85-103 · Zbl 1467.68065
[15] Kiviluoto L, Östergård PRJ, Vaskelainen VP (2009) Sperner capacity of small digraphs. Adv Math Commun 3:125-133 · Zbl 1197.94166
[16] Körner J, Pilotto C, Simonyi G (2005) Local chromatic number and Sperner capacity. J Combin Theory Ser B 95:101-117 · Zbl 1071.05035
[17] Lam CWH, Thiel LH, Swiercz S (1988) A computer search for a projective plane of order 10. In: Deza MM, Frankl P, Rosenberg IG (eds) Algebraic, extremal and metric combinatorics. Cambridge University Press, Cambridge, pp 155-165 · Zbl 0669.51005
[18] Lin H-M, Jou J-Y (2000) On computing the minimum feedback vertex set of a directed graph by contraction operations. IEEE Trans Comput-Aided Design Integr Circuits Syst 19:295-307
[19] Lloyd EL, Soffa ML (1988) On locating minimum feedback vertex sets. J Comput Syst Sci 37:292-311 · Zbl 0661.68065
[20] McGeoch CC (2007) Experimental algorithmics. Commun ACM 50(11):27-31
[21] Neumann-Lara V (1982) The dichromatic number of a digraph. J Combin Theory Ser B 33:265-270 · Zbl 0506.05031
[22] Orenstein T, Kohavi Z, Pomeranz I (1995) An optimal algorithm for cycle breaking in directed graphs. J Electron Test Theory Appl 7:71-81
[23] Östergård PRJ (2002) A fast algorithm for the maximum clique problem. Discrete Appl Math 120:197-207 · Zbl 1019.05054
[24] Östergård PRJ, Vaskelainen VP (2011) Russian doll search for the Steiner triple covering problem. Optim Lett 5:631-638 · Zbl 1228.90100
[25] Pardalos PM, Xue J (1994) The maximum clique problem. J Global Optim 4:301-328 · Zbl 0797.90108
[26] Rhodes N, Willett P, Calvet A, Dunbar JB, Humblet C (2003) CLIP: similarity searching of 3D databases using clique detection. J Chem Inform Comput Sci 43:443-448
[27] Sali A, Simonyi G (1999) Orientations of self-complementary graphs and the relation of Sperner and Shannon capacities. Eur J Combin 20:93-99 · Zbl 0917.05075
[28] Shannon CE (1956) The zero-error capacity of a noisy channel. IRE Trans Inform Theory 2:8-19
[29] Smith GW Jr, Walford RB (1975) The identification of a minimal feedback vertex set of a directed graph. IEEE Trans Circuits Syst 22:9-14
[30] Thiel LH, Lam CWH, Swiercz S (1987) Using a CRAY-1 to perform backtrack search. In: Kartashev LP, Kartashev SI (eds) Supercomputing ’87: supercomputer design, performance evaluation and performance education, vol 3. International Supercomputing Institute, St. Petersburg, FL, pp 92-99 · Zbl 0765.05007
[31] Verfaillie G, Lemaître M, Schiex T (1996) Russian doll search for solving constraint optimization problems. In: Proceedings of the 13th national conference on artificial intelligence (AAAI-96). AAAI Press, Menlo Park, pp 181-187
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.