Exercise Sheet 1

Instructions. Please read the exercises carefully and solve as many as you can. Then, at the latest by 23:55 on 18 March 2025, upload (1) a full description of your solutions (as pdfs, plaintext or scans) into TUWEL (under ‘Solution Upload for Exercise Sheet 1’), and additionally also (2) mark which exercises you solved in TUWEL (under ‘Solved Exercises (Exercise Sheet 1)’). In case of technical issues with uploading your solutions or general questions about the exercises, please contact the email listed above. A set of optional hints is provided on the last page of the sheet

Exercise 1.

Instruction

Consider the following generalisation of the weakly NP-hard subset sum problem:

Input: An integer , a multiset of -dimensional vectors over integers, a targetr -dimensional vector over integers.
Question: Does there exists a subset such that ?

Prove that vector subset sum is strongly NP-hard, i.e., that it is NP-hard even if all numbers on the input are encoded in unary.

We want to prove NP-hardness by reducing a 3-SAT instance to vector subset sum. Instead of packing constraints into the digits of one number, we can give different constraints their own vector coordinates.

Let be a propositional formula in conjunctive normal form, with variables and three literals per clause:

Selecting vectors must encode two requirements:

1. Each variable receives exactly one truth value.
2. Each clause has at least one true literal.

We therefore use coordinates: the first enforce the variable choices, and the last check the clauses. The indicator equals if the proposition holds and otherwise. We use 3-SAT with three distinct variables per clause, so each literal occurs at most once in a clause.

Choose exactly one truth value per variable

For each variable , create two vectors and . Selecting means setting to true; selecting means setting to false. This single choice applies to every occurrence of in .

Give both vectors a in variable coordinate and in the other variable coordinates:

Set each variable coordinate of to . At coordinate , selecting neither vector contributes , selecting exactly one contributes , and selecting both contributes . Thus equality with forces exactly one truth value for . Any vectors added later must have in these first coordinates.

Count the true literals in each clause

In clause coordinate , a selected variable vector should contribute precisely when its truth value makes a literal of true:

• contributes if occurs in .
• contributes if occurs in .

This gives the complete variable vectors:

Here, membership in means occurrence as a literal. Once one vector per variable is selected, the sum at coordinate is exactly the number of true literals in . We need , but vector subset sum tests equality with one target, not membership in this set.

Turn “at least one” into an exact sum

Use as the clause target and allow a contribution of or to be filled up to . The required additions are

We therefore need optional vectors that can add , , or at coordinate , but cannot add . Two copies of a vector with a single do exactly this:

These are two separately selectable occurrences in the multiset . A satisfied clause can reach by selecting copies. An unsatisfied clause starts at and can reach at most .

The resulting instance is

The symbol preserves all occurrences, including equal vectors.

Inspecting the encoding

For , the variable vectors are

For the satisfying assignment , we obtain

Why the NP-hardness is strong

We have encoded satisfiability as a vector subset sum instance. But can we still write this instance in polynomial time if every input number must be encoded in unary?

Let be the length of the original 3-SAT input. The numbers and count variables and clauses appearing in , so . The output is the tuple ; we must count the symbols needed to write it, not just the number of vectors.

First, how many numerical entries do we write? Lay out as a table with one row per vector and one column per coordinate, then add one row for :

Next, how many symbols does each entry require? Every entry of is or , and every entry of is or . Even in unary, each entry therefore takes only symbols, including a delimiter or a marker for zero.

The dimension is also an input number. Writing in unary takes symbols, so it does not change the overall bound:

We can also construct this table in polynomial time: initialise its entries to zero, place the variable-choice and fill-up entries, and scan the three literals of each clause to place its contributions.

Thus the reduction works directly for unary-encoded vector subset sum. A polynomial-time algorithm for that problem would solve 3-SAT in polynomial time. Vector subset sum is therefore strongly NP-hard.

Unlike a construction that packs many constraints into the digits of one large integer, this construction adds coordinates. The table grows, but its entries remain small; unary encoding does not cause an exponential expansion.

Exercise 2.

Instruction

Consider the following variant of the knapsack problem:

Input: A multiset over of integer pairs of the form , integers and .
Question: Does there exists an assignment such that:

• , and
• , and
• ?

Describe a polynomial-time algorithm for two-bag knapsack when all numbers on the input are encoded in unary. Briefly argue correctness for your algorithm.

Fix an order of the items. Assume non-negative integer weights and capacities. The next item has weight and profit .

