Abstract
A forbidden transition graph is a graph defined together with a set of permitted transitions i.e. unordered pair of adjacent edges that one may use consecutively in a walk in the graph. In this paper, we look for the smallest set of transitions needed to be able to go from any vertex of the given graph to any other. We prove that this problem is NP-hard and study approximation algorithms. We develop theoretical tools that help to study this problem.
B. Bergougnoux—This work is supported by French Agency for Research under the GraphEN project (ANR-15-CE-0009).
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
Similar content being viewed by others
References
Ahmed, M., Lubiw, A.: Shortest paths avoiding forbidden subpaths. In: 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, Freiburg, Germany, Proceedings, 26–28 February 2009, pp. 63–74 (2009)
Bellitto, T.: Separating codes and traffic monitoring. Theor. Comput. Sci. 717, 73–85 (2017)
Kotzig, A.: Moves without forbidden transitions in a graph. Matematický časopis 18(1), 76–80 (1968)
Chen, C.C., Daykin, D.E.: Graphs with Hamiltonian cycles having adjacent lines different colors. J. Comb. Theory Ser. B 21(2), 135–139 (1976)
Gutin, G., Kim, E.J.: Properly coloured cycles and paths: results and open problems. In: Graph Theory, Computational Intelligence and Thought, Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday. pp. 200–208 (2009)
Szeider, S.: Finding paths in graphs avoiding forbidden transitions. Discret. Appl. Math. 126(2–3), 261–273 (2003)
Kanté, M.M., Laforest, C., Momège, B.: An exact algorithm to check the existence of (elementary) paths and a generalisation of the cut problem in graphs with forbidden transitions. In: van Emde Boas, P., Groen, F.C.A., Italiano, G.F., Nawrocki, J., Sack, H. (eds.) SOFSEM 2013. LNCS, vol. 7741, pp. 257–267. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-35843-2_23
Kanté, M.M., Moataz, F.Z., Momège, B., Nisse, N.: Finding paths in grids with forbidden transitions. In: Mayr, E.W. (ed.) WG 2015. LNCS, vol. 9224, pp. 154–168. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53174-7_12
Sudakov, B.: Robustness of graph properties. arXiv (2016)
Bellitto, T., Bergougnoux, B.: On minimum connecting transition sets in graphs. arXiv (2018)
Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)
Peleg, D.: Low stretch spanning trees. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 68–80. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45687-2_5
Acknowledgments
The authors would like to thank Marthe Bonamy, Mamadou M. Kanté, Arnaud Pêcher, Théo Pierron and Xuding Zhu for the interest they showed for our work and for inspiring discussions.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Bellitto, T., Bergougnoux, B. (2018). On Minimum Connecting Transition Sets in Graphs. In: Brandstädt, A., Köhler, E., Meer, K. (eds) Graph-Theoretic Concepts in Computer Science. WG 2018. Lecture Notes in Computer Science(), vol 11159. Springer, Cham. https://doi.org/10.1007/978-3-030-00256-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-00256-5_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-00255-8
Online ISBN: 978-3-030-00256-5
eBook Packages: Computer ScienceComputer Science (R0)