# Iterative Compression

50 %
50 %
Technology

Published on March 5, 2014

Author: ASPAK2014

Source: slideshare.net

Iterative Compression

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? Vertex Cover Question

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? Vertex Cover Question

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? A vertex cover of size (k+1). Vertex Cover Question

Input A graph G with a vertex cover of size k+1. Is there a vertex cover of size at most k? A vertex cover of size (k+1). Vertex Cover Question

Input A graph G with a vertex cover of size k+1. Is there a vertex cover of size at most k? A vertex cover of size (k+1). Vertex Cover Question

Input A graph G with a vertex cover of size k+1. Is there a vertex cover of size at most k? A vertex cover of size (k+1). Let us “guess” how a vertex cover of size at most k interacts with this one. Vertex Cover Question

Input A graph G with a vertex cover of size k+1. Is there a vertex cover of size at most k? A vertex cover of size (k+1). Let us “guess” how a vertex cover of size at most k interacts with this one. Vertex Cover Question

Input A graph G with a vertex cover of size k+1. Is there a vertex cover of size at most k? A vertex cover of size (k+1). Let us “guess” how a vertex cover of size at most k interacts with this one. Vertex Cover Question

Input A graph G with a vertex cover of size k+1. Is there a vertex cover of size at most k? A vertex cover of size (k+1). Vertex Cover Question

Input A graph G with a vertex cover of size k+1. Is there a vertex cover of size at most k? A vertex cover of size (k+1). Can there be an edge between two red vertices? Vertex Cover Question

Input A graph G with a vertex cover of size k+1. Is there a vertex cover of size at most k? A vertex cover of size (k+1). Vertex Cover Question

Input A graph G with a vertex cover of size k+1. Is there a vertex cover of size at most k? A vertex cover of size (k+1). Now we need to make up for the work that the red vertices were doing. Vertex Cover Question

Input A graph G with a vertex cover of size k+1. Is there a vertex cover of size at most k? Vertex Cover Question

Input A graph G with a vertex cover of size k+1. Is there a vertex cover of size at most k? Vertex Cover Question

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? Vertex Cover Question

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? Vertex Cover Question

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? Vertex Cover Question

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? Vertex Cover Question

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? The first k+2 vertices in G. Vertex Cover Question

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? Question The first k+2 vertices in G. It has an easy vertex cover of size k+1. Vertex Cover

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? Question The first k+2 vertices in G. It has an easy vertex cover of size k+1. Vertex Cover

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? Question The first k+2 vertices in G. It has an easy vertex cover of size k+1. Vertex Cover

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? Question The first k+2 vertices in G. It has an easy vertex cover of size k+1. Vertex Cover

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? Question The first k+2 vertices in G. It has an easy vertex cover of size k+1. Vertex Cover

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a vertex cover of size at most k? Question The first k+2 vertices in G. It has an easy vertex cover of size k+1. Compress again… rinse, repeat. Vertex Cover

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a subset of vertices S of size at most k that intersects all the edges? Question We have a O*(2k) algorithm for Vertex Cover. Vertex Cover

Input A graph G = (V,E) with n vertices, m edges, and k. Is there a subset of vertices S of size at most k that intersects all the edges? Question We have a O*(2k) algorithm for Vertex Cover. Vertex Cover

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? A Feedback Vertex Set of size (k+1). Let us “guess” how a FVS of size at most k interacts with this one. Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Question A vertex with two neighbors in the same component is forced. Feedback Vertex Set

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Question A leaf that has exactly one neighbor above can be preprocessed. Feedback Vertex Set

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Question …a leaf with at least two neighbors in different components. Feedback Vertex Set

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Question The leaf merges two components when we don’t include it. Feedback Vertex Set

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Question The number of components “on top” decreases. Feedback Vertex Set

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Question Start with a leaf. ! Two neighbors in one component: forced. At most one neighbor above: preprocess. At least two neighbors, all in different components above: branch. Feedback Vertex Set

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Question Let t denote the number of components among the red vertices. Let w = (k+t). Feedback Vertex Set

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Question Let t denote the number of components among the red vertices. Let w = (k+t). Include v… k drops by 1 Exclude v… t drops by at least 1 Feedback Vertex Set

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Question Let t denote the number of components among the red vertices. Let w = (k+t). Include v… k drops by 1 Exclude v… t drops by at least 1 Either way, w drops by at least one. Feedback Vertex Set

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Either way, w drops by at least one. Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Either way, w drops by at least one. Running time: 2w = 2(k+t) Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Either way, w drops by at least one. Running time: 2w = 2(k+t) ≤ 2k+k ≤ 4k Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Either way, w drops by at least one. Running time: 2w = 2(k+t) ≤ 2k+k ≤ 4k Overall Running Time… Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph acyclic? Either way, w drops by at least one. Running time: 2w = 2(k+t) ≤ 2k+k ≤ 4k Overall Running Time… k i=1 k k k 4 =5 i Feedback Vertex Set Question

