Counting Small Patterns in Planar Graphs: Subgraph Isomorphism Study
This study delves into detecting and counting small patterns in planar graphs, focusing on subgraph isomorphism. It explores the concept of subgraph isomorphism, its relevance in various settings with graphical data, and the solvability of the problem in practice and theory. The research session initiated by Viresh Patel in November 2017 forms the starting point for investigating independent sets in planar graphs. Furthermore, significant breakthroughs, such as Babai's solution to the Graph Isomorphism problem in subexponential time, are highlighted.
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) Jesper Nederlof
Starting Point this Research Problem session training week 5, November 2017: Viresh Patel: Count independent sets on ? vertices in n-vertex planar graphs in 2?(?)??(1)time.
subGraph Isomorphism Given two graphs (say ?1and ?2), do they represent the same network?
subGraph Isomorphism Given two graphs (say ?1and ?2), do they represent the same network? 3 1 3 2 4 7 1 4 2 8 5 5 8 6 6 7 Formally, is there a bijective function ?: ? ?1 {?,?} ? ?1 if and only if {?(?),?(?)} ?(?2)? ?(?2) such that
subGraph Isomorphism Relevant for any setting with graphical data e.g. images (fingerprints, handwriting) molecules social networks Solvable relatively fast in practice (NAUTY) In theory, major open question whether in polynomial time Very exciting breakthrough in December 2016 by Babai: Solves GI in 2O(log??) time on ?-vertex graphs, for some constant ?
Subgraph Isomorphism Given a pattern graph ? and host graph ?, does ? occur as subgraph of ??
Subgraph Isomorphism Given a pattern graph ? and host graph ?, does ? occur as subgraph of ??
Subgraph Isomorphism Given a pattern graph ? and host graph ?, does ? occur as subgraph of ?? 2 1 4 3 2 1 3 4 5 6 5 6 Formally, is the set ???(?,?) empty? ??? ?,? = { ?: ? ? ?(?): {?,?} ? ? implies {?(?),?(?)} ?(?) } We also study induced isomorphisms: ??? ?,? = { ?: ? ? ?(?): {?,?} ? ? iff {?(?),?(?)} ?(?) }
Subgraph Isomorphism We denote ? for #vertices of ?, ? for #vertices of ? Subgraph Isomorphism is ???(?,?) empty? Hamiltonian Cycle if ? is a cycle on ? vertices Clique is ? is a complete graph Matching if ? is a matching Induced Subgraph Isomorphism is ???(?,?) empty? Independent set if ? is an independent set Both NP-complete! We focus on computing |???(?,?)| and |???(?,?)| for small P and planar ? Can directly be used to count HC s, matchings, independent sets
Results for Planar Subgraph Isomorphism Assuming the Exponential Time Hypothesis (ETH), none of the results cannot be significantly improved
Count Patterns in Planar Graphs in Subexponential Time Jesper 1. Efficient Inclusion-Exclusion 2. Menger-like Lemma from [FLMPPS (FOCS 16)] 3. Divide & Conquer to sparsify balanced separators 4. Technique from [BNvdZ (ICALP 16)]
Inclusion-Exclusion Expresses the size of a union in terms of sizes of intersections ?1 ?2 = ?1+ ?2 ?1 ?2 Generalizes to ? sets: If ?1, ,?? are sets, then ? 1 ?? = 1 ?? ? [?] ? ? ? ?
Efficient `Inclusion-Exclusion Input: Subgraph of the (? ?)-grid ?, integer ? Output: #independent sets of ? of size ? (#?-IS(?)) Known techniques give 2?(?)??(1) time 1 2 ? 1 2 ? 1 2 ? We ll now sketch a ??( ?)??(1) time algorithm First step: solve special case:? ? Number columns consecutively 1 , ? This partitions columns in ?groups ?1, ,?? Let ? be an IS with ? ? There is an ? with |?? ?| For each ?, compute #k-IS ?, ? ? Only with columns in ??, use dynamic programming. ? options for intersection where ? is the smallest (!) in s.t. |?? ?| ?
Efficient `Inclusion-Exclusion Input: Subgraph of the (? ?)-grid ?, integer ? Output: #independent sets of ? of size ? (#?-IS(?)) Known techniques give 2?(?)??(1) time 1 2 ? 1 2 ? 1 2 ? We ll now sketch a ??( ?)??(1) time algorithm First step: solve special case:? ? Number columns consecutively 1 , ? This partitions columns in ?groups ?1, ,?? Let ? be an IS with ? ? There is an ? with |?? ?| For each ?, compute #k-IS ?, ? ? Only with columns in ??, use dynamic programming. ? options for intersection where ? is the smallest (!) in s.t. |?? ?| ?
Efficient `Inclusion-Exclusion Second step: reduce ? to ? Number rows consecutively 1 ,? + 1 Partition rows in ? + 1groups ?1, ,??+1 Let ? be an IS with ? ? There is an ? with ?? ? = For each ?, compute #k-IS of ? ??; sum values Gives already a (? + 1) factor approximation! 1 2 3 k+1 1 2 3 k+1 [?-IS s avoiding 2 of the Ri s are overcounted] For each ? < ?, subtract #?-IS of ? ?? ?? [?-IS s avoiding 3 of the Ri s are undercounted] For each ? < ? < ?, add #?-IS of ? ?? ?? ?? 1 2
Efficient `Inclusion-Exclusion Second step: reduce ? to ? Number rows consecutively 1 ,? + 1 Partition rows in ? + 1groups ?1, ,??+1 Let ? be an IS with ? ? There is an ? with ?? ? = Apply IE ?? {?-?? ? s.t. ? ??= } 1 2 3 k+1 1 2 3 ? 1#? IS(?[? ?? = 1 ??]) k+1 1 2 ? [?+1] ? ? ? ?+1 ??+1 1 #? IS(?[? ??]) = #?? IS(?[ ??]) ?=??+1 ?0, ,? ?=0 ? {?1< <? }
Conclusion Optimal (assuming ETH) algorithms for Induced Subgraph Isomorphism Before our work, for many pattern only randomized algorithms were known Decision versions can be solved equally fast as counting versions For most patterns, this running time is 2 ?( ?)??(1) Before our work a running time 2?(?)??(1) remained elusive even for basic patterns as independent sets and matchings Still lots of opportunities for follow-up work Thanks for your attention!
