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

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