Exercise Sheet 2

Exercise 1. Set Cover

Instruction

Consider the following minimum set cover problem.
Input: A universe of elements, a collection of subsets of , .
Task: Find a minimum cardinality subcollection of that covers all elements of .

1. Show that minimum set cover admits a -approximation algorithm where is the maximum number of subsets that an element can appear in. (Hint: Adapt the factor-2 approximation algorithm from the minimum vertex cover problem)
2. Show that if every set in has at most elements, then minimum set cover admits a -approximation algorithm.

A -approximation algorithm for this minimisation problem means that the algorithm runs in polynomial time and always returns a set cove with

where is the size of an optimal set cover.

(1) Show that minimum set cover admits a -approximation algorithm where is the maximum number of subsets that an element can appear in. (Hint: Adapt the factor-2 approximation algorithm from the minimum vertex cover problem)

Let be the universe of all elements, be the input collection, and the maximum number of substes that an element can appear in. Then:

Further, let be the set of elements chosen on the choose line:

Each chosen element appears in at most sets by definition of , so . The algorithm adds only sets in on the iteration that chooses . Hence

To bound , first consider what happens to two chosen elements when is chosen before . Suppose an input set contains both. Because , the set belongs to . Hence

The iteration choosing removes from . It would therefore remove , making it impossible to choose from later. This contradiction shows that each input set contains at most one chosen element:

Every valid set cover must cover all elements of . Since one set covers at most one element of , every set cover needs at least sets. Thus

Therefore

so the algorithm is a -approximation algorithm.

(2) Show that if every set in has at most elements, then minimum set cover admits a -approximation algorithm.

Now each contains at most elements; there is no bound on how many sets contain a given element. Choose one set containing an uncovered element on each iteration.

Let be the elements chosen on the choose line. Each iteration chooses a set containing its chosen element and removes that set from . Thus the elements of are distinct, and the algorithm chooses exactly one new set per element of :

Any sets cover at most elements, because each contains at most elements. To cover all elements of , a feasible solution must therefore satisfy , or . In particular,

Combining the bounds gives

Each iteration removes at least its chosen element , so there are at most iterations. Finding a set containing can be done by scanning the input collection. Hence the algorithm runs in polynomial time and is a -approximation.

Exercise 2. Maximum Coverage

Instruction

Consider the following maximisation problem.

Maximum Coverage
Input: An undirected graph and a number .
Task: Find a vertex subset of cardinality at most so that the number of edges that it covers is maximised, where .

Show that for every approximation ratio , if the maximum vertex degree is larger than , then one can find in polynomial time a solution that covers at least edges.

Hint: Sort the vertices by their degrees and take the ones with the highest degrees.

For this maximisation problem, a -approximation means that the algorithm returns a feasible set with

where is the maximum number of edges that can be covered by at most vertices.

Choose the highest-degree vertices

Assume is a simple graph. If , return ; if , every feasible solution meets the stated bound. For and , sort the vertices by degree and take the first :

Computing degrees and sorting takes polynomial time. For a vertex set , let

An edge leaving contributes once to both and . An edge inside contributes twice to but once to . An edge outside contributes to neither. The diagram shows one edge of each kind; the numbers label its contributions to the two counts.

Let be the edges with exactly one endpoint in . In the diagram, and . Adding the degrees of the vertices in counts the internal edge at both endpoints and the leaving edge at only one:

In the diagram this reads . Rearranging the general equality removes the one extra count per internal edge:

Let be an optimal solution, with and . The indices are distinct positions in the degree-sorted list . The -th chosen position cannot be earlier than position : positions must contain all choices , so . For example, if the first three positions of are , then , , and . Since degrees decrease along the list, the vertex at position has no greater degree than the vertex at position :

Therefore

This bounds optimal coverage by the degree sum of , not yet by the number of edges covers. Since has vertices and is simple, there are at most internal edges. Hence

Let be the maximum degree. The first chosen vertex has degree , so . Under the given hypothesis,

Subtracting this overcount from the degree sum yields

Thus is a feasible, polynomial-time -approximation.

Exercise 3. Maximum Independent Set

Instruction

Is it correct that the greedy approach of Minimum-Degree-First can be used to provide a -approximation for the following Maximum Independent Set problem? If yes, prove it; otherwise, provide a counterexample with at most 12 vertices.

Maximum Independent Set
Input: An undirected graph .
Task: Find a maximum-cardinality vertex subset such that no two vertices in are adjacent.

Minimum-Degree-First is not a -approximation

The algorithm repeatedly selects a vertex of minimum degree in the remaining graph, adds to its independent set , and deletes and all its neighbours. A -approximation would require on every graph. We will try to make the algorithm discard a large independent set when it chooses its first vertex.

Try one greedy choice. We might make a vertex adjacent to every other vertex, so that choosing deletes the whole graph. For example, connect to four pairwise non-adjacent vertices :

