Inclusion-Exclusion Seminar on Exact Exponential Algorithms
Explore the Inclusion-Exclusion Principle in exact exponential algorithms with a focus on computing matrices, perfect matchings in bipartite graphs, and more. Dive into algorithms like bin packing, coverings, and graph coloring for a comprehensive understanding of this mathematical concept.
Uploaded on | 0 Views
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
Inclusion-Exclusion Seminar on exact exponential algorithms Keren Solodkin Based on Chapter 4 in Exact exponential algorithms, Fomin, Kratsch, 2010 (FK)
Plan The Inclusion-Exclusion Principle Some Inclusion-Exclusion Algorithms Computing the Permanent of a Matrix Directed Hamiltonian Path Bin Packing Coverings Graph Coloring Polynomial space
The Inclusion-Exclusion Principle ? 1 , ? 2 , ,? ? properties ? ? - Objects having none of the properties ? ? for ? ? ? - The number of objects having all properties ?? ? = ? = 1 ? 1,2, ,? = ? ? 1 +? 1,2 ? 2 + + ? ? 1,? ? 1,2, ,? ? ?
The Inclusion-Exclusion Principle ? 1 ???, ? 2 ??? ? All objects, ? 1 ? 2 Not big objects, ? 1,2 ? The number of objects having all properties (Red and Big) ? = ? ? 1 ? 2 Not red objects Neither red or big objects + ? 1,2 = 12 7 8 + 4 = 1
Some Inclusion-Exclusion Algorithms
Computing the Permanent of a Matrix ? = ???,?,? 1, ,? ,??? 0,1 ? ???? ? = ??,? ? ? ?? ?12 ?22 ?32 ?=1 ?13 ?23 ?33 ?11 ?21 ?31 ? = ???? ? = a11a22a33+ a11a23a32+ a12a21a33+ a12a23a31+ a13a21a32+ a13a22a31 The trivial algorithm runs in ? ?!
Counting Perfect Matchings in Bipartite Graphs A matching ? of a graph ? = ?,? is perfect if ? is an edge cover of ? 1 a 2 b 3 c 4 d
Counting Perfect Matchings in Bipartite Graphs ? = ?,? - Bipartite graph with bipartition ?,? ??= ??? , ???= 1 ??,?? ? ?? ?????? 0 ? ?=1 The number of perfect matchings in ? is ??? ? = 1 ? ??? ? = ???? ?? ? ?? ?=1
Counting Perfect Matchings in Bipartite Graphs ? = ?,? - Bipartite graph with bipartition ?,? ? = ? ? ? = ?, ? ?. ? ?. ?,? ? ?1,?1, ?2,?1, ?3,?2 , ?1,?1, ?2,?2, ?3,?2 , ?1,?1, ?2,?3, ?3,?2 , ?1,?1, ?2,?1, ?3,?3 , ?1,?1, ?2,?2, ?3,?3 , ?1,?1, ?2,?3, ?3,?3 , ? =
Counting Perfect Matchings in Bipartite Graphs ? = ?,? - Bipartite graph with bipartition ?,? ? = ? ? ? = ?, ? ?. ? ?. ?,? ? ? ?? ? ? ? ?. ?,?? ? ? 3 : ?1,?1, ?2,?1, ?3,?2 , ?1,?1, ?2,?2, ?3,?2 , ?1,?1, ?2,?3, ?3,?2 , ?1,?1, ?2,?1, ?3,?3 , ?1,?1, ?2,?2, ?3,?3 , ?1,?1, ?2,?3, ?3,?3 , ? =
Counting Perfect Matchings in Bipartite Graphs ? = ?,? - Bipartite graph with bipartition ?,? ? = ? ? ? = ?, ? ?. ? ?. ?,? ? ? ?? ? ? ? ?. ?,?? ? ? 3 : ?1,?1, ?2,?1, ?3,?2 , ?1,?1, ?2,?2, ?3,?2 , ?1,?1, ?2,?3, ?3,?2 , ?1,?1, ?2,?1, ?3,?3 , ?1,?1, ?2,?2, ?3,?3 , ?1,?1, ?2,?3, ?3,?3 , ? =
Counting Perfect Matchings in Bipartite Graphs ? = ?,? - Bipartite graph with bipartition ?,? ? = ? ? ? = ?, ? ?. ? ?. ?,? ? ? ?? ? ? ? ?. ?,?? ? ? has ? 1 , ,? ? ? = ? 1,2, ,? 1 ? is a perfect matching of ? ?? ?
Counting Perfect Matchings in Bipartite Graphs ? ? ? = ?=1 ? 2 ? ???? = ?11+ ?13 ?21+ ?23 ?31+ ?33 = 1 + 0 1 + 1 0 + 1 = 2 = ?13 ?23 ?33= 0 1 1 ? 1,2 Not ? 2 : ?1,?1, ?2,?1, ?3,?2 , ?1,?1, ?2,?2, ?3,?2 , ?1,?1, ?2,?3, ?3,?2 , ?1,?1, ?2,?1, ?3,?3 , ?1,?1, ?2,?2, ?3,?3 , ?1,?1, ?2,?3, ?3,?3 , ? =
Counting Perfect Matchings in Bipartite Graphs ? ? ? = ?=1 ? = ? 1,2, ,? 1 ???? ??= ? = ? 1,2, ,? 1 Each of the values ?=1 Compute the permanent in ? 2? time and polynomial space ? ???? ?? ? ? ? ?=1 ? ???? ? ? ???? is computable in polynomial time
Directed Hamiltonian Path ? = ?,? directed and simple graph ? = ?,? ?1,?2, ,??
Number of Directed Hamiltonian s,t-paths ? = ? = ?, ,? 0,1,2,3,4,5,6 , 0,1,2,1,2,1,6 , , 0,3,4,5,2,1,6 ? = ? + 1 ? =
Number of Directed Hamiltonian s,t-paths ? = ? = ?, ,? ? has ? ? ? = ? + 1 ?? ? ? 3 : 0,1,2,3,4,5,6 , 0,1,2,1,2,1,6 , , 0,3,4,5,2,1,6 ? =
Number of Directed Hamiltonian s,t-paths ? = ? = ?, ,? ? has ? ? ? has ? 1 , ,? ? ? = ? 1,2, ,? 1 ? = ? + 1 ?? ? ? is a directed Hamiltonian s,t-path ?? ?
Number of Directed Hamiltonian s,t-paths ? ? = ??\W?+1?,? ? 3,4,5 ?\W = 0,1,2,6 6 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 ??\W6= =
Number of Directed Hamiltonian s,t-paths ?? ? ???\W?+1?,? ? = ? 1,2, ,? 1 = ? 1,2, ,? 1 Each of the values ??\W?+1?,? is computable in polynomial time Compute the number in ? 2? time and polynomial space
Finding Hamiltonian Path G has Hamiltonian path If ?\ ? has no Hamiltonian path Hamiltonian path must contain ? Run the counting algorithm recursively The running time is ? ? ? ? 2? Can be reduced to ? log? ? ? 2?
Bin Packing Bin capacity ? ? available bins ? items ? ? = The size of item ?
Bin Packing Relaxed feasible solution Ordered set of ? finite lists of elements from 1,2, ,? for each list ?1,?2, ,??, =1 each of the elements of 1,2, ,? appears in at least one of the lists ? ? ? ?
Bin Packing ? ? = ? = ?1, ,?? ?.??= ?1,?2, ,??, =1 ? has ? ? ?.? ?? ? has ? 1 , ,? ? ? is a solution ? = ? 1,2, ,? 1 ? ? ? ?? ?
Bin Packing ?? ? ? = ? 1,2, ,? 1 Each of the values ? ? is computable in polynomial time Compute ? in ? 2? time and polynomial space
Coverings ? a set of ? elements, ? ? ? ?1,?2, ,?? is a ?-cover of ?,? if ?? ? and ?=1 ? ??= ?
Count The Number of ?-covers ??= ???,? ? = ? = ?1,?2, ,?? ?? ? , ? = ?? ? = 3 ???,??????,????? , ??????,???,????? , ???,???,??? , , ?????,??????,?????? ? =
Count The Number of ?-covers ??= ???,? ? = ? = ?1,?2, ,?? ?? ? , ? = ?? For u ?,? has ? ? ? ? ?=1 ?? ? ?????? ??? ? : ???,??????,????? , ??????,???,????? , , ?????,??????,?????? ? =
Count The Number of ?-covers ??= ???,? ? = ? = ?1,?2, ,?? ?? ? , ? = ?? For u ?,? has ? ? ? has? ? for all u ? ??= ? = ? 1,2, ,? 1 ? ? ?=1 ? is a ?-cover of ? ?? ?? ?
Count The Number of ?-covers ? ? = ? ? ? ? = ? ? = ? ? ? S ??? ??? = ????,??????,???? ???? ? ??? ??? = 3?
Count The Number of ?-covers ? ? = ? ? ? ? = ? ? = ? ?\W? ? ? ? = 1 0 ? ? ?? ??????
Count The Number of ?-covers ? ? = ? ?\W? ? ? ? = 1 ? ? 0 ?? ?????? ??? = ??+1, ,??\W ? ?\W?(?) ?0? = ?\W ? ?\W?(?) = ? ?\W ??? = ? ?\W?(?) = ? ? ??? = ?? 1? ?? 1? ?? ?? ?? ? ?? ?????? + ?? 1?
Count The Number of ?-covers ?? ? = ? 1,2, ,? 1 ? in ? 2? ?? ? ? ??= ? 1,2, ,? 1 Computation of all ? ? Compute the number in ? 2? time and exponential space
Coverings The BIN PACKING problem can be seen as a covering problem ?-Cover the set U = 1,2, ,? ? = ? ?|??? ? ?
Graph Coloring Undirected graph ? = Assign a color to each vertex Adjacent vertices have different colors A color class, is an independent set of ? ? is the set of all independent sets of ? given a ?-cover of V,I it is easy to derive a ?-coloring of ?. V,I has a ?-cover ? has a ?-coloring ?,?
Chromatic Number of a Graph The chromatic number of a graph ? = which ???,? > 0 We can compute the chromatic number of a graph in time ? 2? and exponential space. ?,? is the smallest ? for
Polynomial Space The number of ?-covers ???,? can be computed in polynomial space and ?=0 ???? time assuming that there is a ??? time and polynomial space algorithm to compute ? ? for ? ?, ? = ? ? ?
Polynomial Space ?? ? ? ??= ? 1,2, ,? 1 Iterate over all ? ? add the value of 1 By assumption, there is a polynomial space algorithm to compute ? ? in time ??? for every ? ? with ? = ? ? ???? ?? ? ? to a running total sum ? The total running time is ?=0
Chromatic Number of a Graph Polynomial space ? 1.2461? time algorithm to count the number of independent sets in an ?-vertex graph by Furer, M., Kasiviswanathan , S.P (2007) Can compute |S[W]| using this algorithm for ?\W in ? 1.2461? ? ? ?? 1.2461? ?= ? 2.2461? ? ?=0
