# Directed Graph Exploration

Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond Klaus-Tycho Frster, Rijad Nuridini, Jara Uitto, Roger Wattenhofer ETH Zurich Distributed Computing www.disco.ethz.ch The game of Cops and Robbers How to catch a robber on a graph? The rules of the game

The Cop is placed first C The Robber may then choose a placement C R Next, they alternate in moves

C R Next, they alternate in moves C R Next, they alternate in moves

C R Next, they alternate in moves C R The Cop won!

C The Cop won! C Graphs where cop wins have a cop number of How many moves does the cop need?

For graphs with : nodes: moves always suffice graphs where moves are needed Catch multiple? C R

moves suffice for paths R R Upper bound to catch robbers 1. moves for the first robber 2. Every further robber:

Cop moves to start in at most diameter D moves moves for the next robber moves in total Lower bound to catch robbers

0 .5 0 . 25 0 . 25 Lower bound to catch robbers C

0 .5 0 . 25 0 . 25 Lower bound to catch robbers R

C R R 0 .5 0 . 25 0 . 25

Lower bound to catch robbers R C R R 0 .5 0 . 25

0 . 25 Lower bound to catch robbers R C R R

0 .5 0 . 25 0 . 25 Lower bound to catch robbers C

R R R 0 .5 0 . 25 0 . 25 Lower bound to catch robbers

C R R R 0 .5 0 . 25

0 . 25 Lower bound to catch robbers R C R R

0 .5 0 . 25 0 . 25 Lower bound to catch robbers R C

R R 0 .5 0 . 25 0 . 25 Lower bound to catch robbers C

R R R 0 .5 0 . 25

0 . 25 Lower bound to catch robbers C R R

0 .5 0 . 25 0 . 25 Lower bound to catch robbers C R

0 .5 0 . 25 0 . 25 Lower bound to catch robbers C R

0 .5 0 . 25 0 . 25 Lower bound to catch robbers R C

R 0 .5 moves per robber 0 . 25 0 . 25 Summary so far

cop and robbers (in graphs) - moves always suffice needed in some graphs What about multiple cops and one robber? cops and robber (in graphs) - Best known upper bound: (Berarducci and Intrigila, 1993)

- Lower bound? Lets start with two cops and one robber ( ) Lets start with two cops and one robber R C

C ( ) one cop not enough Lets start with two cops and one robber

R C C ( ) moves are needed Beyond two cops?

? ( ) How large can be compared to ? ? Beyond two cops?

Aigner and Fromme 1984: 3 for planar graphs Meyniels conjecture (1985): Known upper bound: (Chiniforooshan 2008) Improved to (Frieze, Krivelevich, and Loh 2012; Lu and Peng 2012; Scott and Sudakov 2011) Pralat (2010):

Multiple cops and one robber Note that may hold! Pralat (2010) ( ) Robber chooses side with less than cops

Construction has nodes moves are needed Pralat (2010) Summary so far cop and robbers (in graphs) -

moves always suffice needed in some graphs cops and robber (in graphs) - Best known upper bound: - moves with nodes What about multiple cops and multiple robbers? cops androbbers (in graphs)

- ? Multiple cops and multiple robbers ( )= ( )= ( )=

( )= Are we done? Multiple cops and multiple robbers

( )= ( )= ( )=

( )= Problem: ? Multiple cops and multiple robbers ( )=

C Prevents robbers from crossing Problem: ? ( )=

( )= ( )= How to deal with cop ? Multiple paths do not help much: C

Cop emulates robbers Catches fraction each crossing How to deal with cop ? Multiple paths do not help much: Use a ring C

Better idea: Cop emulates robbers Catches fraction each crossing How to deal with cop ? Multiple paths do not help much: Cop emulates robbers Catches fraction each crossing

Better idea: Use a ring C How to deal with cop ? Multiple paths do not help much: Cop emulates robbers Catches fraction each crossing Better idea: Use a ring

C How to deal with cop ? Multiple paths do not help much: Cop emulates robbers Catches fraction each crossing Better idea: Use a ring C Construction of the ring

3 3

10 Robber placement R R R

Robbers choose side with less cops Robber strategy R R R cops needed to catch robber in gadget graph If , then all other robbers escape down

Robber strategy R R R cops needed to catch robber in gadget graph If , then all other robbers escape down But if ?

Robber strategy R R R Can catch half of the robbers! C cops needed to catch robber in gadget graph

If , then all other robbers escape down But if ? Robber strategy R R C R

Robber strategy R R C R Robber strategy R

R R C Robber strategy R R R

C Cops need moves to catch 2 robbers moves to catch all robbers Summary cop and robbers (in graphs) -

moves always suffice needed in some graphs cops and robber (in graphs) - Best known upper bound: - moves with nodes cops androbbers (in graphs)

- moves with - More than robbers? Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond

Klaus-Tycho Frster, Rijad Nuridini, Jara Uitto, Roger Wattenhofer ETH Zurich Distributed Computing www.disco.ethz.ch

## Recently Viewed Presentations

• Regarding bipolar disorder, mortality estimates are 10-15% for bipolar I, same for bipolar II. Suicidal Behavior in Context of Axis I and II Psychopathologies Anxiety disorders: Mortality estimates are less clear here (fearfulness is an issue), but there is risk,...
• "IS-LM", "Multipliers", and other Basic Relationships Subject: Lecture 7 Author: ROGER BRINNER Last modified by: Roger Brinner Created Date: 3/1/1995 9:52:52 AM Document presentation format: On-screen Show Other titles
• Meteorological Data. Details of Pilotage, Regulations and Port Facilities. Guides to major Port entry. worldwide coverage is provided in 74 volumes BA NOTICE TO MARINERS ADMIRALTY LIST OF LIGHTS AND FOG SIGNALS List of Lights Volume A (NP74) - British...
• Microsoft hosted CAS at BETT, ensuring CAS were able to engage with delegates from the UK and overseas ... Barefoot Computing Project. Help primary school teachers ready themselves for the new computing curriculum . Runs a country-wide series of 950+...
• Wallace Pratt had published an estimate of his own and also a questionnaire he had sent to 25 members of the petroleum industry he regarded as especially well informed. Out of this he got 22 replies. Of all of them,...
• Those labels must be on the external part of a shipped container and must meet the DOT requirements set forth in 49 CFR 172, Subpart E. Labels must be legible, in English, and prominently displayed. Other languages may be displayed...
• A class name is an identifier—a series of characters consisting of letters, digits, underscores (_) and dollar signs (\$) that does not begin with a digit and does not contain spaces. Java is case sensitive—uppercase and lowercase letters are distinct—so...
• H.CarlosIII. H. Canto. blanco. Other,nationalreference. H. C. ruz. Roja. ReferralCenter. H. I. n. fanta. Sof. ia. 6.000Patients(in-andout-patients,emergencies) 7 ...