Cut and Count

33 %
67 %
Information about Cut and Count
Education

Published on March 7, 2014

Author: ASPAK2014

Source: slideshare.net

Cut & Count

Steiner Tree

Input A graph G, a set of terminals T, and a number k. Steiner Tree

Input A graph G, a set of terminals T, and a number k. Is there a set X of size at most k such that T is contained in X and G[X] is connected? Steiner Tree Question

Input A graph G, a set of terminals T, and a number k. Is there a set X of size at most k such that T is contained in X and G[X] is connected? Steiner Tree parameterized by treewidth Question

Promise The input either has no solution or has exactly one solution.

Promise The input either has no solution or has exactly one solution.

Want: All connected sets of size at most k that contain the terminals.

Want: All connected sets of size at most k that contain the terminals. U: All sets of size at most k that contain the terminals.

Want: All connected sets of size at most k that contain the terminals. U: All sets of size at most k that contain the terminals.

Want: All connected sets of size at most k that contain the terminals. U: All sets of size at most k that contain the terminals.

Want: All connected sets of size at most k that contain the terminals. U: All sets of size at most k that contain the terminals.

Want: All connected sets of size at most k that contain the terminals. U: All sets of size at most k that contain the terminals.

Want: All connected sets of size at most k that contain the terminals. U: All sets of size at most k that contain the terminals.

Want: All connected sets of size at most k that contain the terminals. U: All sets of size at most k that contain the terminals.

Our universe consists of pairs (X,f) where ! ! ! X is a subset of size at most k containing the terminals, ! and f: X —> {Red,Green} is a 2-coloring of the components of X, where f(v1) = Red.

|U| is odd if, and only if, G is a YES-instance.

For a bag x, store Tx[green,red; i]

Want: All connected sets of size at most k that contain the terminals. U: All sets of size at most k that contain the terminals.

Want: All connected sets of size at most k that contain the terminals. U: All sets of size at most k that contain the terminals.

Want: All connected sets of size at most k that contain the terminals. U: All sets of size at most k that contain the terminals.

For a bag B of a tree decomposition, guess how solution intersects the bag, and further, guess the labeling.

For a bag B of a tree decomposition, guess how solution intersects the bag, and further, guess the labeling. For each i in {1,…,k}, we maintain:

For a bag B of a tree decomposition, guess how solution intersects the bag, and further, guess the labeling. For each i in {1,…,k}, we maintain: T[green,red; i] = #of solutions of size i that intercept the bag according to green/red.

Terminal in gray zone?

v1 in the green zone?

Introduce Bag

Introduce Bag

Introduce Bag if v is not a terminal: Tx[green,red; i] = Ty[green,red; i]

Introduce Bag if v is not a terminal: Tx[green,red; i] = Ty[green,red; i] otherwise: zero

Introduce Bag

Introduce Bag

Introduce Bag Tx[green,red; i] = Ty[green*,red*; i-1], provided v is not v1!

Introduce Bag Tx[green,red; i] = Ty[green*,red*; i-1], provided v is not v1! otherwise: zero

Introduce Bag

Introduce Bag

Introduce Bag Tx[green,red; i] = Ty[green*,red*; i-1]

Forget Bag

Forget Bag

Forget Bag Tx[green,red; i] = Ty[green,red; i]

Forget Bag Tx[green,red; i] = Ty[green,red; i] Sum over all relevant configurations in child bag.

Forget Bag Tx[green,red; i] = Ty[green,red; i] Sum over all relevant configurations in child bag.

Introduce Edge Bag Tx[green,red; i] = Ty[green,red; i]

Introduce Edge Bag Tx[green,red; i] = Ty[green,red; i] Filter out entries with this edge crossing green to red.

Join Bag

Join Bag Tp[green,red; r] x Tq[green,red; s]

Join Bag Tp[green,red; r] x Tq[green,red; s] Sum over all r,s such that: r+s - (#green + #red) = i

Want: All connected sets of size at most k that contain the terminals. U: All sets of size at most k that contain the terminals.

Highlight some solution so it’s easier to find.

Universe Family

Universe Family

Universe Family

Universe Family

Isolation Lemma Let F be a family over an universe U. For each element in the universe, assign a weight from {1,2,…,N} uniformly and independently at random. ! Then, the probability that F is isolated by this weight function is at least ! 1 |U| N

Want: All connected sets of size at most k that contain the terminals.

Want: All connected sets of size at most k that contain the terminals.

Focus: All connected sets of size at most k that contain the terminals, and have weight W.

Focus: All connected sets of size at most k that contain the terminals, and have weight W. U: All sets of size at most k and weight W that contain the terminals.

Introduce Bag

Introduce Bag

Introduce Bag Tx[green,red;i,w] = Ty[green*,red*; i-1,w-w(v)]

Add a comment

Related presentations

Related pages

Apple Theme Count, Color, Cut, and Paste Worksheets

Apple Theme Count, Color, Cut, and Paste Worksheets. In this ten-worksheet series students will follow directions and count, color, cut, and paste the ...
Read more

How to Cut and Count Plastic Canvas.wmv - YouTube

This is a lesson showing you how to look at a pattern on paper and then count the holes to match the pattern and cut the pattern out. When you ...
Read more

Cut & Paste Character count - JavaScript Kit- Your ...

Cut & Paste Character count. Credit: JavaScript Kit: Description: Calculate and display the number of characters within a TEXTAREA with this script.
Read more

Color, Count, and Cut - Preschool Activity Workbook

An Activity Book for Four-Year-Olds. from the Set of 4 Preschool Activity Workbooks. Note to Parents: This third book of this series was designed to ...
Read more

Cut and Paste Activity – Count, Cut and Paste – 1 ...

Cut and Paste Activities Easter Worksheets Count, Cut and Paste - Cut and Paste Activity - Wo...
Read more

cut and paste word count Windows 8 downloads - Free ...

cut and paste word count Windows 8 downloads - Free Download Windows 8 cut and paste word count - Windows 8 Downloads - Free Windows8 Download
Read more

FREE St. Patrick's Day counting activity. Count, cut ...

FREE St. Patrick's Day counting activity. Count, cut, paste! | Weitere Informationen über St. Patricks Day.
Read more

ClipCount: Cut and Paste Word Count - Free download and ...

From Advanced International Translations: ClipCount is ideal for fast text count in any file or program. Just select text you want to count and press CTRL ...
Read more

Cut & Paste Word Count - JavaScript Kit- Your ...

Description: How many times have you had to launch an entire word processor just to find out the # of words a certain paragraph contains? Why not use this ...
Read more