Graph Search is nowadays a classic problem in Graph Theory. Emerging from an evident desire of enthusiastic speleologists to design efficient search \& rescue strategies, the problem and its particularities fascinated and inspired countless mathematicians and computer scientists in their pursuit of deeper cognition. Moreover, various applications broadened the impact of the problem into unexpected or even formerly non-existent domains.

This dissertation thesis attempts to summarize, evaluate and extend the problem state of art. Our fundamental focus lies in Phalanx Search Problem, our custom variant of the Graph Search Problem. We provide a strong motivation and application background that supports the importance of our efforts and impact potential of the results achieved.

We commence by introducing a compact definition of our problem variant to form a solid foundation for the consequent work. We investigate the problem complexity, often parametrized by various Graph Search derivatives, and in most cases, establish a tight boundary for the search numbers, thus fixing the position of our novel variant in the Graph Search Number inequation chain.

In particular, we provide a rigorous analysis of the effect of monotony in Phalanx Graph Search, which is an extensively studied and frequently surprising aspect of existing search variants. These results are especially valuable because they directly affect the problem's complexity classification.

Further, we investigate behaviour of Phalanx Graph Search on the subclass of trees, establishing tight boundaries, defining minimal obstacles and designing optimal algorithms for search strategy construction. This detailed analysis aids us in the subsequent research.

Finally, we introduce a fusion of Phalanx- and Node-Search with Minimal Spanning Tree Problems. We investigate and prove complexity of both problems, propose a pragmatic approximation method and further investigate approximation hardness of our novel challenge.

We are convinced that this document follows very clear motivation, presents valuable insights into the problem nature, fuels its application potential, answers several open problems, and eventually, proposes various loose endpoints suitable for future research in the area.

1 Introduction
2 Preliminary
2.1 Basic Terminology and Notation
2.2 Underlying Problems
2.2.1 Graph Search
2.2.2 Spanning Trees
2.2.3 Shortest and Longest Paths
2.3 Computational Complexity
3 Related Works
3.1 Graph Search Problem
3.1.1 Relations to Graph Invariants
3.1.2 Mobile Robotics
3.1.3 Searching on Grids
3.1.4 Complexity and Obstacles on Graphs and Trees
3.1.5 Other Search Variants and Environments
3.2 Minimum Spanning Tree Problem
3.3 Hamiltonian- and Longest-Path Problems
3.4 Recent Rescue Mission
3.5 Contribution Outlook
4 Phalanx Graph Search
4.1 Motivation
4.2 Problem Statement
4.2.1 Tidiness
4.3 Relation to Connected Search
4.3.1 Node Search
4.3.2 Mixed Search
4.4 Problem Complexity
5 Monotony in Phalanx Graph Search
5.1 Towards the Counterexample
5.2 Scaling the Gap
5.3 Towards an Arbitrary Difference
5.4 The Odd Case of Edge Search
6 The Case of Trees
6.1 Node Search on Trees
6.1.1 Urchins and psn(T)
6.1.2 Algorithm for psn(T)
6.1.3 Urchins and Avenues
6.2 Edge and Mixed Search on Trees
7 Graph Search and Spanning Trees
7.1 Minimum Node Search Spanning Tree Problem
7.1.1 Complexity
7.1.2 Approximation
7.2 Phalanx Graph Search Spanning Tree
7.2.1 Complexity
7.2.2 Approximation
7.2.3 Suitability and Rationale of the Hub Approximation
8 Conclusion
Bibliography
A Optimal Search Strategy on Q

