Optimizing Search Ratio in Graph Theory: Insights and Algorithms

Explore the concept of search ratio in graph theory with insights on expanding search paradigms, search times, and optimality criteria. Discover how the order of searching vertices can impact the efficiency of graph searches, along with key theorems and algorithms for approximating search ratios within polynomial time bounds.

• Graph Theory
• Search Ratio
• Optimization
• Algorithms
• Theorems

hpore Follow

Uploaded on Oct 07, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. The expanding search ratio of a graph Spyros Angelopoulos* Christoph D rr* Thomas Lidbetter** *Sorbonne Universit s, UPMC Univ Paris 06, CNRS, LIP6, Paris, France **Department of Mathematics, London School of Economics, UK

2. Background Searching a fixed graph (Koutsoupias, Papadimitriou, Yannakakis, 1996) Mining coal or finding terrorists: The expanding search paradigm (Alpern, L., 2013)

3. Expanding search An expanding search of a (weighted, connected) graph with root ? is a sequence of edges each one of which is incident to a previously searched vertex. 3 1 1 2 2 3 ?

4. Search time 3 1 1 2 ? 2 3 ? For a search ?, and vertex ?, the search time ?(?,?)is the time ? is first discovered. Eg. ?(?,?) = The normalized search time, ?(?,?)is ?(?,?)/?(?,?). Eg. ? ?,? = 7/2 = 3.5 3+2+2 = 7

5. Search ratio 3 1 1 2 Eg. ??= 3.5 2 3 ? ?(?,?) . The search ratio ??of ? is max ? ?(?,?). The search ratio ? of a graph ? is min ??= min max ? ? ? If ? minimises the search ratio we say ? is optimal.

6. Proposition For trees or graphs with unit edge weights, it is optimal to search the vertices in order of their distance from O. 3 1 1 2 2 3 ?

7. Counterexample for weighted graphs 7 6 10 5 ?

8. Counterexample for weighted graphs 7 6 10 5 ?

9. Theorem It is NP-complete to decide whether ? ?. Proof: Reduction from 3-SAT.

10. Theorem There is a polynomial time algorithm that approximates the search ratio within a factor of 4log4 + ? < 5.55. Proof sketch: ? Min. cost tree con- taining all vertices at distance 8 from ?. Min. cost tree con- taining all vertices at distance 4 from ?. Min. cost tree containing all vertices at distance 2 from ?. ?

11. Randomized search ratio For a randomized search ? and a vertex ?, the expected search time and expecte normalized search time are denoted by ?(?,?) and ? ?,? . The randomized search ratio ?? of a random search ? is max ? ?(?,?). The randomized search ratio ? of a graph is min ? ? ? ?(?,?). ??= min max

12. Game theoretic interpretation Finding the optimal randomized search is equivalent to finding the optimal strategy in a zero-sum search game between a Searcher and Hider. Hider/Searcher 1,2 2,1 1 2 1 3/2 3 1 2 1 ? Optimal randomized search: start with short edge with probability 4/5 and long edge with probability 1/5. Randomized search ratio, ? = 7/5.

13. 2-approximate strategy Proposition: For trees or graphs with unit length edges, the optimal deterministic strategy is a 2-approximation for the optimal randomized strategy. Example ? ? = ? and ? ?/2 1 1 1 ?

14. Randomization can be very bad ? 1 but searching in a random order has search ratio ?/2 ? 1 1 ?

15. Randomized star search ?? ?3 ?2 1 = ?1 ?2 ?? ?1 ? ?1 ?2 ?3 ??

16. Idea: randomize in stages Randomize between all edges with length ? satisfying 2? ? < 2?+1 for ? = 0,1,2, Unfortunately, it doesn t work ? This has search ratio 2? 2= ?. 2 2 2 But ? ? 2 2. 1 ?

17. Better idea: randomize in random stages ?1 ?2 ?3 ?? 1 ?? 2? 2 2? 1 2? 1 2 4 8 ?

18. Better idea: randomize in random stages ?1 ?2 ?3 ?? 1 ?? 2? 2 2? 1 2? 1 2 4 8 ?

19. Better idea: randomize in random stages ?1 ?2 ?3 ?? 1 ?? 2? 2 2? 1 2? 1 2 4 8 ?

20. Better idea: randomize in random stages ?1 ?2 ?3 ?? 1 ?? 2? 2 2? 1 2? 1 2 4 8 ?

21. Better idea: randomize in random stages ?1 ?2 ?3 ?? 1 ?? 2? 2 2? 1 2? 1 2 4 8 Theorem: This has an approximation ratio of 5/4. ?

22. Idea of proof Bound ? from below using a collection of mixed Hider strategies: Lemma: If the Hider chooses from the edges ? = 1,2, ? with probability proportional to the square of the length ?? of the edge, the expected search ratio is at least 2 ? ?=1 ? ?? ??2 1 2 1 + . ?=1

23. An exactly optimal randomized search Theorem: If the lengths of the edges don t increase too fast then the optimal randomized search can be found inductively and 2 ? ?=1 ?=1 ?? ??2 1 21 + . ? Theorem: The graph with ? edges that has maximum randomized search ratio is the one with equal length edges, i.e. ? (? + 1)/2.

24. Further directions Computational complexity of finding randomized search ratio? Continuous version