CS 231 Module 10: Changing the Rules

It is unlikely to be able to find a polynomial-time algorithm to solve a NP-complete problem. (T/F)

True

What instances of a NP-complete problem can we find a polynomial-time algorithm for?

Some restricted instances (inputs with special properties) can be solved in polynomial time.

KNAPSACK

Input: A set of n types of objects, where object i has an integer weight and an integer value w_i, and an integer v_i weight bound W
Output: A subset of objects with total weight at most W and the maximum total value

What is the runtime for the dynamic programming algorithm that solves KNAPSACK?

O(nW)

Why O(nW) isn’t guaranteed to be polynomial in n?

If W were at most n^k for some constant k, O(nW) would be polynomial in n.
But W can be exponentially larger than n while still being represented with only log W bits, so it is not guaranteed to run in polynomial time with respect to input size n.

Pseudo-Polynomial Time Algorithms

An algorithm with the running time depends on (polynomial in) the numeric values in the input.

What is the length of the representation of the instance, when measuring the size of an instance?

The total number of bits (0s and 1s) required to write down the input.

Weakly NP-Complete Problem

A problem in which there exists a known pseudo-polynomial time algorithm that solves it.

Strongly NP-Complete Problem

A problem proven unable to be solved by a pseudo-polynomial time algorithm, unless P = NP

What is the special case for NP-complete problems?

We can solve an instance of a weakly NP-complete problem in polynomial time if the size of the largest integer used in the running time of the pseudo-polynomial time algorithm is at most polynomial in the size of the instance.

The pseudo-polynomial time algorithm effectively becomes polynomial time.

MAXIMUM SUBTOTAL

Input: A nonempty sequence of numbers
Output: The largest sum formed of numbers in positions i through j, where if i < j, the sum is zero

What are the special cases for which the runtime of MAXIMUM SUBTOTAL is less than in the general case?

• Inputs are all non-negative → Maximum is the sum of the entire sequence of numbers

• Inputs are all negative → Maximum is 0

  • If i > j, the sum is 0

  • If we choose i and j normally (i < j), the sum will always be negative

  • Negative sum < 0

K-COLOURING

Input: A graph G and an integer k
Output: Yes or no, answering “Is G k-colourable?”

What are the special cases for K-COLOURING?

2-colouring problem can be solved in polynomial time.

VERTEX COVER

Input: A graph G and an integer k
Output: Yes or no, answering “Does G have a vertex cover of size at most k?”

What is the special case for VERTEX COVER?

If k = 1, we determine if there exists a vertex that is an endpoint to all edges, such that there is a vertex cover of size 1.

This can be solved using exhaustive search to try each of the n vertices, by examining the endpoints of each of the m edges in θ(1), and determine if the vertex is one of them in θ(1).

The total runtime is θ(mn)

HAMILTONIAN CYCLE

Input: A graph G
Output: Yes or no, answering "Does G have a Hamiltonian cycle?"

Hamiltonian Cycle

A closed loop in a graph that visits every single vertex (node) exactly once and returns to the start.

What is the special case of HAMILTONIAN CYCLE?

If the input is a tree, the answer is always no, since a tree can’t have a Hamiltonian cycle.

We can write an algorithm that checks if the input is a tree in θ(1); otherwise, it uses exhaustive search.

Bounded Degree Graph

A graph where the number of neighbours any vertex can have is restricted.

Regular Graph

A graph where each vertex has identical number of neighbours.

Graphs of Bounded Treewidth

Tree-like graphs where there is exactly 1 path between any pair of vertices.

Planar Graphs

Graphs that can be drawn on a piece of paper without any of the edges crossing overlapping.

Can be split into smaller graph of size at most 2n/3 by removing few vertices, used in divide-and-conquer algorithms.

Deterministic Algorithms

The steps taken by the algorithm on a specific instance are completely determined; if the algorithm runs repeatedly on the same instance, it behaves the same every time.

Randomized Algorithm

Certain steps taken by the algorithm are chosen randomly.

Such that the same algorithm on the same instance may lead to different running times and/or different outputs.

Expected Running Time

Assessment of randomized algorithms, based on the running time averaged over all possible executions. (Not the average-case)

How to calculate expected running time?

Consider the average over possible executions on a single instance. There is no dependence on assumptions about distributions on instance.

How to determine an expected value?

Determine the sum over all events of the value of the event multiplied by the probability of the event.

Example: Coin Flip

• ½ for event Heads, ½ for event Tails

• If I win $100 for Heads, $8 for Tails

• Expected value = 100 × ½ + 8 × ½ = 54

Las Vegas Algorithm

A randomized algorithm guaranteed to give the correct answer in expected polynomial time (analyzed the average runtime over all possible random outcomes)

SELECTION

Input: A sequence of distinct numbers and a value j of size at least 1 and at most the # of numbers in the sequence
Output: A number in the sequence that is the j-th largest

Pivot

