Combinatorial optimization: an introduction

Published

18 October 2026

Combinatorial optimization is one of the youngest and most actively developing areas of discrete mathematics. Optimization problems arise in scheduling theory, facility location, network design, database management, information transmission, and also in economics and finance — from investment to auction and marketing strategies.

Unfortunately, most such problems are $\operatorname {NP}$-hard, and it is believed that no efficient algorithms exist for solving them exactly. The main goal of our course is therefore to study methods for constructing approximation algorithms and approximation schemes. To do this we must first formally define the problems under consideration and the properties of the algorithms.

1 Vertex cover

Let us start with a concrete example. One of the typical problems of combinatorial optimization is the vertex cover problem. Recall that a vertex cover of a graph $G=(V, E)$ is a subset of vertices $S \subseteq V$ such that every edge of $G$ has at least one endpoint in $S$.

Minimum-cardinality vertex cover

An undirected graph $G=(V, E)$.

A vertex cover of minimum size (cardinality).

In a more general formulation each vertex is assigned a nonnegative weight, and we must find a vertex cover of minimum total weight.

Minimum-weight vertex cover

An undirected graph $G=(V, E)$, vertex weights $c: V \to \mathbb {Q}_+$.

A vertex cover of minimum total weight.

The minimum-weight vertex cover problem

A graph $G=(V,E)$ with vertex weights $c$ (the numbers on the edges are shown only as an example of labeling; in the problem the weight is attached to each vertex $v_i$). Hover over a vertex to see its weight and highlight its incident edges.

The minimum vertex cover problem is said to be $\operatorname {NP}$-hard. What does this mean?

2 Assessing the hardness of a problem: from optimization to decision

In general, any optimization problem can be paired with a decision problem (i.e., a problem with a YES/NO answer). If we want to minimize some function $f(x)$, say, the corresponding decision problem is stated as follows:

Does there exist a solution $x$ with $f(x) \le k$?

where $k$ is a parameter supplied together with the input.

For example:

Optimization problem: find a vertex cover of minimum size.
Corresponding decision problem: given $k$, determine whether there exists a vertex cover of size at most $k$.

If the decision problem is $\operatorname {NP}$-hard, then the original optimization problem is also said to be $\operatorname {NP}$-hard. Intuitively this means that no efficient (polynomial-time) algorithm exists for finding an exact solution in every possible case.

Problem 1

Show that the minimum-cardinality vertex cover problem is NP-hard.

Hint

You need to show that the language \[ \mathrm{VERTEXCOVER} = \left\{ \langle G,k\rangle \; : \; \text{$G = (V,E)$ is an undirected graph, and $G$ has a vertex cover with at most $k$ vertices}\right\} \] is NP-hard. Use the NP-hardness of the language $\operatorname {CLIQUE}$.

It is still unknown whether the classes $\mathrm{P}$ and $\mathrm{NP}$ coincide. In particular, this means that no fast (polynomial-time) algorithm for exactly solving the vertex cover problem has been found so far. If such an algorithm existed, it would automatically follow that $\mathrm{P} = \mathrm{NP}$.

The prevailing scientific opinion is that $\mathrm{P} \neq \mathrm{NP}$, and hence that, in all likelihood, no efficient algorithm for exactly solving the vertex cover problem exists at all. This is precisely why special attention is paid to approximation algorithms, which yield solutions in polynomial time with a guarantee on their quality.

3 The first approximation algorithm: a greedy algorithm for vertex cover

One of the first methods that it is natural to try when solving an optimization problem is the greedy algorithm. A greedy algorithm is an iterative procedure that at each step chooses the locally best option, trying to improve the objective function as much as possible while ignoring the future consequences of that choice.

For the vertex cover problem this means that at each step we choose the vertex incident to the largest number of edges.

Algorithm 1 Greedy algorithm for the vertex cover problem

