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

Cut, count, match and paste / Free printable | Worksheets ...

Cut, count, match and paste / Free printable | Worksheets ...
Read more

Canon Shutter Count - EOSCount (Windows and Mac)

Easy to use Canon shutter count software for Mac and Windows. Find the number of shutter actuations on a Canon EOS DSLR.
Read more

Plumb - Cut - YouTube

Sign in to make your opinion count. Sign in. 23,166 306. ... I was cut **NO COPYRIGHT INFRINGEMENT INTENDED** Disclaimer: I do not own anything.
Read more

Cut & Paste Character count - JavaScript Kit

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

10 Practical Linux Cut Command Examples to Select File Columns

10 Practical Linux Cut Command Examples to Select File Columns. by Balakrishnan Mariyappan. on June 6, ... find before first space and count cat hdfs-info ...
Read more

Linux and UNIX cut command help and examples - Computer Hope

Linux and Unix cut command. About cut cut syntax cut examples Related commands ... When invoking cut, use the -b, -c, or -f option, but only one of them.
Read more

mp3DirectCut - Download - CHIP

mp3DirectCut 2.22 Deutsch: MP3 schneiden: mp3DirectCut ist eine Freeware, um Musikdateien verlustfrei cutten und splitten zu können.
Read more

c# - How would you count occurrences of a string within a ...

How would you count occurrences of a string within a string? up vote 550 down vote favorite. 96.
Read more

The Count Censored - YouTube

The Count Censored - First Day of School - Duration: 3:23. aleckermit 285,486 views. 3:23 50+ videos Play all Play now; Mix - The Count Censored ...
Read more

Blackboard Learn - Central University of Technology

Blackboard Learn ™ Course Delivery ...
Read more