6.S078 4/25: Finding Long Paths and FPT Lower Bounds.
==============================
Today @ 32-G575, 4pm: Manuel Sabin on "Fine-Grained Derandomization"

***
Faster and Smaller Space Usage for k-PATH

The above algorithms use 2^{Omega(k)} space. For k >> log(n) this is prohibitive.
Can this be improved? 
Yes! We can adapt one of the Hamiltonian path algorithms sketched in the previous lecture:

Thm: k-PATH can be solved in randomized O*(4^k) time and poly(n,k) space.

Instead of doing the randomized algorithm, it seems cleaner to jump directly to the derandomization, 
so that we don't have to calculate any probabilities.

Def: For an m by n matrix M and subset S of [n], 
M|_S is the m by |S| matrix restricted to columns whose indices are in S.

Def: A t by n matrix M is (n,k)-universal if 
for every subset S of [n] with |S| = k,
and for all u in {0,1}^k, there is a row of M|_S equal to u.

Intuively, M gives a set of binary strings of length n, so that every k-subset of indices is "shattered": all possible k-bit strings appear among those k indices.

Certainly, if M included {n choose k} rows which had all possible strings of length n with k ones, that would be (n,k)-universal. An amazing fact is that such M can be constructed, with relatively small t:

Thm [Naor-Schulman-Srinivasan '95] 
(n,k) universal matrices with t=2^k*k^{O(log k)}*log(n) rows 
can be constructed in poly(t,n) time. 

Note: A random matrix with 2^k*k*log(n) rows will be actually (n,k)-universal, whp. That's basically what the randomized alg does...

Proof (of k-PATH Thm):

Given a graph G on n nodes, and a subset of nodes S, and an integer k > = 1,

Algorithm A(G,S,k):
Construct an (n,k)-universal matrix M. 
For all rows i=1,...,t of M 
 For all j in S,
 If M[i,j] = 0, put node j in a set L
           else put node j in a set R. 
 (You can think of this as a "random" red-blue coloring.)
Recurse on set L to find all pairs of vertices in G with paths of length k'=floor(k/2) through L.
Recurse on set R := S-L to find all pairs of vertices with paths of length k-k'=ceil(k/2) through R.

In particular, A(G,S,k) returns an n by n matrix P_S such that

P_{S,k}[i,j] = 1 if there is a k-path in S from i to j, 
			 = 0 otherwise.
			 
We can compute P_{S,k} from all P_{L,k'} and P_{S-L,k-k'} computed recursively over all L and R, by observing:

P_{S,k}[i,j] = 1 
<=> there is an edge (x,y) in G and a k'-set L of S such that 
    P_{L,k'}[i,x] = 1 and P_{S-L,k-k'}[y,j] = 1.

So, A tries all t partitions (L,R) determined by M, recursively calls for t times returning t matrices,
and take the componentwise OR of the t different P_{S,k} matrices obtained.
Given two matrices P_{L,k'} and P_{S-L,k-k'}, it takes O(n^4) time to construct P_{S,k}.

*** Correctness

Does this find a k-path?

In order for P to be found, A needs to correctly guess (k-1) different node partitions of the path P:
- the partition splitting P into k' left nodes and k-k' right nodes,
- the k'-1 different partitions of the k' left nodes, and
- the k-k'-1 different partitions of the k-k' right nodes.

However, since M is (n,k)-universal, *every* possible partition of k nodes is present among the rows! 
For every subset S of k nodes, every possible partition of S into L and R appears in some row.
Thus for each of the (k-1) different partitions we need to guess, it appears among the rows of M. 

*** Runtime analysis.			 
We can bound the running time by the recurrence:

T(n,k) <= 2^k*k^{c log k}*log(n)*[2*T(n,k/2+1)+n^4] for some fixed constant c.

(The n^4 factor comes from trying all possible 4-tuples (i,x,y,j). 
We could probably do better by being more clever. Let's not be clever right now...)

First let's give a funny-looking bound, which we will argue is a nice FPT function:

Claim: T(n,k) <= 4^{k+o(k)}*(log n)^{log k}*poly(n).

Proof: By induction. Suppose inductively that for all L < k, 

T(n,L) <= 4^{L + c*log^3(L)}*(log n)^{log L}*n^c for some fixed c (which is *at least* the c we have above!)

Plug it in the recurrence:

T(n,k) <= 2^k*k^{c log k}*log(n)*[2*4^{k/2+1 + c*log^3(k/2+1)}*log(n)^{log(k/2)}*n^c + n^4].

For c >= 4, and k larger than a fixed constant, the RHS can be bounded from above by 

2^k*2^{k + 2*c log^3(k)}*log(n)^{1+log(k/2)}*n^c
<= 4^{k + c*log^3(k)}*log(n)^{log(k)}*n^c. 

[For large enough k, 2*c log^3(k/2+1) + c log^2(k) + 3 <= 2*clog^3(k).

In particular, 2*c*log^3(k/2+1) + c log^2(k) + 3 <= 2*c*(log(k) - 1)^3 + c log^2(k) + O(1)
<= 2*c*log^3(k) - 6*c*log^2(k) + 6*c*log(k) + c*log^2(k) + O(1) <= 2*c*log^3(k).] 

QED

Should we worry about the (log n)^{log k} factor??

Claim: (log n)^{log k} <= k^{log k}+n.

Proof: If k < log(n) then LHS < (log n)^{log log n} < n.
If k >= log(n) then (log n)^{log k} <= k^{log k}.
QED

So the final bound is 4^{k+O(log^3 k)}*n^c. 

You will work out another algorithm on your next problem set... coming very soon!

***
The fastest known k-PATH algorithms:

Thm [W'09] k-PATH is in randomized O*(2^k) time.
Thm [Zehavi'15] k-PATH in deterministic O*(2.6^k) time.
Thm [Bjorklund et al.'17] Undirected k-PATH in randomized O*(1.66^k) time.
Thm [Brand-Dell-Husfeldt'18] For graphs with <= p distinct k-paths, can find one in O*(p^2*2^k) deterministic time.

Is there an inherent gap between randomized and deterministic algorithms? (Probably not...)

**** Conditional FPT Lower Bounds ***

Recall a parametric problem is FPT if it can be solved in f(k)*n^c time for some computable f and constant c.

We have given lots of techniques for deriving FPT algorithms for problems, but so far we haven't said much about limitations on solving problems in an FPT way. 

What should be considered intractable in the parametrized world? 
Generally speaking, it's problems for which the dependence on the parameter is huge, such as n^{f(k)} for some f.
When the exponent of the polynomial depends on the parameter, this is a much worse dependence.

Def. XP = parametric problems solvable in n^{f(k)} time for some computable f.

Is XP really an "intractable" complexity class? The following theorem confirms this, in some sense:

***
Theorem: FPT != XP.

Proof Idea: This is analogous to the time hierarchy in complexity theory, 
where FPT "is like" P, and XP "is like" EXP (exponential time).

Proof: Define SIM = {((A,x),k) | alg A accepts x in <= (|A|+|x|)^{k+1} steps}.

SIM is in XP: The input length n is O(|A|+|x|+|k|). Using (for example) a universal Turing machine, we can simulate any other algorithm with polynomial overhead, so SIM is in n^{O(k)} time.

Suppose SIM is in FPT, in particular in g(k)*n^c time for some c. We'll derive a contradiction.

Let SIM_c = {(A,x) | alg A accepts x in <= (|A|+|x|)^{c+1} steps}. 
SIM_c is in g(c)*n^c <= O(n^c) time, by hypothesis. 

Let D be any n^{c+1} time algorithm. We can now simulate it in O(n^c) time:

E(x):
On input x of length n, solve SIM_c on (D,x), output its answer.

Algorithm E(x) can be implemented to run in about (|D|+|x|)^c steps, and determines whether or not D accepts x in about (|D|+n)^{c+1} steps. So we have TIME(n^{c+1}) is in TIME(n^c), which is a contradiction to the time hierarchy theorem.
QED

There are many problems in XP that aren't believed to be in FPT. 

In fact there is an infinite hierarchy of such problems (sort of like the polynomial hierarchy, but not quite).
We will only consider the "first level" of this hierarchy, which already contains some very interesting problems.

First though, we should give a notion of FPT reductions. 
What makes NP-completeness so powerful is that an NP-complete problem can be used to express *any* NP problem Pi with only a polynomial-time reduction from Pi. 
Fine-grained hardness is powerful because it "preserves exponents".
The generic form of FPT reducibility, defined below, fits the bill:

Def. A has an \emph{FPT-reduction} to B, which we denote A \leq_{fpt} B, if there is a computable 
$g: \mathcal{N} \rightarrow \mathcal{N}$ and oracle TM $M^B$ (with oracle access to B) such that:
* On every input $(x,k)$, $M^{B}(x,k) = A(x,k)$.
* The running time of $M^B$ is FPT (runs in f(k)*n^c for some f and some c)
* Every query $(y,k')$ made to $B$ by $M^B(x,k)$ has $k' \leq g(k)$.

The last item says that all queries to $B$ by $M^B(x,k)$ must \emph{preserve the original parameter k}. All parameters appearing in all queries must solely be a function of the original parameter k in the input to $A$. 

Our definition of FPT reduction is more general than normally considered: typically in the literature, people have considered many-one reductions from $A$ to $B$ (where there is at most one oracle query). 

However, since the algorithms we consider are all either deterministic or randomized, the more general oracle version seems more logical, as it still satisfies the usual properties one would want from a reducibility notion:

Proposition: If $B$ is FPT and $A \leq_{fpt} B$, then $A$ is FPT.

Proposition: If $A \leq_{fpt} B$ and $B \leq_{fpt} C$, then $A \leq_{fpt} C$.

(Proofs omitted, but you should think about them!)

Now let's define a presumably hard problem.

Def. The *weight* of a bit string is its number of 1s.

Weighted 2-SAT (a.k.a. W2SAT): 
Given a 2CNF formula F and a parameter k, does F have a satisfying assignment of weight k? 

W[1]: Class of parametric problems that are FPT reducible to W2SAT. 

Note FPT is in W[1] (easy: an FPT reduction can solve an FPT problem, then output a yes/no instance of k-Clique).

Why does W[1] contain hard problems? Here's some evidence:

Theorem: k-Clique is in W[1].

Proof: Need to give an FPT reduction from k-Clique to W[1]. 
For a graph G = ({1,...,n},E) make a W2SAT instance F with n variables x_1,...,x_n and |E| clauses:

F = AND_{(i,j) notin E} (\neg x_i \vee \neg x_j).

Observe that F has a SAT assignment with x_{i_1} = ... x_{i_k} = 1 
if and only if {i_1,...,i_k} is a clique in G.
QED

In fact there is an FPT reduction from W2SAT to k-Clique (omitted), so these are FPT equivalent.

Why is k-Clique hard?
Best known algorithms for k-Clique run in n^{delta k} time for some delta > 0. 
If we could get an FPT algorithm then practically all of fine-grained complexity would look very different:

Theorem: k-Clique is in FPT => ETH is false!

Proof. (Much simpler than what you'd normally see... follows R. Williams, ICALP'04.)
 Show:

(1) k-Clique in FPT => Max-2-SAT is in 2^{eps n} time for all eps > 0
(2) Max-2-SAT in 2^{eps n} time for all eps => 3-SAT is in 2^{eps n} time for all eps.

Part (2) follows from standard reductions from 3SAT to Max-2-SAT:
- sparsify the given 3SAT instance so that it has O(n) clauses, 
- then reduce it to Max-2SAT which introduces O(n) new variables.

Part (1) is more interesting.

Suppose k-Clique is in $f(k) \cdot n^c$ time. 
Let $F$ be a 2CNF on $n$ variables with $m \leq O(n^2)$ clauses. 

Partition the variables (arbitrarily) into $k$ groups $G_1, G_2, \ldots, G_{k}$, 
each group having at most $n/k+1$ variables. 

Now we construct a $k$-Clique instance $G$. 

For each group $G_i$ associated with some $n/k+1$ variables, 
make nodes in $G$ for all $O(2^{n/k})$ Boolean assignments on these $n/k+1$ variables. 

So $G$ has $O(k \cdot 2^{n/k})$ nodes. 
Make $G$ $k$-partite, so it only has edges between distinct pairs of groups.

Now we'll put some weights on the edges and nodes (which will be removed later).

For each node $i_1 = 1,...,k$,
put a weight on node $v_1 \in G_{i_1}$ with weight $L$ 
<=> the partial assignment given by $v_1$ satisfies exactly $L$ clauses.

For each pair of groups $(i_1, i_2)$, 
put an edge between $v_1 \in G_{i_1}, v_2 \in G_{i_2}$ with weight $-K$ 
<=> there are exactly $K$ clauses $C$ such that $v_1$ satisfies $C$ *and* $v_2$ also satisfies $C$. 

(Note: this latter condition can only happen if the clause $C=(x_i or x_j)$ has one variable in group G_{i_1} and the other variable in group G_{i_2}.)

Claim: There is a $k$-clique in $G$ with total node and edge weight exactly $m^{\star}$ 
<=> there is an assignment to the vars of $F$ satisfying exactly $m^{\star}$ clauses.

Idea: The node weights count up many satisfied clauses, but their sum will overcount those clauses that are satisfied "twice", by variable assignments from two different groups. Those clauses are subtracted via the edge weights. 

Here we are exploiting the fact that each clause has at most two variables; if clauses had three variables we'd have to worry about a clause's variables appearing among three different groups.

So far, we have reduced Max-2-SAT to finding a k-clique of maximum node and edge weight.

To get rid of the weights, we can simply "brute force" all possible values for the weights.

Suppose we want to know if F has a satisfying assignment of weight exactly m*.

Try all $O(m)^{k^2}$ possible ways to assign edge weights in [0,m] to k nodes and O(k^2) edges such that the sum of weights equals m*.  
Think of it as going over all vectors w=(W1,...,Wk,W12,...,W_{k-1,k}) which say:
- Group i has a node of weight Wi, 
- Groups i and j have an edge of weight -W_{i,j},
such that the sum of all these weights equals m*.

Make an unweighted graph G^w which only includes nodes and edges that obey these node and edge assignments:
Only include node vi of Gi if it has weight exactly Wi, 
only include edge (vi,vj) in Gi x Gj if it has weight exactly -W_{i,j}

Then solve k-Clique on each unweighted graph of $N=O(k 2^{n/k})$ nodes, in time 
$f(k)\cdot N^c \leq f(k) \cdot 2^{cn/k}$.

Total running time is $O(m)^{k^2}\cdot f(k) \cdot 2^{cn/k}$. 
Setting $k$ to be an arbitrarily large constant, this will be $O(2^{eps n})$ for any desired eps > 0.
QED

In fact this proof also shows that if k-Clique is in n^{k/loglogloglog k} time then ETH is false.

Cor: ETH => W[1] != FPT.

Thus W[1] != FPT is widely believed.