Skip to main content
Springer Nature Link
Log in

Algorithms for finding maximum transitive subtournaments

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  • Alon N (1998) On the capacity of digraphs. Eur J Combin 19:1–5

    Article  MATH  Google Scholar 

  • Bang-Jensen J, Gutin G (2001) Digraphs: theory, algorithms and applications. Springer, London

    Google Scholar 

  • Berghammer R, Fronk A (2006) Exact computation of minimum feedback vertex sets with relational algebra. Fund Inform 70:301–316

    MathSciNet  MATH  Google Scholar 

  • 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

  • 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

  • Butenko S, Wilhelm WE (2006) Clique-detection models in computational biochemistry and genomics. Eur J Oper Res 173:1–17

    Article  MathSciNet  MATH  Google Scholar 

  • Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper Res Lett 9:375–382

    Article  MATH  Google Scholar 

  • Chakradhar ST, Balakrishnan A, Agrawal VD (1995) An exact algorithm for selecting partial scan flip-flops. J Electron Test Theory Appl 7:83–93

    Article  Google Scholar 

  • 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

  • Dechter R (2003) Constraint processing. Morgan Kaufmann, San Francisco

  • 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

  • Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H Freeman, San Francisco

    MATH  Google Scholar 

  • Gargano L, Körner J, Vaccaro U (1992) Qualitative independence and Sperner problems for directed graphs. J Combin Theory Ser A 61:173–192

    Article  MathSciNet  MATH  Google Scholar 

  • Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum, New York, pp 85–103

  • Kiviluoto L, Östergård PRJ, Vaskelainen VP (2009) Sperner capacity of small digraphs. Adv Math Commun 3:125–133

    Article  MathSciNet  MATH  Google Scholar 

  • Körner J, Pilotto C, Simonyi G (2005) Local chromatic number and Sperner capacity. J Combin Theory Ser B 95:101–117

    Article  MathSciNet  MATH  Google Scholar 

  • 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

  • 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

  • Lloyd EL, Soffa ML (1988) On locating minimum feedback vertex sets. J Comput Syst Sci 37:292–311

    Article  MathSciNet  MATH  Google Scholar 

  • McGeoch CC (2007) Experimental algorithmics. Commun ACM 50(11):27–31

    Article  Google Scholar 

  • Neumann-Lara V (1982) The dichromatic number of a digraph. J Combin Theory Ser B 33:265–270

    Article  MathSciNet  MATH  Google Scholar 

  • Orenstein T, Kohavi Z, Pomeranz I (1995) An optimal algorithm for cycle breaking in directed graphs. J Electron Test Theory Appl 7:71–81

    Article  Google Scholar 

  • Östergård PRJ (2002) A fast algorithm for the maximum clique problem. Discrete Appl Math 120:197–207

  • Östergård PRJ, Vaskelainen VP (2011) Russian doll search for the Steiner triple covering problem. Optim Lett 5:631–638

    Article  MathSciNet  MATH  Google Scholar 

  • Pardalos PM, Xue J (1994) The maximum clique problem. J Global Optim 4:301–328

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  Google Scholar 

  • Sali A, Simonyi G (1999) Orientations of self-complementary graphs and the relation of Sperner and Shannon capacities. Eur J Combin 20:93–99

    Article  MathSciNet  MATH  Google Scholar 

  • Shannon CE (1956) The zero-error capacity of a noisy channel. IRE Trans Inform Theory 2:8–19

    Article  MathSciNet  Google Scholar 

  • 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

    Article  MathSciNet  Google Scholar 

  • 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

  • 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

Download references

Acknowledgments

The authors thank Brendan McKay for useful discussions and the referees for valuable comments. L. Kiviluoto was supported by the Academy of Finland, Grant No. 100500. P. R. J. Östergård was supported in part by the Academy of Finland, Grants No. 107493, 110196, 130142, and 132122. V. P. Vaskelainen was supported by the Academy of Finland, Grant No. 107493.

Author information

Authors and Affiliations

  1. Speago Ltd, Pieni Roobertinkatu 11, 00130, Helsinki, Finland

    Lasse Kiviluoto

  2. Department of Communications and Networking, Aalto University School of Electrical Engineering, P.O. Box 13000, 00076, Aalto, Finland

    Patric R. J. Östergård & Vesa P. Vaskelainen

Authors
  1. Lasse Kiviluoto
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Patric R. J. Östergård
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Vesa P. Vaskelainen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Patric R. J. Östergård.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kiviluoto, L., Östergård, P.R.J. & Vaskelainen, V.P. Algorithms for finding maximum transitive subtournaments. J Comb Optim 31, 802–814 (2016). https://doi.org/10.1007/s10878-014-9788-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-014-9788-z

Keywords

Search

Navigation