Exercise Sheet 3

Exercise 1

Instruction

Recall the reduction from 3-SAT to Subset Sum presented in the second lecture. Assuming that the Exponential Time Hypothesis holds, what does this reduction imply for the possible running times of algorithms solving Subset Sum? In particular, could Subset Sum then admit an algorithm running in time:

• $O^{\ast }(3^{|P|})$
• $O^{\ast }(2^{0.5|P|+7})$
• $O^{\ast }(2^{\sqrt{|P|}\cdot \log |P|})$

Let the 3-SAT formula $F$ have $n$ variables and $m$ clauses. We want to reduce it to subset sum by creating a set $P$ and a target sum $T$ such that

$$\exists P^{\prime }\subseteq P:\sum _{w\in P^{\prime }}w=T⟺F\text{ is satisfiable}$$

To solve this, we attach a quantity $\mathrm{q}(c)$ to each clause $c\in C$, where each clause should have a quantity of $3$ if $F$ is satisfiable.

We reduce $F$ to subset sum $(P,T)$ by constructing a set $P$ that contains

• two numbers for each variable $x$, i.e. $x_T$ and $x_F$
• two fill-up numbers for each clause

Fill-up numbers

For each clause $c$, let $q(c)$ count how many selected assignment numbers satisfy $c$.

If $c$ is satisfied, then

$$q(c)\in \{1,2,3\}.$$

If $c$ is not satisfied, then

$$q(c)=0.$$

The target asks for every clause digit to equal $3$. Therefore, for each clause, we add two fill-up numbers with value $1$ in that clause digit and $0$ everywhere else.

These can “repair” the satisfied cases:

$$1+1+1=3,2+1=3,3=3.$$

But they cannot repair an unsatisfied clause:

$$0+1+1=2<3.$$

Thus the fill-up numbers make “at least one true literal” equivalent to “the clause digit can be filled to $3$”.

Hence, the constructed set $P$ has cardinality

$$|P|=2n+2m=O(n+m),$$

since we create two numbers $x_T$ and $x_F$ for each variable, and two fill-up numbers for each clause. Thus $|P|$ is linearly bounded in the size of the original 3-SAT formula.

The target sum $T$ is built digit by digit. There is one digit for each variable and one digit for each clause. In every variable digit, $T$ has value $1$, forcing the subset to choose exactly one of $x_T$ and $x_F$. In every clause digit, $T$ has value $3$, forcing the selected assignment numbers together with the fill-up numbers to fill each satisfied clause exactly to $3$. Thus, if there are $n$ variables and $m$ clauses, the target has the form

$$T=\underset{n\text{ variable digits}}{\underbrace{11\cdots 1}}\underset{m\text{ clause digits}}{\underbrace{33\cdots 3}}$$

Shape of one element

Suppose there are $2$ variables and $2$ clauses. Then every number in $P$ has $2+2=4$ digits.

If setting $x_1$ to true satisfies only clause $C_2$, then the corresponding assignment number is

$$x_{1,T}=\underset{\text{variable digits}}{\underbrace{10}}\underset{\text{clause digits}}{\underbrace{01}}.$$

The variable part says that this number belongs to $x_1$. The clause part says that this truth choice contributes $1$ only to $C_2$.

A fill-up number for $C_1$ would look like

$$\underset{\text{variable digits}}{\underbrace{00}}\underset{\text{clause digits}}{\underbrace{10}},$$

since it contributes only to the first clause digit and does not choose any variable value.

If subset sum had an algorithm $A$ with running time $f(|P|)$, then we could first reduce a 3-SAT formula to a subset-sum instance with $|P|=O(n+m)$ and then run $A$. This would give a 3-SAT algorithm with running time $f(O(n+m))$, up to polynomial factors from the reduction.

If the exponential-time hypothesis is true, then 3-SAT cannot be solved in time

$$O^{\ast }(2^{o(n+m)})=O(2^{o(n+m)}\cdot n^d)$$

