Tag Archives: Difficulty 3

Ratio Clique

Last week it was pointed out to me that my reduction for Balanced Complete Bipartite Subgraph was wrong, and in my searches to fix it, I found that the real reduction (by Johnson) used a variant of Clique that said (without proof)) that Clique is NP-Complete even if K was fixed to be |V|/2.  I looked up the Clique problem in G&J, and they say in the comments that it is NP-Complete for K = any fixed ratio of V.

I thought this was a neat easy problem that fit in the 3-6 difficulty range I mentioned last week and decided it was worth a post.  But thinking about this brings up some subtle issues relating to ratios and constants that are common sources of errors among students.  I’ll talk about that at the end.

The problem: I don’t know if there is an official name, so I’m calling it “Ratio Clique”.  It is mentioned in the comments to GT19 (Clique).

The description: For any fixed number r, 0< r < 1, does G have a clique of size r*|V| or more?

Example:  Here’s a graph we’ve used for a previous problem:

maximum fixed-length disjoint paths

If r = .5, then r*|V| = 3.5.  So we’re asking if a clique of 3.5 or more vertices exists (which really means a clique of 4 or more vertices).  It does not exist in this graph.  If r ≤ \frac{3}{7}, then we would be looking for a clique of size 3, which does exist in this graph (vertices b, c, and t)

The reduction: We will be reducing from the regular Clique problem.  Since we want to show this “for any fixed value of r”, we can’t change r inside our reduction.

So we’re given a graph G=(V, E) and a K as our instance of Clique. We need to build a graph G’=(V’, E’) that has a fixed K’ = ⌈r*|V’|⌉.

G’ will start with G, and will add new vertices to the graph.  The vertices we add depend on the ratio s of K to |V|    (K = ⌈s*|V|⌉).  K’ is initially K, but may change as vertices are added to the graph.

If r > s, then we need to add vertices to V’ that will connect to each other vertex in V’, and will increase K’ by 1.  This increases the ratio of \frac{K'}{|V'|}, and we keep adding vertices until that ratio is at least r.

If G has a clique of size K, then the extra vertices in K’ can be added to the clique to form a larger clique (since these new vertices connect to every other vertex)

If G’ has a clique of size K’, notice that it must contain at least K vertices that were initially in G. (We only added K’-K new vertices).  These vertices that exist in G are all connected to each other and so will form a clique in G.

If r < s, then we will add vertices to V’ that are isolated (have no edges connecting to them).  K’ will stay equal to K.  Each vertex we add will reduce the ratio of \frac{K'}{|V'|}, and we keep adding vertices until  K=⌈r*|V’|⌉.

Since these new vertices can not be part of any clique in G’, any clique in G’ must consist only of vertices from G.  Since K=K’, this gives us a clique of size K in both graphs.

It is probably also worth mentioning just how many vertices need to get added to the graph in each case, to make sure that we are adding a polynomial number.  If r>s, we will be adding w vertices to satisfy the equation: ⌈s*|V|⌉ + w = ⌈r*(|V|+w)⌉

(These are both ways of expressing K’)

Dropping the ceiling function (since it only leads to a difference of at most one vertex) Solving for w gets us w = \frac{(s|V|-r|V|)}{(r-1)}.  Since r > s, both sides of that division are negative, so w ends up being positive, and polynomial in |V|.

If r < s, we will be adding w vertices to satisfy the equation:

⌈s*|V|⌉ = ⌈r(|V|+w)⌉

(These are both ways of expressing K)

This can similarly be solved to w = s|V|-r|V|.  Since s > v, this is also a positive (and polynomial) number of new vertices.

A possible source of mistakes: I’m pretty sure this reduction works, but we need to be careful that there is a difference between “for any fixed ratio r of |V|” and “for any fixed K”.  Because for a fixed K (say, K=7) solving the “Does this graph have a 7-Clique?” problem can be solved in polynomial (by enumerating all subgraphs of size 7, for example.  There are n \choose 7 subgraphs, which is O(N^7)).  By choosing a ratio instead of a constant K, we gain the ability to scale the size of K’ along with the size of the graph and avoid this issue.  But it is worth mentioning this to students as a possible pitfall.  It’s very easy to do things in a way that effectively is treating r|V| as a constant K, which won’t work.

Difficulty: 3, but if you’re going to make students to the algebra to show the number of vertices that are added, bump it up to a 4.

