Sunday, August 19, 2018

Fractional Problems: 2.1-colorable, 2.8-SAT

Some graphs are 2-colorable, some graphs are 3-colorable, some graphs are...Does it make sense to say that a graph is 2.1-colorable? It does!(Source_ Factional Graph Theory by Schneinerman and Ullman-- I saw a talk on this by Jim Propp a long time ago.)

Def 1: A graph is (a,b)-colorable (with a \ge b) if you can assign to every vertex a set of b numbers from {1,...,a} such that if u and v are adjacent then the set of numbers are disjoint. Note that k-colorable is (k,1)-colorable. Let chi_b(G) be the least a such that G is (a,b)-col.
 The fractional chrom num of G is lim_{b-->infinity} chi_b(G)/b.

Def 3:  We restate the ordinary Chrom Number problem as an integer program (and NOT by using that
Chrom Num \le SAT \le IP).  In fact, our Int Prog will be LARGE. For every ind set I of G we have a 0-1 valued var x_I which will be 1 iff x_I is all one color. We want to minimize \Sum_I x_I with the constraint that, for every vertex v in the graph. sum_{v in I} x_I \ge 1, so every vertex is colored.
: Fractional Chrom number is what you get if you relax the above IP to an LP with x_I in [0,1] instead of {0,1}.

Defs 1 and 2  turn out to be equiv. The wikipedia entry on Fractional Chromatic Number (see here) is pretty good and has some applications to real world things.

QUESTION: 2-col is in P, 3-col is NPC. What about, say, 2.1-col. It turns out that, for every c>2, c-col is NPC.

Open question (which Jim Propp used to begin his lecture): Every planar graph is 5-col has an EASY proof. Every planar graph is 4-col has a HARD (or at least tedious) proof. Is there a nice proof that every planar graph is (say) 4.5-colorable? The answer is Yes, Every planar graph is 4.5 colorable.  I blogged on it here.

Are there other fractional problems related to NPC problems. YES- at a Dagstuhl there was a paper on (2+epsilon)-SAT. (by Austrin, Guruswami, Hastad) (see here).

What is fractional SAT? Lets recall ordinary k-SAT: every clause has k literals and you need to make at least one of them true. What if you wanted to make at least 2 of them true? (a/b)-SAT is if every clause has exactly b literals and you want an assignment that makes at least a in each clause true.

GOOD NEWS: for all epsilon, (2+epsilon) is NP-complete. Its not so much good that its true, but its good that its known.

BAD NEWS: The proof is hard, uses lots of tools.

ODD NEWS: The speaker said that they PROVED there was no easy proof.

I think its worth having your students try to DEFINE these terms on their own. The NPC proofs may be over their heads (they may be over my head), but the definitions are nice and the students might be able to derive them.

QUESTION: Do other NPC problems have Fractional versions? I would think yes. This could lead to a host of open problems OR perhaps they have already been asked. If you know of any, please comment.


  1. In the definition of fractional chromatic number, shouldn't it be: let chi_a(G) be the least b such that G is (a,b)-colorable? i.e. the number of colors you need if each vertex has to have a colors

  2. The paper on 2+ε-SAT defines gadget reductions too narrowly. Their gadgets require each 3-SAT variable to be assigned a single (1,g,2g+1)-SAT variable (allowing auxiliary variables). (Recall that in (1,g,2g+1)-SAT, every clause has 2g+1 disjuncts, with a promise that a satisfiable instance has an assignment that satisfies at least g disjuncts in every clause.) If we allowed O(1) (dependent on g) variables instead, I expect a gadget reduction from 3-SAT exists, though the complexity of the gadgets would grow with g. Their NP-completeness proof uses a gadget reduction from inapproximability of label cover, but they only use local inapproximability rather than the full PCP theorem (they require satisfiability of label cover instances that are ε-satisfiable everywhere rather than just on average).