A element in the input sequence (instance), used to compare and divide elements into 2 smaller instances:

1. one consists of elements smaller than the pivot

2. one consists of elements larger than the pivot

What is the randomized algorithm sketch for SELECTION?

1. Choose a pivot at random.

2. Check if the pivot is "good".

3. If the pivot is good, solve the problem recursively on the smaller instance or instances.

4. If the pivot is bad, start again at the first step

How to sort using a pivot?

• Compare each element to the pivot, categorizing each as "smaller" or "bigger."

• Recursively sort the "smaller" elements.

• Recursively sort the "bigger" elements.

• Return the concatenation of the two sequences.

What makes a pivot good?

If each smaller instance is a fraction of the size of the original instance, at most ¾.

What is the probability of choosing a good pivot?

1/2, as any of the middle half of the elements will result in smaller instances at most ¾ the size of the original instance.

Monte Carlo Algorithm

A randomized algorithm guaranteed to run in time polynomial in the size of the input, and gives the correct answer with high probability.

What situations arise when randomness has an impact on correctness of decision problems?

False positives and false negatives occur.

False Positives

The algorithm produces ‘yes’ for a no-instance.

False Negatives

The algorithm produces ‘no’ for a yes-instance.

Two-sided Error

If an algorithm for a decision problem can produce both false positives and false negatives.

One-sided Error

If an algorithm for a decision problem can produce either false positives or false negatives.

For example, if it can produce false positives but not false negatives:

• it might answer "yes" for a no-instance

• but will always gives the correct answer for a yes-instance.

Thus, the answer "yes" could be provided for any instance, but "no" will always guarantee a no-instance.

PRIMALITY

Input: An integer
Output: Yes or no, answering "Is the integer a prime number?"

Suggest a randomization algorithm for PRIMALITY.

1. Choose several iterations of a loop that is polynomial in the size of the input to ensure polynomial runtime

2. For each iteration:

   1. Randomly choose an integer greater than 1 and less than the input

   2. Check if the chosen number is a divisor of the instance

      • If it’s a divisor (returns an integer), return ‘No”

3. If we do not find a divisor, return ‘Yes’

Why is the randomization algorithm for PRIMALITY with one-sided error?

Because the algorithm picks a divisor at random, it might not choose a divisor at all, possibly answering “Yes” for a no-instance. However, if the input is a yes-instance, the algorithm will always answer ‘Yes’.

This is an example of a false positive but no false negatives.

MATRIX MULTIPLICATION VERIFICATION

Input: Matrices A, B, and C
Output: Yes or no, answering "Is the C product of A and B?"

Suggest a randomization algorithm for MATRIX MULTIPLICATION VERIFICATION.

1. Choose several iterations of a loop that is polynomial in the size of the input to ensure polynomial runtime

2. For each iteration, randomly choose a position in C

   1. Check if the multiplication for that position is correct
      by multiplying the corresponding row of A and column of B

   2. If the value is wrong, return No

3. If we can’t find an error, return Yes

How to reduce the probability of error of an algorithm with one-sided error?

Increase the number of repetitions (iterations).

If there is a probability of p for each iteration, after k iterations:
P(error) = p^k

How to reduce the probability of error of an algorithm with two-sided error?

Increase the number of repetitions (iterations). By counting the number of yesses and no’s, and return whatever appears more.

Is it possible to convert a Las Vegas algorithm to a Monte Carlo algorithm? If so, why?

Yes

Since a Las Vegas is guaranteed to produce a correct answer, and a Monte Carlo is guaranteed to run in at most polynomial time, we can sacrifice correctness for a faster runtime.

How to convert a Las Vegas algorithm to a Monte Carlo algorithm?

1. Choose a time-bound (limit) polynomial in the size of the instance e.g p(n), run the Las Vegas algorithm, and keep track of how much time has been taken.

2. If the Las Vegas algorithm completes executing in time polynomial in the size of the input, then we have the best of both possible worlds: a correct answer and running time polynomial in the size of the input.

3. However, if Las Vegas has not completed its execution by the time the time bound is reached, we stop the algorithm and randomly produce an answer.

Is it possible to convert a Monte Carlo algorithm to a Las Vegas algorithm?

There is no known way to do so.

Randomization Heuristics

• Instead of starting with an arbitrary solution

  • Randomly choose or construct a solution

• Instead of choosing an arbitrary way to change a solution

  • Make a random change

It helps prevent being stuck at a local optimum.

Worst-case behaviour of randomized sorting is better than worst-case behaviour of deterministic sorting. (T/F)

False because randomization usually improves the expected case, not the worst-case.

Parameterized Problem

Define the problem using k as a parameter,
to create a function that is polynomial in terms of the instance size, but possibly much worse in terms of the parameter or parameters.

VERTEX COVER PARAMETERIZED BY COVER SIZE

Input: A graph G and an integer k
Output: Yes or no, answering "Does G have a vertex cover of size at most k?"
Parameter: k