One item, three possible next states

Orange marks changed coordinates. Below each state is its candidate profit; .

The dynamic programming table has three coordinates and stores one value:

Start: ; all other entries start at .

Repeat: follow the three edges from every reachable state; omit edges exceeding a capacity.

Merge: same means the same future choices; keep the largest candidate profit.

For the recurrence below, we switch from the graph’s exact weights to capacity bounds: stores the best profit using the first items with bag weights at most . Without any items under consideration, we have a total profit of , i.e.,

Iterate over each pair , then , and then , from bottom up. For each pair, we have three different choices available:

1. Skip: The item was skipped and we just copy the previous state, i.e.,

2. Bag1: The item was put into . Therefore, the previous state must’ve been

as we’ve added item with weight ; hence:

3. Bag2: The item was put into . Thereore, the previous state must’ve been

as we’ve added item with weight ; hence:

Together, for item with weight and profit :

Candidates whose conditions fail are omitted from the maximum.

We keep the maximum because the question asks for profit at least :

At each intermediate entry, the candidates satisfy the same capacity bounds; keeping the largest profit cannot hurt any later choice.

Exercise 3.

Instruction

Assume we are given an instance of vertex cover. Let be the instance of dominating set produced by the reduction from vertex cover to dominating set.

1. If has vertices and edges, can we determine the number of vertices and edges in ? If so, compute them; otherwise, explain why not.
2. If has vertices, determine the minimum and maximum possible number of vertices in .

Let , with and . The reduction makes the following changes.

Subdivide every edge

For each edge , introduce a distinct vertex and replace by and . This adds vertices and replaces edges by edges.
A vertex cover contains an endpoint of every edge . The new vertex is adjacent to precisely those endpoints: an original vertex chosen to cover now dominates . This turns each edge-covering requirement into a vertex-domination requirement.

Add a hub for the original vertices

Add a vertex adjacent to every , but not directly to the subdivision vertices. This adds one vertex and edges. The triangle below illustrates the operation; the construction applies to every original vertex.

This does not forbid choosing subdivision vertices. Before the leaves are attached, one can choose original vertices to dominate their incident and , or choose some alongside or an original vertex that dominates . Mixed choices are possible. Selecting dominates every original vertex at once, but not any ; these still require attention.

Force the hub into a small dominating set

Attach distinct leaves to . This adds vertices and edges. Set . If a dominating set of size at most omitted , it would have to select all leaves to dominate them, which is impossible.
Once has used one place in the budget , at most places remain. The leaves force , not a choice between original and subdivision vertices for those remaining places.

Each edge is subdivided, not retained alongside its two replacement edges. Consequently,

If is a vertex cover of with , then dominates . The vertex dominates every original vertex and every new leaf. Each subdivision vertex is adjacent to an endpoint of in . Thus .

Conversely, let dominate with . The leaves force , leaving at most other selected vertices. They need not all be original vertices. We can, however, turn into a dominating set of that form without increasing its size:

1. Discard any selected leaves; already dominates them.

2. For each selected , select either endpoint or in its place. The endpoint still dominates . The only other vertices that could have dominated were and , which are already dominated by . Remove duplicates if two replacements choose the same endpoint.

3. We now have with and . As does not dominate any , each such vertex must have an endpoint in . Hence covers every edge of .

4. For and , the formulas give and . Neither count is determined without . For example, changing from to changes both counts by one.

5. For vertices, . Under the usual convention , the tight bounds are

   An edgeless graph with attains the lower bound; a complete graph with attains the upper bound. If arbitrary non-negative is allowed without normalising it to , there is no upper bound depending only on for this literal construction: it adds leaves.

The leaves are omitted from the next two pictures to keep the selected vertices visible. They force in both cases. Orange-filled vertices are selected; each arrow replaces a selected subdivision vertex by an original endpoint, without adding a place to the budget.

: a triangle

There are four leaves and . Both and dominate the transformed triangle. The replacement preserves domination of ; dominates and . The diagrams show the core of before and after replacement.

: a triangle with a pendant edge

Add and the edge to the triangle. There are five leaves and . The set dominates all four subdivision vertices: dominates and . Replace and to obtain of the same size. The retained still dominates .

Exercise 4.

Instruction

Recall that the Boolean satisfiability problem (SAT) is polynomially solvable when the inputs are restricted to Horn formulas, i.e., formulas in conjunctive normal form where every clause contains at most one positive literal. Consider now a more general class of formulas, which we may here call “3-Horn”, defined as follows: a formula in conjunctive normal form is 3-Horn if each of its clauses contains at most three positive literals.