$G' \gets G$, $\operatorname{Sol} \gets \varnothing$
while $E(G') \neq \varnothing$ do
- find a vertex $v \in V(G')$ incident to the maximum number of edges
- $\operatorname{Sol} \gets \operatorname{Sol} \cup \{v\}$
- remove $v$ and all edges incident to $v$ from $G'$
return $\operatorname{Sol}$

It is easy to construct an example in which the greedy algorithm produces a solution far from optimal. The figure below shows a graph for which the greedy choice leads to a provably suboptimal cover.

The greedy algorithm for vertex cover

At each step the algorithm takes the vertex of maximum degree (among the still-uncovered edges), adds it to the solution, and removes all edges incident to it. The orange outline marks the vertex the algorithm will pick next; hover to see the current degrees.

This example makes it clear that the greedy algorithm can output a solution at least $5/4$ times the optimum. This raises the question: how bad can the greedy algorithm’s result be in the worst case? Is there a tight bound? To answer this we need to carry out a formal analysis and derive a quality bound.

4 Analyzing the algorithm

Assessing the quality of an approximation algorithm usually amounts to comparing its solution with the optimal one. However, for $\operatorname {NP}$-hard problems, not only finding an optimal solution but even computing its cost is an $\operatorname {NP}$-hard problem. In other words, using the optimum directly to control an algorithm’s quality is essentially impossible (it simply cannot be computed in a reasonable amount of time).

The standard approach is therefore to construct polynomially computable lower bounds on the cost of the optimal solution. Such bounds make it possible to assess approximation quality and often suggest the structure of the algorithm itself.

Computing the accuracy of the greedy algorithm given above is not as simple as it might seem. We will deal with this in the next chapter. For now, let us consider another approximation algorithm for the vertex cover problem.

4.1 An algorithm for vertex cover via matchings

Algorithm 2 Algorithm for the vertex cover problem via matchings

$G' \gets G$, $\operatorname{Sol} \gets \varnothing$
while $E(G') \neq \varnothing$ do
- find an arbitrary edge $e \in E(G')$, let $e = \left\{v_1,v_2\right\}$
- $\operatorname{Sol} \gets \operatorname{Sol} \cup \{v_1,v_2\}$
- remove $v_1$, $v_2$, and all edges incident to $v_1$, $v_2$ from $G'$
return $\operatorname{Sol}$

The matching-based algorithm for vertex cover

The algorithm builds a maximal (by inclusion) matching — a set of edges with no shared vertices — and outputs all vertices incident to its edges. Red edges form the matching; hover over an edge to see whether it can still be added.

At first glance this algorithm may seem less efficient than the greedy one. However, as we will show, it has a constant accuracy guarantee: its solution is at most twice as bad as the optimum. The greedy algorithm, on the other hand, as we will see in the next chapter, can in the worst case perform arbitrarily worse than the optimum.

Moreover, the output of the matching-based algorithm is often easy to improve by postprocessing: one can try removing from the resulting set any vertices whose removal does not break the covering of all edges. This brings the solution closer to optimal. This simple trick generally does not work for the output of the greedy algorithm.

4.2 Accuracy of the algorithm

Key fact: the size of a maximal (with respect to inclusion) matching is a lower bound on the size of any vertex cover. Indeed, for every edge of the matching, at least one of its endpoints must belong to the cover. Since the edges of a matching share no vertices, the number of vertices in any cover cannot be smaller than the number of edges in the matching. This simple fact shows how lower bounds are naturally connected to the construction of approximate solutions.

Theorem 1 The matching-based algorithm is a 2-approximation algorithm for the minimum-cardinality vertex cover problem.

Proof

Let $M \subset E$ be a maximal (with respect to inclusion) matching in the graph. The algorithm selects two vertices for each edge of $M$, so $\left|\sigma_{\mathrm{matching}}\right| = 2\left|M\right|$. Since $|M|$ is a lower bound on the size of any vertex cover, we get \[ \left|\sigma _{\mathrm{matching}}\right| = 2\left|M\right| \leq 2 \cdot \left|\sigma ^*\right|, \] where $\sigma^*$ is an optimal cover.

We have obtained our first approximation algorithm. The main questions for improving the result are:

Can the quality analysis of the algorithm be sharpened? Is the bound of 2 given above tight?
Does there exist an algorithm with approximation factor $\rho <2$ that always produces a solution no worse than $\rho$ times the lower bound?
Can other lower bounds be used to construct a $\rho$-approximation algorithm with $\rho <2$?

4.3 Is the algorithm’s bound tight?

The following example shows that the quality analysis of the matching-based algorithm cannot be improved. We construct an infinite family of examples on which it is off by a factor of two. Consider the complete bipartite graph $K_{n, n}$ shown in the figure below. The matching-based algorithm will select all $2 n$ vertices into the solution on this graph, whereas the optimal solution consists of the $n$ vertices of one side.

Tightness of the matching-based algorithm's bound: $K_{n,n}$

In the complete bipartite graph $K_{n,n}$, any perfect matching is already maximal by inclusion, so the algorithm selects all $2n$ vertices, whereas the optimal cover is a single side of $n$ vertices: the ratio tends to $2$.

$n=$3

4.4 Is there another algorithm that improves on the lower bound we obtained via the size of a maximal matching?

Suppose the lower bound via the size of a matching is used to assess solution quality. Let us give an example on which the value of this lower bound differs from the optimum by a factor of two. Consider the complete graph on $n$ vertices, where $n$ is odd. The size of a maximum matching equals $(n-1) / 2$, while the size of an optimal vertex cover is $n-1$. Hence the cost of the solution produced by any algorithm (even a non-polynomial one) can be almost twice as bad as the lower bound.

The complete graph $K_5$: a 2-edge matching versus a 4-vertex cover

In $K_5$ (an odd number of vertices), a maximum matching contains only 2 edges, e.g. $\{v_1,v_2\}$ and $\{v_3,v_4\}$ — the matching-based algorithm will return 4 vertices. But the optimal cover also consists of 4 vertices (any 4 out of 5): here the algorithm happens to be exact.

4.5 Is there another algorithm that is better overall, perhaps using some other lower bound?

The question of whether a $\rho$-approximation algorithm with $\rho <2$ exists, using some other lower bound, is much harder. Recently Subhash Khot put forward a plausible conjecture [7], [8], according to which the existence of a polynomial-time algorithm for the vertex cover problem with a guaranteed bound of $2-\varepsilon$ for any fixed $\varepsilon >0$ would imply that the classes $\operatorname {P}$ and $\operatorname {NP}$ coincide.

5 Optimization problems and approximation algorithms

Let us give the general definitions.

Definition 1 A problem $\Pi$ is defined by the following information:

a general list of all its parameters (Given);
a statement of the properties that the answer, or in other words the solution of the problem, must satisfy (Find).

An individual problem (also called an instance) $I$ is obtained from the problem $\Pi$ by assigning specific values to all the parameters of $\Pi$.

A problem $\Pi$ is called an optimization problem (of minimization or maximization type) if it consists of:

a set $\Omega_{\Pi}$ of individual problems (instances);
a finite set $\operatorname {Sol}_{\Pi }(I)$ of feasible solutions of an individual problem $I \in \Omega_{\Pi }$;
an objective function (criterion) $\operatorname {COST}_{\Pi }$, assigning to each individual problem $I \in \Omega_{\Pi }$ and each feasible solution $\sigma \in \operatorname {Sol}_{\Pi }(I)$ a rational number $\operatorname {COST}_{\Pi }(I, \sigma )$, called the cost of the solution $\sigma$.

If $\Pi$ is a minimization problem, then an optimal solution of an individual problem $I \in \Omega_{\Pi }$ is a feasible solution $\sigma^{*} \in \operatorname {Sol}_{\Pi }(I)$ such that for every $\sigma \in \operatorname {Sol}_{\Pi }(I)$ the inequality

\[ \operatorname {COST}_{\Pi }\left(I, \sigma ^{*}\right) \leq \operatorname {COST}_{\Pi }(I, \sigma ) \]

holds (if $\Pi$ is a maximization problem, the inequality is reversed).

An algorithm that finds an optimal solution for every instance of the problem is called exact.

Most combinatorial optimization problems arising in applications are $\operatorname {NP}$-hard. There are various approaches to solving such problems.

Solve exactly with “brute-force” algorithms. Unfortunately, for most $\operatorname {NP}$-hard problems, brute-force algorithms only handle instances of small size.
Solve approximately.
- Algorithms with an a posteriori accuracy guarantee. The accuracy is not known in advance, although in practice such algorithms often find solutions close to optimal.
- Algorithms with an a priori accuracy guarantee. For such algorithms one can prove that they always find a solution with a guaranteed accuracy bound in the worst case.

In this course we will mainly study approximation algorithms with a guaranteed worst-case accuracy bound.

Definition 2 For a problem $\Pi$, fix an individual problem (instance) $I \in \Omega_{\Pi }$. Let $\operatorname {COST}(\sigma_{A})$ be the cost of the solution $\sigma_A = \sigma_A(I)$ found by algorithm $A$, and let $\operatorname {OPT}(I) := \operatorname {COST}(\sigma^*)$ be the cost of an optimal solution $\sigma^* = \sigma^*(I)$. A polynomial-time algorithm $A$ is called a $\rho$-approximation algorithm ($\rho > 0$) for the optimization problem $\Pi$ if for every instance $I \in \Omega_{\Pi }$ the algorithm finds a solution satisfying the inequality

$\operatorname {COST}(I, \sigma_{A}) \leq \rho \operatorname {OPT}(I)$, if $\Pi$ is a minimization problem (here $\rho \in (1, +\infty )$);
$\operatorname {COST}(I, \sigma_{A}) \geq \rho \operatorname {OPT}(I)$, if $\Pi$ is a maximization problem (here $\rho \in (0, 1)$).

We call the quantity $\rho$ the accuracy bound (approximation ratio) of algorithm $A$.

How does one construct an approximation algorithm?

Study the combinatorial structure of the problem.
Study the properties of an optimal solution.
Look for an algorithmic technique that exploits these properties.
Generalize and extend techniques and experience accumulated while building polynomial-time algorithms.

6 Polynomially solvable problems

There is a range of classical combinatorial optimization problems for which efficient exact polynomial-time algorithms are known. Below are the best-known examples.

6.1 Minimum spanning tree

The minimum-weight spanning tree problem (minimum spanning tree, MST). A spanning tree of a connected graph $G = (V,E)$ is a tree containing all the vertices of the graph. Weights are assigned to the edges, and we must find a spanning tree of minimum total weight.

Classical polynomial-time algorithms exist for this problem: Kruskal’s algorithm, Prim’s algorithm, and also faster algorithms based on modern data structures.

6.2 Shortest paths

One of the fundamental problems is finding shortest paths in a graph.

From a single source (single-source shortest paths): Dijkstra’s algorithm (for nonnegative weights), the Bellman–Ford algorithm (also works with negative edge weights).
Between all pairs of vertices: the Floyd–Warshall algorithm and Johnson’s algorithm.

All of these problems can be solved in polynomial time and are widely used in practice.

6.3 Maximum flow

The maximum flow problem in a transportation network. Given a directed network $G = (V,E)$ with capacities $c : E \to \mathbb {R}_+$, we must find the largest flow from a source $s$ to a sink $t$ satisfying the edge constraints and conservation laws.

Known algorithms: the Ford–Fulkerson algorithm, the Edmonds–Karp algorithm, Dinic’s algorithm, and various modern refinements. Closely related is the minimum cut problem, which is equivalent to the maximum flow problem (the max-flow min-cut theorem).

6.4 Minimum-cost flow

A generalization of the maximum flow and assignment problems. Given a network with capacities $c : E \to \mathbb {R}_+$ and costs $w : E \to \mathbb {R}$, we must find a flow of a given value with minimum cost.

Exact polynomial-time algorithms are known for this problem, for example based on potential (successive shortest paths) algorithms.

6.5 Maximum matching

A subset of edges $M \subseteq E$ is called a matching if no two edges of $M$ share a vertex.

A maximum matching is a matching with the largest possible number of edges.
A maximal matching is a matching to which no edge can be added.

Every maximum matching is maximal, but not conversely.

For bipartite graphs the problem is solved by the Hungarian algorithm (Kuhn’s algorithm). For general graphs, Edmonds’ algorithm (the blossom algorithm) is used.

6.6 Minimum-weight $k$-factor

A spanning subgraph is a subgraph containing all the vertices of the original graph.

A graph is called $k$-regular if all of its vertices have degree $k$.

A $k$-factor of a graph $G$ is a $k$-regular spanning subgraph of $G$. In particular:

a $1$-factor is a perfect matching, i.e., a matching covering all vertices of the graph;
a $2$-factor is a collection of cycles covering all vertices of the graph.

Exact polynomial-time algorithms exist for the minimum-weight $k$-factor problem, including ones based on a reduction to the perfect matching problem.

Thus, although many combinatorial optimization problems are $\operatorname {NP}$-hard, there is a broad class of fundamental problems for which efficient polynomial-time algorithms have been developed. These problems and methods serve as building blocks for more complex algorithms and approximation schemes.

7 Exercises

Problem 2

Propose a $\frac{1}{2}$-approximation algorithm for the following problem.

Maximum acyclic subgraph

A directed graph $G=(V, E)$.

A maximum-cardinality set of arcs $E^*$ such that the resulting subgraph $(G, E^*)$ contains no cycles.

Hint

Number the vertices in an arbitrary order. Now every edge goes either from a smaller number to a larger one, or from a larger number to a smaller one. Choose the larger of these two edge sets, $E'$. How can the optimum be bounded from above?

Problem 3

Recall that in an undirected graph $G = (V,E)$ a matching $E'$ is called maximal with respect to inclusion (we will call it an MIM) if no edge $e$ from $E \setminus E'$ can be added to $E'$ so that $E' \cup \left\{ e\right\}$ remains a matching. Maximal matchings can differ in their number of elements. Devise a 2-approximation algorithm for finding a minimum-cardinality MIM in an undirected graph.

Use the fact that an arbitrary maximal matching has at least half as many edges as a maximum matching.

Problem 4

Consider the following 2-approximation algorithm for the minimum-cardinality vertex cover problem. Using depth-first search, build a tree in the graph $G$ and output the set $S$ of internal vertices of this tree. Show that $S$ is indeed a vertex cover of $G$ and that $|S| \leq 2 \cdot \operatorname {OPT}$.

Hint

Show that $G$ has a matching of size $|S| / 2$.

Problem 5

Consider the following greedy algorithm for the minimum-cardinality vertex cover problem. At each step choose a vertex of maximum degree, add it to the cover, and remove it together with all edges incident to it. Continue until all edges have been removed. Prove that for a graph with $n$ vertices this algorithm always produces a solution whose cost is at most $\ln n$ times the optimum. Construct an example on which the solution produced by the greedy algorithm is $100$ times worse than optimal.

Problem 6

In the maximum cut problem we are given a graph $G=(V, E)$ and must partition the vertex set $V$ into two disjoint subsets (two sides) $V_{1}$ and $V_{2}$ so as to maximize the number of edges connecting vertices in different subsets.

Choose an arbitrary partition of the vertex set $V$.
If there is a vertex $v \in V$ such that the number of its neighbors on the side it belongs to is greater than the number of its neighbors on the other side, move this vertex from one side to the other.
If there is no such vertex, output the resulting partition.

Prove that the algorithm terminates after a finite number of steps and that the solution it finds contains at least half of all the edges of $G$.

Combinatorial optimization: an introduction

1 Vertex cover

The minimum-weight vertex cover problem

2 Assessing the hardness of a problem: from optimization to decision

3 The first approximation algorithm: a greedy algorithm for vertex cover

The greedy algorithm for vertex cover

4 Analyzing the algorithm

4.1 An algorithm for vertex cover via matchings

The matching-based algorithm for vertex cover

4.2 Accuracy of the algorithm

4.3 Is the algorithm’s bound tight?

Tightness of the matching-based algorithm's bound: \(K_{n,n}\)

4.4 Is there another algorithm that improves on the lower bound we obtained via the size of a maximal matching?

The complete graph \(K_5\): a 2-edge matching versus a 4-vertex cover

4.5 Is there another algorithm that is better overall, perhaps using some other lower bound?

5 Optimization problems and approximation algorithms

6 Polynomially solvable problems

6.1 Minimum spanning tree

6.2 Shortest paths

6.3 Maximum flow

6.4 Minimum-cost flow

6.5 Maximum matching

6.6 Minimum-weight \(k\)-factor

7 Exercises