Choosing would be terrible, but Minimum-Degree-First chooses a leaf of degree instead. This is not just a defect of this particular star. If greedy returned only , its first choice must have deleted every vertex, so . Since had minimum degree, every other vertex must also have degree at least . That is the greatest possible degree: the graph is complete, and . A one-choice counterexample is impossible.

Allow two greedy choices. Aim for and an independent set of size , so that . Keep adjacent to the four independent vertices . If greedy chooses , it deletes . Call the vertices left behind .

Greedy must take exactly one vertex from . If had a non-adjacent pair, some vertex would have degree at most . A minimum-degree vertex of would therefore also have a non-neighbour, which would survive its selection and force a third greedy choice. Thus every pair in needs an edge: must be a clique, rather than a shape chosen arbitrarily. To give the optimum a fifth vertex, reserve one vertex with no neighbours in ; then stays independent.

How large must be? We will need , of degree , to have strictly smaller degree than . We cannot connect to without destroying that independent set, or to without deleting it when is chosen. Its only neighbours are therefore the other vertices of . Since is a clique, , which requires . Take the smallest such choice, . First draw only the star and this clique, with no edges between and :

The surviving clique now explains why choosing would leave only one more greedy choice, while explains how the optimum could take five vertices. But this is not yet a counterexample: each vertex in has degree , whereas . Greedy would still choose from first.

Make the minimum-degree choice. Each vertex of needs at least four more neighbours to exceed . We cannot add edges inside or to without spoiling the five-vertex independent set. The five vertices in are available: join each vertex of to all five. These are the faint cross-edges in the completed graph below. They raise the degree of each vertex of to , without adding an edge inside . No other edges are added. The retained vertices have the same positions and colours as in the previous picture.

In the original graph, the degrees are

Thus is the unique minimum-degree vertex. Selecting removes , leaving exactly the clique . From a clique the algorithm can select only one vertex, regardless of tie-breaking, so . Yet contains no adjacent pair and has size . Consequently,

This graph disproves the claimed -approximation.

Exercise 4. FPTAS versus Pseudo-Polynomial

Instruction

For certain types of NP-optimisation problems, an FPTAS implies pseudo-polynomial solvability. However, the converse does not always hold. This exercise illustrates this point. Consider the following generalisation of the Knapsack problem.

Bi Knapsack
Input: items , where each has two integer sizes ; two capacity bounds and .
Task: Find a subset of items with and such that is maximised.

1. Show that Bi Knapsack admits a pseudo-polynomial-time algorithm via dynamic programming. Prove correctness and analyse the running time of your algorithm.

   Hint: Extend the Max-Value Knapsack DP table to two capacity dimensions: maximum items picked from with size-1 budget and size-2 budget .

2. It is known that Bi Knapsack is (weakly) NP-hard. Show that it does not admit an FPTAS unless .

   Hint: It suffices to show that if Bi Knapsack had an FPTAS, then Bi Knapsack would even be polynomial-time solvable.

(1) Dynamic programming with two capacities

For and (), let be the largest number of items from that fit within capacities :

The empty set is feasible, so . For item , write . An optimal subset either skips or takes it. The latter is possible only when and :

Fill the table in increasing order of :

Correctness. Induct on . With no items, is optimal for every capacity pair. Assume row is correct. If an optimal subset of excludes , its maximum size is . If it includes , the remaining items fit within , so its maximum size is . These are precisely the feasible cases compared by the recurrence. Thus row is correct, and is the optimum. Predecessor choices can be stored if the actual subset is required.

Running time. First fix the instance itself, rather than treating as its input length:

The item pairs are listed explicitly in , so . By contrast, each capacity is one encoded integer, not a list of all budgets it permits. The table nevertheless visits every triple

It therefore has entries. In the usual table-cost model, computing each entry takes constant work, so time and space have that same order. The distinction is between the explicit item pairs in and the budget ranges implicit in the two capacity numbers.

Encode the integers in in binary. To see what this means for , consider the family of actual instances

There is one item, and each capacity is written as a followed by zeros. Including fixed tuple delimiters, the binary input has length . Yet the table materialises both ranges :

Thus this DP can take exponential time in the length of a binary input, even with only one item. If instead the same instance were written in unary, writing each capacity would already take symbols. More generally, unary input length is at least proportional to , making the table size polynomial in that length. The DP is therefore pseudo-polynomial: its table is polynomial in the numerical capacities, but not necessarily in the length of their binary encodings. This describes this DP, not a lower bound on every algorithm for Bi Knapsack.

(2) An FPTAS would solve Bi Knapsack exactly

Suppose an FPTAS exists. For , run it with . Its running time is polynomial in the input length and , hence polynomial in the input length. If it returns a feasible subset , its guarantee gives

because . Feasibility also gives . Both quantities are integers, so . When the empty set is already optimal. Thus the FPTAS would yield a polynomial-time exact algorithm for an NP-hard problem, implying . Unless , no FPTAS exists.

Exercise 5. Maximum Satisfiability and Knapsack

Instruction

