Abstract
A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it.
This work is supported by the Research Council of Norway through grant 166429/V30.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, London (1980)
Hakimi, S.L., Schmeichel, E.F., Young, N.E.: Orienting graphs to optimize reachability. Information Processing Letters 63(5), 229–235 (1997)
Heggernes, P., Mancini, F.: Minimal split completions of graphs. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 592–604. Springer, Heidelberg (2006)
Heggernes, P., Mancini, F., Papadopoulos, C.: Minimal comparabiltiy completions. Reports in Informatics 317, University of Bergen (2006), http://www.ii.uib.no/publikasjoner/texrap/pdf/2006-317.pdf
Heggernes, P., Suchan, K., Todinca, I., Villanger, Y.: Minimal interval completions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 403–414. Springer, Heidelberg (2005)
Heggernes, P., Telle, J.A., Villanger, Y.: Computing minimal triangulations in time O(n αlogn) = o(n 2.376). In: Proceedings of SODA 2005 - 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 907–916 (2005)
Kratsch, D., McConnell, R.M., Mehlhorn, K., Spinrad, J.P.: Certifying algorithms for recognizing interval graphs and permutation graphs. SIAM J. Comput. (to appear, 2006)
Kratsch, D., Spinrad, J.P.: Between O(nm) and O(n α). In: Proceedings of SODA 2003 - 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 709–716 (2003)
Kratsch, D., Spinrad, J.P.: Minimal fill in o(n 3) time. Discrete Math. 306(3), 366–371 (2006)
Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Disc. Appl. Math. 113, 109–128 (2001)
Rapaport, I., Suchan, K., Todinca, I.: Minimal proper interval completions. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 2006–2032. Springer, Heidelberg (2006)
Roberts, F.S.: Graph Theory and Its Application to Problems of Society. Society for Industrial and Applied Mathematics, Philadelphia, PA (1978)
Rose, D., Tarjan, R.E., Lueker, G.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5, 266–283 (1976)
Spinrad, J.: On comparability and permutation graphs. SIAM J. Comput. 14, 658–670 (1985)
Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Alg. Disc. Meth. 2, 77–79 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Heggernes, P., Mancini, F., Papadopoulos, C. (2006). Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_43
Download citation
DOI: https://doi.org/10.1007/11940128_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)