Our course starts with the rather pessimistic message that the computational state of virtually every problem of interest to us is undetermined. It is quite difficult to determine whether a given problem admits an efficient (polynomial-time) algorithm or "not"; in which case we refer to it as intractable. We distinguish between two time-complexity classes. The first is called P and it comprises of all languages that can be efficiently solved. The second is called NP and it consists of all languages that can be solved efficiently using a non-deterministic computational model. A subclass of the latter, referred to as the set of NP-complete languages will become synonymous with what we shall refer to as intractable languages.
SOLVED EXERCISEs:
This link leads to various solved exercises on the topic of NP-Completeness
2ND SHORTEST PATH​
The shortest (or lightest) path problem is efficiently soluble using algorithms by Bellman-Ford and Dijkstra. Navigation systems often offer you several paths that you may choose to travel through. This, in particular, raises the problem of finding the 2nd shortest path (or more generally the kth shortest path) between two vertices in a graph.
Why study Graph Theory?
It was through graph theory that computer scientists came to a true understanding of how hard is the P vs. NP problem. Indeed, we have seen through various examples that NPC-reductions rely intimately on knowledge from Graph Theory.
​
Nevertheless, we have another agenda bringing us head to head with Graph Theory; we are interested in optimisation.
Rudiments of Matching Theory
Matchings in graphs
A veteran problem in Combinatorial Optimisation is the maximum matching problem in graphs. Here, one seeks a set of independent edges (= sharing no common end) of maximum size.
​
This problems is quite natural and admits numerous applications.
Solved Exercises
The following links lead to exercises on matchings in graphs.
Vertex-Connectivity in Graphs
Solved Exercises
The following links lead to exercises on both vertex and edge connectivity in graphs.
Hamiltonicity
Solved Exercises
The following link leads to exercises on the Hamiltonicity of graphs
VIDEO LECTURE
VIDEO LECTURE
Solved Exercises
Linear programming: Exercises
​
Approximation Algorithms: Exercises
​
Approximating the minimum edge-dominating set problem
​
Sanity check: short review problems