1. Show that there exists a randomised algorithm which returns a truth assignment for MaxE4SAT satisfying in expectation clauses, where denotes the total number of clauses.

2. Show that the Highest Value-per-Size First greedy algorithm for Max-Value Knapsack can return arbitrarily bad solutions in the following sense.

   Hint: Show that for each fractional value there exists an instance with two items such that the greedy algorithm returns a solution with . Make sure that the item sizes and values are positive integers.

(1) A uniformly random assignment

Independently set each variable of the formula to true or false with equal probability, then return the resulting assignment .

In MaxE4SAT, each clause has four literals on distinct variables. It is unsatisfied only if all four literals are false. Their truth values are independent under this assignment, so

Let be if is satisfied and otherwise. The number of satisfied clauses is . By linearity of expectation, which does not require the clauses to be independent,

(2) Value-per-size greedy can be arbitrarily bad

What must go wrong? Greedy ranks items by value divided by size, but it cannot take a fraction of an item. We want it to pick a small item with slightly higher density, leaving too little room for a large item whose total value is much greater. With only two items, greedy must take the small one first and then be unable to take the large one; the optimum must take the large one instead.

Let the capacity be an integer . Make the large item have size exactly . Any positive-size item taken before it will then block it. Give the small item the smallest positive integer size and value, both . Its density is . If the large item’s integer value is , the conditions we need are

The first condition forces . To make the optimum as valuable as possible while keeping greedy’s choice strict, take the largest allowed integer, . This derives the two-item instance:

Item	Size	Value	Value per size

The same capacity is shown twice. Greedy’s first item has the higher density, but occupying even one unit prevents the full-width item from fitting. The widths are schematic; the marked lengths give the actual sizes.

Greedy chooses . Its remaining capacity is , so cannot fit and its value is . Taking alone is feasible and gives ; both items together have size . Thus, for ,

Why choose at all? So far we have a family of counterexamples, one for each integer . Their greedy-to-optimal ratio is : increasing leaves greedy’s value at while increasing the optimum to . To prove arbitrarily bad performance, we must respond to any requested threshold with an instance whose ratio is at most .

Fix first. Because and , we can multiply and divide by and without reversing the inequality. Work backwards from the required ratio:

Since must be an integer, take the smallest permitted value:

Thus for which the greedy ratio is at most . The indivisible, full-capacity item lets one tiny greedy choice block a value that grows with .

Exercise 6. Maximum Cut

Instruction

Consider the following graph optimisation problem.

Max Cut
Input: An undirected graph .
Task: Find a bipartition of the vertices such that the number of edges with endpoints in both and is maximised.

Here, let denote the set of edges that each have one endpoint in and another endpoint in . Show that the following local search algorithm is a -approximation algorithm.

1. Start with an arbitrary bipartition , . Let .
2. If there exists a vertex such that adding to the other set increases the cut size, i.e., , pick such a vertex ; set and . Increase .
3. Analogously, if there exists a vertex such that adding to the other set increases the cut size, i.e., , pick such a vertex; set and . Increase .
4. Terminate when no suitable vertex is found; otherwise repeat steps 2–3.

Hint: Use the local-optimality condition at termination together with double counting.

Local optimality counts at least half the edges

A -approximation must return a bipartition with . Start from any bipartition and repeatedly move a vertex to the other part whenever doing so strictly increases the cut size. This is the local search described above.

A cut is the set of edges crossing between and . In the small graph below, has two neighbours in its own part and one neighbour across the cut in . Move only to : the other vertices stay put. Orange edges cross the cut; cyan edges do not.

The edge stops crossing the cut: subtract one. The edges and start crossing it: add two. All other edges are unchanged, so the new cut size minus the old cut size is . For any vertex , write for its number of neighbours across the cut and for its number of neighbours on the same side. Moving loses cut edges and gains cut edges. Hence

The algorithm stops only when no vertex can make the cut larger by moving. Since is the new cut size minus the current cut size, this means for every ; equality is allowed because a move that changes nothing is not an improvement. Using , we obtain

Here is a cut at which moving cannot help. The orange edges already cross the cut; the cyan edges do not. Vertex has two orange edges to lose but only one cyan edge to gain:

All four vertices in this graph have two neighbours across the cut and one on their own side, so no single move improves it. The condition holds for each vertex separately. In the next graph, equality holds instead: each vertex has one orange cut edge and one cyan same-part edge, so .

Write for the cut edges and for the same-part edges. In the pictured graph, and . The edge contributes to and to ; it contributes nothing at the other vertices. Likewise, contributes to and to . Thus this graph gives and .

The same count holds for any graph: each edge has two endpoints. A cut edge is counted once in at each endpoint, while a same-part edge is counted once in at each endpoint. Summing over all vertices therefore gives

Since and partition and ,

Also, , so

The cut size is an integer and increases by at least one on every move. It never exceeds , so there are at most moves. Checking all vertices for an improving move takes polynomial time; hence the whole local search runs in polynomial time.