[1] Abramovskaya, T. V. and Petrov, N. N. (2013). The theory of guaranteed search on
graphs. Vestnik St. Petersburg University: Mathematics, 46(2):49{75.
[2] Backstrom, L., Boldi, P., Rosa, M., Ugander, J., and Vigna, S. (2011). Four Degrees
of Separation. Proceedings of the 4th Annual ACM Web Science Conference, New
York, NY, USA.
[3] Barriere, L., Flocchini, P., Fomin, F. V., Fraigniaud, P., Nisse, N., Santoro, N., and
Thilikos, D. M. (2012). Connected graph searching. Information and Computation,
219:1{16.
[4] Barriere, L., Flocchini, P., Fraigniaud, P., and Santoro, N. (2002). Capture of an
Intruder by Mobile Agents. In Proceedings of the Fourteenth Annual ACM Symposium
on Parallel Algorithms and Architectures, SPAA '02, pages 200{209, New York, NY,
USA. ACM. event-place: Winnipeg, Manitoba, Canada.
[5] Barriere, L., Fraigniaud, P., Santoro, N., and Thilikos, D. M. (2003). Searching Is
Not Jumping. In Bodlaender, H. L., editor, Graph-Theoretic Concepts in Computer
Science, Lecture Notes in Computer Science, pages 34{45. Springer Berlin Heidelberg.
[6] Barriere Figueroa, E., Fraigniaud, P., Santoro, N., and Thilikos Touloupas, D.
(2002). Connected and internal graph searching.
[7] Berger, F., Gilbers, A., Grune, A., and Klein, R. (2009). How Many Lions Are
Needed to Clear a Grid? Algorithms, 2(3):1069{1086.
[8] Best, M. J., Gupta, A., Thilikos, D. M., and Zoros, D. (2016). Contraction obstructions
for connected graph searching. Discrete Applied Mathematics, 209:27{47.
95
[9] Bienstock, D. and Seymour, P. (1991). Monotonicity in graph searching. Journal of
Algorithms, 12(2):239{245.
[10] Bjorklund, A., Husfeldt, T., and Khanna, S. (2004). Approximating longest directed
paths and cycles. In International Colloquium on Automata, Languages, and
Programming, pages 222{233. Springer.
[11] Blin, L., Burman, J., and Nisse, N. (2017). Exclusive Graph Searching. Algorith-
mica, 77(3):942{969.
[12] Blin, L., Fraigniaud, P., Nisse, N., and Vial, S. (2006). Distributed Chasing of
Network Intruders. In Flocchini, P. and Gasieniec, L., editors, Structural Information
and Communication Complexity, Lecture Notes in Computer Science, pages 70{84,
Berlin, Heidelberg. Springer Berlin Heidelberg.
[13] Borassi, M., Crescenzi, P., Habib, M., Kosters, W., Marino, A., and Takes, F.
(2014). On the Solvability of the Six Degrees of Kevin Bacon Game. In Ferro,
A., Luccio, F., and Widmayer, P., editors, Fun with Algorithms, Lecture Notes in
Computer Science, pages 52{63, Cham. Springer International Publishing.
[14] Borchardt, C. W. (1860). Uber eine Interpolationsformel fur eine Art symmetrischer
Functionen und uber deren Anwendung. Math. Abh. der Akademie der
Wissenschaften zu Berlin, pages 1{20.
[15] Borie, R., Tovey, C., and Koenig, S. (2011). Algorithms and complexity results for
graph-based pursuit evasion. Autonomous Robots, 31(4):317.
[16] Boruvka, Otakar (1926). O jistem problemu minimalnm. Prace Moravske
Prrodovedecke spolecnosti, III(3).
[17] Breisch, R. (1967). An intuitive approach to speleotopology. Southwestern Cavers
(A publication of the Southwestern Region of the National Speleological Society), 6:72{
78.
[18] Breisch, R. L. (2012). Lost in a Cave - Applying Graph Theory to Cave Exploration.
National Speleological Society, Huntsville, Alabama, 1st edition edition.
96
[19] Brooks, R. R., Schwier, J., and Grin, C. (2009). Markovian Search Games in
Heterogeneous Spaces. IEEE Transactions on Systems, Man, and Cybernetics, Part
B (Cybernetics), 39(3):626{635.
[20] Cayley, A. (1889). A Theorem on Trees. Quart. J. Pure Appl. Math., 23:376{378.
[21] Cheng, C.-S. (1981). Maximizing the Total Number of Spanning Trees in a Graph:
Two Related Problems in Graph Theory and Optimum Design Theory. JOURNAL
OF COMBINATORIAL THEOR, pages 240{248.
[22] Cheng, P. (2003). A short survey on pursuit-evasion games.
[23] Chung, M.-J., Makedon, F., Sudborough, I. H., and Turner, J. (1985). Polynomial
Time Algorithms for the MIN CUT Problem on Degree Restricted Trees. SIAM
Journal on Computing, 14(1):158{177. Publisher: Society for Industrial and Applied
Mathematics.
[24] Chung, T. H., Hollinger, G. A., and Isler, V. (2011). Search and pursuit-evasion in
mobile robotics. Autonomous Robots, 31(4):299.
[25] Coudert, D., Huc, F., and Mazauric, D. (2008). Computing and Updating the
Process Number in Trees. In Baker, T. P., Bui, A., and Tixeuil, S., editors, Principles
of Distributed Systems, Lecture Notes in Computer Science, pages 546{550, Berlin,
Heidelberg. Springer.
[26] Coudert, D., Huc, F., and Mazauric, D. (2012). A Distributed Algorithm for
Computing the Node Search Number in Trees. Algorithmica, 63(1):158{190.
[27] Coudert, D. and Sereni, J.-S. (2011). Characterization of graphs and digraphs with
small process numbers. Discrete Applied Mathematics, 159(11):1094{1109.
[28] Crescenzi, P., Grossi, R., Habib, M., Lanzi, L., and Marino, A. (2013). On computing
the diameter of real-world undirected graphs. Theoretical Computer Science,
514:84{95.
[29] Crescenzi, P., Grossi, R., Imbrenda, C., Lanzi, L., and Marino, A. (2010). Finding
the Diameter in Real-World Graphs. In de Berg, M. and Meyer, U., editors,
97
Algorithms { ESA 2010, Lecture Notes in Computer Science, pages 302{313, Berlin,
Heidelberg. Springer.
[30] Crescenzi, P., Grossi, R., Lanzi, L., and Marino, A. (2012). On Computing the
Diameter of Real-World Directed (Weighted) Graphs. In Klasing, R., editor, Ex-
perimental Algorithms, Lecture Notes in Computer Science, pages 99{110, Berlin,
Heidelberg. Springer.
[31] Dawes, R. W. (1992). Some pursuit-evasion problems on grids. Information Pro-
cessing Letters, 43(5):241{247.
[32] Dereniowski, D., Diner, z. Y., and Dyer, D. (2013). Three-fast-searchable graphs.
Discrete Applied Mathematics, 161(13):1950{1958.
[33] Dereniowski, D., Lingas, A., Osula, D., Persson, M., and Z_ ylinski, P. (2019). Clearing
directed subgraphs by mobile agents: Variations on covering with paths. Journal
of Computer and System Sciences, 102:57{68.
[34] Dereniowski, D., Lingas, A., Persson, M., Urbanska, D., and Z_ ylinski, P. (2017).
The Snow Team Problem. In Klasing, R. and Zeitoun, M., editors, Fundamentals
of Computation Theory, Lecture Notes in Computer Science, pages 190{203, Berlin,
Heidelberg. Springer.
[35] Dijkstra, E. W. (1959). A Note on Two Problems in Connexion with Graphs.
Numerische Mathematik, 1:269{271.
[36] Dumitrescu, A., Kok, H., Suzuki, I., and Z_ ylinski, P. (2010). Vision-Based Pursuit-
Evasion in a Grid. SIAM Journal on Discrete Mathematics, 24(3):1177{1204.
[37] Ellis, J. A., Sudborough, H., and Turner, J. S. (1987). Graph Separation and Search
Number. All Computer Science and Engineering Research WUCS-87-11, Washington
University in St. Louis.
[38] Ellis, J. A., Sudborough, I. H., and Turner, J. S. (1994). The Vertex Separation
and Search Number of a Graph. Information and Computation, 113(1):50{79.
98
[39] Fomin, F. V. and Golovach, P. A. (2000). Graph Searching and Interval Completion.
SIAM Journal on Discrete Mathematics, 13(4):454{464.
[40] Fomin, F. V., Golovach, P. A., Kratochvl, J., Nisse, N., and Suchan, K. (2010).
Pursuing a fast robber on a graph. Theoretical Computer Science, 411(7):1167{1181.
[41] Fomin, F. V., Heggernes, P., and Telle, J. A. (2005a). Graph Searching, Elimination
Trees, and a Generalization of Bandwidth. Algorithmica, 41(2):73{87.
[42] Fomin, F. V. and Thilikos, D. M. (2008). An annotated bibliography on guaranteed
graph searching. Theoretical Computer Science, 399(3):236{245.
[43] Fomin, F. V., Thilikos, D. M., and Todinca, I. (2005b). Connected Graph Searching
in Outerplanar Graphs. In 7th International Colloquium on Graph Theory (ICGT
2005).
[44] Fraigniaud, P. and Nisse, N. (2006). Connected Treewidth and Connected Graph
Searching. In Correa, J. R., Hevia, A., and Kiwi, M., editors, LATIN 2006: Theoret-
ical Informatics, Lecture Notes in Computer Science, pages 479{490, Berlin, Heidelberg.
Springer.
[45] Fraigniaud, P. and Nisse, N. (2008). Monotony properties of connected visible graph
searching. Information and Computation, 206(12):1383{1393.
[46] Gabow, H. and Myers, E. (1978). Finding All Spanning Trees of Directed and
Undirected Graphs. SIAM Journal on Computing, 7(3):280{287.
[47] Gabow, H. N. and Nie, S. (2008). Finding long paths, cycles and circuits. In
International Symposium on Algorithms and Computation, pages 752{763. Springer.
[48] Garey, M. R. and Johnson, D. S. (1979). Computers and intractability, volume 174.
freeman San Francisco.
[49] Golovach, P. A. (1989). A topological invariant in pursuit problems. Dier. Uravn.,
25(6):923{929.
[50] Golovach, P. A. (1992). Minimal trees of a given search number. Cybernetics and
Systems Analysis, 28(4):509{513.
99
[51] Graham, R. L. and Hell, P. (1985). On the History of the Minimum Spanning Tree
Problem. Annals of the History of Computing, 7(1):43{57.
[52] Hakimi, S. and Green, D. (1964). Generation and Realization of Trees and k-
Trees. IEEE Transactions on Circuit Theory, 11(2):247{255. Conference Name: IEEE
Transactions on Circuit Theory.
[53] Hollinger, G., Kehagias, A., and Singh, S. (2010). GSST: anytime guaranteed
search. Autonomous Robots, 29(1):99{118.
[54] Imani, N., Sarbazi-Azad, H., and Zomaya, A. Y. (2007). Capturing an intruder in
product networks. Journal of Parallel and Distributed Computing, 67(9):1018{1028.
[55] Jarnk, V. (1930). O jistem problemu minimalnm. (Z dopisu panu O. Boruvkovi).
Prace moravske prrodovedecke spolecnosti, 6(4):57{63.
[56] Karger, D., Motwani, R., and Ramkumar, G. D. S. (1997). On approximating the
longest path in a graph. Algorithmica, 18(1):82{98.
[57] Kehagias, A., Hollinger, G., and Singh, S. (2009). A graph search algorithm for
indoor pursuit/evasion. Mathematical and Computer Modelling, 50(9):1305{1317.
[58] Kelmans, A. and Chelnokov, V. (1974). A certain polynomial of a graph and graphs
with an extremal number of trees. Journal of Combinatorial Theory, 16(3):197{214.
[59] Kel'mans, A. K. (1965). The number of trees in a graph. Avtomat. i Telemekh,
26(12):2194{2204.
[60] Kirousis, L. M. and Papadimitriou, C. H. (1985). Interval graphs and seatching.
Discrete Mathematics, 55(2):181{184.
[61] Kirousis, L. M. and Papadimitriou, C. H. (1986). Searching and pebbling. Theo-
retical Computer Science, 47:205{218.
[62] Klein, K. and Suri, S. (2015). Capture bounds for visibility-based pursuit evasion.
Computational Geometry, 48(3):205{220.
100
[63] Kolling, A., Kleiner, A., Lewis, M., and Sycara, K. (2011). Computing and executing
strategies for moving target search. In 2011 IEEE International Conference on
Robotics and Automation, pages 4246{4253. ISSN: 1050-4729.
[64] Kruskal, J. B. (1956). On the Shortest Spanning Subtree of a Graph and the
Traveling Salesman Problem. Proceedings of the American Mathematical Society,
7(1):48{50.
[65] Lamprou, I. (2018). Mobility Problems in Distributed Search and Combinatorial
Games. phd, University of Liverpool.
[66] LaPaugh, A. S. (1993). Recontamination Does Not Help to Search a Graph. J.
ACM, 40(2):224{245.
[67] Leskovec, J., Kleinberg, J., and Faloutsos, C. (2005). Graphs over time: densi-
cation laws, shrinking diameters and possible explanations. In Proceedings of the
eleventh ACM SIGKDD international conference on Knowledge discovery in data
mining, KDD '05, pages 177{187, Chicago, Illinois, USA. Association for Computing
Machinery.
[68] Li, H. and Chong, E. K. P. (2009). Search on lines and graphs. In Proceedings of
the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th
Chinese Control Conference, pages 5780{5785. ISSN: 0191-2216.
[69] Lin, C.-F., Navratil, O., and Peng, S.-L. (2018). On the Cooperative Graph Searching
Problem. In Tian, C., Nagoya, F., Liu, S., and Duan, Z., editors, Structured
Object-Oriented Formal Language and Method, pages 39{47. Springer International
Publishing.
[70] Loberman, H. and Weinberger, A. (1957). Formal Procedures for Connecting Tern-
nals with a Minimum Total Wire Length. Journal of the ACM, 4(4):428{437.
[71] Maamoun, M. and Meyniel, H. (1987). On a game of policemen and robber. Discrete
Applied Mathematics, 17(3):307{309.
101
[72] Mayeda, W. and Seshu, S. (1965). Generation of Trees without Duplications. IEEE
Transactions on Circuit Theory, 12(2):181{185. Conference Name: IEEE Transactions
on Circuit Theory.
[73] Megiddo, N., Hakimi, S. L., Garey, M. R., Johnson, D. S., and Papadimitriou,
C. H. (1988). The Complexity of Searching a Graph. J. ACM, 35(1):18{44.
[74] Nisse, N. (2009). Connected graph searching in chordal graphs. Discrete Applied
Mathematics, 157(12):2603{2610.
[75] Nisse, N. (2014). Algorithmic complexity: Between Structure and Knowledge How
Pursuit-evasion Games help. thesis, Universite Nice Sophia Antipolis.
[76] Nisse, N. (2019). Network Decontamination. In Flocchini, P., Prencipe, G., and
Santoro, N., editors, Distributed Computing by Mobile Entities: Current Research in
Moving and Computing, Lecture Notes in Computer Science, pages 516{548. Springer
International Publishing, Cham.
[77] P. A. Golovach (1992). Minimal trees with a given vertex-search number. Diskr.
Mat., 4(2):52{60.
[78] Parsons, T. D. (1978). Pursuit-evasion in a graph. In Alavi, Y. and Lick, D. R.,
editors, Theory and Applications of Graphs, Lecture Notes in Mathematics, pages
426{441, Berlin, Heidelberg. Springer.
[79] Peng, S.-L., Ho, C.-W., Hsu, T.-s., Ko, M.-T., and Tang, C. Y. (1998). A Linear-
Time Algorithm for Constructing an Optimal Node-Search Strategy of a Tree. In
Hsu, W.-L. and Kao, M.-Y., editors, Computing and Combinatorics, Lecture Notes
in Computer Science, pages 279{289. Springer Berlin Heidelberg.
[80] Petrov, N. N. (1982). A problem of pursuit in the absence of information on the
pursued. Dier. Uravn., 18(8):1345{1352.
[81] Petrov, N. N. (1983). On the dierential game "Casacks-robbers". Dierentsial'nye
Uravneniya, 19(8):1366{1374.
102
[82] Prim, R. C. (1957). Shortest connection networks and some generalizations. The
Bell System Technical Journal, 36(6):1389{1401. Conference Name: The Bell System
Technical Journal.
[83] Scheer, P. (1990). A Linear Algorithm for the Pathwidth of Trees. In Bodendiek,
P. D. R. and Henn, P. D. R., editors, Topics in Combinatorics and Graph Theory,
pages 613{620. Physica-Verlag HD.
[84] Sheng-Lung Peng (1999). A Study of Graph Searching on Special Graphs. Dissertation,
National Tsing Hua University.
[85] Smith, J. D. H. (1987). Minimal trees of given search number. Discrete Mathemat-
ics, 66(1):191{202.
[86] Sugihara, K. and Suzuki, I. (1989). Optimal Algorithms for a Pursuit-Evasion
Problem in Grids. SIAM Journal on Discrete Mathematics, 2(1):126{143.
[87] Takahashi, A., Ueno, S., and Kajitani, Y. (1995). Mixed searching and properpath-
width. Theoretical Computer Science, 137(2):253{268.
[88] Takes, F. W. and Kosters, W. A. (2011). Determining the diameter of small world
networks. In Proceedings of the 20th ACM international conference on Information
and knowledge management, CIKM '11, pages 1191{1196, Glasgow, Scotland, UK.
Association for Computing Machinery.
[89] Thilikos, D. M. (2000). Algorithms and obstructions for linear-width and related
search parameters. Discrete Applied Mathematics, 105(1{3):239{271.
[90] Yang, B., Dyer, D., and Alspach, B. (2005). Sweeping Graphs with Large Clique
Number. In Fleischer, R. and Trippen, G., editors, Algorithms and Computation,
Lecture Notes in Computer Science, pages 908{920. Springer Berlin Heidelberg.
[91] Yang, B., Dyer, D., and Alspach, B. (2009). Sweeping graphs with large clique
number. Discrete Mathematics, 309(18):5770{5780.