What is the purpose of introducing a parameter p in parameterized problems?

p represents the size of the parameter(s) that affect the difficulty of the problem. It generalizes the idea of using a single parameter k.

What are the two parts of a parameterized algorithm's running time?

1. A part depending on n:

   • Polynomial

   • Does not depend on p

2. A part depending on p:

   • May not be polynomial

   • Does not depend on n

What does "blaming p" mean?

It means attributing the non-polynomial part of the running time to the parameter p, rather than the input size n.

Why do we want to distinguish between n and p?

Because a problem may be hard only when the parameter is large, while still being efficient for small parameter values.

What happens if p is constant?

The running time becomes polynomial in n. (aka a good p)

What happens to fixed-parameter tractability if p depends on n?

The algorithm is no longer considered fixed-parameter tractable because the running time is not polynomial in the size of the instance.

Fixed-Parameter Tractable Algorithms

Runs in time O(g(p) n^O(1)), where p is a parameter, g is any function, and n is the instance size

Goals:

• Require the part dependent on the size of the instance to be polynomial in the size of the instance

• Allow the part dependent on the parameter to be exponential (or worse)

  • If the parameter is small, this part will also be small

Bounded Search Tree Paradigm

A paradigm that uses a search tree, such as backtracking and branch-and-bound. The parameter p is used to determine when to stop searching.

E.g., if the parameter is the size of the solution:
Building a candidate of size p can be achieved in a tree of height in θ(p)

How many nodes does a tree of height h has, where each node has at most c children?

This tree has O(c^h) nodes.

How to prove that our search tree is part of a fixed-parameter tractable algorithm?

Since the cost of the algorithm
= number of nodes x Cost(processing a single node)
= O(c^h) x Cost(processing a single node)

Needs to be of the form O(g(p) n^O(1))

Fixed-Parameter Tractable Algorithm for VERTEX COVER PARAMETERIZED BY COVER SIZE

Every node contains:

1. A subset P of the vertices (building to a vertex cover)

2. A graph H with edges not visited yet

The root contains an empty set and the input graph.

To determine if we can extend the partial solution into 2 children,

1. Determine if there are no uncovered edges in the graph; or

   • If a partial solution satisfies this, it is a candidate

2. If the size of the subset is at most k

   • If a partial solution satisfies this, it can’t be extended

Otherwise, we can extend the partial solution by choosing an uncovered edge {u, v}. And create 2 children:

1. Adding {u} to P and removing {u} and all edges incident on {u}

2. Adding {v} to P and removing {v} and all edges incident on {v}

Return Yes if a partial solution with no uncovered edges has been found. Otherwise return No.

What is the height of the bounded search tree for parameter k in VERTEX COVER PARAMETERIZED BY COVER SIZE?

The tree height will be at most k, since we do not consider solutions of size greater than k.

What is the bound on the total number of nodes in the search tree for VERTEX COVER PARAMETERIZED BY COVER SIZE?

The height of the tree is at most k, and the number of children of a node is 2.
Number of nodes = O(2^k)

How to prove that the algorithm for VERTEX COVER PARAMETERIZED BY COVER SIZE is fixed-parameter tractable?

Consider:

• Number of nodes = O(2^k)

• Runtime = Number of nodes x Cost(processing a node)

• Processing a node consists of choosing an edge and creating 2 new graphs, which can be completed in at most n^O(1)

The total cost is in O(2^kn^O(1)). Since 2^k is a function of k, it proves the algorithm is a fixed-parameter tractable algorithm.

N^O(1)

A polynomial function of n, where the exponent on n must be a constant.

Examples:

• n² where 2 is O(1)

• n⁵ where 5 is O(1)

nⁿ is not in N^O(1) since n is not in O(1)

Kernelization Paradigm

Process of replacing an instance by a kernel, a smaller instance of same problem. The goals are:

1. the kernel is a yes-instance if and only if the original instance is a yes-instance, and

2. the size of the kernel is bounded by a function of p.

How to solve the original instance with kernelization?

Form the kernel and then solve the problem on the kernel.

How to obtain a kernelization algorithm that’s fixed-parameter tractable?

The processes of:

• forming the kernel

• solving the problem on the kernel

Can both be accomplished by fixed-parameter tractable algorithms

How to solve the problem on the kernel?

Solve the problem on an instance of size bounded by a function of p

What if a vertex v is not in the cover?

All of the neighbours of v must be in the vertex cover.

High Degree Vertex

A vertex with degree > k, and must be in the vertex cover.

How to characterize G’, which is G but with high degree vertices removed.

Since high degree vertices must be part of the vertex cover, k’ = k- # of high degree vertex.
A yes-instance of G’ can have at most k’ + k’k vertices (bound).

If an instance G’ has more than k’ + k’k vertices, it is a no-instance. Otherwise, we can use exhaustive search to determine if G’ is a yes-instance or no-instance, using the size of the graph is bounded by a function of k.