Treewidth Meets Planar Separator Theorem and Tree Decomposition
Explore the intersection of treewidth and planar separator theorem, discussing the effectiveness for planar graphs and the maximum independent set problem. Learn about tree decomposition and its role in graph theory.
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
Treewidth meets Planarity Jesper Nederlof CO seminar 15/02/2019, Eindhoven
Treewidth meets Planar Separator Theorem Treewidth Especially effective for planar graphs: Planar separator theorem: If ? is planar, can partition ?(?) in ?,?,? such that no edges between ? and ?, ? 11 ?, ? , ? 9?/10. measures how well a graph can be `decomposed in a tree-like way A S B
Treewidth meets Planar Separator Theorem Max Independent set (IS): Given ? = (?,?)find largest ? ?without edges Thm: Max IS on planar graphs in 2?( ?) time Let S be separator, ?1, ,?? be connected components of ? ? ? For every independent set ? of ?[?] Recursively find max IS of ?[?? ?(?)] for ? = 1, ,? Return union with ? 2? ( ? ? ?? ) Recurrence: ? ? Can show that 21000 ? fits for ? large enough easily: T(n) n 211 ?T(9n/10) ?211 ?+1000 9?/10 21000 ?
Treewidth Refer to as a bag. Definition A tree decomposition of graph ? = ?,? is a pair (?,?) where ? = {?1, ,??} with ?? ? and ? a tree with vertex set ? such that 1. ?=1 ??= ?, 2. ? ?=1 ?? ??, 3. ? ?: all ?? containing ? induce connected subtree if ?. ? ?
Treewidth Refer to as a bag. Definition A tree decomposition of graph ? = ?,? is a pair (?,?) where ? = {?1, ,??} with ?? ? and ? a tree with vertex set ? such that 1. ?=1 ??= ?, 2. ? ?=1 ?? ??, 3. ? ?: all ?? containing ? induce connected subtree if ?. ? ?
Treewidth Refer to as a bag. Definition A tree decomposition of graph ? = ?,? is a pair (?,?) where ? = {?1, ,??} with ?? ? and ? a tree with vertex set ? such that 1. ?=1 ??= ?, 2. ? ?=1 ?? ??, 3. ? ?: all ?? containing ? induce connected subtree if ?. ? ? b a c d e h f g
Treewidth Refer to as a bag. Definition A tree decomposition of graph ? = ?,? is a pair (?,?) where ? = {?1, ,??} with ?? ? and ? a tree with vertex set ? such that 1. ?=1 ??= ?, 2. ? ?=1 ?? ??, 3. ? ?: all ?? containing ? induce connected subtree if ?. ? ? b a b a c d d e h f g
Treewidth Refer to as a bag. Definition A tree decomposition of graph ? = ?,? is a pair (?,?) where ? = {?1, ,??} with ?? ? and ? a tree with vertex set ? such that 1. ?=1 ??= ?, 2. ? ?=1 ?? ??, 3. ? ?: all ?? containing ? induce connected subtree if ?. ? ? b a b a c d b dg d e h f g
Treewidth Refer to as a bag. Definition A tree decomposition of graph ? = ?,? is a pair (?,?) where ? = {?1, ,??} with ?? ? and ? a tree with vertex set ? such that 1. ?=1 ??= ?, 2. ? ?=1 ?? ??, 3. ? ?: all ?? containing ? induce connected subtree if ?. ? ? b a b a c d b dg d e d f g h f g
Treewidth Refer to as a bag. Definition A tree decomposition of graph ? = ?,? is a pair (?,?) where ? = {?1, ,??} with ?? ? and ? a tree with vertex set ? such that 1. ?=1 ??= ?, 2. ? ?=1 ?? ??, 3. ? ?: all ?? containing ? induce connected subtree if ?. ? ? b a b a c d b be dg g d e d f g h f g
Treewidth Refer to as a bag. Definition A tree decomposition of graph ? = ?,? is a pair (?,?) where ? = {?1, ,??} with ?? ? and ? a tree with vertex set ? such that 1. ?=1 ??= ?, 2. ? ?=1 ?? ??, 3. ? ?: all ?? containing ? induce connected subtree if ?. ? ? b c e b a b a c d b be dg g d e d f g h f g
Treewidth Refer to as a bag. Definition A tree decomposition of graph ? = ?,? is a pair (?,?) where ? = {?1, ,??} with ?? ? and ? a tree with vertex set ? such that 1. ?=1 ??= ?, 2. ? ?=1 ?? ??, 3. ? ?: all ?? containing ? induce connected subtree if ?. ? ? Separates a, f and ceh. b c e b a b a c d b be dg g d e d e f g g h h f g
Treewidth Refer to as a bag. Definition A tree decomposition of graph ? = ?,? is a pair (?,?) where ? = {?1, ,??} with ?? ? and ? a tree with vertex set ? such that 1. ?=1 ??= ?, 2. ? ?=1 ?? ??, 3. ? ?: all ?? containing ? induce connected subtree if ?. ? ? Definition The width of a treedecomposition is treewidth of a graph is the minimum width among all possible tree decompositions of G. . The
Treewidth meets Planar Separator Theorem Treewidth is very useful because many NP-complete problems can be solved in ???? (or more generally ? ?? ?)on ?-vertex graphs of treewidth ?? Cool question: try to find optimal ?! For example: ????(1), and not in Thm[CKN]: Hamiltonian cycle in 2 + 2 ????(1) unless ?-var CNF-SAT in 2 ????(1) 2 + 2 ?
Graph Minor ? is a minor of ?: ? can be obtained from ? with edge deletion, vertex deletion and edge contraction a f a f Edge contraction: b d e g de b g c h i c h i is a minor of Fact: If ? is a minor of ? and ? has treewidth ??, then ? has treewidth at most ??.
Grid Minors (? ?)-grid Grid Minor Theorem For every integer ?, every planar graph either has a (? ?)-grid as a minor, or treewidth at most 9?. Proof uses max-flow min-cut arguments Def (?-outer planar graphs): If you subsequently remove the vertices on the outer boundary ? times, you removed all vertices. A minor of an ?-outer planar graph is ?-outerplanar, thus: ?-outer planar graphs have no (? ?)-grid minor, thus: ?-outer planar graphs have treewidth ?(?).
Bakers approach for approximation in planar graphs Given planar graph ?. Finds IS of size 1 ? |???| in ?(2?(1/?) ?2) time Pick vertex ? arbitrarily. Do BFS from ? Let ?? be all vertices at distance ? Let ? = 1/? Let ??= ? ? (??? ?)?? ?? ?4 ?3 ?2 ?1 s
Bakers approach for approximation in planar graphs Given planar graph ?. Finds IS of size 1 ? |???| in ?(2?(1/?) ?2) time Pick vertex ? arbitrarily. Do BFS from ? Let ?? be all vertices at distance ? Let ? = 1/? Let ??= ? ? (??? ?)?? For ? = 1, ,? Find max size IS of ? ?? Can be done in 2?(?)? time: all components of ? ?? are ?-outer-planar! Thus 2??? runs in 2?? = 21/?? time For ? ?, ? ?? is disjoint from ? ??, thus for some ?: ??? ?? |???|(1 1/?) ?? ?4 ?3 ?2 ?1 s Return largest IS found
`Bidimensionality Fancy word for relatively simple `win/win trick. Say want to determine if ? has a simple path on ? vertices Think ? ? If ? has a ( ? ?)-grid minor -> YES Otherwise treewidth ?( ?) Can solve the problem in 2?( ?)??(1) time Doesn t work for all problems
Beyond Bidimensionality Theorem Theorem(FLMPPS, FOCS 16) Given planar graph ? and int ?, can in poly time sample ? ?(?) s.t.: 1. ?[?] has treewidth ?( ?log?), ?(?) ? with ?[?] connected, Pr ? ? (2 ? New problems solvable in 2 ? Weighted, Directed ?-path, cycle of length exactly ? Subgraph Isomorphism with ?-vertex connected Still leaves open challenges: 1. Derandomize 2. Relax connectivity restriction 3. 2 ? ?|?|) 1. 2. for each ? ? probabilistic probabilistic time. For example: connected pattern of bounded degree (in [FLMPPS]) ? time for counting variants (in several open problem sessions/talks)