Prove that SAT remains NP-complete even when restricted to inputs that are 3-Horn formulas.

To prove that 3-Horn SAT is NP-complete, we must prove two properties: that it is in NP, and that it is NP-hard.

Membership in NP: 3-HORN SAT is a more restricted version of the more general SAT. Since SAT is in NP, any restricted subset of SAT, including 3-HORN SAT, is inherently also in NP. Essentially, a subset of problems of a problem can’t be more complex than the problemm itself.

NP-hardness: To prove NP-hardness, we perform a Karp reduction from 3-SAT. Given a Boolean formula in CNF, where every clause contains at mmost three literals in total, 3-SAT decides whether can be satisfied. Taking such an instance , we can just re-use as as the target instance for 3-Horn SAT. As only contains three literals per clause, trivially, it follows that it can only contain at most three positive literals. Hence, is structurally valid input for 3-Horn SAT. Since is completely identical to :

Therefore, every YES-instance of 3-SAT is true iff 3-Horn SAT is a YES-instance. Equivalently for NO-instances. Given that we make no structural modifications and simply copy , this reduction runs in polynomial running time.

Given NP-membership and NP-hardness, we conclude that 3-Horn SAT is NP-complete.

Exercise 5.

Instruction

Recall that the Boolean satisfiability problem (SAT) is also polynomially solvable when the inputs are restricted to 2-SAT formulas, i.e., formulas in conjunctive normal form where every clause contains at most two literals. Consider now a more general class of formulas, which we may here call “2-SAT4”, defined as follows: a formula in conjunctive normal form is 2-SAT4 if it contains at most 4 clauses of size at least 3. Equivalently stated, a formula is 2-SAT4 if and only if it can be transformed into a 2-SAT formula by deleting at most 4 clauses.

What the restriction says

A 2-SAT4 formula may have many clauses of size at most two, but at most four large clauses. For instance, this formula has two large clauses:

Deleting the two whole clauses and leaves , a 2-SAT formula. The number 4 in “2-SAT4” limits how many large clauses there are, not how many literals one large clause may contain.

We can solve the 2-SAT4 problem in polynomial time given that the number of transformations (clause deletions) required fromm 2-SAT4 to 2-SAT is bounded by constant , and 2-SAT is solvable in polynomial time (presented in the lecture).

Let be a 2-SAT4 formula over variables and clauses. We partition the formula into two distinct set of clauses:

• : The 2-SAT formula (clause of size or )
• : The set of deleted clauses that prevent from being pure 2-SAT (clause size ).

For , we already know a polynomial-time algorithm from the lecture via implication graphs.; thus, we can solve it efficiently.

For , we know that the number of these large clauses is bounded, i.e.,

Denote thse large clauses as .

• If , is already a pure 2-SAT formula and can be solved directly via .
• If , any satisfying assignment for must satisfy and also satisfy every large clause .

To satisfy a specific clause , at least one of it literals must evaluate to true. We can iteratove over every possible way to to satisfy by picking exactly one literal from each big clause , i.e.,

This search over al tuples still runs in polynomial-time, because there are at most large clauses. If each clause contains at most literals, then the total number of tuples is at most

which is polynomial in the input size. For each possible tuple , we construct a new restricted 2-SAT formula

Given that is a 2-SAT formula, we can efficiently solve it via implication graphs (as shown in the lecture). If the solver returns YES for any , our algorithm halts and returns YES. Otherwise, if the algorithm exhausts all possible tuples without finding a satisfiable , it returns NO.

Exercise 6.

Instruction

Give a polynomial reduction (i.e., an encoding) from the dominating set problem to integer linear programming.

Given an arbitrary dominating set instance , we transform into ILP instance as follows:

1. Variables: For each vertex , we create an integer variable with

2. Domain constraints: is supposed to be binary; thus:

3. Maximum constraint: To ensure that the chosen dominating set contains at most vertices, we bound the sum of all variables:

3. Domination constraints: Let denote all adjacent vertices of vertex and itself. For each vertex , it must either be selected or having a selected neighbour; hence:

3. Opt. function and target: Given that dominating set is a decision problem, we only care about whether the constraints are feasible, i.e.,

This ensures that condition always evaluates to , which is always true, i.e., only the constraints above must be fulfilled.