Training Program Evaluation and Enhancement
Training materials are deemed dry and lack real-life practice scenarios. Recommendations include implementing a blended learning approach with technology-driven resources and simulation activities to improve learning outcomes.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Detecting and Counting Small Patterns in Planar Graphs (in Subexponential Parameterized Time) STOC 2020 -- online Jesper Nederlof (Utrecht University)
(Induced) Subgraph Isomorphism Problem ? ? Given a pattern graph ? and a host graph ?, does ? occur as an (induced) subgraph of ??
(Induced) Subgraph Isomorphism Problem ? ? Given a pattern graph ? and a host graph ?, does ? occur as an (induced) subgraph of ?? 2 1 2 3 4 3 1 4 5 6 5 6
(Induced) Subgraph Isomorphism Problem ? ? Given a pattern graph ? and a host graph ?, does ? occur as an (induced) subgraph of ?? 1 Natural problem. Generalizes Hamiltonian Cycle / Longest Path, Clique / Independent Set, . 2 2 3 1 4 4 5 5 6 3 6 In this talk we assume ? planar; So ? planar as well Still NP-complete! Counting version: count number of subgraph occurrences
Results for Planar (Induced) Subgraph Isomorphism Notes 1. Can it avoid random bits? 2. Can it count all pattern occurrences? 3. Expressed in ? ? ? , ? ? ? , omitting ??(1)factors Deterministic1 Counting2 Runtime3 Reference Pattern Restriction ?
Results for Planar (Induced) Subgraph Isomorphism Notes 1. Can it avoid random bits? 2. Can it count all pattern occurrences? 3. Expressed in ? ? ? , ? ? ? , omitting ??(1)factors Deterministic1 Counting2 Runtime3 Reference [MT92] Pattern Restriction ? connected bounded degree YES YES ??(?)
Results for Planar (Induced) Subgraph Isomorphism Notes 1. Can it avoid random bits? 2. Can it count all pattern occurrences? 3. Expressed in ? ? ? , ? ? ? , omitting ??(1)factors Deterministic1 Counting2 Runtime3 Reference [MT92] [Epp99] Pattern Restriction ? connected bounded degree - YES YES ??(?) YES YES ??(?)
Results for Planar (Induced) Subgraph Isomorphism Notes 1. Can it avoid random bits? 2. Can it count all pattern occurrences? 3. Expressed in ? ? ? , ? ? ? , omitting ??(1)factors Deterministic1 Counting2 Runtime3 Reference [MT92] [Epp99] [Dor07] Pattern Restriction ? connected bounded degree - undirected path YES YES ??(?) YES YES ??(?) YES NO 2?( ?)
Results for Planar (Induced) Subgraph Isomorphism Notes 1. Can it avoid random bits? 2. Can it count all pattern occurrences? 3. Expressed in ? ? ? , ? ? ? , omitting ??(1)factors Deterministic1 Counting2 Runtime3 Reference [MT92] [Epp99] [Dor07] Pattern Restriction ? connected bounded degree - undirected path YES YES ??(?) YES YES ??(?) YES NO 2?( ?) [Dor10] - YES YES 2?(?)
Results for Planar (Induced) Subgraph Isomorphism Notes 1. Can it avoid random bits? 2. Can it count all pattern occurrences? 3. Expressed in ? ? ? , ? ? ? , omitting ??(1)factors 4. Not in 2?(?/ log ?)time, assuming ETH Deterministic1 Counting2 Runtime3 Reference [MT92] [Epp99] [Dor07] Pattern Restriction ? connected bounded degree - undirected path YES YES ??(?) YES YES ??(?) YES NO 2?( ?) [Dor10] [BNvdZ16] - - YES YES 2?(?) 4 YES YES 2?(?/log ?)
Results for Planar (Induced) Subgraph Isomorphism Notes 1. Can it avoid random bits? 2. Can it count all pattern occurrences? 3. Expressed in ? ? ? , ? ? ? , omitting ??(1)factors 4. Not in 2?(?/ log ?)time, assuming ETH Deterministic1 Counting2 Runtime3 Reference [MT92] [Epp99] [Dor07] Pattern Restriction ? connected bounded degree - undirected path YES YES ??(?) YES YES ??(?) YES NO 2?( ?) [Dor10] [BNvdZ16] - - connected bounded degree YES YES 2?(?) 4 YES YES 2?(?/log ?) NO NO 2 ?( ?) [FLM+16] directed path NO NO 2 ?( ?)
Results for Planar (Induced) Subgraph Isomorphism Notes 1. Can it avoid random bits? 2. Can it count all pattern occurrences? 3. Expressed in ? ? ? , ? ? ? , omitting ??(1)factors 4. Not in 2?(?/ log ?)time, assuming ETH Deterministic1 Counting2 Runtime3 Reference [MT92] [Epp99] [Dor07] Pattern Restriction ? connected bounded degree - undirected path YES YES ??(?) YES YES ??(?) YES NO 2?( ?) [Dor10] [BNvdZ16] - - connected bounded degree YES YES 2?(?) 4 YES YES 2?(?/log ?) NO NO 2 ?( ?) [FLM+16] directed path NO NO 2 ?( ?) [BNvdZ16] &[FLM+16] connected NO NO 2?(?/ log ?)
Results for Planar (Induced) Subgraph Isomorphism Notes 1. Can it avoid random bits? 2. Can it count all pattern occurrences? 3. Expressed in ? ? ? , ? ? ? , omitting ??(1)factors 4. Not in 2?(?/ log ?)time, assuming ETH Deterministic1 Counting2 Runtime3 Reference [MT92] [Epp99] [Dor07] Pattern Restriction ? connected bounded degree - undirected path YES YES ??(?) YES YES ??(?) YES NO 2?( ?) [Dor10] [BNvdZ16] - - connected bounded degree YES YES 2?(?) 4 YES YES 2?(?/log ?) NO NO 2 ?( ?) [FLM+16] directed path NO NO 2 ?( ?) [BNvdZ16] &[FLM+16] connected NO NO 2?(?/ log ?) - connected bounded degree, independent set, matching YES YES 2?(?/ log ?) this work YES YES 2 ?( ?)
Our Contribution Main Theorem Number of occurrences of ? as (induced) subgraph of ? can be computed in time 2 ? where ?(?) is the number of non-isomorphic separations of ? of order ?. ?? ? ??(1), ? ? is 2 ? ? ? is 2?(?/ log ?) ?if e.g. ? is independent set, matching or connected bounded degree Settles complexity of detecting and counting patterns in planar graphs Derandomizes previous work, extends to most general pattern classes Previously, no 2?(?)time counting algorithms were known for any non-trivial case Now we have ETH-optimal counting algorithms for all natural pattern classes
Our Approach Starts from Baker s technique (as applied by Eppstein for SI) 1. Pick a vertex ? ? ? arbitrarily 2. Partition ?(?) into ?1, ,??+1, where ?? {? ? ? : dist ?,? ?+1?} 3. For each ?, search for pattern occurrences in ? ?? Crux For every ?, the graph ? ??has treewidth ?(?) s
Our Approach Starts from Baker s technique (as applied by Eppstein for SI) 1. Pick a vertex ? ? ? arbitrarily 2. Partition ?(?) into ?1, ,??+1, where ?? {? ? ? : dist ?,? ?+1?} 3. For each ?, search for pattern occurrences in ? ?? Crux For every ?, the graph ? ??has treewidth ?(?) Problem Treewidth bound only gives 2?(?)time algorithms s Baker s separator ?? doesn t make enough progress! Main Technique 1: `Balanced Cycle Separator Sparsification Start with a balanced cycle separator ?? Construct equally-balanced cycle separators with limited mutual overlap
Main Technique 1: Sparsifying Balanced Cycle Separators Lemma Let a triangulated graph ? with a cycle ? on ? vertices be given. There exist cycles ?1, ,??and sets ?1, ,??with ?? ?(??) such that: 1. ? ?? ?? = ?(? log?) 2. for each ? ? a) ? is disjoint from ??, b) |?(??) ?| = ? ? log ? , c) if ? is ?-balanced2for ?, then ??is max{?,3/4}-balanced for ?. 3. ? is at most ?? log ? Moreover, the ?? s and ?? s can be constructed in (??)?(1)time. Notes 1. Sum of weight equals 1 2. Sum of weights of the interior (exterior) of ? are at most ? Each planar graph of ?(?) treewidth has balanced separators of ?(?)! Completely oblivious to ?! and normalized1?:? ? , there is an ? s.t: ?(?) Proof technique is an adaptive recursive procedure Inspired by proof of grid minor theorem Key ingredient is a generalization of Menger s theorem from [FLM+16]
Our Approach Starts from Baker s technique (as applied by Eppstein for SI) 1. Pick a vertex ? ? ? arbitrarily 2. Partition ?(?) into ?1, ,??+1, where ?? {? ? ? : dist ?,? ?+1?} 3. For each ?, search for pattern occurrences in ? ?? Crux For every ?, the graph ? ??has treewidth ?(?) Problem Treewidth bound only gives 2?(?)time algorithms s Baker s separator ?? doesn t make enough progress! Main Technique 1: `Balanced Cycle Separator Sparsification Start with a balanced cycle ?? Construct equally-balanced cycle separators with limited mutual overlap Gives separators of size ?(?) of which ? ? are in the pattern occurrence ?(?) ? ? Can use dynamic programming table index with Balance either with respect to #vx s in ?(?) or in pattern occurrence mappings
Our Approach Starts from Baker s technique (as applied by Eppstein for SI) 1. Pick a vertex ? ? ? arbitrarily 2. Partition ?(?) into ?1, ,??+1, where ?? {? ? ? : dist ?,? ?+1?} 3. For each ?, search for pattern occurrences in ? ?? Crux For every ?, the graph ? ??has treewidth ?(?) s Problem Hard to extend to counting problems! Even unclear how to count independent sets on k vx s in subgraphs of grids! Main Technique 2: `Efficient Inclusion-Exclusion Define #? ??(?) #Ind. sets of ? of size ? ? #? ??(?) #? ??(? ??) ? #? ??(?) ?=0
Our Approach Starts from Baker s technique (as applied by Eppstein for SI) 1. Pick a vertex ? ? ? arbitrarily 2. Partition ?(?) into ?1, ,??+1, where ?? {? ? ? : dist ?,? ?+1?} 3. For each ?, search for pattern occurrences in ? ?? Crux For every ?, the graph ? ??has treewidth ?(?) s Problem Hard to extend to counting problems! Even unclear how to count independent sets on k vx s in subgraphs of grids! Main Technique 2: `Efficient Inclusion-Exclusion Define #? ??(?) #Ind. sets of ? of size ? By inclusion-exclusion ? 1#? ?? ? #? ??(?) = 1 ? ??? ? 0, ,? This sum has too many terms, but we show only ?(?2) are independent
Our Approach Starts from Baker s technique (as applied by Eppstein for SI) 1. Pick a vertex ? ? ? arbitrarily 2. Partition ?(?) into ?1, ,??+1, where ?? {? ? ? : dist ?,? ?+1?} 3. For each ?, search for pattern occurrences in ? ?? Crux For every ?, the graph ? ??has treewidth ?(?) s Problem Hard to extend to counting problems! Even unclear how to count independent sets on k vx s in subgraphs of grids! Main Technique 2: `Efficient Inclusion-Exclusion Define #? ??(?) #Ind. sets of ? of size ? By inclusion-exclusion ? 1#? ?? ? #? ??(?) = 1 ? ??? ? 0, ,? This sum has too many terms, but we show only ?(?2) are independent
Summary General algorithm for counting (induced) patterns in planar graphs Detecting Patterns For several pattern graphs, the first deterministic algorithm that runs in time sub-exponential in ? Resolves the complexity of general planar SI: In 2?(?/ log ?)time (and not in 2?(?/ log ?)time assuming ETH [BNvdZ16]) In 2 ?( ?)time for most natural patterns (and not in 2?( ?)assuming ETH by standard reductions ) Counting Patterns Before our work, no 2?(?)time algorithms were known for special cases such as counting independent sets of size ? in subgraphs of grids We match the run times of the counting version with the detection version Settling the complexity of counting patterns in planar graphs assuming ETH Techniques: `Balanced Cycle Separator Sparsification and `Efficient Inclusion-Exclusion