where $o(\cdot )$ is the small-o notation, i.e. strict asymptotic upper bound, and $O^{\ast }(\cdot )$ is the big-o-star notation, i.e. the asymptotic upper bound suppressing polynomial factors. Therefore, the reduction above rules out a subexponential algorithm w.r.t. $|P|$ under the assumption of ETH for subset sum.

Solution

Assuming ETH being true, then:

1. $O^{\ast }(3^{|P|})$ is allowed , since

$$3^{|P|}=2^{{\log }_2(3)|P|}=2^{O(|P|)},$$

which is still single-exponential in $|P|$, not subexponential.

2. $O^{\ast }(2^{0.5|P|+7})$ is also allowed, given that the exponent

$$0.5|P|+7=O(|P|)$$

is still linear in $|P|$. ETH does not forbid improving the constant in a linear exponent. That would be the role of SETH.

3. $O^{\ast }(2^{\sqrt{|P|}\log |P|})$ is not allowed, as its exponent is sublinear:

$$\sqrt{|P|}\cdot \log |P|=o(|P|),$$

as

$$\begin{array}{rl}\underset{|P|\to \infty }{\lim }\frac{\sqrt{|P|}\log |P|}{|P|}& =\underset{|P|\to \infty }{\lim }\frac{\cancel{\sqrt{|P|}}\log |P|}{\cancel{\sqrt{|P|}\cdot }\sqrt{|P|}}\\ & =\underset{|P|\to \infty }{\lim }\frac{\log |P|}{\sqrt{|P|}}\\ & =0,\end{array}$$

given that $\log |P|\ll \sqrt{|P|}$. Since $|P|=O(n+m)$, this would give a 3-SAT algorithm running in

$$O^{\ast }(2^{o(n+m)}),$$

contradicting ETH.

Exercise 2

Instruction

Consider the following variant of the classical graph 4-colouring problem. In Equitable 4-Colouring, we are given a graph and are asked for a proper 4-colouring (i.e., one where neighbours do not receive the same colour) but where additionally each colour is used essentially the same number of times ($\pm 1$). To avoid any confusion, a formal definition of the problem is provided below.

Equitable 4-Colouring Input: A connected $n$-vertex graph $G$ Question: Does there exist a partition of the vertices $V(G)$ of $G$ into four sets $A_1,A_2,A_3,A_4$ such that

1. for each $1\le i\le 4$, each $A_i$ is an independent set, and
2. for each $1\le i\le 4$ and $1\le j\le 4$, $|A_i|\le |A_j|+1$?

EQUITABLE 4-COLOURING admits a simple brute-force exponential algorithm that runs in time $O^{\ast }(4^n)$ and simply exhaustively enumerates all possible assignments of colours to the vertices (whereas for each assignment, one can check in polynomial time whether conditions (1) and (2) are satisfied).

The task is to design a single-exponential algorithm for EQUITABLE 4-COLOURING with a running time that has a better base of exponent than $4$, i.e., one with running time $O^{\ast }(c^n)$ for some $c<4$.

A 4-colouring is a function $f:V(G)\to \{1,2,3,4\}$. If we ignore all graph structure, then every vertex has four possible colours. Hence the naive search space is

$$4^n=|\{1,2,3,4\}{|}^n$$

So the base $4$ comes from the fact that we treat every vertex as if all four colours were always possible. To improve the base, we need to force the situation that, for most vertices, at least one colour is already unavailable, so that the search has running time $O^{\ast }(c^n)$ for some $c<4$.

The proper-colouring condition says that neighbours must not have the same colour assignment, i.e.

$$\forall uv\in E(G):f(u)\ne f(v)$$

So if a vertex $v$ already has an already-coloured neighbour $u$, then $v$ is forbidden from using colour $f(u)$. Since there are at most four colours, this leaves at most $4-1=3$ possible colours for $v$.

Given that $G$ is connected, it has a DFS tree. Pick an arbitrary root vertex $v_1$. Then order the remaining vertices according to DFS discovery order

$$v_1,v_2,\dots ,v_n,$$

where the DFS run takes polynomial time.

For every $i>1$, the vertex $v_i$ has a parent in the DFS tree. That parent appears earlier in the order. Hence