Bin Packing Take 2

[So WordPress’s search function has failed me.  A search for posts on Bin Packing didn’t turn up this post, so I went ahead and wrote a whole second post for this problem.  Since this time my reduction uses 3-Partition instead of Partition (and so is a little less trivial for use as a homework problem), I figured I’d leave it for you as an alternate reduction.

I have been thinking off and on about whether it would be useful when I’m done with this project (years from now) to go back and try to find reductions that can be done easier (or harder) than what I’ve shown here, to give more options that are in the 3-6 difficulty range that I think is best for homework problems.  I’m not sure how feasible that task would be, but it’s something I’ll try to keep in mind as I go forward.

Anyway, here’s my post that talks about Bin Packing again:]

On to a new chapter! A4- “Storage and Retrieval”

This first one is a classic problem that I guess I haven’t done yet.

The problem: Bin Packing.  This is problem SR1 in the appendix.

The description: Given a finite set U of items, each with a positive integer size, and positive integers B and K.  Can we split U into k disjoint sets such that the sum of the elements in each set is B or less?

Example: Suppose U was {1,2,3,4,5,6}, K=4, and B= 6.  We want 4 disjoint sets that each sum to 6 or less.  For example:

  • {1,5}
  • {2,4}
  • {3}
  • {6}

Note that if K = 3, we would need 3 sets instead of 4, and this wouldn’t be solvable.

The simple reduction: G&J on page 124 say that Bin Packing contains 3-Partition as a special case.  So let’s try reducing from there. Recall the definition of 3-Partition:

Given a set A of 3M elements and an integer B such that the sizes of each element are between B/4 and B/2 and the sum of all of the elements is m*B, can we split A into m disjoint sets that each sum to exactly B?

Keeping in mind that the bounds on the elements in A mean that there are exactly 3 elements in each set in the partition, we can see how this maps easily to the Bin Packing problem:

  • U = A
  • K = m
  • Use the same B

While it is true that the Bin Packing problem allows the sums to be B or less, and the 3-Parittion problem forces the sets to sum to exactly B, the fact that all of the sets have to contain 3 elements and the fact that the sum of all of the element in U is m*B means that if any set in the Bin Packing answer is < B some other set will necessarily be more than B.

Difficulty: 3.  It is basically the same problem, but I think there is enough work needed to justify the reduction that it makes sense as a good easy homework problem.

Numerical Matching With Target Sums

In an effort to make my semesters easier, during breaks I do most of the research on the problems and write quick sketches of the reductions out.  This way when I get to the weekly post, most of the hard math work is done, and I don’t get surprised by a super hard problem.

(I’m doing something similar over our winter break at the present.  I’ve  got sketches up through the middle of April, and I’m currently working on problem SR13- “Sparse Matrix Compression”- which is an “unpublished manuscript”  problem that I’m having a lot of trouble with.  Keep your fingers crossed).

Anyway, I was looking through my notes today and I realized that I’d skipped this problem!  Luckily, I think the reduction is pretty easy.

The problem: Numerical Matching With Target Sums.  This is problem SP17 in the appendix.

The description: Given two sets X and Y, each with the same number (m) of elements, and each with a positive integer size.  We’re also given a “target vector” V, also of M elements, consisting of positive integer entities.  Can we create m sets A1 through Am such that:

  • Each Ai has one element from X and one element from Y
  • Each element in X and Y appears exactly once in some Ai
  • The sum of the sizes of the elements in each Ai is exactly Bi?

Example: I’ll use an example derived from last week’s Numerical 3-Dimensional Matching example because I think it will illustrate how the reduction will work:

  • X = {12,11,7,5}
  • Y = {1,1,4,5}
  • B = {13,12,11,10}

(W from last week was {1,2,3,4}, and B was 14.)

Letting A1 be the first elements of X and Y, A2 being the second elements of X and Y, and so on down, gives us a solution.

Reduction: G&J say to use Numerical 3-Dimensional Matching, and don’t even bother to mark it as “unpublished results”, probably because they think it’s so easy.

Our Numerical 3DM instance is three sets: W, X, and Y, and a bound B.  We need 2 sets and a “bound vector” for the instance of the Numerical Matching problem.  So what we do is:

  • X’ = X
  • Y’ = Y
  • Each bi in the B vector will be set to B-wi.  This is the amount we need the element from X and Y to add up to, so that when we add in the element from W, we get B.

