Lecture 5

Takeaway from Bipartite Matching

• We saw how to solve a problem (bi-partite matching and others) by reducing it to another problem (maximum flow).
• In general, we can design an algorithm to map instances of a new problem to instances of known solvable problem (e.g., max-flow) to solve this new problem!
• Mapping from one problem to another which preserves solutions is called reduction.

Reduction: Basic Idea

Convert solutions to the known problem to the solutions to the new problem

• Instance of new problem
• Instance of known problem
• Solution of known problem
• Solution of new problem

Reduction: Formal Definition

Problems $L,K$.

$L$ reduces to $K$ ($L\leq K$) if there is a mapping $\phi$ from any instance $l\in L$ to some instance $\phi(l)\in K'\subset K$, such that the solution for $\phi(l)$ yields a solution for $l$.

This means that L is no harder than K

Using reduction to design algorithms

In the example of reduction to solve Bipartite Matching:

$L:$ Bipartite Matching

$K:$ Max-flow Problem

Efficiency:

1. Reduction: $\phi:l\to\phi(l)$ (Polynomial time reduction $\phi(l)$)
2. Solve prom $\phi(l)$ (Polynomial time to solve $poly(g)$)
3. Convert the solution for $\phi(l)$ to a solution to $l$ (Polynomial time to solve $poly(g)$)

Efficient Reduction

A reduction $\phi:l\to\phi(l)$ is efficient ($L\leq p(k)$) if for any $l\in L$:

1. $\phi(l)$ is computable from $l$ in polynomial ($|l|$) time.
2. Solution to $l$ is computable from solution of $\phi(l)$ in polynomial ($|l|$) time.

We call $L$ is poly-time reducible to $K$, or $L$ poly-time reduces to $K$.

Which problem is harder?

Theorem: If $L\leq p(k)$ and there is a polynomial time algorithm to solve $K$, then there is a polynomial time algorithm to solve $L$.

Proof: Given an instance of $l\in L$ If we can convert the problem in polynomial time with respect to the original problem $l$.

1. Compute $\phi(l)$: $p(l)$
2. Solve $\phi(l)$: $p(\phi(l))$
3. Convert solution: $p(\phi(l))$

Total time: $p(l)+p(\phi(l))+p(\phi(l))=p(l)+p(\phi(l))$ Need to show: $|\phi(l)|=poly(|l|)$

Proof:

Since we can convert $\phi(l)$ in $p(l)$ time, and on every time step, (constant step) we can only write constant amount of data.

So $|\phi(l)|=poly(|l|)$

Hardness Problems

Reductions show the relationship between problem hardness!

Question: Could you solve a problem in polynomial time?

Easy: polynomial time solution Hard: No polynomial time solution (as far as we know)

Types of Problems

Decision Problem: Yes/No answer

Examples: Subset sums

1. Is the there a flow of size $F$
2. Is there a shortest path of length $L$ from vertex $u$ to vertex $v$.
3. Given a set of intercal, can you schedule $k$ of them.

Optimization Problem: What is the value of an optimal feasible solution of a problem?

• Minimization: Minimize cost
  • min cut
  • minimal spanning tree
  • shortest path
• Maximization: Maximize profit
  • interval scheduling
  • maximum flow
  • maximum matching

Canonical Decision Problem

Does the instance $l\in L$ (an optimization problem) have a feasible solution with objective value $k$:

Objective value $\geq k$ (maximization) $\leq k$ (minimization)

$DL$ is the reduced Canonical Decision problem $L$

Hardness of Canonical Decision Problems

Lemma 1: $DL\leq p(L)$ ($DL$ is no harder than $L$)

Proof: Assume $L$ maximization problem $DL(l)$: does have a solution $\geq k$.

Example: Does graph $G$ have flow $\geq k$.

Let $v^∗$ be the maximum objective on $l$ by solving $l$.

Let the instance of $DL:(l,k)$ and $l$ be the problem and $k$ be the objective