$$\forall i>1:\exists j<i:v_i{v}_j\in E(G).$$

So when colouring $v_i$, it has at least one already-coloured neighbour.

Further, we can fix the root node’s colour to an arbitrary colour, e.g.

$$f(v_1)=1,$$

given that the names of the colours don’t matter, only the constraints they impose on the graph. Hence, we only have to search through 3 colours for each of the remaining $n-1$ vertices. Therefore, with a fixed root, we have a runtime complexity of

$$O^{\ast }(3^{n-1})=O^{\ast }(3^n),$$

which is single-exponential given that the exponent is linearly bounded.

For every completed colouring, we then check in polynomial time whether it is actually a valid solution. First, we check the proper-colouring condition, i.e. whether adjacent vertices receive different colours. Then we form the four colour classes $A_1,A_2,A_3,A_4$ and check the equitable size condition

$$\forall 1\le i,j\le 4:|A_i|\le |A_j|+1.$$

These checks only add a polynomial factor, so they are hidden by the $O^{\ast }(\cdot )$ notation.

Correctness

If the algorithm finds a solution, the produced partition

$$V(G)=A_1\cup A_2\cup A_3\cup A_4$$

satisfies that every $A_i$ is an independent set, because adjacent vertices have different colours.

It also satisfies the equitable condition, because the algorithm only accepts a colouring after checking that the four colour classes differ in size by at most one. In other words, for all $1\le i,j\le 4$, it verifies that

$$|A_i|\le |A_j|+1.$$

Hence the accepted partition is not only a proper 4-colouring, but an equitable 4-colouring.

Conversely, suppose that $G$ has an equitable 4-colouring. Since the names of the four colours are arbitrary, we may rename the colours so that the root $v_1$ receives colour $1$. The algorithm fixes exactly this root colour and then enumerates all valid colour choices for the remaining vertices. Therefore, it eventually considers this equitable colouring. Since it is proper and its colour classes satisfy the size condition, the algorithm accepts it.

Exercise 3

Instruction

Design a subexponential algorithm for SAT when the input is restricted to instances such that $m\le \sqrt{n}$, where $m$ is the number of clauses and $n$ the number of variables.

Given a SAT formula $F$ over $n$ variables and $m$ clauses of form

$$F=C_1\wedge C_2\wedge \cdots \wedge C_m$$

with the promise that $m\le \sqrt{n},$ we want to find a subexponential algorithm, i.e. an algorithm that has a runtime of $2^{o(n)}$.

A naive SAT algorithm enumerates all assignments

$$\alpha :\{x_1,x_2,\dots ,x_n\}\to \{0,1\},$$

i.e. has a naive runtime of $O^{\ast }(2^n)$. However, we’re given a upper boundary for the number of clauses, which means that it makes more sense to branch over clauses rather than variables.

CNF formula $F$ is satisfiable iff every clause has at least one true literal. Further, each clause in $F$ has at most $2n$ distinct literals, given that each variable has only two possible literals:

$$x_i\text{or}\neg x_i$$

So the number of possible choices is at most

$$\prod _{i=1}^m|C_i|\le (2n{)}^m.$$

Given $m\le \sqrt{n}$, this is at most

$$(2n{)}^m\le (2n{)}^{\sqrt{n}}$$

For every tuple $({\ell }_1,\dots ,{\ell }_m)\in C_1\times \cdots \times C_m$ do the following:

1. Remove duplicate literals, if any.
2. Check whether the chosen literals are consistent, i.e. there must not be a variable such that $x$ and $\neg x$ are in the chosen literals.
3. If the chosen literals are consistent, assign all of them to true.

Example

If the chosen literals are $x_1,\neg x_4,x_7$, then set

$$x_1=\text{true},x_4=\text{false},x_7=\text{true}$$

3. Assign all remaining variables arbitrarily.
4. Accept.

If no tuple of chosen literals is consistent, reject.

Boolean SubexpSAT(Formula F)

let F = C_1 ∧ C_2 ∧ ... ∧ C_m;
let α := empty partial assignment;

