Category Archives: Appendix-Graph Theory

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.

Weighted Diameter

It took over a year (the first problem strictly from the Appendix was Domatic Number, last August), but we’re finally at the end of the Graph Theory section!  And the last problem is one that’s actually good for students to solve.

The problem: Weighted Diameter.  This is problem GT65 in the appendix

The description: Given a graph G=(V,E) a collection C of  |E| not necessarily distinct, non-negative integers, and a positive integer K.  Can we find a one-to-one function f  mapping each edge in E to an element of C such that if f(e) is the length of edge e, then G has a diameter of K or less.

In other words, given a set of edge weights C, can we give each edge in E a (distinct) weight from C such that the resulting weighted graph has a path between any two vertices of length ≤ K?

Example: Suppose I have a graph:

weighted dimater3

And C= {1,2,2,2,3,5}.  I think the best was you can label this is:

weighted dimater2

The Diameter here is 7 (The length of the path from A-D).

The reduction: G&J say to use 3-Partition, so we’ll go with that.  We’re given a set A, with 3m elements, a bound B, and want to split the elements of B into sets of size 3 so that each set adds up to m.  We know several things about A, but the important thing for our purposes is that all of the elements in A add up to m*B.

We’ll also assume that |A| is at least 9.  If it’s smaller than that, we can just brute-force the answer.

What we’re going to do is build a graph that is a tree with 3m+1 vertices.  We have a root, and the root has m chains of length 3 extending from it. This gives us exactly 3*m edges.

We set K = 2*B, and set C = A

If there exists a 3-parition of A, then each of the sets of 3 elements can map onto a different chain in the graph.  This makes the longest path in the graph be between any 2 leaves.  Since the length from a leaf to a root is exactly B, the diameter of the graph is 2B.

If there exists a weighted diameter of the graph of cost 2*B, then we need to show the the cost of each chain is exactly B.  Suppose it wasn’t, and the cost from the root to some leaf v is > B, let’s say B+x.  Then , since there are least 3 chains (since |A| >= 9) and since the sum of all of the weights is m*B exactly), there must exist some leaf w, with the cost of the chain from the root to w > B-x.  The cost of the path from v to w is now > 2B, a contradiction.

If the cost from the root to some leaf is < B, then there must be some other leaf u with the cost from the root to u > B (since the cost of all of the edges add up to m*B) , and we can do the above on u.

Since each chain costs exactly B, we can use the edge weights of each chain as the sets of 3 elements that make our 3-Partition.

Difficulty: 4. G&J does say in the comments that this problem is NP-Complete even for trees, so that may have been a hint.  The proof is a little tricky (getting from “diameter ≤ K” to “set adding up to exactly K” requires some work, and there may be a more elegant way than what I did).  But I think this would make a good homework problem.

Protected: Oriented Diameter

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

Protected: Threshold Number

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

Protected: Nesetril-Rödl Dimension

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

Protected: Path Distinguishers

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

Protected: K-Closure

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

Protected: Metric Dimension

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

Protected: Intersection Graph Basis

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

Protected: Kernel

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