lib/examples/Presentations/Beamer_%28Complex%29.lyx

   1 #LyX 2.4 created this file. For more info see https://www.lyx.org/
   2 \lyxformat 600
   3 \begin_document
   4 \begin_header
   5 \save_transient_properties true
   6 \origin /systemlyxdir/examples/Presentations/
   7 \textclass beamer
   8 \begin_preamble
   9 \beamertemplateshadingbackground{red!5}{structure!5}
  10
  11 \usepackage{beamerthemeshadow}
  12 \usepackage{pgfnodes,pgfarrows,pgfheaps}
  13
  14 \beamertemplatetransparentcovereddynamicmedium
  15
  16
  17 \pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
  18 \logo{\pgfuseimage{icsi-logo}}
  19
  20
  21
  22
  23 \newcommand{\Class}[1]{\operatorname{\mathchoice
  24   {\text{\small #1}}
  25   {\text{\small #1}}
  26   {\text{#1}}
  27   {\text{#1}}}}
  28
  29 \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
  30
  31 % This gets defined by beamerbasecolor.sty, but only at the beginning of
  32 % the document
  33 \colorlet{averagebackgroundcolor}{normal text.bg}
  34
  35 \newcommand{\tape}[3]{%
  36   \color{structure!30!averagebackgroundcolor}
  37   \pgfmoveto{\pgfxy(-0.5,0)}
  38   \pgflineto{\pgfxy(-0.6,0.1)}
  39   \pgflineto{\pgfxy(-0.4,0.2)}
  40   \pgflineto{\pgfxy(-0.6,0.3)}
  41   \pgflineto{\pgfxy(-0.4,0.4)}
  42   \pgflineto{\pgfxy(-0.5,0.5)}
  43   \pgflineto{\pgfxy(4,0.5)}
  44   \pgflineto{\pgfxy(4.1,0.4)}
  45   \pgflineto{\pgfxy(3.9,0.3)}
  46   \pgflineto{\pgfxy(4.1,0.2)}
  47   \pgflineto{\pgfxy(3.9,0.1)}
  48   \pgflineto{\pgfxy(4,0)}
  49   \pgfclosepath
  50   \pgffill
  51
  52   \color{structure}
  53   \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
  54   \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
  55
  56   \color{black}
  57   \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
  58 }
  59
  60 \newcommand{\shorttape}[3]{%
  61   \color{structure!30!averagebackgroundcolor}
  62   \pgfmoveto{\pgfxy(-0.5,0)}
  63   \pgflineto{\pgfxy(-0.6,0.1)}
  64   \pgflineto{\pgfxy(-0.4,0.2)}
  65   \pgflineto{\pgfxy(-0.6,0.3)}
  66   \pgflineto{\pgfxy(-0.4,0.4)}
  67   \pgflineto{\pgfxy(-0.5,0.5)}
  68   \pgflineto{\pgfxy(1,0.5)}
  69   \pgflineto{\pgfxy(1.1,0.4)}
  70   \pgflineto{\pgfxy(0.9,0.3)}
  71   \pgflineto{\pgfxy(1.1,0.2)}
  72   \pgflineto{\pgfxy(0.9,0.1)}
  73   \pgflineto{\pgfxy(1,0)}
  74   \pgfclosepath
  75   \pgffill
  76
  77   \color{structure}
  78   \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
  79   \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
  80
  81   \color{black}
  82   \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
  83 }
  84
  85 \pgfdeclareverticalshading{heap1}{\the\paperwidth}%
  86   {color(0pt)=(black); color(1cm)=(structure!65!white)}
  87 \pgfdeclareverticalshading{heap2}{\the\paperwidth}%
  88   {color(0pt)=(black); color(1cm)=(structure!55!white)}
  89 \pgfdeclareverticalshading{heap3}{\the\paperwidth}%
  90   {color(0pt)=(black); color(1cm)=(structure!45!white)}
  91 \pgfdeclareverticalshading{heap4}{\the\paperwidth}%
  92   {color(0pt)=(black); color(1cm)=(structure!35!white)}
  93 \pgfdeclareverticalshading{heap5}{\the\paperwidth}%
  94   {color(0pt)=(black); color(1cm)=(structure!25!white)}
  95 \pgfdeclareverticalshading{heap6}{\the\paperwidth}%
  96   {color(0pt)=(black); color(1cm)=(red!35!white)}
  97
  98 \newcommand{\heap}[5]{%
  99   \begin{pgfscope}
 100     \color{#4}
 101     \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
 102     \pgfclip
 103     \begin{pgfmagnify}{1}{#1}
 104       \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
 105     \end{pgfmagnify}
 106   \end{pgfscope}
 107   %\pgffill
 108
 109   \color{#4}
 110   \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
 111   \pgfstroke
 112
 113   \color{white}
 114   \pgfheaplabel{\pgfxy(0,#1)}{#3}%
 115 }
 116
 117
 118 \newcommand{\langat}[2]{%
 119   \color{black!30!beamerexample}
 120   \pgfsetlinewidth{0.6pt}
 121   \pgfsetendarrow{\pgfarrowdot}
 122   \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
 123   \color{beamerexample}
 124   \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
 125 }
 126
 127 \newcommand{\langatother}[2]{%
 128   \color{black!30!beamerexample}
 129   \pgfsetlinewidth{0.6pt}
 130   \pgfsetendarrow{\pgfarrowdot}
 131   \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
 132   \color{beamerexample}
 133   \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
 134 }
 135
 136
 137 \pgfdeclaremask{knight1-mask}{beamer-knight1-mask} \pgfdeclareimage[height=2cm,mask=knight1-mask]{knight1}{beamer-knight1} \pgfdeclaremask{knight2-mask}{beamer-knight2-mask} \pgfdeclareimage[height=2cm,mask=knight2-mask]{knight2}{beamer-knight2} \pgfdeclaremask{knight3-mask}{beamer-knight3-mask} \pgfdeclareimage[height=2cm,mask=knight3-mask,interpolate=true]{knight3}{beamer-knight3} \pgfdeclaremask{knight4-mask}{beamer-knight4-mask} \pgfdeclareimage[height=2cm,mask=knight4-mask,interpolate=true]{knight4}{beamer-knight4}
 138
 139
 140 \pgfdeclareradialshading{graphnode}
 141   {\pgfpoint{-3pt}{3.6pt}}%
 142   {color(0cm)=(beamerexample!15);
 143     color(2.63pt)=(beamerexample!75);
 144     color(5.26pt)=(beamerexample!70!black);
 145     color(7.6pt)=(beamerexample!50!black);
 146     color(8pt)=(beamerexample!10!averagebackgroundcolor)}
 147
 148 \newcommand{\graphnode}[2]{
 149   \pgfnodecircle{#1}[virtual]{#2}{8pt}
 150   \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
 151 }
 152 \end_preamble
 153 \options notes=show
 154 \use_default_options false
 155 \maintain_unincluded_children no
 156 \language english
 157 \language_package default
 158 \inputencoding utf8
 159 \fontencoding auto
 160 \font_roman "lmodern" "default"
 161 \font_sans "lmss" "default"
 162 \font_typewriter "lmtt" "default"
 163 \font_math "auto" "auto"
 164 \font_default_family default
 165 \use_non_tex_fonts false
 166 \font_sc false
 167 \font_sans_osf false
 168 \font_typewriter_osf false
 169 \font_roman_osf false
 170 \font_sf_scale 100 100
 171 \font_tt_scale 100 100
 172 \use_microtype false
 173 \use_dash_ligatures false
 174 \graphics default
 175 \default_output_format default
 176 \output_sync 0
 177 \bibtex_command default
 178 \index_command default
 179 \paperfontsize default
 180 \spacing single
 181 \use_hyperref false
 182 \papersize default
 183 \use_geometry true
 184 \use_package amsmath 2
 185 \use_package amssymb 2
 186 \use_package cancel 1
 187 \use_package esint 1
 188 \use_package mathdots 1
 189 \use_package mathtools 1
 190 \use_package mhchem 1
 191 \use_package stackrel 1
 192 \use_package stmaryrd 1
 193 \use_package undertilde 1
 194 \cite_engine basic
 195 \cite_engine_type default
 196 \biblio_style plain
 197 \use_bibtopic false
 198 \use_indices false
 199 \paperorientation portrait
 200 \suppress_date false
 201 \justification true
 202 \use_refstyle 0
 203 \use_minted 0
 204 \use_lineno 0
 205 \index Index
 206 \shortcut idx
 207 \color #008000
 208 \end_index
 209 \secnumdepth 2
 210 \tocdepth 2
 211 \paragraph_separation indent
 212 \paragraph_indentation default
 213 \is_math_indent 0
 214 \math_numbering_side default
 215 \quotes_style english
 216 \dynamic_quotes 0
 217 \papercolumns 1
 218 \papersides 1
 219 \paperpagestyle default
 220 \tracking_changes false
 221 \postpone_fragile_content false
 222 \output_changes false
 223 \html_math_output 0
 224 \html_css_as_file 0
 225 \html_be_strict false
 226 \end_header
 227
 228 \begin_body
 229
 230 \begin_layout Title
 231 The Complexity of
 232 \begin_inset Newline newline
 233 \end_inset
 234
 235 Finding Paths in Tournaments
 236 \end_layout
 237
 238 \begin_layout Author
 239 Till Tantau
 240 \end_layout
 241
 242 \begin_layout Institute
 243 International Computer Science Institute
 244 \begin_inset Newline newline
 245 \end_inset
 246
 247 Berkeley, California
 248 \begin_inset Argument 1
 249 status collapsed
 250
 251 \begin_layout Plain Layout
 252 ICSI
 253 \end_layout
 254
 255 \end_inset
 256
 257
 258 \end_layout
 259
 260 \begin_layout Date
 261 January 30th, 2004
 262 \end_layout
 263
 264 \begin_layout Frame
 265 \begin_inset Argument 4
 266 status open
 267
 268 \begin_layout Plain Layout
 269 Outline
 270 \end_layout
 271
 272 \end_inset
 273
 274
 275 \end_layout
 276
 277 \begin_deeper
 278 \begin_layout Standard
 279 \begin_inset CommandInset toc
 280 LatexCommand tableofcontents
 281
 282 \end_inset
 283
 284
 285 \begin_inset ERT
 286 status collapsed
 287
 288 \begin_layout Plain Layout
 289
 290 [pausesections]
 291 \end_layout
 292
 293 \end_inset
 294
 295
 296 \end_layout
 297
 298 \end_deeper
 299 \begin_layout Standard
 300 \begin_inset ERT
 301 status open
 302
 303 \begin_layout Plain Layout
 304
 305 % Show the table of contents at the beginning
 306 \end_layout
 307
 308 \begin_layout Plain Layout
 309
 310 % of every subsection.
 311 \end_layout
 312
 313 \begin_layout Plain Layout
 314
 315
 316 \backslash
 317 AtBeginSubsection[]{%
 318 \end_layout
 319
 320 \begin_layout Plain Layout
 321
 322
 323 \backslash
 324 frame<handout:0>{
 325 \end_layout
 326
 327 \begin_layout Plain Layout
 328
 329
 330 \backslash
 331 frametitle{Outline}
 332 \end_layout
 333
 334 \begin_layout Plain Layout
 335
 336
 337 \backslash
 338 tableofcontents[current,currentsubsection]
 339 \end_layout
 340
 341 \begin_layout Plain Layout
 342
 343   }
 344 \end_layout
 345
 346 \begin_layout Plain Layout
 347
 348 }
 349 \end_layout
 350
 351 \end_inset
 352
 353
 354 \end_layout
 355
 356 \begin_layout Section
 357 Introduction
 358 \end_layout
 359
 360 \begin_layout Subsection
 361 What are Tournaments?
 362 \end_layout
 363
 364 \begin_layout Frame
 365 \begin_inset Argument 4
 366 status open
 367
 368 \begin_layout Plain Layout
 369 Tournaments Consist of Jousts Between Knights
 370 \end_layout
 371
 372 \end_inset
 373
 374
 375 \end_layout
 376
 377 \begin_deeper
 378 \begin_layout Columns
 379
 380 \end_layout
 381
 382 \begin_deeper
 383 \begin_layout Column
 384 5.75cm
 385 \end_layout
 386
 387 \begin_layout Standard
 388 \begin_inset ERT
 389 status collapsed
 390
 391 \begin_layout Plain Layout
 392
 393
 394 \backslash
 395 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
 396 \end_layout
 397
 398 \begin_layout Plain Layout
 399
 400
 401 \backslash
 402 pgfnodebox{A}[virtual]{
 403 \backslash
 404 pgfxy(2,1)}{%
 405 \end_layout
 406
 407 \begin_layout Plain Layout
 408
 409
 410 \backslash
 411 pgfuseimage{knight1}}{2pt}{2pt}
 412 \end_layout
 413
 414 \begin_layout Plain Layout
 415
 416
 417 \backslash
 418 pgfnodebox{B}[virtual]{
 419 \backslash
 420 pgfxy(6,1)}{%
 421 \end_layout
 422
 423 \begin_layout Plain Layout
 424
 425
 426 \backslash
 427 pgfuseimage{knight2}}{2pt}{2pt}
 428 \end_layout
 429
 430 \begin_layout Plain Layout
 431
 432
 433 \backslash
 434 pgfnodebox{C}[virtual]{
 435 \backslash
 436 pgfxy(4,-1)}{%
 437 \end_layout
 438
 439 \begin_layout Plain Layout
 440
 441
 442 \backslash
 443 pgfuseimage{knight3}}{2pt}{2pt}
 444 \end_layout
 445
 446 \begin_layout Plain Layout
 447
 448
 449 \backslash
 450 pgfnodebox{D}[virtual]{
 451 \backslash
 452 pgfxy(4,3)}{%
 453 \end_layout
 454
 455 \begin_layout Plain Layout
 456
 457
 458 \backslash
 459 pgfuseimage{knight4}}{2pt}{2pt}
 460 \end_layout
 461
 462 \begin_layout Plain Layout
 463
 464
 465 \backslash
 466 color{beamerexample}
 467 \end_layout
 468
 469 \begin_layout Plain Layout
 470
 471
 472 \backslash
 473 only<3->{
 474 \backslash
 475 pgfsetendarrow{
 476 \backslash
 477 pgfarrowto}}
 478 \end_layout
 479
 480 \begin_layout Plain Layout
 481
 482
 483 \backslash
 484 only<2->{%
 485 \end_layout
 486
 487 \begin_layout Plain Layout
 488
 489
 490 \backslash
 491 pgfsetlinewidth{0.6pt}
 492 \end_layout
 493
 494 \begin_layout Plain Layout
 495
 496
 497 \backslash
 498 pgfnodeconnline{A}{B}
 499 \end_layout
 500
 501 \begin_layout Plain Layout
 502
 503
 504 \backslash
 505 pgfnodeconnline{A}{C}
 506 \end_layout
 507
 508 \begin_layout Plain Layout
 509
 510
 511 \backslash
 512 pgfnodeconnline{D}{A}
 513 \end_layout
 514
 515 \begin_layout Plain Layout
 516
 517
 518 \backslash
 519 pgfnodeconnline{C}{B}
 520 \end_layout
 521
 522 \begin_layout Plain Layout
 523
 524
 525 \backslash
 526 pgfnodeconnline{B}{D}
 527 \end_layout
 528
 529 \begin_layout Plain Layout
 530
 531
 532 \backslash
 533 pgfnodeconnline{C}{D}
 534 \end_layout
 535
 536 \begin_layout Plain Layout
 537
 538 }
 539 \end_layout
 540
 541 \begin_layout Plain Layout
 542
 543
 544 \backslash
 545 end{pgfpicture}
 546 \end_layout
 547
 548 \end_inset
 549
 550
 551 \end_layout
 552
 553 \begin_layout Column
 554 6cm
 555 \end_layout
 556
 557 \begin_layout Block
 558 \begin_inset Argument 2
 559 status open
 560
 561 \begin_layout Plain Layout
 562 What is a Tournament?
 563 \end_layout
 564
 565 \end_inset
 566
 567
 568 \end_layout
 569
 570 \begin_deeper
 571 \begin_layout Itemize
 572 \begin_inset Argument item:2
 573 status open
 574
 575 \begin_layout Plain Layout
 576
 577 1-
 578 \end_layout
 579
 580 \end_inset
 581
 582 A group of knights.
 583 \end_layout
 584
 585 \begin_layout Itemize
 586 \begin_inset Argument item:2
 587 status open
 588
 589 \begin_layout Plain Layout
 590
 591 2-
 592 \end_layout
 593
 594 \end_inset
 595
 596 Every pair has a joust.
 597 \end_layout
 598
 599 \begin_layout Itemize
 600 \begin_inset Argument item:2
 601 status open
 602
 603 \begin_layout Plain Layout
 604
 605 3-
 606 \end_layout
 607
 608 \end_inset
 609
 610 In every joust one knight wins.
 611 \end_layout
 612
 613 \end_deeper
 614 \end_deeper
 615 \end_deeper
 616 \begin_layout Standard
 617 \begin_inset Separator plain
 618 \end_inset
 619
 620
 621 \end_layout
 622
 623 \begin_layout Frame
 624 \begin_inset Argument 4
 625 status open
 626
 627 \begin_layout Plain Layout
 628 Tournaments are Complete Directed Graphs
 629 \end_layout
 630
 631 \end_inset
 632
 633
 634 \end_layout
 635
 636 \begin_deeper
 637 \begin_layout Columns
 638
 639 \end_layout
 640
 641 \begin_deeper
 642 \begin_layout Column
 643 5cm
 644 \end_layout
 645
 646 \begin_layout Standard
 647 \begin_inset ERT
 648 status collapsed
 649
 650 \begin_layout Plain Layout
 651
 652
 653 \backslash
 654 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
 655 \end_layout
 656
 657 \begin_layout Plain Layout
 658
 659
 660 \backslash
 661 color{beamerexample}
 662 \end_layout
 663
 664 \begin_layout Plain Layout
 665
 666
 667 \backslash
 668 pgfsetlinewidth{0.6pt}
 669 \end_layout
 670
 671 \begin_layout Plain Layout
 672
 673
 674 \backslash
 675 graphnode{A}{
 676 \backslash
 677 pgfxy(2.5,1)}
 678 \end_layout
 679
 680 \begin_layout Plain Layout
 681
 682
 683 \backslash
 684 graphnode{B}{
 685 \backslash
 686 pgfxy(5.5,1)}
 687 \end_layout
 688
 689 \begin_layout Plain Layout
 690
 691
 692 \backslash
 693 graphnode{C}{
 694 \backslash
 695 pgfxy(4,-0.5)}
 696 \end_layout
 697
 698 \begin_layout Plain Layout
 699
 700
 701 \backslash
 702 graphnode{D}{
 703 \backslash
 704 pgfxy(4,2.5)}
 705 \end_layout
 706
 707 \begin_layout Plain Layout
 708
 709
 710 \backslash
 711 color{white}
 712 \end_layout
 713
 714 \begin_layout Plain Layout
 715
 716
 717 \backslash
 718 pgfputat{
 719 \backslash
 720 pgfnodecenter{A}}{
 721 \backslash
 722 pgfbox[center,center]{$v_2$}}
 723 \end_layout
 724
 725 \begin_layout Plain Layout
 726
 727
 728 \backslash
 729 pgfputat{
 730 \backslash
 731 pgfnodecenter{B}}{
 732 \backslash
 733 pgfbox[center,center]{$v_3$}}
 734 \end_layout
 735
 736 \begin_layout Plain Layout
 737
 738
 739 \backslash
 740 pgfputat{
 741 \backslash
 742 pgfnodecenter{C}}{
 743 \backslash
 744 pgfbox[center,center]{$v_4$}}
 745 \end_layout
 746
 747 \begin_layout Plain Layout
 748
 749
 750 \backslash
 751 pgfputat{
 752 \backslash
 753 pgfnodecenter{D}}{
 754 \backslash
 755 pgfbox[center,center]{$v_1$}}
 756 \end_layout
 757
 758 \begin_layout Plain Layout
 759
 760
 761 \backslash
 762 color{beamerexample}
 763 \end_layout
 764
 765 \begin_layout Plain Layout
 766
 767
 768 \backslash
 769 pgfsetendarrow{
 770 \backslash
 771 pgfarrowto}
 772 \end_layout
 773
 774 \begin_layout Plain Layout
 775
 776
 777 \backslash
 778 pgfnodesetsepstart{2pt}
 779 \end_layout
 780
 781 \begin_layout Plain Layout
 782
 783
 784 \backslash
 785 pgfnodesetsepend{4pt}
 786 \end_layout
 787
 788 \begin_layout Plain Layout
 789
 790
 791 \backslash
 792 pgfnodeconnline{A}{B}
 793 \end_layout
 794
 795 \begin_layout Plain Layout
 796
 797
 798 \backslash
 799 pgfnodeconnline{A}{C}
 800 \end_layout
 801
 802 \begin_layout Plain Layout
 803
 804
 805 \backslash
 806 pgfnodeconnline{D}{A}
 807 \end_layout
 808
 809 \begin_layout Plain Layout
 810
 811
 812 \backslash
 813 pgfnodeconnline{C}{B}
 814 \end_layout
 815
 816 \begin_layout Plain Layout
 817
 818
 819 \backslash
 820 pgfnodeconnline{B}{D}
 821 \end_layout
 822
 823 \begin_layout Plain Layout
 824
 825
 826 \backslash
 827 pgfnodeconnline{D}{C}
 828 \end_layout
 829
 830 \begin_layout Plain Layout
 831
 832
 833 \backslash
 834 end{pgfpicture}
 835 \end_layout
 836
 837 \end_inset
 838
 839
 840 \end_layout
 841
 842 \begin_layout Column
 843 6cm
 844 \end_layout
 845
 846 \begin_layout Definition
 847 \begin_inset Argument 1
 848 status collapsed
 849
 850 \begin_layout Plain Layout
 851
 852 2-
 853 \end_layout
 854
 855 \end_inset
 856
 857 A
 858 \color none
 859
 860 \color red
 861 tournament
 862 \color none
 863
 864 \color inherit
 865 is a
 866 \end_layout
 867
 868 \begin_deeper
 869 \begin_layout Enumerate
 870 directed graphs,
 871 \end_layout
 872
 873 \begin_layout Enumerate
 874 with exactly one edge between
 875 \begin_inset Newline newline
 876 \end_inset
 877
 878 any two different vertices.
 879 \end_layout
 880
 881 \end_deeper
 882 \end_deeper
 883 \end_deeper
 884 \begin_layout Standard
 885 \begin_inset Separator plain
 886 \end_inset
 887
 888
 889 \end_layout
 890
 891 \begin_layout Frame
 892 \begin_inset Argument 2
 893 status collapsed
 894
 895 \begin_layout Plain Layout
 896
 897 +
 898 \end_layout
 899
 900 \end_inset
 901
 902
 903 \begin_inset Argument 4
 904 status open
 905
 906 \begin_layout Plain Layout
 907 Tournaments Arise Naturally in Different Situations
 908 \end_layout
 909
 910 \end_inset
 911
 912
 913 \end_layout
 914
 915 \begin_deeper
 916 \begin_layout ExampleBlock
 917 \begin_inset Argument 2
 918 status collapsed
 919
 920 \begin_layout Plain Layout
 921 Applications in Ordering Theory
 922 \end_layout
 923
 924 \end_inset
 925
 926
 927 \end_layout
 928
 929 \begin_deeper
 930 \begin_layout Standard
 931 Elements in a set need to be sorted.
 932
 933 \begin_inset Newline newline
 934 \end_inset
 935
 936 The comparison relation may be cyclic, however.
 937 \end_layout
 938
 939 \end_deeper
 940 \begin_layout Standard
 941 \begin_inset Separator plain
 942 \end_inset
 943
 944
 945 \end_layout
 946
 947 \begin_layout ExampleBlock
 948 \begin_inset Argument 2
 949 status collapsed
 950
 951 \begin_layout Plain Layout
 952 Applications in Sociology
 953 \end_layout
 954
 955 \end_inset
 956
 957
 958 \end_layout
 959
 960 \begin_deeper
 961 \begin_layout Standard
 962 Several candidates apply for a position.
 963 \begin_inset Newline newline
 964 \end_inset
 965
 966 Reviewers decide for any two candidates whom they prefer.
 967
 968 \end_layout
 969
 970 \end_deeper
 971 \begin_layout Standard
 972 \begin_inset Separator plain
 973 \end_inset
 974
 975
 976 \end_layout
 977
 978 \begin_layout ExampleBlock
 979 \begin_inset Argument 2
 980 status collapsed
 981
 982 \begin_layout Plain Layout
 983 Applications in Structural Complexity Theory
 984 \end_layout
 985
 986 \end_inset
 987
 988
 989 \end_layout
 990
 991 \begin_deeper
 992 \begin_layout Standard
 993 A language
 994 \begin_inset Formula $L$
 995 \end_inset
 996
 997  is given and a selector function
 998 \begin_inset Formula $f$
 999 \end_inset
1000
1001 .
1002 \begin_inset Newline newline
1003 \end_inset
1004
1005 It chooses from any two words the one more likely to be in
1006 \begin_inset Formula $f$
1007 \end_inset
1008
1009 .
1010 \end_layout
1011
1012 \end_deeper
1013 \end_deeper
1014 \begin_layout Subsection
1015 What Does ``Finding Paths'' Mean?
1016 \end_layout
1017
1018 \begin_layout Frame
1019 \begin_inset Argument 4
1020 status open
1021
1022 \begin_layout Plain Layout
1023 ``Finding Paths'' is Ambiguous
1024 \end_layout
1025
1026 \end_inset
1027
1028
1029 \end_layout
1030
1031 \begin_deeper
1032 \begin_layout Block
1033 \begin_inset Argument 2
1034 status open
1035
1036 \begin_layout Plain Layout
1037 Input for
1038 \begin_inset Flex Only
1039 status open
1040
1041 \begin_layout Plain Layout
1042 \begin_inset Argument 1
1043 status open
1044
1045 \begin_layout Plain Layout
1046
1047 1
1048 \end_layout
1049
1050 \end_inset
1051
1052 Path Finding Problems
1053 \end_layout
1054
1055 \end_inset
1056
1057
1058 \begin_inset Flex Only
1059 status open
1060
1061 \begin_layout Plain Layout
1062 \begin_inset Argument 1
1063 status open
1064
1065 \begin_layout Plain Layout
1066
1067 2-3
1068 \end_layout
1069
1070 \end_inset
1071
1072
1073 \begin_inset Formula $\Lang{reach}$
1074 \end_inset
1075
1076
1077 \end_layout
1078
1079 \end_inset
1080
1081
1082 \begin_inset Flex Only
1083 status open
1084
1085 \begin_layout Plain Layout
1086 \begin_inset Argument 1
1087 status open
1088
1089 \begin_layout Plain Layout
1090
1091 4-5
1092 \end_layout
1093
1094 \end_inset
1095
1096 the Construction Problem
1097 \end_layout
1098
1099 \end_inset
1100
1101
1102 \begin_inset Flex Only
1103 status open
1104
1105 \begin_layout Plain Layout
1106 \begin_inset Argument 1
1107 status open
1108
1109 \begin_layout Plain Layout
1110
1111 6-7
1112 \end_layout
1113
1114 \end_inset
1115
1116 the Optimization Problem
1117 \end_layout
1118
1119 \end_inset
1120
1121
1122 \begin_inset Flex Only
1123 status open
1124
1125 \begin_layout Plain Layout
1126 \begin_inset Argument 1
1127 status open
1128
1129 \begin_layout Plain Layout
1130
1131 8-9
1132 \end_layout
1133
1134 \end_inset
1135
1136
1137 \begin_inset Formula $\Lang{distance}$
1138 \end_inset
1139
1140
1141 \end_layout
1142
1143 \end_inset
1144
1145
1146 \begin_inset Flex Only
1147 status open
1148
1149 \begin_layout Plain Layout
1150 \begin_inset Argument 1
1151 status open
1152
1153 \begin_layout Plain Layout
1154
1155 10-
1156 \end_layout
1157
1158 \end_inset
1159
1160 the Approximation Problem
1161 \end_layout
1162
1163 \end_inset
1164
1165
1166 \end_layout
1167
1168 \end_inset
1169
1170
1171 \end_layout
1172
1173 \begin_deeper
1174 \begin_layout Itemize
1175 A
1176 \color none
1177
1178 \color red
1179 graph
1180 \color none
1181
1182 \color inherit
1183
1184 \begin_inset Formula $G=(V,E)$
1185 \end_inset
1186
1187 , a
1188 \color none
1189
1190 \color red
1191 source
1192 \color none
1193
1194 \color inherit
1195
1196 \begin_inset Formula $s\in V$
1197 \end_inset
1198
1199  and a
1200 \color none
1201
1202 \color red
1203 target
1204 \color none
1205
1206 \color inherit
1207
1208 \begin_inset Formula $t\in V$
1209 \end_inset
1210
1211 .
1212 \end_layout
1213
1214 \begin_layout Itemize
1215 \begin_inset Argument item:2
1216 status open
1217
1218 \begin_layout Plain Layout
1219
1220 only@-9| visible@8-
1221 \end_layout
1222
1223 \end_inset
1224
1225 A
1226 \color none
1227
1228 \color red
1229 maximum distance
1230 \color inherit
1231
1232 \begin_inset space ~
1233 \end_inset
1234
1235
1236 \begin_inset Formula $d$
1237 \end_inset
1238
1239 .
1240 \begin_inset ERT
1241 status collapsed
1242
1243 \begin_layout Plain Layout
1244
1245
1246 \backslash
1247 phantom{p}
1248 \end_layout
1249
1250 \end_inset
1251
1252
1253 \end_layout
1254
1255 \begin_layout Itemize
1256 \begin_inset Argument item:2
1257 status open
1258
1259 \begin_layout Plain Layout
1260
1261 only@10-
1262 \end_layout
1263
1264 \end_inset
1265
1266 An
1267 \color none
1268
1269 \color red
1270 approximation ratio
1271 \color none
1272
1273 \color inherit
1274
1275 \begin_inset Formula $r>1$
1276 \end_inset
1277
1278 .
1279 \end_layout
1280
1281 \end_deeper
1282 \begin_layout Standard
1283 \begin_inset ERT
1284 status collapsed
1285
1286 \begin_layout Plain Layout
1287
1288
1289 \backslash
1290 nointerlineskip
1291 \end_layout
1292
1293 \end_inset
1294
1295
1296 \end_layout
1297
1298 \begin_layout Overprint
1299 \begin_inset Argument item:1
1300 status open
1301
1302 \begin_layout Plain Layout
1303
1304 1,3,5,7,9,11-12
1305 \end_layout
1306
1307 \end_inset
1308
1309
1310 \end_layout
1311
1312 \begin_deeper
1313 \begin_layout Columns
1314 \begin_inset Argument 1
1315 status open
1316
1317 \begin_layout Plain Layout
1318 t,onlytextwidth
1319 \end_layout
1320
1321 \end_inset
1322
1323
1324 \end_layout
1325
1326 \begin_deeper
1327 \begin_layout Standard
1328 \begin_inset Flex Alternative
1329 status open
1330
1331 \begin_layout Plain Layout
1332 \begin_inset Argument 1
1333 status open
1334
1335 \begin_layout Plain Layout
1336
1337 1-2
1338 \end_layout
1339
1340 \end_inset
1341
1342
1343 \begin_inset Argument 2
1344 status open
1345
1346 \begin_layout Plain Layout
1347 \begin_inset ERT
1348 status open
1349
1350 \begin_layout Plain Layout
1351
1352
1353 \backslash
1354 column{
1355 \backslash
1356 textwidth}
1357 \end_layout
1358
1359 \end_inset
1360
1361
1362 \end_layout
1363
1364 \end_inset
1365
1366
1367 \begin_inset ERT
1368 status open
1369
1370 \begin_layout Plain Layout
1371
1372
1373 \backslash
1374 column{5cm}
1375 \end_layout
1376
1377 \end_inset
1378
1379
1380 \end_layout
1381
1382 \end_inset
1383
1384
1385 \end_layout
1386
1387 \begin_layout ExampleBlock
1388 \begin_inset Argument 2
1389 status collapsed
1390
1391 \begin_layout Plain Layout
1392 Example Input
1393 \end_layout
1394
1395 \end_inset
1396
1397
1398 \end_layout
1399
1400 \begin_deeper
1401 \begin_layout Standard
1402 \begin_inset ERT
1403 status collapsed
1404
1405 \begin_layout Plain Layout
1406
1407
1408 \backslash
1409 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1410 \end_layout
1411
1412 \begin_layout Plain Layout
1413
1414 \end_layout
1415
1416 \begin_layout Plain Layout
1417
1418
1419 \backslash
1420 color{beamerexample}
1421 \end_layout
1422
1423 \begin_layout Plain Layout
1424
1425 \end_layout
1426
1427 \begin_layout Plain Layout
1428
1429
1430 \backslash
1431 pgfsetlinewidth{0.6pt}
1432 \end_layout
1433
1434 \begin_layout Plain Layout
1435
1436 \end_layout
1437
1438 \begin_layout Plain Layout
1439
1440
1441 \backslash
1442 graphnode{A}{
1443 \backslash
1444 pgfxy(3,1)}
1445 \end_layout
1446
1447 \begin_layout Plain Layout
1448
1449 \end_layout
1450
1451 \begin_layout Plain Layout
1452
1453
1454 \backslash
1455 graphnode{B}{
1456 \backslash
1457 pgfxy(5,1)}
1458 \end_layout
1459
1460 \begin_layout Plain Layout
1461
1462 \end_layout
1463
1464 \begin_layout Plain Layout
1465
1466
1467 \backslash
1468 graphnode{C}{
1469 \backslash
1470 pgfxy(4,0)}
1471 \end_layout
1472
1473 \begin_layout Plain Layout
1474
1475 \end_layout
1476
1477 \begin_layout Plain Layout
1478
1479
1480 \backslash
1481 graphnode{D}{
1482 \backslash
1483 pgfxy(4,2)}
1484 \end_layout
1485
1486 \begin_layout Plain Layout
1487
1488 \end_layout
1489
1490 \begin_layout Plain Layout
1491
1492 \end_layout
1493
1494 \begin_layout Plain Layout
1495
1496 \end_layout
1497
1498 \begin_layout Plain Layout
1499
1500
1501 \backslash
1502 color{white}
1503 \end_layout
1504
1505 \begin_layout Plain Layout
1506
1507 \end_layout
1508
1509 \begin_layout Plain Layout
1510
1511
1512 \backslash
1513 pgfputat{
1514 \backslash
1515 pgfnodecenter{B}}{
1516 \backslash
1517 pgfbox[center,center]{$t$}}
1518 \end_layout
1519
1520 \begin_layout Plain Layout
1521
1522 \end_layout
1523
1524 \begin_layout Plain Layout
1525
1526
1527 \backslash
1528 pgfputat{
1529 \backslash
1530 pgfnodecenter{D}}{
1531 \backslash
1532 pgfbox[center,center]{$s$}}
1533 \end_layout
1534
1535 \begin_layout Plain Layout
1536
1537 \end_layout
1538
1539 \begin_layout Plain Layout
1540
1541 \end_layout
1542
1543 \begin_layout Plain Layout
1544
1545 \end_layout
1546
1547 \begin_layout Plain Layout
1548
1549
1550 \backslash
1551 color{beamerexample}
1552 \end_layout
1553
1554 \begin_layout Plain Layout
1555
1556 \end_layout
1557
1558 \begin_layout Plain Layout
1559
1560
1561 \backslash
1562 pgfsetendarrow{
1563 \backslash
1564 pgfarrowto}
1565 \end_layout
1566
1567 \begin_layout Plain Layout
1568
1569 \end_layout
1570
1571 \begin_layout Plain Layout
1572
1573
1574 \backslash
1575 pgfnodesetsepstart{2pt}
1576 \end_layout
1577
1578 \begin_layout Plain Layout
1579
1580 \end_layout
1581
1582 \begin_layout Plain Layout
1583
1584
1585 \backslash
1586 pgfnodesetsepend{4pt}
1587 \end_layout
1588
1589 \begin_layout Plain Layout
1590
1591 \end_layout
1592
1593 \begin_layout Plain Layout
1594
1595
1596 \backslash
1597 pgfnodeconnline{A}{B}
1598 \end_layout
1599
1600 \begin_layout Plain Layout
1601
1602 \end_layout
1603
1604 \begin_layout Plain Layout
1605
1606
1607 \backslash
1608 pgfnodeconnline{A}{C}
1609 \end_layout
1610
1611 \begin_layout Plain Layout
1612
1613 \end_layout
1614
1615 \begin_layout Plain Layout
1616
1617
1618 \backslash
1619 pgfnodeconnline{D}{A}
1620 \end_layout
1621
1622 \begin_layout Plain Layout
1623
1624 \end_layout
1625
1626 \begin_layout Plain Layout
1627
1628
1629 \backslash
1630 pgfnodeconnline{C}{B}
1631 \end_layout
1632
1633 \begin_layout Plain Layout
1634
1635 \end_layout
1636
1637 \begin_layout Plain Layout
1638
1639
1640 \backslash
1641 pgfnodeconnline{B}{D}
1642 \end_layout
1643
1644 \begin_layout Plain Layout
1645
1646 \end_layout
1647
1648 \begin_layout Plain Layout
1649
1650
1651 \backslash
1652 pgfnodeconnline{D}{C}
1653 \end_layout
1654
1655 \begin_layout Plain Layout
1656
1657 \end_layout
1658
1659 \begin_layout Plain Layout
1660
1661 \end_layout
1662
1663 \begin_layout Plain Layout
1664
1665 \end_layout
1666
1667 \begin_layout Plain Layout
1668
1669
1670 \backslash
1671 only<9> {
1672 \backslash
1673 pgfputat{
1674 \backslash
1675 pgfxy(5.3,1)}{
1676 \backslash
1677 pgfbox[left,center]{, $d=2$}}}
1678 \end_layout
1679
1680 \begin_layout Plain Layout
1681
1682 \end_layout
1683
1684 \begin_layout Plain Layout
1685
1686
1687 \backslash
1688 only<11>{
1689 \backslash
1690 pgfputat{
1691 \backslash
1692 pgfxy(5.3,1)}{
1693 \backslash
1694 pgfbox[left,center]{, $r=1.5$}}}
1695 \end_layout
1696
1697 \begin_layout Plain Layout
1698
1699 \end_layout
1700
1701 \begin_layout Plain Layout
1702
1703
1704 \backslash
1705 only<12>{
1706 \backslash
1707 pgfputat{
1708 \backslash
1709 pgfxy(5.3,1)}{
1710 \backslash
1711 pgfbox[left,center]{, $r=1.25$}}}
1712 \end_layout
1713
1714 \begin_layout Plain Layout
1715
1716 \end_layout
1717
1718 \begin_layout Plain Layout
1719
1720
1721 \backslash
1722 end{pgfpicture}
1723 \end_layout
1724
1725 \end_inset
1726
1727
1728 \end_layout
1729
1730 \end_deeper
1731 \begin_layout Standard
1732 \begin_inset Flex Only
1733 status open
1734
1735 \begin_layout Plain Layout
1736 \begin_inset Argument 1
1737 status open
1738
1739 \begin_layout Plain Layout
1740
1741 3-
1742 \end_layout
1743
1744 \end_inset
1745
1746
1747 \begin_inset ERT
1748 status open
1749
1750 \begin_layout Plain Layout
1751
1752
1753 \backslash
1754 column{5cm}
1755 \end_layout
1756
1757 \end_inset
1758
1759
1760 \end_layout
1761
1762 \end_inset
1763
1764
1765 \end_layout
1766
1767 \begin_layout ExampleBlock
1768 \begin_inset Argument 1
1769 status collapsed
1770
1771 \begin_layout Plain Layout
1772
1773 only@3-
1774 \end_layout
1775
1776 \end_inset
1777
1778
1779 \begin_inset Argument 2
1780 status collapsed
1781
1782 \begin_layout Plain Layout
1783 Example Output
1784 \end_layout
1785
1786 \end_inset
1787
1788
1789 \end_layout
1790
1791 \begin_deeper
1792 \begin_layout Standard
1793 \begin_inset ERT
1794 status collapsed
1795
1796 \begin_layout Plain Layout
1797
1798
1799 \backslash
1800 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1801 \end_layout
1802
1803 \begin_layout Plain Layout
1804
1805
1806 \backslash
1807 only<5-8,10->{%
1808 \end_layout
1809
1810 \begin_layout Plain Layout
1811
1812
1813 \backslash
1814 color{beamerexample}
1815 \end_layout
1816
1817 \begin_layout Plain Layout
1818
1819
1820 \backslash
1821 pgfsetlinewidth{0.6pt}
1822 \end_layout
1823
1824 \begin_layout Plain Layout
1825
1826
1827 \backslash
1828 graphnode{A}{
1829 \backslash
1830 pgfxy(3,1)}
1831 \end_layout
1832
1833 \begin_layout Plain Layout
1834
1835
1836 \backslash
1837 graphnode{B}{
1838 \backslash
1839 pgfxy(5,1)}
1840 \end_layout
1841
1842 \begin_layout Plain Layout
1843
1844
1845 \backslash
1846 graphnode{C}{
1847 \backslash
1848 pgfxy(4,0)}
1849 \end_layout
1850
1851 \begin_layout Plain Layout
1852
1853
1854 \backslash
1855 graphnode{D}{
1856 \backslash
1857 pgfxy(4,2)}
1858 \end_layout
1859
1860 \begin_layout Plain Layout
1861
1862
1863 \backslash
1864 color{white}
1865 \end_layout
1866
1867 \begin_layout Plain Layout
1868
1869
1870 \backslash
1871 pgfputat{
1872 \backslash
1873 pgfnodecenter{B}}{
1874 \backslash
1875 pgfbox[center,center]{$t$}}
1876 \end_layout
1877
1878 \begin_layout Plain Layout
1879
1880
1881 \backslash
1882 pgfputat{
1883 \backslash
1884 pgfnodecenter{D}}{
1885 \backslash
1886 pgfbox[center,center]{$s$}}
1887 \end_layout
1888
1889 \begin_layout Plain Layout
1890
1891
1892 \backslash
1893 color{beamerexample}
1894 \end_layout
1895
1896 \begin_layout Plain Layout
1897
1898
1899 \backslash
1900 pgfsetendarrow{
1901 \backslash
1902 pgfarrowto}
1903 \end_layout
1904
1905 \begin_layout Plain Layout
1906
1907
1908 \backslash
1909 pgfnodesetsepstart{2pt}
1910 \end_layout
1911
1912 \begin_layout Plain Layout
1913
1914
1915 \backslash
1916 pgfnodesetsepend{4pt}
1917 \end_layout
1918
1919 \begin_layout Plain Layout
1920
1921
1922 \backslash
1923 alert<7,12>{
1924 \backslash
1925 pgfnodeconnline{A}{B}}
1926 \end_layout
1927
1928 \begin_layout Plain Layout
1929
1930
1931 \backslash
1932 alert<5,11>{
1933 \backslash
1934 pgfnodeconnline{A}{C}}
1935 \end_layout
1936
1937 \begin_layout Plain Layout
1938
1939
1940 \backslash
1941 alert<5,7,11-12>{
1942 \backslash
1943 pgfnodeconnline{D}{A}}
1944 \end_layout
1945
1946 \begin_layout Plain Layout
1947
1948
1949 \backslash
1950 alert<5,11>{
1951 \backslash
1952 pgfnodeconnline{C}{B}}
1953 \end_layout
1954
1955 \begin_layout Plain Layout
1956
1957
1958 \backslash
1959 pgfnodeconnline{B}{D}
1960 \end_layout
1961
1962 \begin_layout Plain Layout
1963
1964
1965 \backslash
1966 pgfnodeconnline{D}{C}
1967 \end_layout
1968
1969 \begin_layout Plain Layout
1970
1971 }
1972 \end_layout
1973
1974 \begin_layout Plain Layout
1975
1976
1977 \backslash
1978 only<3,9>{
1979 \backslash
1980 pgfputat{
1981 \backslash
1982 pgfxy(2.75,1)}{
1983 \backslash
1984 pgfbox[left,center]{
1985 \backslash
1986 alert{``Yes''}}}}
1987 \end_layout
1988
1989 \begin_layout Plain Layout
1990
1991
1992 \backslash
1993 end{pgfpicture}
1994 \end_layout
1995
1996 \end_inset
1997
1998
1999 \end_layout
2000
2001 \end_deeper
2002 \end_deeper
2003 \end_deeper
2004 \begin_layout Overprint
2005 \begin_inset Argument item:1
2006 status open
2007
2008 \begin_layout Plain Layout
2009
2010 2,4,6,8,10
2011 \end_layout
2012
2013 \end_inset
2014
2015
2016 \end_layout
2017
2018 \begin_deeper
2019 \begin_layout Block
2020 \begin_inset Argument 2
2021 status collapsed
2022
2023 \begin_layout Plain Layout
2024 Variants of Path Finding Problems
2025 \end_layout
2026
2027 \end_inset
2028
2029
2030 \end_layout
2031
2032 \begin_deeper
2033 \begin_layout Description
2034 \begin_inset Argument item:1
2035 status open
2036
2037 \begin_layout Plain Layout
2038
2039 2-
2040 \end_layout
2041
2042 \end_inset
2043
2044 Reachability
2045 \begin_inset space ~
2046 \end_inset
2047
2048 Problem: Is there a path from
2049 \begin_inset Formula $s$
2050 \end_inset
2051
2052  to
2053 \begin_inset space ~
2054 \end_inset
2055
2056
2057 \begin_inset Formula $t$
2058 \end_inset
2059
2060 ?
2061 \begin_inset Argument 2
2062 status open
2063
2064 \begin_layout Plain Layout
2065 Approximation Problem:
2066 \end_layout
2067
2068 \end_inset
2069
2070
2071 \end_layout
2072
2073 \begin_layout Description
2074 \begin_inset Argument item:1
2075 status open
2076
2077 \begin_layout Plain Layout
2078
2079 4-
2080 \end_layout
2081
2082 \end_inset
2083
2084 Construction
2085 \begin_inset space ~
2086 \end_inset
2087
2088 Problem: Construct a path from
2089 \begin_inset Formula $s$
2090 \end_inset
2091
2092  to
2093 \begin_inset space ~
2094 \end_inset
2095
2096
2097 \begin_inset Formula $t$
2098 \end_inset
2099
2100 ?
2101 \end_layout
2102
2103 \begin_layout Description
2104 \begin_inset Argument item:1
2105 status open
2106
2107 \begin_layout Plain Layout
2108
2109 6-
2110 \end_layout
2111
2112 \end_inset
2113
2114 Optimization
2115 \begin_inset space ~
2116 \end_inset
2117
2118 Problem: Construct a shortest path from
2119 \begin_inset Formula $s$
2120 \end_inset
2121
2122  to
2123 \begin_inset space ~
2124 \end_inset
2125
2126
2127 \begin_inset Formula $t$
2128 \end_inset
2129
2130 .
2131 \end_layout
2132
2133 \begin_layout Description
2134 \begin_inset Argument item:1
2135 status open
2136
2137 \begin_layout Plain Layout
2138
2139 8-
2140 \end_layout
2141
2142 \end_inset
2143
2144 Distance
2145 \begin_inset space ~
2146 \end_inset
2147
2148 Problem: Is the distance of
2149 \begin_inset Formula $s$
2150 \end_inset
2151
2152  and
2153 \begin_inset space ~
2154 \end_inset
2155
2156
2157 \begin_inset Formula $t$
2158 \end_inset
2159
2160  at most
2161 \begin_inset space ~
2162 \end_inset
2163
2164
2165 \begin_inset Formula $d$
2166 \end_inset
2167
2168 ?
2169 \end_layout
2170
2171 \begin_layout Description
2172 \begin_inset Argument item:1
2173 status open
2174
2175 \begin_layout Plain Layout
2176
2177 10-
2178 \end_layout
2179
2180 \end_inset
2181
2182 Approximation
2183 \begin_inset space ~
2184 \end_inset
2185
2186 Problem: Construct a path from
2187 \begin_inset Formula $s$
2188 \end_inset
2189
2190  to
2191 \begin_inset space ~
2192 \end_inset
2193
2194
2195 \begin_inset Formula $t$
2196 \end_inset
2197
2198  of length
2199 \begin_inset Newline newline
2200 \end_inset
2201
2202 approximately their distance.
2203 \end_layout
2204
2205 \end_deeper
2206 \end_deeper
2207 \end_deeper
2208 \begin_layout Section
2209 Review
2210 \end_layout
2211
2212 \begin_layout Subsection
2213 Standard Complexity Classes
2214 \end_layout
2215
2216 \begin_layout Standard
2217 \begin_inset ERT
2218 status collapsed
2219
2220 \begin_layout Plain Layout
2221
2222
2223 \backslash
2224 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2225 \backslash
2226 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2227 -g4}
2228 \end_layout
2229
2230 \end_inset
2231
2232
2233 \end_layout
2234
2235 \begin_layout Frame
2236 \begin_inset Argument 4
2237 status open
2238
2239 \begin_layout Plain Layout
2240 The Classes L and NL are Defined via
2241 \begin_inset Newline newline
2242 \end_inset
2243
2244 Logspace Turing Machines
2245 \end_layout
2246
2247 \end_inset
2248
2249
2250 \end_layout
2251
2252 \begin_deeper
2253 \begin_layout Standard
2254 \begin_inset ERT
2255 status collapsed
2256
2257 \begin_layout Plain Layout
2258
2259
2260 \backslash
2261 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2262 \end_layout
2263
2264 \begin_layout Plain Layout
2265
2266
2267 \backslash
2268 pgfputat{
2269 \backslash
2270 pgfxy(0,4)}{%
2271 \end_layout
2272
2273 \begin_layout Plain Layout
2274
2275
2276 \backslash
2277 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2278 \end_layout
2279
2280 \begin_layout Plain Layout
2281
2282
2283 \backslash
2284 uncover<2->{%
2285 \end_layout
2286
2287 \begin_layout Plain Layout
2288
2289
2290 \backslash
2291 pgfputat{
2292 \backslash
2293 pgfxy(0,0.5)}{%
2294 \end_layout
2295
2296 \begin_layout Plain Layout
2297
2298
2299 \backslash
2300 tape{}{output tape (write only)}{10690836937182}}
2301 \end_layout
2302
2303 \begin_layout Plain Layout
2304
2305 }
2306 \end_layout
2307
2308 \begin_layout Plain Layout
2309
2310
2311 \backslash
2312 uncover<3->{%
2313 \end_layout
2314
2315 \begin_layout Plain Layout
2316
2317
2318 \backslash
2319 pgfputat{
2320 \backslash
2321 pgfxy(7,2)}{%
2322 \end_layout
2323
2324 \begin_layout Plain Layout
2325
2326
2327 \backslash
2328 shorttape{work tape (read/write), $O(
2329 \backslash
2330 log n)$ symbols}{}{42}}
2331 \end_layout
2332
2333 \begin_layout Plain Layout
2334
2335
2336 \backslash
2337 pgfputat{
2338 \backslash
2339 pgfxy(1.75,2.5)}{%
2340 \end_layout
2341
2342 \begin_layout Plain Layout
2343
2344
2345 \backslash
2346 pgfbox[center,center]{
2347 \backslash
2348 pgfuseimage{computer}}}
2349 \end_layout
2350
2351 \begin_layout Plain Layout
2352
2353 }
2354 \end_layout
2355
2356 \begin_layout Plain Layout
2357
2358
2359 \backslash
2360 pgfsetlinewidth{0.6pt}
2361 \end_layout
2362
2363 \begin_layout Plain Layout
2364
2365
2366 \backslash
2367 color{structure}
2368 \end_layout
2369
2370 \begin_layout Plain Layout
2371
2372
2373 \backslash
2374 pgfsetendarrow{
2375 \backslash
2376 pgfarrowto}
2377 \end_layout
2378
2379 \begin_layout Plain Layout
2380
2381
2382 \backslash
2383 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2384 \end_layout
2385
2386 \begin_layout Plain Layout
2387
2388
2389 \backslash
2390 uncover<2->{
2391 \backslash
2392 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2393 \end_layout
2394
2395 \begin_layout Plain Layout
2396
2397
2398 \backslash
2399 uncover<3->{
2400 \backslash
2401 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2402 \end_layout
2403
2404 \begin_layout Plain Layout
2405
2406
2407 \backslash
2408 end{pgfpicture}
2409 \end_layout
2410
2411 \end_inset
2412
2413
2414 \end_layout
2415
2416 \end_deeper
2417 \begin_layout Standard
2418 \begin_inset Separator plain
2419 \end_inset
2420
2421
2422 \end_layout
2423
2424 \begin_layout Frame
2425 \begin_inset Argument 4
2426 status open
2427
2428 \begin_layout Plain Layout
2429 Logspace Turing Machines Are Quite Powerful
2430 \end_layout
2431
2432 \end_inset
2433
2434
2435 \end_layout
2436
2437 \begin_deeper
2438 \begin_layout Block
2439 \begin_inset Argument 2
2440 status collapsed
2441
2442 \begin_layout Plain Layout
2443 Deterministic logspace machines can compute
2444 \end_layout
2445
2446 \end_inset
2447
2448
2449 \end_layout
2450
2451 \begin_deeper
2452 \begin_layout Itemize
2453 addition, multiplication, and even division
2454 \end_layout
2455
2456 \begin_layout Itemize
2457 reductions used in completeness proofs,
2458 \end_layout
2459
2460 \begin_layout Itemize
2461 reachability in forests.
2462 \end_layout
2463
2464 \end_deeper
2465 \begin_layout Pause
2466
2467 \end_layout
2468
2469 \begin_layout Block
2470 \begin_inset Argument 2
2471 status collapsed
2472
2473 \begin_layout Plain Layout
2474 Non-deterministic logspace machines can compute
2475 \end_layout
2476
2477 \end_inset
2478
2479
2480 \end_layout
2481
2482 \begin_deeper
2483 \begin_layout Itemize
2484 reachability in graphs,
2485 \end_layout
2486
2487 \begin_layout Itemize
2488 non-reachability in graphs,
2489 \end_layout
2490
2491 \begin_layout Itemize
2492 satisfiability with two literals per clause.
2493 \end_layout
2494
2495 \end_deeper
2496 \end_deeper
2497 \begin_layout Standard
2498 \begin_inset Separator plain
2499 \end_inset
2500
2501
2502 \end_layout
2503
2504 \begin_layout Frame
2505 \begin_inset Argument 1
2506 status collapsed
2507
2508 \begin_layout Plain Layout
2509
2510 1
2511 \end_layout
2512
2513 \end_inset
2514
2515
2516 \begin_inset Argument 3
2517 status collapsed
2518
2519 \begin_layout Plain Layout
2520 label=hierarchy
2521 \end_layout
2522
2523 \end_inset
2524
2525
2526 \begin_inset Argument 4
2527 status open
2528
2529 \begin_layout Plain Layout
2530 The Complexity Class Hierarchy
2531 \end_layout
2532
2533 \end_inset
2534
2535
2536 \end_layout
2537
2538 \begin_deeper
2539 \begin_layout Standard
2540 \begin_inset ERT
2541 status collapsed
2542
2543 \begin_layout Plain Layout
2544
2545
2546 \backslash
2547 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2548 \end_layout
2549
2550 \begin_layout Plain Layout
2551
2552
2553 \backslash
2554 pgfsetlinewidth{0.8pt}
2555 \end_layout
2556
2557 \begin_layout Plain Layout
2558
2559
2560 \backslash
2561 heap{5.5}{3.5}{$
2562 \backslash
2563 Class P$}{black}{1}
2564 \end_layout
2565
2566 \begin_layout Plain Layout
2567
2568
2569 \backslash
2570 pgfsetdash{{2pt}}{0pt}
2571 \end_layout
2572
2573 \begin_layout Plain Layout
2574
2575
2576 \backslash
2577 only<2->{
2578 \backslash
2579 heap{4.5}{3}{$
2580 \backslash
2581 Class{NC}^2$}{black!50!structure}{2}}
2582 \end_layout
2583
2584 \begin_layout Plain Layout
2585
2586
2587 \backslash
2588 heap{3.5}{2.5}{$
2589 \backslash
2590 Class{NL}$}{black!50!structure}{3}
2591 \end_layout
2592
2593 \begin_layout Plain Layout
2594
2595
2596 \backslash
2597 heap{2.5}{2}{$
2598 \backslash
2599 Class{L}$}{black!50!structure}{4}
2600 \end_layout
2601
2602 \begin_layout Plain Layout
2603
2604
2605 \backslash
2606 only<2->{
2607 \backslash
2608 heap{1.75}{1.5}{$
2609 \backslash
2610 vphantom{A}%
2611 \end_layout
2612
2613 \begin_layout Plain Layout
2614
2615
2616 \backslash
2617 smash{
2618 \backslash
2619 Class{NC}^1}$}{black!50!structure}{5}
2620 \end_layout
2621
2622 \begin_layout Plain Layout
2623
2624 }
2625 \end_layout
2626
2627 \begin_layout Plain Layout
2628
2629
2630 \backslash
2631 pgfsetdash{}{0pt}
2632 \end_layout
2633
2634 \begin_layout Plain Layout
2635
2636
2637 \backslash
2638 only<2->{
2639 \backslash
2640 heap{1.1}{1}{$
2641 \backslash
2642 vphantom{A}%
2643 \end_layout
2644
2645 \begin_layout Plain Layout
2646
2647
2648 \backslash
2649 smash{
2650 \backslash
2651 Class{AC}^0}$}{black}{6}
2652 \end_layout
2653
2654 \begin_layout Plain Layout
2655
2656 }
2657 \end_layout
2658
2659 \begin_layout Plain Layout
2660
2661
2662 \backslash
2663 pgfsetlinewidth{1.0pt}
2664 \end_layout
2665
2666 \begin_layout Plain Layout
2667
2668
2669 \backslash
2670 color{black}
2671 \end_layout
2672
2673 \begin_layout Plain Layout
2674
2675
2676 \backslash
2677 pgfxyline(-5,0)(5,0)
2678 \end_layout
2679
2680 \begin_layout Plain Layout
2681
2682
2683 \backslash
2684 only<1-2>{
2685 \backslash
2686 langat{3.375}{$
2687 \backslash
2688 Lang{reach}$}}
2689 \end_layout
2690
2691 \begin_layout Plain Layout
2692
2693
2694 \backslash
2695 only<1-2>{
2696 \backslash
2697 langat{2.375}{$
2698 \backslash
2699 Lang{reach}_{
2700 \backslash
2701 operatorname{forest}}$}}
2702 \end_layout
2703
2704 \begin_layout Plain Layout
2705
2706
2707 \backslash
2708 only<2>{
2709 \backslash
2710 langat{0.975}{$
2711 \backslash
2712 Lang{addition}$}}
2713 \end_layout
2714
2715 \begin_layout Plain Layout
2716
2717
2718 \backslash
2719 only<2>{
2720 \backslash
2721 langatother{1.6}{
2722 \backslash
2723 vbox{
2724 \backslash
2725 hbox{$
2726 \backslash
2727 Lang{division}$,}
2728 \backslash
2729 hbox{$
2730 \backslash
2731 Lang{parity}$}}}}
2732 \end_layout
2733
2734 \begin_layout Plain Layout
2735
2736
2737 \backslash
2738 only<3-5>{
2739 \backslash
2740 langat{3.375}{
2741 \backslash
2742 vbox{
2743 \backslash
2744 hbox{$
2745 \backslash
2746 Lang{distance}$,}
2747 \backslash
2748 hbox{$
2749 \backslash
2750 Lang{reach}$}}}}
2751 \end_layout
2752
2753 \begin_layout Plain Layout
2754
2755
2756 \backslash
2757 only<4->{
2758 \backslash
2759 langatother{2.375}{
2760 \backslash
2761 vbox{
2762 \backslash
2763 ignorespaces
2764 \end_layout
2765
2766 \begin_layout Plain Layout
2767
2768
2769 \backslash
2770 hbox{$
2771 \backslash
2772 Lang{distance}_{
2773 \backslash
2774 operatorname{forest}}$,}
2775 \backslash
2776 ignorespaces
2777 \end_layout
2778
2779 \begin_layout Plain Layout
2780
2781
2782 \backslash
2783 hbox{$
2784 \backslash
2785 Lang{reach}_{
2786 \backslash
2787 operatorname{forest}}$,}
2788 \backslash
2789 ignorespaces
2790 \end_layout
2791
2792 \begin_layout Plain Layout
2793
2794
2795 \backslash
2796 hbox{$
2797 \backslash
2798 Lang{distance}_{
2799 \backslash
2800 operatorname{path}}$,}
2801 \backslash
2802 ignorespaces
2803 \end_layout
2804
2805 \begin_layout Plain Layout
2806
2807
2808 \backslash
2809 hbox{$
2810 \backslash
2811 Lang{reach}_{
2812 \backslash
2813 operatorname{path}}$}}}
2814 \end_layout
2815
2816 \begin_layout Plain Layout
2817
2818 }
2819 \end_layout
2820
2821 \begin_layout Plain Layout
2822
2823
2824 \backslash
2825 only<5->{
2826 \backslash
2827 langat{0.975}{$
2828 \backslash
2829 Lang{reach}_{
2830 \backslash
2831 operatorname{tourn}}$}}
2832 \end_layout
2833
2834 \begin_layout Plain Layout
2835
2836
2837 \backslash
2838 only<6->{
2839 \backslash
2840 langat{3.375}{
2841 \backslash
2842 vbox{
2843 \backslash
2844 ignorespaces
2845 \end_layout
2846
2847 \begin_layout Plain Layout
2848
2849
2850 \backslash
2851 hbox{$
2852 \backslash
2853 Lang{distance}_{
2854 \backslash
2855 operatorname{tourn}}$,}
2856 \backslash
2857 ignorespaces
2858 \end_layout
2859
2860 \begin_layout Plain Layout
2861
2862
2863 \backslash
2864 hbox{$
2865 \backslash
2866 Lang{distance}$,}
2867 \backslash
2868 ignorespaces
2869 \end_layout
2870
2871 \begin_layout Plain Layout
2872
2873
2874 \backslash
2875 hbox{$
2876 \backslash
2877 Lang{reach}$}}}
2878 \end_layout
2879
2880 \begin_layout Plain Layout
2881
2882 }
2883 \end_layout
2884
2885 \begin_layout Plain Layout
2886
2887
2888 \backslash
2889 only<7->{
2890 \backslash
2891 pgfsetdash{{1pt}}{0pt}%
2892 \end_layout
2893
2894 \begin_layout Plain Layout
2895
2896
2897 \backslash
2898 langat{2.375}{``$
2899 \backslash
2900 Lang{approx}_{
2901 \backslash
2902 operatorname{tourn}}$''}
2903 \end_layout
2904
2905 \begin_layout Plain Layout
2906
2907 }
2908 \end_layout
2909
2910 \begin_layout Plain Layout
2911
2912
2913 \backslash
2914 end{pgfpicture}
2915 \end_layout
2916
2917 \end_inset
2918
2919
2920 \end_layout
2921
2922 \end_deeper
2923 \begin_layout Standard
2924 \begin_inset Separator plain
2925 \end_inset
2926
2927
2928 \end_layout
2929
2930 \begin_layout Frame
2931 \begin_inset Argument 4
2932 status open
2933
2934 \begin_layout Plain Layout
2935 The Circuit Complexity Classes AC
2936 \begin_inset Formula $^{0}$
2937 \end_inset
2938
2939 , NC
2940 \begin_inset Formula $^{1}$
2941 \end_inset
2942
2943 , and NC
2944 \begin_inset Formula $^{2}$
2945 \end_inset
2946
2947
2948 \begin_inset Newline newline
2949 \end_inset
2950
2951 Limit the Circuit Depth
2952 \end_layout
2953
2954 \end_inset
2955
2956
2957 \end_layout
2958
2959 \begin_deeper
2960 \begin_layout Standard
2961 \begin_inset ERT
2962 status collapsed
2963
2964 \begin_layout Plain Layout
2965
2966
2967 \backslash
2968 setlength
2969 \backslash
2970 leftmargini{1em}
2971 \end_layout
2972
2973 \begin_layout Plain Layout
2974
2975
2976 \backslash
2977 nointerlineskip
2978 \end_layout
2979
2980 \end_inset
2981
2982
2983 \end_layout
2984
2985 \begin_layout Columns
2986 \begin_inset Argument 1
2987 status open
2988
2989 \begin_layout Plain Layout
2990 t
2991 \end_layout
2992
2993 \end_inset
2994
2995
2996 \end_layout
2997
2998 \begin_deeper
2999 \begin_layout Column
3000 3.6cm
3001 \end_layout
3002
3003 \begin_layout Block
3004 \begin_inset Argument 2
3005 status open
3006
3007 \begin_layout Plain Layout
3008 Circuit Class
3009 \begin_inset Formula $\Class{AC}^{0}$
3010 \end_inset
3011
3012
3013 \end_layout
3014
3015 \end_inset
3016
3017
3018 \end_layout
3019
3020 \begin_deeper
3021 \begin_layout Itemize
3022 \begin_inset Formula $O(1)$
3023 \end_inset
3024
3025  depth
3026 \end_layout
3027
3028 \begin_layout Itemize
3029 unbounded fan-in
3030 \end_layout
3031
3032 \end_deeper
3033 \begin_layout Examples
3034
3035 \end_layout
3036
3037 \begin_deeper
3038 \begin_layout Itemize
3039 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3040 \end_inset
3041
3042 .
3043 \end_layout
3044
3045 \begin_layout Itemize
3046 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3047 \end_inset
3048
3049 .
3050 \end_layout
3051
3052 \end_deeper
3053 \begin_layout Pause
3054
3055 \end_layout
3056
3057 \begin_layout Column
3058 3.6cm
3059 \end_layout
3060
3061 \begin_layout Block
3062 \begin_inset Argument 2
3063 status open
3064
3065 \begin_layout Plain Layout
3066 Circuit Class
3067 \begin_inset Formula $\Class{NC}^{1}$
3068 \end_inset
3069
3070
3071 \end_layout
3072
3073 \end_inset
3074
3075
3076 \end_layout
3077
3078 \begin_deeper
3079 \begin_layout Itemize
3080 \begin_inset Formula $O(\log n)$
3081 \end_inset
3082
3083  depth
3084 \end_layout
3085
3086 \begin_layout Itemize
3087 bounded fan-in
3088 \end_layout
3089
3090 \end_deeper
3091 \begin_layout Examples
3092
3093 \end_layout
3094
3095 \begin_deeper
3096 \begin_layout Itemize
3097 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3098 \end_inset
3099
3100 .
3101 \end_layout
3102
3103 \begin_layout Itemize
3104 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3105 \end_inset
3106
3107 .
3108 \end_layout
3109
3110 \begin_layout Itemize
3111 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3112 \end_inset
3113
3114 .
3115 \end_layout
3116
3117 \end_deeper
3118 \begin_layout Pause
3119
3120 \end_layout
3121
3122 \begin_layout Column
3123 3.6cm
3124 \end_layout
3125
3126 \begin_layout Block
3127 \begin_inset Argument 2
3128 status open
3129
3130 \begin_layout Plain Layout
3131 Circuit Class
3132 \begin_inset Formula $\Class{NC}^{2}$
3133 \end_inset
3134
3135
3136 \end_layout
3137
3138 \end_inset
3139
3140
3141 \end_layout
3142
3143 \begin_deeper
3144 \begin_layout Itemize
3145 \begin_inset Formula $O(\log^{2}n)$
3146 \end_inset
3147
3148  depth
3149 \end_layout
3150
3151 \begin_layout Itemize
3152 bounded fan-in
3153 \end_layout
3154
3155 \end_deeper
3156 \begin_layout Examples
3157
3158 \end_layout
3159
3160 \begin_deeper
3161 \begin_layout Itemize
3162 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3163 \end_inset
3164
3165 .
3166 \end_layout
3167
3168 \end_deeper
3169 \end_deeper
3170 \end_deeper
3171 \begin_layout AgainFrame
3172 \begin_inset Argument 1
3173 status collapsed
3174
3175 \begin_layout Plain Layout
3176
3177 2
3178 \end_layout
3179
3180 \end_inset
3181
3182 hierarchy
3183 \end_layout
3184
3185 \begin_layout Subsection
3186 Standard Complexity Results on Finding Paths
3187 \end_layout
3188
3189 \begin_layout Frame
3190 \begin_inset Argument 4
3191 status open
3192
3193 \begin_layout Plain Layout
3194 All Variants of Finding Paths in Directed Graphs
3195 \begin_inset Newline newline
3196 \end_inset
3197
3198 Are Equally Difficult
3199 \end_layout
3200
3201 \end_inset
3202
3203
3204 \end_layout
3205
3206 \begin_deeper
3207 \begin_layout Fact
3208 \begin_inset Formula $\Lang{reach}$
3209 \end_inset
3210
3211  and
3212 \begin_inset Formula $\Lang{distance}$
3213 \end_inset
3214
3215  are
3216 \begin_inset Formula $\Class{NL}$
3217 \end_inset
3218
3219 -complete.
3220
3221 \end_layout
3222
3223 \begin_layout Pause
3224
3225 \end_layout
3226
3227 \begin_layout Corollary
3228 For directed graphs, we can solve
3229 \end_layout
3230
3231 \begin_deeper
3232 \begin_layout Itemize
3233 the reachability problem in logspace iff
3234 \begin_inset Formula $\Class{L}=\Class{NL}$
3235 \end_inset
3236
3237 .
3238 \end_layout
3239
3240 \begin_layout Itemize
3241 the construction problem in logspace iff
3242 \begin_inset Formula $\Class{L}=\Class{NL}$
3243 \end_inset
3244
3245 .
3246 \end_layout
3247
3248 \begin_layout Itemize
3249 the optimization problem in logspace iff
3250 \begin_inset Formula $\Class{L}=\Class{NL}$
3251 \end_inset
3252
3253 .
3254 \end_layout
3255
3256 \begin_layout Itemize
3257 the approximation problem in logspace iff
3258 \begin_inset Formula $\Class{L}=\Class{NL}$
3259 \end_inset
3260
3261 .
3262 \end_layout
3263
3264 \end_deeper
3265 \end_deeper
3266 \begin_layout AgainFrame
3267 \begin_inset Argument 1
3268 status collapsed
3269
3270 \begin_layout Plain Layout
3271
3272 3
3273 \end_layout
3274
3275 \end_inset
3276
3277 hierarchy
3278 \end_layout
3279
3280 \begin_layout Frame
3281 \begin_inset Argument 4
3282 status open
3283
3284 \begin_layout Plain Layout
3285 Finding Paths in Forests and Directed Paths is Easy,
3286 \begin_inset Newline newline
3287 \end_inset
3288
3289 But Not Trivial
3290 \end_layout
3291
3292 \end_inset
3293
3294
3295 \end_layout
3296
3297 \begin_deeper
3298 \begin_layout Fact
3299 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3300 \end_inset
3301
3302  and
3303 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3304 \end_inset
3305
3306  are
3307 \begin_inset Formula $\Class{L}$
3308 \end_inset
3309
3310 -complete.
3311 \end_layout
3312
3313 \begin_layout Standard
3314 \begin_inset Separator plain
3315 \end_inset
3316
3317
3318 \end_layout
3319
3320 \begin_layout Fact
3321 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3322 \end_inset
3323
3324  and
3325 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3326 \end_inset
3327
3328  are
3329 \begin_inset Formula $\Class{L}$
3330 \end_inset
3331
3332 -complete.
3333 \end_layout
3334
3335 \end_deeper
3336 \begin_layout AgainFrame
3337 \begin_inset Argument 1
3338 status collapsed
3339
3340 \begin_layout Plain Layout
3341
3342 4
3343 \end_layout
3344
3345 \end_inset
3346
3347 hierarchy
3348 \end_layout
3349
3350 \begin_layout Section
3351 Finding Paths in Tournaments
3352 \end_layout
3353
3354 \begin_layout Subsection
3355 Complexity of: Does a Path Exist?
3356 \end_layout
3357
3358 \begin_layout Frame
3359 \begin_inset Argument 4
3360 status open
3361
3362 \begin_layout Plain Layout
3363 Definition of the Tournament Reachability Problem
3364 \end_layout
3365
3366 \end_inset
3367
3368
3369 \end_layout
3370
3371 \begin_deeper
3372 \begin_layout Definition
3373 Let
3374 \color none
3375
3376 \color red
3377
3378 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3379 \end_inset
3380
3381
3382 \color none
3383
3384 \color inherit
3385 contain all triples
3386 \begin_inset Formula $(T,s,t)$
3387 \end_inset
3388
3389  such that
3390 \end_layout
3391
3392 \begin_deeper
3393 \begin_layout Enumerate
3394 \begin_inset Formula $T=(V,E)$
3395 \end_inset
3396
3397  is a tournament and
3398 \end_layout
3399
3400 \begin_layout Enumerate
3401 there exists a path from
3402 \begin_inset space ~
3403 \end_inset
3404
3405
3406 \begin_inset Formula $s$
3407 \end_inset
3408
3409  to
3410 \begin_inset space ~
3411 \end_inset
3412
3413
3414 \begin_inset Formula $t$
3415 \end_inset
3416
3417 .
3418 \end_layout
3419
3420 \end_deeper
3421 \end_deeper
3422 \begin_layout Standard
3423 \begin_inset Separator plain
3424 \end_inset
3425
3426
3427 \end_layout
3428
3429 \begin_layout Frame
3430 \begin_inset Argument 4
3431 status open
3432
3433 \begin_layout Plain Layout
3434 The Tournament Reachability Problem is Very Easy
3435 \end_layout
3436
3437 \end_inset
3438
3439
3440 \end_layout
3441
3442 \begin_deeper
3443 \begin_layout Theorem
3444 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3445 \end_inset
3446
3447 .
3448 \end_layout
3449
3450 \begin_layout Pause
3451
3452 \end_layout
3453
3454 \begin_layout AlertBlock
3455 \begin_inset Argument 2
3456 status collapsed
3457
3458 \begin_layout Plain Layout
3459 Implications
3460 \end_layout
3461
3462 \end_inset
3463
3464
3465 \end_layout
3466
3467 \begin_deeper
3468 \begin_layout Itemize
3469 The problem is
3470 \begin_inset Quotes eld
3471 \end_inset
3472
3473 easier
3474 \begin_inset Quotes erd
3475 \end_inset
3476
3477  than
3478 \begin_inset Formula $\Lang{reach}$
3479 \end_inset
3480
3481  and even
3482 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3483 \end_inset
3484
3485 .
3486 \end_layout
3487
3488 \begin_layout Itemize
3489 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3490 \end_inset
3491
3492 .
3493 \end_layout
3494
3495 \end_deeper
3496 \end_deeper
3497 \begin_layout AgainFrame
3498 \begin_inset Argument 1
3499 status open
3500
3501 \begin_layout Plain Layout
3502
3503 5
3504 \end_layout
3505
3506 \end_inset
3507
3508 hierarchy
3509 \end_layout
3510
3511 \begin_layout Subsection
3512 Complexity of: Construct a Shortest Path
3513 \end_layout
3514
3515 \begin_layout Frame
3516 \begin_inset Argument 4
3517 status open
3518
3519 \begin_layout Plain Layout
3520 Finding a Shortest Path Is as Difficult as
3521 \begin_inset Newline newline
3522 \end_inset
3523
3524 the Distance Problem
3525 \end_layout
3526
3527 \end_inset
3528
3529
3530 \end_layout
3531
3532 \begin_deeper
3533 \begin_layout Definition
3534 Let
3535 \color none
3536
3537 \color red
3538
3539 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3540 \end_inset
3541
3542
3543 \color none
3544
3545 \color inherit
3546 contain all tuples
3547 \begin_inset Formula $(T,s,t,d)$
3548 \end_inset
3549
3550  such that
3551 \end_layout
3552
3553 \begin_deeper
3554 \begin_layout Enumerate
3555 \begin_inset Formula $T=(V,E)$
3556 \end_inset
3557
3558  is a tournament in which
3559 \end_layout
3560
3561 \begin_layout Enumerate
3562 the distance of
3563 \begin_inset Formula $s$
3564 \end_inset
3565
3566  and
3567 \begin_inset space ~
3568 \end_inset
3569
3570
3571 \begin_inset Formula $t$
3572 \end_inset
3573
3574  is at most
3575 \begin_inset space ~
3576 \end_inset
3577
3578
3579 \begin_inset Formula $d$
3580 \end_inset
3581
3582 .
3583 \end_layout
3584
3585 \end_deeper
3586 \end_deeper
3587 \begin_layout Standard
3588 \begin_inset Separator plain
3589 \end_inset
3590
3591
3592 \end_layout
3593
3594 \begin_layout Frame
3595 \begin_inset Argument 4
3596 status open
3597
3598 \begin_layout Plain Layout
3599 The Tournament Distance Problem is Hard
3600 \end_layout
3601
3602 \end_inset
3603
3604
3605 \end_layout
3606
3607 \begin_deeper
3608 \begin_layout Theorem
3609 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3610 \end_inset
3611
3612  is
3613 \begin_inset Formula $\Class{NL}$
3614 \end_inset
3615
3616 -complete.
3617 \end_layout
3618
3619 \begin_layout Standard
3620 \begin_inset space \hfill{}
3621 \end_inset
3622
3623
3624 \begin_inset ERT
3625 status collapsed
3626
3627 \begin_layout Plain Layout
3628
3629
3630 \backslash
3631 hyperlink{hierarchy<6>}{
3632 \backslash
3633 beamerskipbutton{Skip Proof}}
3634 \end_layout
3635
3636 \end_inset
3637
3638
3639 \end_layout
3640
3641 \begin_layout Pause
3642
3643 \end_layout
3644
3645 \begin_layout Corollary
3646 Shortest path in tournaments can be constructed
3647 \begin_inset Newline newline
3648 \end_inset
3649
3650 in logarithmic space, iff
3651 \begin_inset Formula $\Class{L}=\Class{NL}$
3652 \end_inset
3653
3654 .
3655 \end_layout
3656
3657 \begin_layout Pause
3658
3659 \end_layout
3660
3661 \begin_layout Corollary
3662 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3663 \end_inset
3664
3665 .
3666 \end_layout
3667
3668 \end_deeper
3669 \begin_layout Standard
3670 \begin_inset Separator plain
3671 \end_inset
3672
3673
3674 \end_layout
3675
3676 \begin_layout Frame
3677 \begin_inset Argument 4
3678 status open
3679
3680 \begin_layout Plain Layout
3681 Proof That
3682 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3683 \end_inset
3684
3685  is NL-complete
3686 \end_layout
3687
3688 \end_inset
3689
3690
3691 \end_layout
3692
3693 \begin_deeper
3694 \begin_layout Standard
3695 \begin_inset ERT
3696 status collapsed
3697
3698 \begin_layout Plain Layout
3699
3700
3701 \backslash
3702 nointerlineskip
3703 \end_layout
3704
3705 \end_inset
3706
3707
3708 \end_layout
3709
3710 \begin_layout Columns
3711 \begin_inset Argument 1
3712 status open
3713
3714 \begin_layout Plain Layout
3715 t,onlytextwidth
3716 \end_layout
3717
3718 \end_inset
3719
3720
3721 \end_layout
3722
3723 \begin_deeper
3724 \begin_layout Column
3725 5.7cm
3726 \end_layout
3727
3728 \begin_layout Standard
3729 \begin_inset ERT
3730 status collapsed
3731
3732 \begin_layout Plain Layout
3733
3734
3735 \backslash
3736 setlength
3737 \backslash
3738 leftmargini{1.5em}
3739 \end_layout
3740
3741 \end_inset
3742
3743
3744 \end_layout
3745
3746 \begin_layout Block
3747 \begin_inset Argument 2
3748 status open
3749
3750 \begin_layout Plain Layout
3751 Reduce
3752 \begin_inset Formula $\Lang{reach}$
3753 \end_inset
3754
3755  to
3756 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3757 \end_inset
3758
3759
3760 \end_layout
3761
3762 \end_inset
3763
3764
3765 \end_layout
3766
3767 \begin_deeper
3768 \begin_layout Enumerate
3769 \begin_inset Argument item:2
3770 status open
3771
3772 \begin_layout Plain Layout
3773
3774 alert@1
3775 \end_layout
3776
3777 \end_inset
3778
3779 Is input
3780 \begin_inset Formula $(G,s,t)$
3781 \end_inset
3782
3783  in
3784 \begin_inset Formula $\Lang{reach}$
3785 \end_inset
3786
3787 ?
3788 \end_layout
3789
3790 \begin_layout Enumerate
3791 \begin_inset Argument item:2
3792 status open
3793
3794 \begin_layout Plain Layout
3795
3796 2-| alert@2-8
3797 \end_layout
3798
3799 \end_inset
3800
3801 Map
3802 \begin_inset Formula $G$
3803 \end_inset
3804
3805  to
3806 \begin_inset Formula $G'$
3807 \end_inset
3808
3809 .
3810 \end_layout
3811
3812 \begin_layout Enumerate
3813 \begin_inset Argument item:2
3814 status open
3815
3816 \begin_layout Plain Layout
3817
3818 9-| alert@9
3819 \end_layout
3820
3821 \end_inset
3822
3823 Query:
3824 \begin_inset Newline newline
3825 \end_inset
3826
3827
3828 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3829 \end_inset
3830
3831 ?
3832 \end_layout
3833
3834 \end_deeper
3835 \begin_layout Standard
3836 \begin_inset Separator plain
3837 \end_inset
3838
3839
3840 \end_layout
3841
3842 \begin_layout Block
3843 \begin_inset Argument 2
3844 status open
3845
3846 \begin_layout Plain Layout
3847 Correctness
3848 \end_layout
3849
3850 \end_inset
3851
3852
3853 \begin_inset Argument 1
3854 status open
3855
3856 \begin_layout Plain Layout
3857
3858 10-
3859 \end_layout
3860
3861 \end_inset
3862
3863
3864 \end_layout
3865
3866 \begin_deeper
3867 \begin_layout Enumerate
3868 \begin_inset Argument item:2
3869 status open
3870
3871 \begin_layout Plain Layout
3872
3873 10-| alert@10-11
3874 \end_layout
3875
3876 \end_inset
3877
3878 A path in
3879 \begin_inset space ~
3880 \end_inset
3881
3882
3883 \begin_inset Formula $G$
3884 \end_inset
3885
3886  induces
3887 \begin_inset Newline newline
3888 \end_inset
3889
3890 a length-3 path in
3891 \begin_inset space ~
3892 \end_inset
3893
3894
3895 \begin_inset Formula $G'$
3896 \end_inset
3897
3898 .
3899 \end_layout
3900
3901 \begin_layout Enumerate
3902 \begin_inset Argument item:2
3903 status open
3904
3905 \begin_layout Plain Layout
3906
3907 12-| alert@12-13
3908 \end_layout
3909
3910 \end_inset
3911
3912 A length-3 path in
3913 \begin_inset space ~
3914 \end_inset
3915
3916
3917 \begin_inset Formula $G'$
3918 \end_inset
3919
3920  induces
3921 \begin_inset Newline newline
3922 \end_inset
3923
3924 a path in
3925 \begin_inset space ~
3926 \end_inset
3927
3928
3929 \begin_inset Formula $G'$
3930 \end_inset
3931
3932 .
3933 \end_layout
3934
3935 \end_deeper
3936 \begin_layout Column
3937 4.5cm
3938 \end_layout
3939
3940 \begin_layout Example
3941 \begin_inset ERT
3942 status collapsed
3943
3944 \begin_layout Plain Layout
3945
3946
3947 \backslash
3948 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
3949 \end_layout
3950
3951 \begin_layout Plain Layout
3952
3953
3954 \backslash
3955 color{beamerexample}
3956 \end_layout
3957
3958 \begin_layout Plain Layout
3959
3960
3961 \backslash
3962 pgfsetlinewidth{0.6pt}
3963 \end_layout
3964
3965 \begin_layout Plain Layout
3966
3967
3968 \backslash
3969 graphnode{A}{
3970 \backslash
3971 pgfxy(1,3.3)}
3972 \end_layout
3973
3974 \begin_layout Plain Layout
3975
3976
3977 \backslash
3978 graphnode{B}{
3979 \backslash
3980 pgfxy(2,3.3)}
3981 \end_layout
3982
3983 \begin_layout Plain Layout
3984
3985
3986 \backslash
3987 graphnode{C}{
3988 \backslash
3989 pgfxy(3,3.3)}
3990 \end_layout
3991
3992 \begin_layout Plain Layout
3993
3994
3995 \backslash
3996 graphnode{D}{
3997 \backslash
3998 pgfxy(4,3.3)}
3999 \end_layout
4000
4001 \begin_layout Plain Layout
4002
4003
4004 \backslash
4005 color{white}
4006 \end_layout
4007
4008 \begin_layout Plain Layout
4009
4010
4011 \backslash
4012 pgfputat{
4013 \backslash
4014 pgfnodecenter{A}}{
4015 \backslash
4016 pgfbox[center,center]{$s$}}
4017 \end_layout
4018
4019 \begin_layout Plain Layout
4020
4021
4022 \backslash
4023 pgfputat{
4024 \backslash
4025 pgfnodecenter{D}}{
4026 \backslash
4027 pgfbox[center,center]{$t$}}
4028 \end_layout
4029
4030 \begin_layout Plain Layout
4031
4032
4033 \backslash
4034 color{beamerexample}
4035 \end_layout
4036
4037 \begin_layout Plain Layout
4038
4039
4040 \backslash
4041 pgfsetendarrow{
4042 \backslash
4043 pgfarrowto}
4044 \end_layout
4045
4046 \begin_layout Plain Layout
4047
4048
4049 \backslash
4050 pgfnodesetsepstart{2pt}
4051 \end_layout
4052
4053 \begin_layout Plain Layout
4054
4055
4056 \backslash
4057 pgfnodesetsepend{2pt}
4058 \end_layout
4059
4060 \begin_layout Plain Layout
4061
4062
4063 \backslash
4064 alert<3>{
4065 \backslash
4066 pgfnodeconnline{B}{A}}
4067 \end_layout
4068
4069 \begin_layout Plain Layout
4070
4071
4072 \backslash
4073 alert<4>{
4074 \backslash
4075 pgfnodeconnline{B}{C}}
4076 \end_layout
4077
4078 \begin_layout Plain Layout
4079
4080
4081 \backslash
4082 alert<5,10-11,13>{
4083 \backslash
4084 pgfnodeconnline{C}{D}}
4085 \end_layout
4086
4087 \begin_layout Plain Layout
4088
4089
4090 \backslash
4091 alert<6,10-11,13>{
4092 \backslash
4093 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4094 \end_layout
4095
4096 \begin_layout Plain Layout
4097
4098
4099 \backslash
4100 pgfputat{
4101 \backslash
4102 pgfxy(0,3.3)}{
4103 \backslash
4104 pgfbox[left,center]{$G
4105 \backslash
4106 colon$}}
4107 \end_layout
4108
4109 \begin_layout Plain Layout
4110
4111
4112 \backslash
4113 only<2->{%
4114 \end_layout
4115
4116 \begin_layout Plain Layout
4117
4118
4119 \backslash
4120 pgfputat{
4121 \backslash
4122 pgfxy(0,2.25)}{
4123 \backslash
4124 pgfbox[left,center]{$G'
4125 \backslash
4126 colon$}}
4127 \end_layout
4128
4129 \begin_layout Plain Layout
4130
4131
4132 \backslash
4133 graphnode{A1}{
4134 \backslash
4135 pgfxy(1,2.25)}
4136 \end_layout
4137
4138 \begin_layout Plain Layout
4139
4140
4141 \backslash
4142 graphnode{B1}{
4143 \backslash
4144 pgfxy(2,2.25)}
4145 \end_layout
4146
4147 \begin_layout Plain Layout
4148
4149
4150 \backslash
4151 graphnode{C1}{
4152 \backslash
4153 pgfxy(3,2.25)}
4154 \end_layout
4155
4156 \begin_layout Plain Layout
4157
4158
4159 \backslash
4160 graphnode{D1}{
4161 \backslash
4162 pgfxy(4,2.25)}
4163 \end_layout
4164
4165 \begin_layout Plain Layout
4166
4167
4168 \backslash
4169 graphnode{A2}{
4170 \backslash
4171 pgfxy(1,1.25)}
4172 \end_layout
4173
4174 \begin_layout Plain Layout
4175
4176
4177 \backslash
4178 graphnode{B2}{
4179 \backslash
4180 pgfxy(2,1.25)}
4181 \end_layout
4182
4183 \begin_layout Plain Layout
4184
4185
4186 \backslash
4187 graphnode{C2}{
4188 \backslash
4189 pgfxy(3,1.25)}
4190 \end_layout
4191
4192 \begin_layout Plain Layout
4193
4194
4195 \backslash
4196 graphnode{D2}{
4197 \backslash
4198 pgfxy(4,1.25)}
4199 \end_layout
4200
4201 \begin_layout Plain Layout
4202
4203
4204 \backslash
4205 graphnode{A3}{
4206 \backslash
4207 pgfxy(1,0.25)}
4208 \end_layout
4209
4210 \begin_layout Plain Layout
4211
4212
4213 \backslash
4214 graphnode{B3}{
4215 \backslash
4216 pgfxy(2,0.25)}
4217 \end_layout
4218
4219 \begin_layout Plain Layout
4220
4221
4222 \backslash
4223 graphnode{C3}{
4224 \backslash
4225 pgfxy(3,0.25)}
4226 \end_layout
4227
4228 \begin_layout Plain Layout
4229
4230
4231 \backslash
4232 graphnode{D3}{
4233 \backslash
4234 pgfxy(4,0.25)}
4235 \end_layout
4236
4237 \begin_layout Plain Layout
4238
4239
4240 \backslash
4241 graphnode{A4}{
4242 \backslash
4243 pgfxy(1,-.75)}
4244 \end_layout
4245
4246 \begin_layout Plain Layout
4247
4248
4249 \backslash
4250 graphnode{B4}{
4251 \backslash
4252 pgfxy(2,-.75)}
4253 \end_layout
4254
4255 \begin_layout Plain Layout
4256
4257
4258 \backslash
4259 graphnode{C4}{
4260 \backslash
4261 pgfxy(3,-.75)}
4262 \end_layout
4263
4264 \begin_layout Plain Layout
4265
4266
4267 \backslash
4268 graphnode{D4}{
4269 \backslash
4270 pgfxy(4,-.75)}
4271 \end_layout
4272
4273 \begin_layout Plain Layout
4274
4275    {
4276 \backslash
4277 color{white}
4278 \end_layout
4279
4280 \begin_layout Plain Layout
4281
4282
4283 \backslash
4284 pgfputat{
4285 \backslash
4286 pgfnodecenter{A1}}{
4287 \backslash
4288 pgfbox[center,center]{$s'$}}
4289 \end_layout
4290
4291 \begin_layout Plain Layout
4292
4293
4294 \backslash
4295 pgfputat{
4296 \backslash
4297 pgfnodecenter{D4}}{
4298 \backslash
4299 pgfbox[center,center]{$t'$}}
4300 \end_layout
4301
4302 \begin_layout Plain Layout
4303
4304    }
4305 \end_layout
4306
4307 \begin_layout Plain Layout
4308
4309 }
4310 \end_layout
4311
4312 \begin_layout Plain Layout
4313
4314
4315 \backslash
4316 only<8->{%
4317 \end_layout
4318
4319 \begin_layout Plain Layout
4320
4321
4322 \backslash
4323 pgfsetlinewidth{0.4pt}
4324 \end_layout
4325
4326 \begin_layout Plain Layout
4327
4328
4329 \backslash
4330 color{beamerexample!25!averagebackgroundcolor}
4331 \end_layout
4332
4333 \begin_layout Plain Layout
4334
4335
4336 \backslash
4337 pgfnodeconnline{A2}{C1}
4338 \end_layout
4339
4340 \begin_layout Plain Layout
4341
4342
4343 \backslash
4344 pgfnodeconnline{A2}{D1}
4345 \end_layout
4346
4347 \begin_layout Plain Layout
4348
4349
4350 \backslash
4351 pgfnodeconnline{B2}{A1}
4352 \end_layout
4353
4354 \begin_layout Plain Layout
4355
4356
4357 \backslash
4358 pgfnodeconnline{B2}{C1}
4359 \end_layout
4360
4361 \begin_layout Plain Layout
4362
4363
4364 \backslash
4365 pgfnodeconnline{B2}{D1}
4366 \end_layout
4367
4368 \begin_layout Plain Layout
4369
4370
4371 \backslash
4372 pgfnodeconnline{C2}{D1}
4373 \end_layout
4374
4375 \begin_layout Plain Layout
4376
4377
4378 \backslash
4379 pgfnodeconnline{D2}{A1}
4380 \end_layout
4381
4382 \begin_layout Plain Layout
4383
4384
4385 \backslash
4386 pgfnodeconnline{D2}{B1}
4387 \end_layout
4388
4389 \begin_layout Plain Layout
4390
4391
4392 \backslash
4393 pgfnodeconnline{A3}{C2}
4394 \end_layout
4395
4396 \begin_layout Plain Layout
4397
4398
4399 \backslash
4400 pgfnodeconnline{A3}{D2}
4401 \end_layout
4402
4403 \begin_layout Plain Layout
4404
4405
4406 \backslash
4407 pgfnodeconnline{B3}{A2}
4408 \end_layout
4409
4410 \begin_layout Plain Layout
4411
4412
4413 \backslash
4414 pgfnodeconnline{B3}{C2}
4415 \end_layout
4416
4417 \begin_layout Plain Layout
4418
4419
4420 \backslash
4421 pgfnodeconnline{B3}{D2}
4422 \end_layout
4423
4424 \begin_layout Plain Layout
4425
4426
4427 \backslash
4428 pgfnodeconnline{C3}{D2}
4429 \end_layout
4430
4431 \begin_layout Plain Layout
4432
4433
4434 \backslash
4435 pgfnodeconnline{D3}{A2}
4436 \end_layout
4437
4438 \begin_layout Plain Layout
4439
4440
4441 \backslash
4442 pgfnodeconnline{D3}{B2}
4443 \end_layout
4444
4445 \begin_layout Plain Layout
4446
4447
4448 \backslash
4449 pgfnodeconnline{A4}{C3}
4450 \end_layout
4451
4452 \begin_layout Plain Layout
4453
4454
4455 \backslash
4456 pgfnodeconnline{A4}{D3}
4457 \end_layout
4458
4459 \begin_layout Plain Layout
4460
4461
4462 \backslash
4463 pgfnodeconnline{B4}{A3}
4464 \end_layout
4465
4466 \begin_layout Plain Layout
4467
4468
4469 \backslash
4470 pgfnodeconnline{B4}{C3}
4471 \end_layout
4472
4473 \begin_layout Plain Layout
4474
4475
4476 \backslash
4477 pgfnodeconnline{B4}{D3}
4478 \end_layout
4479
4480 \begin_layout Plain Layout
4481
4482
4483 \backslash
4484 pgfnodeconnline{C4}{D3}
4485 \end_layout
4486
4487 \begin_layout Plain Layout
4488
4489
4490 \backslash
4491 pgfnodeconnline{D4}{A3}
4492 \end_layout
4493
4494 \begin_layout Plain Layout
4495
4496
4497 \backslash
4498 pgfnodeconnline{D4}{B3}
4499 \end_layout
4500
4501 \begin_layout Plain Layout
4502
4503
4504 \backslash
4505 pgfsetstartarrow{
4506 \backslash
4507 pgfarrowto}
4508 \end_layout
4509
4510 \begin_layout Plain Layout
4511
4512
4513 \backslash
4514 pgfnodeconnline{A1}{B1}
4515 \end_layout
4516
4517 \begin_layout Plain Layout
4518
4519
4520 \backslash
4521 pgfnodeconnline{B1}{C1}
4522 \end_layout
4523
4524 \begin_layout Plain Layout
4525
4526
4527 \backslash
4528 pgfnodeconnline{C1}{D1}
4529 \end_layout
4530
4531 \begin_layout Plain Layout
4532
4533
4534 \backslash
4535 pgfnodeconnline{A2}{B2}
4536 \end_layout
4537
4538 \begin_layout Plain Layout
4539
4540
4541 \backslash
4542 pgfnodeconnline{B2}{C2}
4543 \end_layout
4544
4545 \begin_layout Plain Layout
4546
4547
4548 \backslash
4549 pgfnodeconnline{C2}{D2}
4550 \end_layout
4551
4552 \begin_layout Plain Layout
4553
4554
4555 \backslash
4556 pgfnodeconnline{A3}{B3}
4557 \end_layout
4558
4559 \begin_layout Plain Layout
4560
4561
4562 \backslash
4563 pgfnodeconnline{B3}{C3}
4564 \end_layout
4565
4566 \begin_layout Plain Layout
4567
4568
4569 \backslash
4570 pgfnodeconnline{C3}{D3}
4571 \end_layout
4572
4573 \begin_layout Plain Layout
4574
4575
4576 \backslash
4577 pgfnodeconnline{A4}{B4}
4578 \end_layout
4579
4580 \begin_layout Plain Layout
4581
4582
4583 \backslash
4584 pgfnodeconnline{B4}{C4}
4585 \end_layout
4586
4587 \begin_layout Plain Layout
4588
4589
4590 \backslash
4591 pgfnodeconnline{C4}{D4}
4592 \end_layout
4593
4594 \begin_layout Plain Layout
4595
4596
4597 \backslash
4598 pgfclearstartarrow
4599 \end_layout
4600
4601 \begin_layout Plain Layout
4602
4603
4604 \backslash
4605 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
4606 \end_layout
4607
4608 \begin_layout Plain Layout
4609
4610
4611 \backslash
4612 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
4613 \end_layout
4614
4615 \begin_layout Plain Layout
4616
4617
4618 \backslash
4619 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
4620 \end_layout
4621
4622 \begin_layout Plain Layout
4623
4624
4625 \backslash
4626 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
4627 \end_layout
4628
4629 \begin_layout Plain Layout
4630
4631
4632 \backslash
4633 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
4634 \end_layout
4635
4636 \begin_layout Plain Layout
4637
4638
4639 \backslash
4640 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
4641 \end_layout
4642
4643 \begin_layout Plain Layout
4644
4645
4646 \backslash
4647 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
4648 \end_layout
4649
4650 \begin_layout Plain Layout
4651
4652
4653 \backslash
4654 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
4655 \end_layout
4656
4657 \begin_layout Plain Layout
4658
4659
4660 \backslash
4661 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
4662 \end_layout
4663
4664 \begin_layout Plain Layout
4665
4666
4667 \backslash
4668 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
4669 \end_layout
4670
4671 \begin_layout Plain Layout
4672
4673
4674 \backslash
4675 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
4676 \end_layout
4677
4678 \begin_layout Plain Layout
4679
4680
4681 \backslash
4682 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
4683 \end_layout
4684
4685 \begin_layout Plain Layout
4686
4687
4688 \backslash
4689 color{beamerexample}
4690 \end_layout
4691
4692 \begin_layout Plain Layout
4693
4694
4695 \backslash
4696 pgfsetlinewidth{0.6pt}
4697 \end_layout
4698
4699 \begin_layout Plain Layout
4700
4701 }
4702 \end_layout
4703
4704 \begin_layout Plain Layout
4705
4706
4707 \backslash
4708 only<3->{%
4709 \end_layout
4710
4711 \begin_layout Plain Layout
4712
4713
4714 \backslash
4715 color<3>{red}
4716 \end_layout
4717
4718 \begin_layout Plain Layout
4719
4720
4721 \backslash
4722 pgfnodeconnline{B1}{A2}
4723 \end_layout
4724
4725 \begin_layout Plain Layout
4726
4727
4728 \backslash
4729 pgfnodeconnline{B2}{A3}
4730 \end_layout
4731
4732 \begin_layout Plain Layout
4733
4734
4735 \backslash
4736 pgfnodeconnline{B3}{A4}
4737 \end_layout
4738
4739 \begin_layout Plain Layout
4740
4741 }
4742 \end_layout
4743
4744 \begin_layout Plain Layout
4745
4746
4747 \backslash
4748 only<4->{%
4749 \end_layout
4750
4751 \begin_layout Plain Layout
4752
4753
4754 \backslash
4755 color<4>{red}
4756 \end_layout
4757
4758 \begin_layout Plain Layout
4759
4760
4761 \backslash
4762 pgfnodeconnline{B1}{C2}
4763 \end_layout
4764
4765 \begin_layout Plain Layout
4766
4767
4768 \backslash
4769 pgfnodeconnline{B2}{C3}
4770 \end_layout
4771
4772 \begin_layout Plain Layout
4773
4774
4775 \backslash
4776 pgfnodeconnline{B3}{C4}
4777 \end_layout
4778
4779 \begin_layout Plain Layout
4780
4781 }
4782 \end_layout
4783
4784 \begin_layout Plain Layout
4785
4786
4787 \backslash
4788 only<5->{%
4789 \end_layout
4790
4791 \begin_layout Plain Layout
4792
4793
4794 \backslash
4795 color<5>{red}
4796 \end_layout
4797
4798 \begin_layout Plain Layout
4799
4800
4801 \backslash
4802 pgfnodeconnline{C1}{D2}
4803 \end_layout
4804
4805 \begin_layout Plain Layout
4806
4807
4808 \backslash
4809 alert<11>{
4810 \backslash
4811 pgfnodeconnline{C2}{D3}}
4812 \end_layout
4813
4814 \begin_layout Plain Layout
4815
4816
4817 \backslash
4818 alert<12-13>{
4819 \backslash
4820 pgfnodeconnline{C3}{D4}}
4821 \end_layout
4822
4823 \begin_layout Plain Layout
4824
4825 }
4826 \end_layout
4827
4828 \begin_layout Plain Layout
4829
4830
4831 \backslash
4832 only<6->{%
4833 \end_layout
4834
4835 \begin_layout Plain Layout
4836
4837
4838 \backslash
4839 color<6>{red}
4840 \end_layout
4841
4842 \begin_layout Plain Layout
4843
4844
4845 \backslash
4846 alert<11>{
4847 \backslash
4848 pgfnodeconnline{A1}{C2}}
4849 \end_layout
4850
4851 \begin_layout Plain Layout
4852
4853
4854 \backslash
4855 alert<12-13>{
4856 \backslash
4857 pgfnodeconnline{A2}{C3}}
4858 \end_layout
4859
4860 \begin_layout Plain Layout
4861
4862
4863 \backslash
4864 pgfnodeconnline{A3}{C4}
4865 \end_layout
4866
4867 \begin_layout Plain Layout
4868
4869 }
4870 \end_layout
4871
4872 \begin_layout Plain Layout
4873
4874
4875 \backslash
4876 only<7->{%
4877 \end_layout
4878
4879 \begin_layout Plain Layout
4880
4881
4882 \backslash
4883 color<7>{red}
4884 \end_layout
4885
4886 \begin_layout Plain Layout
4887
4888
4889 \backslash
4890 alert<12-13>{
4891 \backslash
4892 pgfnodeconnline{A1}{A2}}
4893 \end_layout
4894
4895 \begin_layout Plain Layout
4896
4897
4898 \backslash
4899 pgfnodeconnline{A2}{A3}
4900 \end_layout
4901
4902 \begin_layout Plain Layout
4903
4904
4905 \backslash
4906 pgfnodeconnline{A3}{A4}
4907 \end_layout
4908
4909 \begin_layout Plain Layout
4910
4911
4912 \backslash
4913 pgfnodeconnline{B1}{B2}
4914 \end_layout
4915
4916 \begin_layout Plain Layout
4917
4918
4919 \backslash
4920 pgfnodeconnline{B2}{B3}
4921 \end_layout
4922
4923 \begin_layout Plain Layout
4924
4925
4926 \backslash
4927 pgfnodeconnline{B3}{B4}
4928 \end_layout
4929
4930 \begin_layout Plain Layout
4931
4932
4933 \backslash
4934 pgfnodeconnline{C1}{C2}
4935 \end_layout
4936
4937 \begin_layout Plain Layout
4938
4939
4940 \backslash
4941 pgfnodeconnline{C2}{C3}
4942 \end_layout
4943
4944 \begin_layout Plain Layout
4945
4946
4947 \backslash
4948 pgfnodeconnline{C3}{C4}
4949 \end_layout
4950
4951 \begin_layout Plain Layout
4952
4953
4954 \backslash
4955 pgfnodeconnline{D1}{D2}
4956 \end_layout
4957
4958 \begin_layout Plain Layout
4959
4960
4961 \backslash
4962 pgfnodeconnline{D2}{D3}
4963 \end_layout
4964
4965 \begin_layout Plain Layout
4966
4967
4968 \backslash
4969 alert<11>{
4970 \backslash
4971 pgfnodeconnline{D3}{D4}}
4972 \end_layout
4973
4974 \begin_layout Plain Layout
4975
4976 }
4977 \end_layout
4978
4979 \begin_layout Plain Layout
4980
4981
4982 \backslash
4983 end{pgfpicture}
4984 \end_layout
4985
4986 \end_inset
4987
4988
4989 \end_layout
4990
4991 \end_deeper
4992 \end_deeper
4993 \begin_layout AgainFrame
4994 \begin_inset Argument 1
4995 status open
4996
4997 \begin_layout Plain Layout
4998
4999 6
5000 \end_layout
5001
5002 \end_inset
5003
5004 hierarchy
5005 \end_layout
5006
5007 \begin_layout Subsection
5008 Complexity of: Approximating the Shortest Path
5009 \end_layout
5010
5011 \begin_layout Frame
5012 \begin_inset Argument 4
5013 status open
5014
5015 \begin_layout Plain Layout
5016 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
5017 \end_layout
5018
5019 \end_inset
5020
5021
5022 \end_layout
5023
5024 \begin_deeper
5025 \begin_layout Definition
5026 An
5027 \color none
5028
5029 \color red
5030 approximation scheme for
5031 \begin_inset Formula $\Lang{tournament-shortest-path}$
5032 \end_inset
5033
5034
5035 \color none
5036
5037 \color inherit
5038 gets as input
5039 \end_layout
5040
5041 \begin_deeper
5042 \begin_layout Enumerate
5043 a tuple
5044 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5045 \end_inset
5046
5047  and
5048 \end_layout
5049
5050 \begin_layout Enumerate
5051 a number
5052 \begin_inset Formula $r>1$
5053 \end_inset
5054
5055 .
5056 \end_layout
5057
5058 \begin_layout Standard
5059 It outputs
5060 \end_layout
5061
5062 \begin_layout Itemize
5063 a path from
5064 \begin_inset Formula $s$
5065 \end_inset
5066
5067  to
5068 \begin_inset space ~
5069 \end_inset
5070
5071
5072 \begin_inset Formula $t$
5073 \end_inset
5074
5075  of length at most
5076 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5077 \end_inset
5078
5079 .
5080 \end_layout
5081
5082 \end_deeper
5083 \end_deeper
5084 \begin_layout Standard
5085 \begin_inset Separator plain
5086 \end_inset
5087
5088
5089 \end_layout
5090
5091 \begin_layout Frame
5092 \begin_inset Argument 4
5093 status open
5094
5095 \begin_layout Plain Layout
5096 There Exists a Logspace Approximation Scheme for
5097 \begin_inset Newline newline
5098 \end_inset
5099
5100 the Tournament Shortest Path Problem
5101 \end_layout
5102
5103 \end_inset
5104
5105
5106 \end_layout
5107
5108 \begin_deeper
5109 \begin_layout Theorem
5110 There exists an approximation scheme for
5111 \begin_inset Formula $\Lang{tournament-shortest-path}$
5112 \end_inset
5113
5114  that for
5115 \begin_inset Formula $1<r<2$
5116 \end_inset
5117
5118  needs space
5119 \begin_inset Formula
5120 \[
5121 O\left(\log|V|\log\frac{1}{r-1}\right).
5122 \]
5123
5124 \end_inset
5125
5126
5127 \end_layout
5128
5129 \begin_layout Pause
5130
5131 \end_layout
5132
5133 \begin_layout Corollary
5134 In tournaments, paths can be constructed in logarithmic space.
5135 \end_layout
5136
5137 \begin_layout Standard
5138 \begin_inset space \hfill{}
5139 \end_inset
5140
5141
5142 \begin_inset ERT
5143 status collapsed
5144
5145 \begin_layout Plain Layout
5146
5147
5148 \backslash
5149 hyperlink{optimality}{
5150 \backslash
5151 beamergotobutton{More Details}}
5152 \end_layout
5153
5154 \end_inset
5155
5156
5157 \end_layout
5158
5159 \end_deeper
5160 \begin_layout AgainFrame
5161 \begin_inset Argument 1
5162 status collapsed
5163
5164 \begin_layout Plain Layout
5165
5166 7
5167 \end_layout
5168
5169 \end_inset
5170
5171 hierarchy
5172 \end_layout
5173
5174 \begin_layout Standard
5175 \begin_inset Note Note
5176 status open
5177
5178 \begin_layout Plain Layout
5179 If a frame includes a program listing, the frame needs to be marked as
5180 \begin_inset Quotes eld
5181 \end_inset
5182
5183 fragile
5184 \begin_inset Quotes erd
5185 \end_inset
5186
5187 .
5188  \SpecialChar LyX
5189  has the FragileFrame layout for this.
5190 \end_layout
5191
5192 \end_inset
5193
5194
5195 \end_layout
5196
5197 \begin_layout FragileFrame
5198 \begin_inset Argument 4
5199 status open
5200
5201 \begin_layout Plain Layout
5202 Just a frame with a program code listing
5203 \end_layout
5204
5205 \end_inset
5206
5207
5208 \end_layout
5209
5210 \begin_layout FragileFrame
5211 This is some program code:
5212 \end_layout
5213
5214 \begin_deeper
5215 \begin_layout Standard
5216 \begin_inset listings
5217 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
5218 inline false
5219 status open
5220
5221 \begin_layout Plain Layout
5222
5223 def func(param):
5224 \end_layout
5225
5226 \begin_layout Plain Layout
5227
5228     'this is a python function'
5229 \end_layout
5230
5231 \begin_layout Plain Layout
5232
5233     pass
5234 \end_layout
5235
5236 \begin_layout Plain Layout
5237
5238 def func(param):
5239 \end_layout
5240
5241 \begin_layout Plain Layout
5242
5243 'This is a German word: Tschüs'
5244 \end_layout
5245
5246 \begin_layout Plain Layout
5247
5248 pass
5249 \end_layout
5250
5251 \begin_layout Plain Layout
5252
5253 def func(param):
5254 \end_layout
5255
5256 \begin_layout Plain Layout
5257
5258 'this is a python function'
5259 \end_layout
5260
5261 \begin_layout Plain Layout
5262
5263 pass
5264 \end_layout
5265
5266 \end_inset
5267
5268
5269 \end_layout
5270
5271 \end_deeper
5272 \begin_layout Section*
5273 Summary
5274 \end_layout
5275
5276 \begin_layout Subsection*
5277 Summary
5278 \end_layout
5279
5280 \begin_layout Frame
5281 \begin_inset Argument 4
5282 status open
5283
5284 \begin_layout Plain Layout
5285 Summary
5286 \end_layout
5287
5288 \end_inset
5289
5290
5291 \end_layout
5292
5293 \begin_deeper
5294 \begin_layout Block
5295 \begin_inset Argument 2
5296 status collapsed
5297
5298 \begin_layout Plain Layout
5299 Summary
5300 \end_layout
5301
5302 \end_inset
5303
5304
5305 \end_layout
5306
5307 \begin_deeper
5308 \begin_layout Itemize
5309 Tournament
5310 \color none
5311
5312 \color red
5313 reachability
5314 \color none
5315
5316 \color inherit
5317 is in
5318 \color none
5319
5320 \color red
5321
5322 \begin_inset Formula $\Class{AC}^{0}$
5323 \end_inset
5324
5325
5326 \color inherit
5327 .
5328
5329 \end_layout
5330
5331 \begin_layout Itemize
5332 There exists a
5333 \color none
5334
5335 \color red
5336 logspace approximation scheme
5337 \color none
5338
5339 \color inherit
5340 for
5341 \color none
5342
5343 \color red
5344 approximating
5345 \color none
5346
5347 \color inherit
5348 shortest paths in tournaments.
5349 \end_layout
5350
5351 \begin_layout Itemize
5352 Finding
5353 \color none
5354
5355 \color red
5356 shortest paths
5357 \color none
5358
5359 \color inherit
5360 in tournaments is
5361 \color none
5362
5363 \color red
5364
5365 \begin_inset Formula $\Class{NL}$
5366 \end_inset
5367
5368 -complete
5369 \color inherit
5370 .
5371 \end_layout
5372
5373 \end_deeper
5374 \begin_layout Standard
5375 \begin_inset Separator plain
5376 \end_inset
5377
5378
5379 \end_layout
5380
5381 \begin_layout Block
5382 \begin_inset Argument 2
5383 status collapsed
5384
5385 \begin_layout Plain Layout
5386 Outlook
5387 \end_layout
5388
5389 \end_inset
5390
5391
5392 \end_layout
5393
5394 \begin_deeper
5395 \begin_layout Itemize
5396 The same results apply to graphs with
5397 \begin_inset Newline newline
5398 \end_inset
5399
5400 bounded independence number.
5401 \begin_inset space \hfill{}
5402 \end_inset
5403
5404
5405 \begin_inset ERT
5406 status collapsed
5407
5408 \begin_layout Plain Layout
5409
5410
5411 \backslash
5412 hyperlink{independence}{
5413 \backslash
5414 beamergotobutton{More Details}}
5415 \end_layout
5416
5417 \end_inset
5418
5419
5420 \end_layout
5421
5422 \begin_layout Itemize
5423 The complexity of finding paths in undirected graphs
5424 \begin_inset Newline newline
5425 \end_inset
5426
5427 is partly open.
5428 \begin_inset space \hfill{}
5429 \end_inset
5430
5431
5432 \begin_inset ERT
5433 status collapsed
5434
5435 \begin_layout Plain Layout
5436
5437
5438 \backslash
5439 hyperlink{undirected}{
5440 \backslash
5441 beamergotobutton{More Details}}
5442 \end_layout
5443
5444 \end_inset
5445
5446
5447 \end_layout
5448
5449 \end_deeper
5450 \end_deeper
5451 \begin_layout Subsection*
5452 For Further Reading
5453 \end_layout
5454
5455 \begin_layout Frame
5456 \begin_inset Argument 4
5457 status open
5458
5459 \begin_layout Plain Layout
5460 For Further Reading
5461 \end_layout
5462
5463 \end_inset
5464
5465
5466 \end_layout
5467
5468 \begin_deeper
5469 \begin_layout Standard
5470 \begin_inset ERT
5471 status open
5472
5473 \begin_layout Plain Layout
5474
5475
5476 \backslash
5477 beamertemplatebookbibitems
5478 \end_layout
5479
5480 \end_inset
5481
5482
5483 \end_layout
5484
5485 \begin_layout Bibliography
5486 \begin_inset CommandInset bibitem
5487 LatexCommand bibitem
5488 key "Moon1968"
5489 literal "true"
5490
5491 \end_inset
5492
5493
5494 \begin_inset space ~
5495 \end_inset
5496
5497 John Moon.
5498
5499 \begin_inset ERT
5500 status collapsed
5501
5502 \begin_layout Plain Layout
5503
5504
5505 \backslash
5506 newblock
5507 \end_layout
5508
5509 \end_inset
5510
5511
5512 \emph on
5513 Topics on Tournaments.
5514
5515 \emph default
5516
5517 \begin_inset ERT
5518 status collapsed
5519
5520 \begin_layout Plain Layout
5521
5522
5523 \backslash
5524 newblock
5525 \end_layout
5526
5527 \end_inset
5528
5529  Holt, Rinehart, and Winston, 1968.
5530
5531 \begin_inset ERT
5532 status collapsed
5533
5534 \begin_layout Plain Layout
5535
5536
5537 \backslash
5538 beamertemplatearticlebibitems
5539 \end_layout
5540
5541 \end_inset
5542
5543
5544 \end_layout
5545
5546 \begin_layout Bibliography
5547 \begin_inset CommandInset bibitem
5548 LatexCommand bibitem
5549 key "NickelsenT2002"
5550 literal "true"
5551
5552 \end_inset
5553
5554
5555 \begin_inset space ~
5556 \end_inset
5557
5558 Arfst Nickelsen and Till Tantau.
5559
5560 \begin_inset ERT
5561 status collapsed
5562
5563 \begin_layout Plain Layout
5564
5565
5566 \backslash
5567 newblock
5568 \end_layout
5569
5570 \end_inset
5571
5572  On reachability in graphs with bounded independence number.
5573 \begin_inset ERT
5574 status collapsed
5575
5576 \begin_layout Plain Layout
5577
5578
5579 \backslash
5580 newblock
5581 \end_layout
5582
5583 \end_inset
5584
5585  In
5586 \emph on
5587 Proc.
5588  of COCOON 2002
5589 \emph default
5590 , Springer-Verlag, 2002.
5591 \end_layout
5592
5593 \begin_layout Bibliography
5594 \begin_inset CommandInset bibitem
5595 LatexCommand bibitem
5596 key "Tantau2004b"
5597 literal "true"
5598
5599 \end_inset
5600
5601
5602 \begin_inset space ~
5603 \end_inset
5604
5605 Till Tantau
5606 \begin_inset ERT
5607 status collapsed
5608
5609 \begin_layout Plain Layout
5610
5611
5612 \backslash
5613 newblock
5614 \end_layout
5615
5616 \end_inset
5617
5618  A logspace approximation scheme for the shortest path problem for graphs
5619  with bounded independence number.
5620 \begin_inset ERT
5621 status collapsed
5622
5623 \begin_layout Plain Layout
5624
5625
5626 \backslash
5627 newblock
5628 \end_layout
5629
5630 \end_inset
5631
5632  In
5633 \emph on
5634 Proc.
5635  of STACS 2004
5636 \emph default
5637 , Springer-Verlag, 2004.
5638
5639 \begin_inset ERT
5640 status collapsed
5641
5642 \begin_layout Plain Layout
5643
5644
5645 \backslash
5646 newblock
5647 \end_layout
5648
5649 \end_inset
5650
5651  In press.
5652 \end_layout
5653
5654 \end_deeper
5655 \begin_layout Standard
5656 \start_of_appendix
5657 \begin_inset ERT
5658 status open
5659
5660 \begin_layout Plain Layout
5661
5662
5663 \backslash
5664 AtBeginSubsection[]{}
5665 \end_layout
5666
5667 \end_inset
5668
5669
5670 \end_layout
5671
5672 \begin_layout Section
5673 Appendix
5674 \end_layout
5675
5676 \begin_layout Subsection
5677 Graphs With Bounded Independence Number
5678 \end_layout
5679
5680 \begin_layout Frame
5681 \begin_inset Argument 3
5682 status collapsed
5683
5684 \begin_layout Plain Layout
5685 label=independence
5686 \end_layout
5687
5688 \end_inset
5689
5690
5691 \begin_inset Argument 4
5692 status open
5693
5694 \begin_layout Plain Layout
5695 Definition of Independence Number of a Graph
5696 \end_layout
5697
5698 \end_inset
5699
5700
5701 \end_layout
5702
5703 \begin_deeper
5704 \begin_layout Definition
5705 The
5706 \color none
5707
5708 \color red
5709 independence number
5710 \color none
5711
5712 \color inherit
5713
5714 \begin_inset Formula $\alpha(G)$
5715 \end_inset
5716
5717  of a directed graph
5718 \begin_inset Newline newline
5719 \end_inset
5720
5721 is the maximum number of vertices we can pick,
5722 \begin_inset Newline newline
5723 \end_inset
5724
5725 such that there is no edge between them.
5726 \end_layout
5727
5728 \begin_layout Example
5729 Tournaments have independence number 1.
5730
5731 \end_layout
5732
5733 \end_deeper
5734 \begin_layout Standard
5735 \begin_inset Separator plain
5736 \end_inset
5737
5738
5739 \end_layout
5740
5741 \begin_layout Frame
5742 \begin_inset Argument 4
5743 status open
5744
5745 \begin_layout Plain Layout
5746 The Results for Tournaments also Apply to
5747 \begin_inset Newline newline
5748 \end_inset
5749
5750 Graphs With Bounded Independence Number
5751 \end_layout
5752
5753 \end_inset
5754
5755
5756 \end_layout
5757
5758 \begin_deeper
5759 \begin_layout Theorem
5760 For each
5761 \begin_inset space ~
5762 \end_inset
5763
5764
5765 \begin_inset Formula $k$
5766 \end_inset
5767
5768 ,
5769 \color none
5770
5771 \color red
5772 reachability
5773 \color none
5774
5775 \color inherit
5776 in graphs with independence number
5777 \begin_inset Newline newline
5778 \end_inset
5779
5780 at most
5781 \begin_inset space ~
5782 \end_inset
5783
5784
5785 \begin_inset Formula $k$
5786 \end_inset
5787
5788  is in
5789 \begin_inset Formula $\Class{AC}^{0}$
5790 \end_inset
5791
5792 .
5793 \end_layout
5794
5795 \begin_layout Standard
5796 \begin_inset Separator plain
5797 \end_inset
5798
5799
5800 \end_layout
5801
5802 \begin_layout Theorem
5803 For each
5804 \begin_inset space ~
5805 \end_inset
5806
5807
5808 \begin_inset Formula $k$
5809 \end_inset
5810
5811 , there exists a
5812 \color none
5813
5814 \color red
5815 logspace approximation scheme
5816 \color none
5817
5818 \color inherit
5819 for approximating the shortest path in graphs with independence number at
5820  most
5821 \begin_inset space ~
5822 \end_inset
5823
5824
5825 \begin_inset Formula $k$
5826 \end_inset
5827
5828
5829 \end_layout
5830
5831 \begin_layout Standard
5832 \begin_inset Separator plain
5833 \end_inset
5834
5835
5836 \end_layout
5837
5838 \begin_layout Theorem
5839 For each
5840 \begin_inset space ~
5841 \end_inset
5842
5843
5844 \begin_inset Formula $k$
5845 \end_inset
5846
5847 , finding the
5848 \color none
5849
5850 \color red
5851 shortest path
5852 \color none
5853
5854 \color inherit
5855 in graphs with independence number at most
5856 \begin_inset space ~
5857 \end_inset
5858
5859
5860 \begin_inset Formula $k$
5861 \end_inset
5862
5863  is
5864 \color none
5865
5866 \color red
5867
5868 \begin_inset Formula $\Class{NL}$
5869 \end_inset
5870
5871 -complete
5872 \color inherit
5873 .
5874 \end_layout
5875
5876 \end_deeper
5877 \begin_layout Subsection
5878 Finding Paths in Undirected Graphs
5879 \end_layout
5880
5881 \begin_layout Frame
5882 \begin_inset Argument 1
5883 status collapsed
5884
5885 \begin_layout Plain Layout
5886
5887 1-2
5888 \end_layout
5889
5890 \end_inset
5891
5892
5893 \begin_inset Argument 3
5894 status collapsed
5895
5896 \begin_layout Plain Layout
5897 label=undirected
5898 \end_layout
5899
5900 \end_inset
5901
5902
5903 \begin_inset Argument 4
5904 status open
5905
5906 \begin_layout Plain Layout
5907 The Complexity of Finding Paths in Undirected Graphs
5908 \begin_inset Newline newline
5909 \end_inset
5910
5911 Is Party Unknown.
5912 \end_layout
5913
5914 \end_inset
5915
5916
5917 \end_layout
5918
5919 \begin_deeper
5920 \begin_layout Fact
5921 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
5922 \end_inset
5923
5924  is
5925 \begin_inset Formula $\Class{SL}$
5926 \end_inset
5927
5928 -complete.
5929 \end_layout
5930
5931 \begin_layout Corollary
5932 For undirected graphs, we can solve
5933 \end_layout
5934
5935 \begin_deeper
5936 \begin_layout Itemize
5937 the reachability problem in logspace iff
5938 \begin_inset Formula $\Class L=\Class{SL}$
5939 \end_inset
5940
5941 ,
5942 \end_layout
5943
5944 \begin_layout Itemize
5945 the construction problem in logspace iff
5946 \begin_inset Flex Alternative
5947 status open
5948
5949 \begin_layout Plain Layout
5950 \begin_inset Argument 1
5951 status open
5952
5953 \begin_layout Plain Layout
5954
5955 1
5956 \end_layout
5957
5958 \end_inset
5959
5960
5961 \begin_inset Argument 2
5962 status open
5963
5964 \begin_layout Plain Layout
5965 ?
5966 \end_layout
5967
5968 \end_inset
5969
5970
5971 \begin_inset Flex Alert
5972 status open
5973
5974 \begin_layout Plain Layout
5975 \begin_inset Formula $\Class L=\Class{SL}$
5976 \end_inset
5977
5978
5979 \end_layout
5980
5981 \end_inset
5982
5983
5984 \end_layout
5985
5986 \end_inset
5987
5988 ,
5989 \end_layout
5990
5991 \begin_layout Itemize
5992 the optimization problem in logspace iff
5993 \begin_inset Flex Alternative
5994 status open
5995
5996 \begin_layout Plain Layout
5997 \begin_inset Argument 1
5998 status open
5999
6000 \begin_layout Plain Layout
6001
6002 1
6003 \end_layout
6004
6005 \end_inset
6006
6007
6008 \begin_inset Argument 2
6009 status open
6010
6011 \begin_layout Plain Layout
6012 ?
6013 \end_layout
6014
6015 \end_inset
6016
6017
6018 \begin_inset Flex Alert
6019 status open
6020
6021 \begin_layout Plain Layout
6022 \begin_inset Formula $\Class L=\Class{NL}$
6023 \end_inset
6024
6025
6026 \end_layout
6027
6028 \end_inset
6029
6030
6031 \end_layout
6032
6033 \end_inset
6034
6035 ,
6036 \end_layout
6037
6038 \begin_layout Itemize
6039 the approximation problem in logspace iff ?.
6040
6041 \end_layout
6042
6043 \end_deeper
6044 \end_deeper
6045 \begin_layout Subsection
6046 The Approximation Scheme is Optimal
6047 \end_layout
6048
6049 \begin_layout Frame
6050 \begin_inset Argument 3
6051 status collapsed
6052
6053 \begin_layout Plain Layout
6054 label=optimality
6055 \end_layout
6056
6057 \end_inset
6058
6059
6060 \begin_inset Argument 4
6061 status open
6062
6063 \begin_layout Plain Layout
6064 The Approximation Scheme is Optimal
6065 \end_layout
6066
6067 \end_inset
6068
6069
6070 \end_layout
6071
6072 \begin_deeper
6073 \begin_layout Theorem
6074 Suppose there exists an approximation scheme for
6075 \begin_inset Formula $\Lang{tournament-shortest-path}$
6076 \end_inset
6077
6078  that needs space
6079 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6080 \end_inset
6081
6082 .
6083  Then
6084 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6085 \end_inset
6086
6087 .
6088 \end_layout
6089
6090 \begin_layout Proof
6091
6092 \end_layout
6093
6094 \begin_deeper
6095 \begin_layout Enumerate
6096 Suppose the approximation scheme exists.
6097 \begin_inset Newline newline
6098 \end_inset
6099
6100 We show
6101 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6102 \end_inset
6103
6104 .
6105
6106 \end_layout
6107
6108 \begin_layout Enumerate
6109 Let
6110 \begin_inset Formula $(T,s,t)$
6111 \end_inset
6112
6113  be an input.
6114  Let
6115 \begin_inset Formula $n$
6116 \end_inset
6117
6118  be the number of vertices.
6119 \end_layout
6120
6121 \begin_layout Enumerate
6122 Run the approximation scheme for
6123 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6124 \end_inset
6125
6126 .
6127 \begin_inset Newline newline
6128 \end_inset
6129
6130 This needs space
6131 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6132 \end_inset
6133
6134 .
6135 \end_layout
6136
6137 \begin_layout Enumerate
6138 The resulting path has optimal length.
6139
6140 \begin_inset ERT
6141 status collapsed
6142
6143 \begin_layout Plain Layout
6144
6145
6146 \backslash
6147 qedhere
6148 \end_layout
6149
6150 \end_inset
6151
6152
6153 \end_layout
6154
6155 \end_deeper
6156 \end_deeper
6157 \end_body
6158 \end_document