for each (ℓ_1, ℓ_2, ..., ℓ_m) ∈ (C_1 × C_2 × ... × C_m) {
    α := empty partial assignment;
    consistent := true;

    for i := 1 to m {
        if (ℓ_i = x) {
            required := true;
        }

        if (ℓ_i = ¬x) {
            required := false;
        }

        if (x ∈ dom(α)) {
            if (α(x) ≠ required) {
                consistent := false;
                break;
            }
        } else {
            α(x) := required;
        }
    }

    if (consistent = true) {
        return true;
    }
}

return false;

Correctness

Suppose the algorithm accepts, then it found one chosen literal

$${\ell }_i\in C_i$$

for every clause $C_i$, and all chosen literals are mutually consistent. So we can assign all chosen literals to true. Therefore every clause $C_i$ contains at least one true literal, namely ${\ell }_i$, i.e. the whole formula is satisfied.

Conversely, suppose $F$ is satisfiable. Let $\alpha$ be a satisfying assignment. Since $\alpha$ satisfies every clause, every clause $C_i$ contains at least one literal that is true under $\alpha$. Choose one such literal ${\ell }_i$ from every clause. The tuple

$$({\ell }_1,\dots ,{\ell }_m)$$

is consistent, because all chosen literals are true under the same assignment $\alpha$. The algorithm enumerates this tuple and accepts.

Therefore, the algorithm is correct.

Running Time

For each clause, there are at most $2n$ possible literals. Hence, the number of tuples is at most $(2n{)}^m$. Using the promise $m\le \sqrt{n}$, we get

$$(2n{)}^m\le (2n{)}^{\sqrt{n}}=2^{\sqrt{n}{\log }_2(2n)}$$

Given that $\sqrt{n}\log n=o(n)$, we have

$$2^{\sqrt{n}{\log }_2(2n)}=2^{o(n)}$$

The consistency check for each tuple is polynomial time, so it is hidden inside $O^{\ast }(\cdot )$. Thus the running time is

$$O^{\ast }((2n{)}^m)\subseteq O^{\ast }((2n{)}^{\sqrt{n}})=2^{O(\sqrt{n}\log n)}=2^{o(n)}$$

Therefore, SAT with $m\le \sqrt{n}$ can be solved in $2^{o(n)}$, i.e. subexponential time.

Exercise 4

Instruction

Consider an NP-complete graph problem $\mathcal{P}$. Assume $\mathcal{P}$ admits a polynomial reduction from 3-SAT which transforms each $n$-variable 3-SAT formula into an instance of $\mathcal{P}$ with at most $n^3$ vertices.

Now, say we have an algorithm $A$ that solves any $z$-vertex instance of $\mathcal{P}$. Under the Exponential Time Hypothesis, which of the following running times can we exclude for $A$?

1. $O^{\ast }(2^{(z^4)})$
2. $O^{\ast }(2^{\sqrt{z}})$
3. $O^{\ast }(2^{z^{\log z}})$
4. $O(z^7)$

We’re given an NP-complete graph problem $\mathcal{P}$ that with

• $\mathcal{P}$ admits a polynomial-time reduction 3-SAT ${\le }_p\mathcal{P}$
  • that transforms $n$ variables of 3-SAT
  • into $n^3$ vertices of $\mathcal{P}$
• $A$ solves $\mathcal{P}$ in $T(z)$ time for $z$ vertices.

We know that after the reduction, the number of vertices $z$ is constrained by

$$z\le n^3.$$

If $T(n^3)=2^{o(n)}$, then 3-SAT can be solved in subexponential time, contradicting ETH.

Solution

1. $O^{\ast }(2^{z^4})$: Given that

$$z^4\le (n^3{)}^4=n^{12},$$

we know that

$$O^{\ast }(2^{z^4})\subseteq O^{\ast }(2^{n^{12}}).$$

Given that the exponent is worse than linear, i.e. $O^{\ast }(2^{n^{12}})$ is not subexponential, (1) is not excluded under the ETH.

2. $O^{\ast }(2^{\sqrt{z}})$: Given that

$$z\le n^3,$$

it follows that