If we have a solution to the Numerical 3-Dimensional Matching solution, then each Ai in that solution consists of 3 elements: wi, xj and yk that sum to B.  Then in our Numerical Matching With target Sums instance, we have a set Ai‘ where xj + yk sum to B-wi.  The same is true in the reverse direction.

Difficulty: 3, which may be too high.  I can see people getting confused by the fact that the sets in the 3DM instance can be taken in any order, but the B vector in the Target Sum matching problem needs to have Ai‘s element sum exactly to bi, and wondering how to force the correct W element to be in that spot?

(The answer is that you define it when you build B.  We set b1 to be “the sum that works when you use wi“, so it (or something with the exact same size, so we can swap the elements) has to go in that position in the vector).

Protected: Min-Max Multicenter

This content is password protected. To view it please enter your password below:

Monotone EQSat

Today I’m posting 2 problems relating to my student Dan Thornton’s independent study work.  I’m out of town this week and next, so I have these posts set to automatically go up on Tuesday afternoon.

Dan’s independent study was based on the “Automaton Identification” problem, but to show that reduction, he needs to use a variant of 3SAT, which he shows here:

The problem: Monotone EQ SAT. This is a specific instance of Monotone SAT.

The description:
We are given a conjunction of clauses F = \wedge_{i=1}^{l} C_{i} where each clause in F contains all negated or non-negated variables z_{j} and the number of clauses and variables are equal, is there an assignment of the variables so that F is satisfied? Our instance will have l clauses and variables.

Example:
Here is an F that has 4 variables and 4 clauses.

F =( \neg x_{1} \vee \neg x_{2} \vee \neg x_{3} \vee \neg x_{4} ) \wedge ( x_{1} \vee x_{2} \vee x_{4} ) \wedge ( \neg x_{2} \vee \neg x_{3} \vee \neg x_{4} ) \wedge ( x_{1} )

The above F may be satisfied by the following assignment:
x_{1} \rightarrow True
x_{2} \rightarrow False
x_{3} \rightarrow False
x_{4} \rightarrow True

The reduction:
We will reduce from Monotone SAT. So we are given an instance of Monotone  SAT with the clauses F = \wedge_{i=1}^{n} C_{i} here each clause is of the form C_{i} = (x_{i1} \vee ... \vee x_{ik_i} ) where each clause has all negated or non-negated variables. This is different from Monotone EQ SAT as we do not require the number of variables and clauses to be equal.
From this F we must build an instance of Monotone EQ SAT.
We may transform our instance of Monotone SAT, F, into one of Monotone EQ SAT by the following iterative procedure. New variables will be denoted by z'_{j} and new clauses by C'_{i}.

 F' = F;
 i = 1;
 j = 1;
 While{number of clauses != number of variables}{
   introduce two new variables z'_{j} \ , \ z'_{j+1};
   If{number of variables < number of clauses}{
     Create the new clause C'_{i} = (z'_{j} \vee z'_{j+1});
     F' = F' \wedge C'_{i};
     i = i+1;
   }
   else {
     Create three new clauses:
      C'_{i} = z'_{j} \ ,
      C'_{i+1} = z'_{j+1} \ ,
      C'_{i + 2} = (z'_{j} \vee z'_{j+1} );
     F' = F' \wedge C'_{i} \wedge C'_{i+1} \wedge C'_{i+2};
     i = i + 3;
   }
 j = j+2;
 }

The above algorithm will produce an equation F' that is in Monotone EQ  SAT. This may be shown by induction. Notice that before the procedure if number \ of \ variables > number \ of \ clauses that we will add 2 new variables and 3 new clauses.

If number \ of \ variables < number \ of \ clauses then we will add 2 new variables but only a single new clause. Either way the difference between the number of variables and clauses, dif =| number \ of \ clauses \ - \ number \ of \ variables | will decrease by 1. So in O(dif) steps we will obtain an formula where dif = 0. Such an formula is an instance of Monotone EQ SAT.