1. $l\to \phi(l)\in L$ (optimization problem) $\phi(l,k)=l$
2. Is $v^*(l)\geq k$? If so, return true, else return false.

Lemma 2: If $v^* =O(c^{|l|})$ for any constant $c$, then $L\leq p(DL)$.

Proof: First we could show $L\leq DL$. Suppose maximization problem, canonical decision problem is is there a solution $\geq k$.

Naïve Linear Search: Ask $DL(l,k)$, if returns false, ask $DL(l,k+1)$ until returns true

Runtime: At most $k$ search to iterate all possibilities.

This is exponential! How to reduce it?

Our old friend Binary (exponential) Search is back!

You gets a no at some value: try power of 2 until you get a no, then do binary search

# questions: $=log_2(v^*(l))=poly(l)$

Binary search in area: from last yes to first no.

Runtime: Binary search ($O(n)=\log(v^*(l))$)

Reduction for Algorithm Design vs Hardness

For problems $L,K$

If $K$ is “easy” (exists a poly-time solution), then $L$ is also easy.

If $L$ is “hard” (no poly-time solution), then $k$ is also hard.

Every problem that we worked on so far, $K$ is “easy”, so we reduce from new problem to known problem (e.g., max-flow).

Reduction for Hardness: Independent Set (ISET)

Input: Given an undirected graph $G = (V,E)$,

A subset of vertices $S\subset V$ is called an independent set if no two vertices of are connected by an edge.

Problem: Does $G$ contain an independent set of size $\geq k$?

$ISET(G,k)$ returns true if $G$ contains an independent set of size $\geq k$, and false otherwise.

Algorithm? NO! We think that this is a hard problem.

A lot of people have tried and could not find a poly-time solution

Example: Vertex Cover (VC)

Input: Given an undirected graph $G = (V,E)$

A subset of vertices $C\subset V$ is called a vertex cover if contains at least one end point of every edge.

Formally, for all edges $(u,v)\in E$, either $u\in C$, or $v\in C$.

Problem: $VC(G,j)$ returns true if has a vertex cover of size $\leq j$, and false otherwise (minimization problem)

Example:

How hard is Vertex Cover?

Claim: $ISET\leq p(VC)$ Side Note: when we prove $VC$ is hard, we prove it is no easier than $ISET$.

DO NOT: $VC\leq p(ISET)$

Proof: Show that $G=(V,E)$ has an independent set of $k$ if and only if the same graph (not always!) has a vertex cover of size $|V|-k$.

Map:

$G'=G$

Proof of reduction: Direction 1

Claim 1: $ISET$ of size $k\to$ $VC$ of size $|V|-k$

Proof: Assume $G$ has an $ISET$ of size $k:S$, consider $C = V-S,|C|=|V|-k$

Claim: $C$ is a vertex cover

Proof of reduction: Direction 2

Claim 2: $VC$ of size $|V|-k\to ISET$ of size $k$

Proof: Assume $G$ has an $VC$ of size $|V| −k:C$, consider $S = V − C, |S| =k$

Claim: $S$ is an independent set

What does poly-time mean?

Algorithm runs in time polynomial to input size.

• If the input has items, algorithm runs in $\Theta(n^c)$ for any constant is poly-time.
  • Examples: intervals to schedule, number of integers to sort, # vertices + # edges in a graph
• Numerical Value (Integer $n$), what is the input size?
  • Examples: weights, capacity, total time, flow constraints
  • It is not straightforward!

Real time complexity of F-F?

In class: $O(F( |V| + |E|))$

• $|V| + |E|$ = this much space to represent the graph
• $F$ : size of the maximum flow.

If every edge has capacity , then $F = O(CE)$ Running time:$O(C|E|(|V| + |E| )))$

What is the actual input size?

Each edge ($|E|$ edges):

• 2 vertices: $|V|$ distinct symbol, $\log |V|$ bits per symbol
• 1 capacity: $\log C$