Input A tournament T on n vertices and an integer k. Is there a subset of k arcs that can be reversed to make the tournament acyclic? This implies an O(5k) algorithm for FVS. Feedback Vertex Set Question

Input A tournament T on n vertices and an integer k. Is there a subset of k arcs that can be reversed to make the tournament acyclic? This implies an O(5k) algorithm for FVS. Feedback Vertex Set Question

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? Question A Odd Cycle Transversal of size (k+1). Let us “guess” how a OCT of size at most k interacts with this one. Odd Cycle Transversal (OCT)

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? Question Odd Cycle Transversal (OCT)

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? Question Odd Cycle Transversal (OCT)

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? Question Odd Cycle Transversal (OCT)

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? Question Odd Cycle Transversal (OCT)

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? Question Odd Cycle Transversal (OCT)

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? Question Odd Cycle Transversal (OCT)

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? Question Odd Cycle Transversal (OCT)

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? Question Odd Cycle Transversal (OCT)

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? Question Odd Cycle Transversal (OCT)

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? Question Odd Cycle Transversal (OCT)

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? Question Can we remove at most b vertices so that the resulting graph has a bipartition extending this pre-coloring? Odd Cycle Transversal (OCT)

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? GREEN Question YELLOW Can we remove at most b vertices so that the resulting graph has a bipartition extending this pre-coloring? Odd Cycle Transversal (OCT)

Input A graph on n vertices, m edges and an integer k. Is there a subset of at most k vertices whose removal makes the graph bipartite? GREEN Question YELLOW Can we remove at most b vertices so that the resulting graph has a bipartition extending this pre-coloring? Odd Cycle Transversal (OCT)

Input A tournament T on n vertices and an integer k. Is there a subset of k arcs that can be reversed to make the tournament acyclic? Question This implies an O*(3k) algorithm for OCT. Odd Cycle Transversal (OCT)

Input A tournament T on n vertices and an integer k. Is there a subset of k arcs that can be reversed to make the tournament acyclic? Question This implies an O*(3k) algorithm for OCT. Odd Cycle Transversal (OCT)

Take Away…

Show that the problem has a hereditary property Solve the “compression” question, or even a “Disjoint” version.

Show that the problem has a hereditary property Solve the “compression” question, or even a “Disjoint” version. Is a framework that can be setup quite easily.

Show that the problem has a hereditary property Solve the “compression” question, or even a “Disjoint” version. Is a framework that can be setup quite easily. The compression algorithm can be fairly non-trivial.

 User name: Comment:

## Related presentations

#### Neuquén y el Gobierno Abierto

October 30, 2014

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

#### Decision CAMP 2014 - Erik Marutian - Using rules-b...

October 16, 2014

In this presentation we will describe our experience developing with a highly dyna...

#### Schema.org: What It Means For You and Your Library

November 7, 2014

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

#### WearableTech: Una transformación social de los p...

November 3, 2014

Un recorrido por los cambios que nos generará el wearabletech en el futuro

#### O Impacto de Wearable Computers na vida das pessoa...

November 5, 2014

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

#### All you need to know about the Microsoft Band

November 6, 2014

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

## Related pages

### Iterative Compression, and Measure and Conquer, for ...

We introduce the technique of iterative compression. We illustrate how this can be combined with analytical techniques such as measure and conquer.

### Iterative Compression for Exactly Solving NP-Hard ...

Algorithmics of Large and Complex Networks, LNCS 5515, pp. 65-80, 2009 Iterative Compression for Exactly Solving NP-Hard Minimization Problems Jiong Guo⋆ ...

### Iterative Compression and Exact Algorithms

Iterative Compression and Exact Algorithms Fedor V. Fomin Serge Gaspersy Dieter Kratschz Mathieu Liedlo x Saket Saurabh{Abstract Iterative Compression has ...

### Iterative Compression and Exact Algorithms - ResearchGate

Iterative Compression and Exact Algorithms Fedor V. Fomin 1?, Serge Gaspers , Dieter Kratsch2, Mathieu Liedloﬀ2 and Saket Saurabh1 1 Department of ...

### An Iterative Compression Algorithm for Vertex Cover

An Iterative Compression Algorithm for Vertex Cover on ResearchGate, the professional network for scientists.

### Hannos Blog » Iterative Compression

Das Proseminar „Parametrisierte Algorithmen“, das ich diese Sommersemester genommen hatte, ist nun fast vorbei. Die VortrÃ¤ge wurden alle gehalten ...

### Iterative compression - Wikipedia, the free encyclopedia

In computer science, iterative compression is an algorithmic technique for the design of fixed-parameter tractable algorithms, in which one element (such ...