$$O^{\ast }(2^{\sqrt{z}})\subseteq O^{\ast }(2^{n^{1.5}}).$$

Again, the running time is not subexponential, meaning that (2) is not excluded under the ETH.

3. $O^{\ast }(2^{z^{\log z}})$: From

$$z^{\log z}\le (n^3{)}^{\log n^3}=n^{9\log n}$$

it follows that

$$O^{\ast }(2^{z^{\log z}})\subseteq O^{\ast }(2^{n^{9\log n}}).$$

Again, (3) is not subexponential, i.e., it is not excluded under ETH.

4. $O(z^7)$: From

$$z^7\le (n^3{)}^7=n^{21}$$

it follows that

$$O(z^7)\subseteq O(n^{21}).$$

This result would conclude that we have found a polynomial-time algorithm (polynomial reduction + polynomial algorithm) that can solve 3-SAT. This contradicts the ETH, i.e., it is excluded.

Exercise 5

Instruction

For each of the following basic scheduling algorithms, construct an example instance of $1\mid r_j;\overline{d_j}\mid -$ where the algorithm fails.

• Earliest Due Date (EDD) First
• Earliest Release Date First
• Shortest Processing Time First

The notation

$$1\mid r_j;\overline{d_j}\mid -$$

means that

• we have one machine,
• job $j$ can’t be processed before $r_j$ (its release time), and
• we have no objective function.

Earliest Due Date First

The earliest due date first algorithm selection policy chooses, at a time $t$, the available job $j$ with the earliest due date $d_j$.

Take two jobs $j_1,j_2$ with:

• $j_1$:
  • $r_{j_1}=0$
  • $p_{j_1}=2$
  • $d_{j_1}=4$
• $j_2$:
  • $r_{j_2}=1$
  • $p_{j_2}=1$
  • $d_{j_2}=2$

At $t=0$, only $j_1$ can be chosen, because $j_2$ has not yet been released. Hence EDD chooses $j_1$.

At $t=2$, only $j_2$ remains. But $j_2$ cannot meet its deadline anymore, since it would complete at time $3$:

$$C_{j_2}=3>2=d_{j_2}.$$

This is not because the instance itself is infeasible. A feasible schedule is obtained by idling until $t=1$ and then processing

$$j_2,j_1.$$

Earliest Release Date First

The earliest release date first algorithm selection policy chooses, at a time $t$, the available job $j$ with the earliest release date $r_j$.

Take three jobs $j_1,j_2,j_3$ with:

• $j_1$:
  • $r_{j_1}=0$
  • $p_{j_1}=1$
  • $d_{j_1}=1$
• $j_2$:
  • $r_{j_2}=0$
  • $p_{j_2}=3$
  • $d_{j_2}=5$
• $j_3$:
  • $r_{j_3}=1$
  • $p_{j_3}=1$
  • $d_{j_3}=3$

At $t=0$, $j_1,j_2$ are available with equal release times. The algorithm chooses $j_1$; this is the best tie-breaking choice, since it meets the tight deadline

$$d_{j_1}=1.$$

At $t=1$, the algorithm can choose between $j_2$ and $j_3$. It chooses $j_2$, because

$$r_{j_2}=0<1=r_{j_3}.$$

At $t=4$, only $j_3$ remains. It would complete too late, since

$$C_{j_3}=5>3=d_{j_3}.$$

This is not because the instance itself is infeasible. A feasible schedule is obtained by processing

$$j_1,j_3,j_2.$$

Shortest Processing Time First

The shortest processing time first algorithm selection policy chooses, at a time $t$, the available job $j$ with the shortest processing time $p_j$.

Take two jobs $j_1,j_2$ with:

• $j_1$:
  • $r_{j_1}=0$
  • $p_{j_1}=2$
  • $d_{j_1}=2$
• $j_2$:
  • $r_{j_2}=0$
  • $p_{j_2}=1$
  • $d_{j_2}=3$

At $t=0$, both jobs are available. The algorithm chooses $j_2$, since

$$p_{j_2}=1<2=p_{j_1}.$$

At $t=1$, only $j_1$ remains. It would complete too late, since