Size of graph:

• $O(|E|(|V| + \log C))$
  • $p( |E| , |V| , \log C)$

Running time:

• $P( |E| , |V| , |C| )$
  • Exponential if is exponential in $|V|+|E|$

Pseudo-polynomial

Naïve Ford-Fulkerson is bad!

Problem ’s inputs contain some numerical values, say $|W|$. We need only log bits to store . If algorithms runs in $p(W)$, then it is exponential, or pseudopolynomial.

In homework, you improved F-F to make it work in $p( |V| ,|E| , \log C)$, to make it a real polynomial algorithm.

Conclusion: Reductions

• Reduction
  • Construction of mapping with runtime
  • Bidirectional proof
• Efficient Reduction $L\leq p(K)$
  • Which problem is harder?
  • If $L$ is hard, then $K$ is hard. $\to$ Used to show hardness
  • If $K$ is easy, then $L$ is easy. $\to$ Used for design algorithms
• Canonical Decision Problem
  • Reduction to and from the optimization problem
• Reduction for hardness
  • Independent Set$leq p$ Vertex Cover

On class

Reduction: $V^* = O(c^k)$

OPT: Find max flow of at least one instance $(G,s,t)$

DEC: Is there a flow of size $pK$, given $G,s,t \implies$ the instance is defined by the tuple $(G,s,t,k)$

Yes, if there exists one No, otherwise

Forget about F-F and assume that you have an oracle that solves the decision problem.

First solution (the naive solution): iterate over $k = 1, 2, \dots$ until the oracle returns false and the last one returns true would be the max flow.

Time complexity: $K\cdot X$, where $X$ is the time complexity of the oracle Input size: $poly(||V|,|E|, |E|log(max-capacity))$, and $V^* \leq \sum$ capacities

A better solution: do a binary search. If there is no upper bound, we use exponential binary search instead. Then,

As $\log(maxCapacity)$ is linear in the size of the input, the running time is polynomial to the solution of the original problem.

Assume that ISET is a hard problem, i.e. we don't know of any polynomial time solution. We want to show that vertex cover is also a hard problem here:

$ISET \leq_{p} VC$

1. Given an instance of ISET, construct an instance of VC
2. Show that the construction can be done in polynomial time
3. Show that if the ISET instance is true than the CV instance is true
4. Show that if the VC instance is true then the ISET instance is true.

ISET: given $(G,K)$, is there a set of vertices that do not share edges of size $K$
VC: given $(G,K)$, is there a set of vertices that cover all edges of size $K$

1. Given $l: (G,K)$ being an instance of ISET, we construct $\phi(l): (G',K')$ as an instance of VC. $\phi(l): (G, |V|-K), \textup{i.e., } G' = G \cup K' = |V| - K$
2. It is obvious that it is a polynomial time construction since copying the graph is linear, in the size of the graph and the subtraction of integers is constant time.

Direction 1: ISET of size k $\implies$ VC of size $|V| - K$ Assume that ISET(G,K) returns true, show that $VC(G, |V|-K)$ returns true

Let $S$ be an independent set of size $K$ and $C = V-S$

We claim that $C$ is a vertex cover of size $|V|-K$

Proof:

We proceed by contradiction. Assume that $C$ is NOT a vertex cover, and it means that there is an edge $(u,v)$ such that $u\notin c , v\notin C$. And it implies that $u\in S , v\in S$, which contradicts with the assumption that S is an independent set. Therefore, $c$ is an vertex cover

Direction 2: VC of size $|V|-K \implies$ ISET of size $K$

Let $C$ be a vertex cover of size $|V|-K$ , let $s = |v| - c$

We claim that $S$ is an independent set of size $K$.

Again, assume, for the sake of contradiction, that $S$ is not an independent set. And we get

$\exists (u,v) \textup{such that } u\in S, v \in S$

$u,v \notinC$

$C \textup{ is not a vertex cover}$

And this is a contradiction with our assumption.