The concept of linear tangle was introduced as an obstruction to mixed searching number. The concept of single ideal has been introduced as an obstruction to linear-width. Moreover, it was already known that mixed search number is equivalent to linear-width. Hence, by combining those results, we obtain a proof of the equivalence between linear tangle and single ideal. This short report gives an alternative proof of the equivalence.
References
[1]
Aigner, M. and Fromme, M. (1984) A Game of Cops and Robbers. Discrete Applied Mathematics, 8, 1-12. https://doi.org/10.1016/0166-218X(84)90073-8
[2]
Bonato, A. (2011) The Game of Cops and Robbers on Graphs. Vo. 12, The Student Mathematical Library. https://doi.org/10.1090/stml/061
[3]
Bonato, A. and Yang, B.T. (2013) Graph Searching and Related Problems. In: Pardalos, P., Du, D.Z. and Graham, R., Eds., Handbook of Combinatorial Optimization, Springer, Berlin, 1511-1558. https://doi.org/10.1007/978-1-4419-7997-1_76
[4]
Angelopoulos, S., Fraignaud, P., Fomin, F., Nisse, N. and Thilikos, D.M. (2017) Report on GRASTA 2017, 6th Workshop on Graph Searching, Theory and Applications, Anogia, Crete, Greece, April 10-13, 2017. https://hal-lirmm.ccsd.cnrs.fr/lirmm-01645614
[5]
Fomin, F.V. and Thilikos, D.M. (2008) An Annotated Bibliography on Guaranteed Graph Searching. Theoretical Computer Science, 399, 236-245. https://doi.org/10.1016/j.tcs.2008.02.040
[6]
Thilikos, D.M. (2000) Algorithms and Obstructions for Linear-Width and Related Search Parameters. Discrete Applied Mathematics, 105, 239-271. https://doi.org/10.1016/S0166-218X(00)00175-X
[7]
Bienstock, D. (1989) Graph Searching, Path-Width, Tree-Width and Related Problems (a Survey). In Reliability of Computer and Communication Networks, Vol. 5 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 33-50.
[8]
Fomin, F.V. and Thilikos, D.M. (2003) On the Monotonicity of Games Generated by Symmetric Submodular Functions. Discrete Applied Mathematics, 131, 323-335. https://doi.org/10.1016/S0166-218X(02)00459-6
[9]
Fujita, T. and Yamazaki, K. (2017) Linear-Width and Single Ideal. The 20th Anniversary of the Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo University of Science, 29th August-1st September 2017, 110-111. http://www.jcdcgg.u-tokai.ac.jp/JCDCG3_2017_abstracts.pdf
[10]
Geelen, J., Gerards, B., Robertson, N. and Whittle, G. (2006) Obstructions to Branch-Decomposition of Matroids. Journal of Combinatorial Theory, Series B, 96, 560-570. https://doi.org/10.1016/j.jctb.2005.11.001