$$C_{j_1}=3>2=d_{j_1}.$$

This is not because the instance itself is infeasible. A feasible schedule is obtained by processing

$$j_1,j_2.$$

Exercise 6

Instruction

Consider the following three schedules for $1||\sum C_j$ (i.e., the scheduling problem with one machine where the aim is to minimize the sum of completion times) for an instance with precisely 4 jobs $a,b,c,d$:

• $S_1:a,b,c,d$
• $S_2:c,d,a,b$
• $S_3:b,a,d,c$

Assume that the job durations satisfy $p_a+p_b=p_c+p_d$. Under this assumption, answer the following two questions:

1. Do $S_1$ and $S_2$ always have the same sum of completion times?
2. Do $S_1$ and $S_3$ always have the same sum of completion times?

In each case, if the answer is yes then provide a proof sketch, and otherwise provide a counterexample.

The notation

$$1\mid \mid \sum C_j$$

means that there’s one machine, no further constraints, and the objective function is the total completion time .

Let’s take $S_1$ first. The completion times are

• $C_a=p_a$,
• $C_b=p_a+p_b$,
• $C_c=p_a+p_b+p_c$, and
• $C_d=p_a+p_b+p_c+p_d$.

So the total completion time for $S_1$ is

$$\begin{array}{rl}\sum _j{C}_j& =C_a+C_b+C_c+C_d\\ & =4p_a+3p_b+2p_c+p_d\end{array}$$

For $S_2$, the completion times are

• $C_c=p_c$,
• $C_d=p_c+p_d$,
• $C_a=p_c+p_d+p_a$, and
• $C_b=p_c+p_d+p_a+p_b$.

Thus, the total completion time for $S_2$ is

$$\begin{array}{rl}\sum _j{C}_j& =C_c+C_d+C_a+C_b\\ & =4p_c+3p_d+2p_a+p_b.\end{array}$$

For $S_3$, the completion times are

• $C_b=p_b$,
• $C_a=p_b+p_a$,
• $C_d=p_b+p_a+p_d$, and
• $C_c=p_b+p_a+p_d+p_c$.

Thus, the total completion time for $S_3$ is

$$\begin{array}{rl}\sum _j{C}_j& =C_b+C_a+C_d+C_c\\ & =4p_b+3p_a+2p_d+p_c\end{array}$$

(1) Do $S_1$ and $S_2$ always have the same sum of completion times?

If $S_1$ and $S_2$ have the same sum of completion times, then the difference of their sums should be $0$.

$$\begin{array}{rl}\left(4p_a+3p_b+2p_c+p_d\right)-\left(4p_c+3p_d+2p_a+p_b\right)& =2p_a+2p_b-2p_c-2p_d\\ & =2(p_a+p_b)-2(p_c+p_d)\end{array}$$

Given the assumption

$$p_a+p_b=p_c+p_d,$$

we get

$$\begin{array}{rl}2(p_a+p_b)-2(p_c+p_d)& =2(p_a+p_b)-2(p_a+p_b)\\ & =0\end{array}$$

Therefore, the completion times of $S_1$ and $S_2$ always have the same sum of completion times under the assumption..

(2) Do $S_1$ and $S_3$ always have the same sum of completion times?

If $S_1$ and $S_3$ have the same sum of completion times, then the difference of their sums should be $0$.

$$\begin{array}{rl}\left(4p_a+3p_b+2p_c+p_d\right)-\left(4p_b+3p_a+2p_d+p_c\right)& =p_a-p_b+p_c-p_d\\ & =(p_a+p_c)-(p_b+p_d)\end{array}$$

Under the assumption above, it doesn’t follow that the difference of total completion times is $0$. Therefore, $S_1$ and $S_3$ do not always have the same sum of completion times.

Counterexample

A counterexample is

$$p_a=1,p_b=3,p_c=2,p_d=2.$$

Plugging those processing times into the equation gives

$$\begin{array}{rl}(p_a+p_c)-(p_b+p_d)& =(1+2)-(3+2)\\ & =3-5\\ & \ne 0.\end{array}$$