高级算法 (Fall 2016)/Greedy and Local Search

Under construction. 

Set cover

Given a number of subsets [math]\displaystyle{ S_1,S_2,\ldots,S_n\subseteq U }[/math] of a universe [math]\displaystyle{ U }[/math], a [math]\displaystyle{ C\subseteq\{1,2,\ldots,n\} }[/math] forms a set cover if [math]\displaystyle{ U=\bigcup_{i\in\mathcal{C}}S_i }[/math], that is, [math]\displaystyle{ \mathcal{C} }[/math] is a sub-collection of sets whose union "covers" all elements in the universe.

This defines a natural optimization problem:

Set Cover Problem

Input: a number of sets [math]\displaystyle{ S_1,S_2,\ldots,S_n }[/math] with the universe [math]\displaystyle{ U=\bigcup_{i=1}^nS_i }[/math]; Output: the smallest [math]\displaystyle{ C\subseteq\{1,2,\ldots,n\} }[/math] such that [math]\displaystyle{ U=\bigcup_{i\in C}S_i }[/math].

We can think of each instance as a bipartite graph [math]\displaystyle{ G(U,\{S_1,S_2,\ldots,S_n\}, E) }[/math] with elements [math]\displaystyle{ x\in U }[/math] of the universe on the left side, subsets [math]\displaystyle{ S_1,S_2,\ldots,S_n }[/math] on the right side, and there is a bipartite edge between element [math]\displaystyle{ x }[/math] and set [math]\displaystyle{ S_i }[/math] if and only if [math]\displaystyle{ x\in S_i }[/math]. By this translation the set cover problem is precisely the problem of given as input a bipartite graph [math]\displaystyle{ G(U,V,E) }[/math], to find the smallest subset [math]\displaystyle{ C\subseteq V }[/math] of vertices on the right side to "cover" all vertices on the left side, i.e. every vertex on the left side [math]\displaystyle{ x\in U }[/math] is incident to some vertex in [math]\displaystyle{ C }[/math].

By alternating the roles of sets and elements in the above interpretation of set cover as bipartite cover, the set cover problem can be translated to the following equivalent hitting set problem.

Hitting Set Problem

Input: a number of sets [math]\displaystyle{ S_1,S_2,\ldots,S_m }[/math] with the universe [math]\displaystyle{ U=\bigcup_{i=1}^mS_i }[/math]; Output: the smallest subset [math]\displaystyle{ C\subseteq U }[/math] of elements such that [math]\displaystyle{ C }[/math] intersects with every set [math]\displaystyle{ S_i }[/math] for [math]\displaystyle{ 1\le i\le m }[/math].

Frequency and Vertex Cover

Given an instance of set cover problem [math]\displaystyle{ S_1,S_2,\ldots,S_n\subseteq U }[/math], for every element [math]\displaystyle{ x\in U }[/math], its frequency denoted as [math]\displaystyle{ frequency(x) }[/math] is defined as the number of sets containing [math]\displaystyle{ X }[/math]. Formally,

[math]\displaystyle{ frequency(x)=\{i\mid x\in S_i\} }[/math].

In the hitting set version, the frequency should be defined on each set and for a set [math]\displaystyle{ S_i }[/math] its frequency [math]\displaystyle{ frequency(S_i)=|S_i| }[/math] is just the size of [math]\displaystyle{ |S_i| }[/math].

The set cover problem restricted to the instances with frequency 2, becomes the vertex cover problem.

Given an undirected graph [math]\displaystyle{ G(U,V) }[/math], a vertex cover is a subset [math]\displaystyle{ C\subseteq V }[/math] of vertices such that every edge [math]\displaystyle{ uv\in E }[/math] has at least one endpoint in [math]\displaystyle{ C }[/math].

Vertex Cover Problem

Input: an undirected graph [math]\displaystyle{ G(V,E) }[/math] Output: the smallest [math]\displaystyle{ C\subseteq V }[/math] such that every edge [math]\displaystyle{ e\in E }[/math] is incident to at least one vertex in [math]\displaystyle{ C }[/math].

It is easy to compare with the hitting set problem:

• For graph [math]\displaystyle{ G(V,E) }[/math], its edges [math]\displaystyle{ e_1,e_2,\ldots,e_m\subseteq V }[/math] are vertex-sets of size 2.
• A subset [math]\displaystyle{ C\subseteq V }[/math] of vertices is a vertex cover if and only if it is a hitting sets for [math]\displaystyle{ e_1,e_2,\ldots,e_m }[/math], i.e. every [math]\displaystyle{ e_i }[/math] intersects with [math]\displaystyle{ C }[/math].

Therefore vertex cover is just set cover with frequency 2.

The vertex cover problem is NP-hard. Its decision version is among Karp's 21 NP-complete problems. Since vertex cover is a special case of set cover, the set cover problem is also NP-hard.