# 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