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)]

 User name: Comment:

Related pages

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

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

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.

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.

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.

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 ...

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.

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

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.