NP-Complete & Fibonacci Heap

This post covers concepts but, sadly, provides no code samples (particularly, no implementation of a fibonacci heap). This will be a rarity in this series. Although I think it's a worthwhile exercise to write code whilst covering topics, the Fibonnaci heap is seldomly (if ever) required to be implemented (say, in interviews) - but it is important to know what it is. Also consider that I have a large number of topics to cover in a defined window of time (which I intend to keep to).

Polynomial Time

Resources

1. What exactly is polynomial time?

Takeaways

• O(n^k). Where k is non negative.
• Some examples of polynomial run times: O(3n^4), O(n^100), O(n^2), O(n), O(log n), O(n log n).
• Faster than factorial (O(n!)) and exponential (O(2^n)) run times.

---

NP, NP-Hard, NP-Complete

Resources

1. Video explanation
2. Video on computational complexity
3. Explanation of each complexity class

Takeaways

• P, NP, NP-Hard, & NP-Complete are classes of complexity
• P is a set of problems solvable in polynomial time
• NP is a set of decision problems solvable in polynomial time using a nondeterministic algorithm (NP stands for Nondeterministic Polynomial time)
• Nondeterministic algorithms are a hypothetical model
  • They allow us to imagine a solution to a problem, or subproblem, that can be solved in a not-yet possible/discovered run time
  • For example, a solution to an NP problem in polynomial time might assert that the search algorithm it uses for the solution is O(1) (constant time).
  • Of course, we know that there is no such algorithm that can search, reliably, in O(1). This is exactly the point of nondeterministic algorithms. They are aware of the constraints in reality, but hypothetically if we can make decisions in algorithms in faster than possible run times (that we know of today) then we can theoretically prove that NP problems are solvable in polynomial time.
• A problem is in P if it can be solved in polynomial time
• An example of a problem in P: Given a list of n integers and an integer k, is there an integer in the list greater than k?
  • We can solve this problem using linear search or, if the list is sorted, binary search.
  • Both linear and binary search run in polynomial time, therefore the problem is solvable in polynomial time and is in P.
• A problem is in NP if it can be solved in polynomial time, using a nondeterministic algorithm
• An example of a problem in NP: Given a set of integers A, partition A into three subsets whose sum are equal.
  • Essentially we need to split the list into 3 subsets, and each of those subsets must have an equal sum.
  • This problem has no known solution that runs in polynomial time (deterministically)
• NP-Complete are simply NP problems that can be reduced* to each other, such that solving one of them in polynomial time means that we can solve the rest of them, also in polynomial time.
  • Formally: All problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time.
• NP-Hard problems:
  • These are at least as hard as the hardest problems in NP. If we can solve these problems in polynomial time, we can solve any NP problem.
  • NP-hard problems don't have to be decision problems, and they do not have to be in NP.
  • Formally: A problem X is NP-hard, if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time.
• There is a famous question in computer science: Does P = NP?
  • Most people think P != NP, instead it is widely believed that P is a subset of NP (see diagram below). However, we have not yet proved that P does not equal NP.

Visualization

*Reductions:

• A process whereby we reduce (convert) problem X into problem Y
• We do this to answer "Can we use the solution for X to solve Y?"
• Reduction is the most common algorithm design technique
• Reduction allows us to reuse/re-purpose algorithms for a variety of problems.
• An example of this reuse is the partitioning logic for both Quicksort() & Quickselect()
  • To learn more about quicksort see my post: Common Sorting Algorithms
  • To learn more about quickselect see my post Searching Algorithms

---

Fibonacci Heap

Resources

1. Very good video explanation
2. Overview and explanation (slide show)

Takeaways

	delete-min	insert	decrease-key
Binary Heap	O(log n)	O(log n)	O(log n)
Binomial Heap	O(log n)	O(1) amortized	O(log n)
Linked List	O(n)	O(1)	O(1)
Fibonacci Heap	O(log n) amortized	O(1) amortized	O(1) amortized

• Motivation behind inventing the Fibonacci heap was to speed up Dijkstra's algorithm
• Dijkstra's algorithm will be covered in depth in a later post, but it is an algorithm for finding the shortest path between vertices in a graph.
  • To learn more about graphs, check out my post: Learning Graphs.
• Dijkstra's algorithm makes use of a primary queue in it's implementation, and makes heavy use of insert & decrease-key operations - as well some use of delete-min.
• Binary Heaps are a common backing data structure for a priority queue
  • To learn more about priority queues & binary heaps, see my posts: Learning Binary Heaps & Learning Priority Queues.
• As you can see in the above table, the Fibonacci heap greatly speeds up the insert and decrease-key operations
• The Fibonacci heap takes advantage of the fact that batch operations are more efficient
• Example:
  • A binary heap's insert operation is O(log n). But it can only take 1 element at a time. So if we insert n items into a binary heap this will take O(n log n).
  • But to convert n elements to a binary heap via heapify (which accepts n elements, and represents our batch operation) only takes O(n).
  • This demonstrates that batching can be faster than single operations within a binary heap. The Fibonacci heap capitalizes on batching and is able to speed up insert & decrease-key operations as a result.
• So at it's core, what is a Fibonacci heap?
• A Fibonacci heap is essentially just a list of trees, with each tree being a heap.
• The Fibonacci heap keeps track of the smallest root in it's list of heaps. This pointer can be referred to as the min-root.
• The Fibonacci heap is considered a lazy heap, remember that batching concept mentioned earlier? This is related to the Fibonacci heap's laziness
• A Fibonacci heap lazily defers merging/consolidating trees until delete-min is called.
• Notice how insert and decrease-key are essentially constant time (O(1)) operations? This is due to the fact that they don't do any related cleanup for their operation - they defer/delegate the work to delete-min.
• This means if you do a series of insert or decrease-keyoperations on a Fibonacci heap, no related cleanup is being performed. This allows those operations to be faster than the same operations in a binary heap.
• So when does the cleanup happen? The next time delete-min is called.
• So using our example of doing a series of insert/decrease-key operations, if we followed those with a delete-min operation - this would trigger our batch cleanup operation.
• Lets go through what each operation is doing under the hood:
  • insert: This just adds a new node to the list of heaps (it doesn't add the node to an existing heap in the list)
  • delete-min:
    • Removes the min-root
    • Children of min-root get promoted to the root list
    • Trees with the same degree (number of children) are merged together
    • The min-root pointer is updated
  • decrease-key:
    • If decreasing the key of a child node such that the child node's key is now less than its parent's key: consider the child node a heap violating node
    • Put heap violating nodes into the root list and mark the old parent as loser
    • If a parent loses two children in this fashion, it is also put into the root list (removed from it's heap - same as it's children were)
    • Moving parents in this way prevents parents from having a large number of children but no grandchildren
    • Having little to no grandchildren in a heap would make delete-min very slow - so it is best avoided

---

As always, if you found any errors in this post please let me know!