True{Monotone SAT \Rightarrow True{Monotone EQ SAT}
Here we assume that there is a truth assignment function \theta: z_{j} \rightarrow \lbrace True,False \rbrace that maps every variable to a truth value, such that F is satisfied. Then after we preform the above algorithm we have an instance of F', now our instance of F' will be of the form F \wedge ( \wedge_{i=1}^{k} C'_{i}) for some k \geq 1. Now notice that \theta above will satisfy F in F' and we may trivially satisfy \wedge_{i=1}^{k} C'_{i} by simply assigning all new variables z'_{j} to true.
This will give us a new truth assignment function \theta' that will satisfy F'

True{Monotone EQ SAT} \Rightarrow True{Monotone SAT}
Here we assume that there is a truth assignment function theta' that will satisfy F' then obviously as F' = F \wedge ( \wedge_{i=1}^{k} C'_{i}) then theta' must also satisfy F.

(Back to me)

Difficulty: 3.  The logical manipulations aren’t hard, but it is possible to mess them up.  For example, it’s important that the algorithm above reduces the difference in variables and clauses by 1 each iteration.  If it can reduce by more, you run the risk of skipping over the EQ state.

Monotone Satisfiability

This semester I’m doing an independent study with a student, Daniel Thornton, looking at NP-Complete problems.  He came up with a reduction for Monotone Satisfiability, and since I hadn’t gotten to that problem yet, I told him if he wrote it up, I’d post it.

So, here it is.  Take it away, Daniel!

The Problem: Monotone SAT. This is mentioned in problem LO2 in the book.

The description:
Given an set of clauses F' = \wedge_{i=1}^{n} C_{i} where each clause in F contains all negated or non-negated variables, is there an assignment of the variables so that F' is satisfied?

Example:
F' = (x_{1} \vee x_{3} \vee x_{4}) \wedge (\neg x_{2} \vee \neg x_{3} \vee \neg x_{4}) \wedge (x_{3} \vee x_{2} \vee x_{4})
the following assignment satisfies F':
x_{1} \mapsto False
x_{2} \mapsto False
x_{3} \mapsto False
x_{4} \mapsto True

The reduction:
In the following reduction we are given an instance of SAT, with the clauses:
F = \wedge_{i=1}^{n} C_{i}. Here each clause is of the form C_{i} = x_{i1} \vee x_{i2} \vee ... \vee x_{ik_i}and each x_{ij} is a literal of the form \neg z_{ij} \ or \ z_{ij}
Now we build an instance of Monotone SAT from the instance of SAT given above:
For each C_{i} we construct two new clauses \\ C'_{2i} = z_{i l_1} \vee ... \vee z_{il_k } \vee z'_{i} and  \ C'_{2i-1}= \neg z_{il_k+1} \vee ... \vee \neg z_{il_m} \vee \neg z'_{i}, such that all elements of C'_{2i} are non-negated literals and all terms in C'_{2i-1} are negated literals with the addition of the new special term z'_{i}. Now let us build a new formula F' = \wedge_{i'=1}^{2n} C'_{i'} this is our instance of Monotone SAT, clauses are either all non-negated or negated.

True_{Monotone SAT} \Rightarrow True_{SAT}:
Notice how we added the extra literal z'_{i} or \neg z'_{i} to each of the clauses C'_{2i} or C'_{2i-1} respectfully. Now if there is an assignment that satisfies all of the clauses of F' then as only C_{2i} or C_{2i-1} may be satisfied by the appended extra literal, one of the clauses must be satisfied by it’s other literals. These literals are also in C_{i} so such an assignment satisfies all C_{i} \in F.

True_{SAT} \Rightarrow True_{Monotone SAT}:
Using an argument similar to the one above, For F to be satisfied there must be at least one literal assignment say z_{iy} that satisfies each clause C_{i} Now z_{iy} is in either C'_{2i} or C'_{2i-1}. This implies that at least one of C'_{2i} or C'_{2i -1} is also satisfied by z_{iy}, so simply assign the new term z'_{i} accordingly to satisfy the clause in F' not satisfied by z_{iy}

(back to me again)

Difficulty: 3.  I like that the reduction involves manipulating the formula, instead of applying logical identities.

Protected: Biconnectivity Augmentation, Strong Connectivity Augmentation

This content is password protected. To view it please enter your password below:

Protected: Optimum Communication Spanning Tree

This content is password protected. To view it please enter your password below:

Protected: Dominating Set on Bipartite Graphs

This content is password protected. To view it please enter your password below:

Protected: Graph Homomorphism

This content is password protected. To view it please enter your password below: