Parameterized Complexity and ETH

Note: Cross-Posted from the complexity-theory class at CMU :)

After another long hiatus, on the day yet another semester got over, we look into Parameterized Complexity theory (introduced by Downey and Fellows via many papers) and its connections to classical complexity theory specifically via the Exponential Time Hypothesis (of Impaggliazzo and Paturi 2001) in this post. Parameterized complexity provides a framework for a more refined analysis of hard problems. Heuristics, parallel algorithms, approximation schemes, randomized algorithms are some of the approaches used to counter such problems. But these approaches suffer from many defects ranging from no hard bounds on the quality of the solution (heuristics), to not being applicable to really large instances (parallel algorithms) to impractical solutions (like some PTAS's etc.).

Introduction:

Classical complexity classifies problems using the concept of some resource (time or space). This leads to a good theory but it also ignores any structural information in the input which makes problems appear harder then they really are. There is a wide variation in the worst-case complexities of known exact algorithms for the NP-complete problems. For e.g., there are pretty good 3SAT solvers present right now which scale to a large number of variables.

Parameterized complexity tries to explain these differences by assuming that there is some part of the problem (the `parameter') will be small and allow us to develop efficient poly-time algorithms. The classic example for this is to consider a database query - it has two parts the database and the query of which query is usually much smaller than the database. The query size $k$ would be the natural paramter for a parameterized complexity analysis by admitting algorithms whose non-polynomial behavior is restricted by the parameter: if $k$ is small and $n$ is large, $O(2^k . n)$ is better than $O(n^k)$.

The main contribution of the theory is establishing the intractability of certain problems by classifying problems into complexity classes by reductions which are inherently 2-dimensional depending on the problem size as well the parameter. A problem can have different parameterizations also, each leading to different results.


Complexity Classes - FPT and the W[t] hierarchy:

A parameterized language $L$ is a subset of $\Sigma^* x \Sigma^*$ where $\Sigma$ is a finite alphabet. Let $(x, k) \in L$, then we call $x$ the main part and $k$ the parameter.

a) Tractability - Fixed-parameter tractable (FPT): $L \in FPT$ if it can be decided in time at most $f(k) . x^{O(1)}$ for an arbitary function $f$. For a fixed $k$ it is in P, moreover for every $k$ it is in the same polynomial class via the same machine. As an example, consider the $p-SAT$ problem where given the formula $\phi$ and the parameter $k = $ number of variables in $\phi$ decide whether $\phi$ is satisfiable. This is clearly in FPT as the obvious brute force approach for formula of size $n$ with $k$ variables will take time $O(2^k . n)$. There are many real world problems which are in FPT like parameterized Vertex Cover which uses the kernelization technique to get a $O(k . n + 1.286^k)$ algorithm (due to Chen, Kanj and Jia, 2001). Note that the classical Vertex Cover is NP complete - yet this result shows that it
is not as `hard' as say Independent Set.

b) Parametric Intractability: Analogously to classical complexity theory, Downey and Fellows developed a completeness program for intractable parameterized problems. In order to compare the hardness of parameterized problems, we need a 2-dimensional reduction (called `parameterized-reduction'). Roughly, a language $L$ is parameterically reducible to $L'$ if there is an FPT algorithm that transforms $(x, k)$ to $(x', k')$ so that $(x, k) \in L$ iff $(x', k') \in L'$ and $k' = g(k)$ where $g$ is an unrestricted function. Note that Karp reductions are rarely parameterized reductions (e.g. Clique to Independent Set is one of the exceptions).


1) W[1]: The lowest class of parameterized intractability can be defined as the set of languages that are reducible to the Short-Turing Machine Acceptance problem (also called the $k$-step halting problem) where we want to determine for an input consisting of a nondeterministic Turing machine M and a string x, whether M has a computation path accepting x in at most k steps. In some sense, this is the parameterized analogue to the Turing machine acceptance problem: the basic generic NP-complete problem in classical complexity theory. Canonical problems include Independent Set (does $G$ have an independent of size $k$), Weighted 3SAT (does $\phi$ have a satisfying assignment of weight $k$) etc. We will also give an alternative definition of W[1] afterwards which is actually used for the basic results.


2) The W[t] hierarchy: Interestingly, while general $k-$SAT and 3SAT are equivalent for NP-hardness in classical complexity, there is no known parameterized reduction computing general satisfiability from 3-CNF formulae. This leads to a realization that the logical depth of a formula affects its parameterized complexity. Intuitively it is related to the number of alternations between unbounded fan-in AND and OR gates. Hence, we can base the hierarchy on the complexity of circuits required to check a solution.

The W[t] is based on Circuit-SAT problem (parameterized by the weight of input like for Weighted 3SAT) for family of circuits $F_{h, t}$ having:
1. Small gates: with constant fan-in
2. Large gates: with unbounded fan-in

and of depth $h$ (max. number of gates in the path) and weft (max. number of large gates in the path) at most $t$. Clearly, we have the containments:

$FPT \subseteq W[1] \subseteq W[2] \ldots $

It is not known whether the containments are strict or not. Note that W[1] can now be defined as the class that can be reduced to an parameterized Circuit SAT on the family of constant depth weft 1 circuits. Downey and Fellows (1995) proved that parameterized Independent Set is W[1]-complete. The hardness proof is very intricate and we omit it here. Note that using this definition it is easy to see why Independent Set is in W[1] (sketch):
1. Each vertex in $G$ corresponds to one input gate in the circuit
2. For every edge $(v, u) \in G$ build a small OR gate: $(1-v) \wedge (1-u))$
3. Output from small gates are given as input to a single large AND gate.

Interestingly unlike NP-hardness results, W[1]-hardness for the $k-$Halting Problem uses Independent Set completeness as intermediate results. There have been many papers demonstrating naturally occuring W[t]-complete problems like Dominating Set for W[2] etc.)- for an extensive list of already classified problems see the Downey and Fellows monograph.

Exponential Time Hypothesis (ETH)

ETH was first studied by Impagliazzo, Paturi and Zane 2001 and it states that 3SAT $\notin$ DTIME$(2^{o(n)})$, where $n$ is the number of variables. They also proved that the hypothesis is robust to analogous hypotheses for other NP-complete problems like Independent Set etc. In fact, they also showed that the ETH is independent of size measure: 3SAT is solvable in time $2^{o(n)}$ iff it is solvable in time $2^{o(m)}$ for input size $m$. Note that this suggests that weighted 3SAT should also be intractable for `any parameter'.

Connections with Classical complexity:

The above paragraph suggests that ETH and parameterized complexity might be related. In fact they are and Chen and Grohe recently proved that ETH and paramterized complexity theory are isomorphic by an explicit reduction preserving isomorphism. We don't show that here, instead we prove a simpler result that yet provides a strong link to ETH (proof is a version from Downey, Castro et. al 2003 and uses parameterized miniaturization and is different from the original proof by Abhramson, Downey and Fellows):

Theorem: If FPT = W[1], then ETH fails i.e. 3SAT $\in$ DTIME$(2^{o(n)})$.

Proof: We use the equivalent definition of ETH based on simple Circuit SAT. The idea is to capture the ETH perfectly in a parameterized complexity class. The starting point is the Mini-Circuit SAT problem which is a parameterized miniaturization of simple Circuit SAT:
Input: Positive integers $k$ and $n$, and a Boolean circuit of total size at most $k\log n$.
Decision: Does there exist any $x$ for which $C(x) = 1$.

Note that the parameter here is $k$. Also, trying all possible inputs gives a brute force $O(n^k)$ algorithm. Next we give a cruicial lemma due to Cai and Juedes 2001. It essentially fully characterizes the ETH with a complexity class in parameterized theory.

Lemma 1: Mini-Circuit SAT is in FPT iff ETH fails.
Proof: One direction follows from the brute force algorithm and noting that $2^{o(k \log n)}$ is a FPT function.

Now suppose we are given a boolean circuit $C$ of size $N$ and that Mini-Cirsuit SAT is solvable in FPT time $f(k)n^c$. Set $k = f^{-1}(N)$ and $n = 2^{N/k}$. In general $k = f^{-1}(N)$ will be some slowly growing function of $N$; so $N/k = o(N)$ and also $cN/k = o(N)$. Hence using the FPT algorithm for Mini-Circuit SAT we have a running time for Circuit SAT as: $f(f^{-1}(N)) (2^{N/k})^c = N 2^{cN/k} = 2^{cN/k + \log N} = 2^{o(N)}$.
Thus ETH fails. Proved.

Now lets define the complexity class MINI[1] to be the set of languages that are FPT reducible to Mini-Circuit SAT. It turns out that many $k\log n$ miniatures of familiar NP-complete problems are MINI[1] complete (Downey, Fellows et al. 2002). It is easy to see this because essentially all the usual NP-complete reductions of Circuit SAT to these problems work as FPT reductions because they were also linear size reductions.

We concentrate on the Mini-Independent Set problem. Surprisingly, it can be reduced to the usual parameterized Independent Set problem.

Lemma 2: Independent Set parameterized by the size of independent set is MINI[1]-hard.
Proof: We give a Turing reduction. Let graph $G = (V, E)$ be the miniature, for which we wish to determine whether $G$ has an independent set of size $r$ with $V \leq k\log n$. We can think of verices of $G$ as organized in $k$ blocks $V_1, V_2, \ldots, V_k$ each of size $\log n$. So for each possible way of writing $r$ as a sum of $k$ terms $r = r_1 + r_2 + r_3 + \ldots + r_k$ with each $r_i \leq \log n$, we have a turing reduction branch which represnts a commitment to choose $r_i$ vertices from the corresponding block $V_i$ to be in the independent set. The total number of branches are $(\log n)^k$ and again it is a FPT-function.

For each branch, we produce a graph $G'$ that has an independent set of size $k$ iff the miniature $G$ has an independent set of size $r$ distributed as indicated by the commitment made on that branch. The graph $G'$ consists of $k$ cliques with some cross edges. The ith clique consists of vertices in correspondence with the subsets of $V_i$ of size $r_i$. An edge connects a vertex $x$ in the ith clique and a vertex $y$ in the jth clique iff there is a vertex $u$ in the subset $S_x \subseteq V_i$ represented by $x$ and a vertex $v$ in the subset $S_y \subseteq V_j$ represented by $y$, such that $(u, v) \in E$.

From Lemma 2 we can conclude that $FPT \subseteq MINI[1] \subseteq W[1]$. We just need to observe now that if FPT = W[1] it implies $M[1] \subseteq FPT$. By Lemma 1, ETH fails.
Proved.

Discussion:

The above result hints that FPT vs W[1] problem is like the P vs NP problem of classical complexity theory. In fact it was also proved by Downey and Fellows that FPT $\neq$ W[1] implies P $\neq$ NP. But it is not known that if FPT $\neq$ W[1] implies anything about the rest of W[t] hierarchy. Importantly, practical intracbility of problems in NP, which are unlikely to be complete for NP, can be shown using W[t] hardness results. Parameterized complexity has deep connections to other complexity results as well. Just recently (a week back) Galesi and Lauria showed a connection with Proof Complexity based on randomized algorithms for W[t]-hard problems. The field is very active and there are many papers and surveys being published in it.

Mumbai

I spent four wonderful years at IIT-Bombay pursuing my undergraduate studies. The times were good, I was carefree and world seemed to be a better place then. But this post is about Mumbai the city - from an outsider who is not a Marathi manoosh :) This looks to be a good time after the movie Slumdog Millionaire which was based in Mumbai has swept the Oscars.

I never quite understood Mumbai as a city. When I first came to Bombay (as it was called then), it was raining cats and dogs, roads were full of sewage, auto-rickshaws were driving with death-defying deftness, my luggage was fully wet, and my dorm room was at the ground floor with the brown water threatening to flood it. IIT-B itself from outside looked like a dilapidated cloth mill.

Bombay is full of peculiarities. For most parts, I didn't use to venture out of the campus - out of fear of getting lost! Well undergraduate life is demanding, so I had to go out for passport, a desktop computer etc. etc. Desktop computer took me to the red-light area of Bombay while passport office was in the posh area of Worli full with hip-hopping teens (it has a big Ganesha temple as well). Funnily enough, typical of Bombay, it is very easy to cross from Worli to the shady area without knowing (I learnt it first-hand unfortunately). I had to take the local trains for my travels. Traveling in locals at Bombay makes you ready for anything in life. You are so close to people that you can have to take in the smell of their sweat! Once I was stranded on the stairs as the platform was too full of people - you just could not go in! And local trains go through some pretty amusingly named stations - sample Chinchpokli, Kandivili, Borivili, Sion, Bhandup etc. etc. And for good measure, Mumbai's airport is ranked as the worst in recent surveys. Every year the city drains clog making the stench outside somehow reassuringly familiar.

So, what was there to love? First you just wonder at the sheer magnitude of humanity in this city. There are just too too many people. Your eyes get saturated to be frank. I think no other city in India can match Mumbai in this (except possibly Calcutta).

Secondly, the filth and squalor. It is hard to miss the abject poverty of many people. You go out and usually run into scores of people begging. Although poverty is disconcerting and has an universal appeal (go to the 'depressed areas' in New York City, LA, Pittsburgh etc. and you would know), poverty in Mumbai has a different feel. Yes, you have the usual criminals and beggars and robbers but you also have the inescapable hard workers who dream of breaking the shackles and making it big. The level of poverty in Mumbai is truly shocking in some areas. But yet, life goes on - they sell kid's color pencils on the local trains, sell beads on the platform, sell flowers whenever your taxi stops at a red-signal...

And with all this depressing reality Mumbai's glitz is like no other in India. It is the commercial and entertainment capital and a leading educational center (with a IIT, BARC and TIFR). Leading men of business, science, politics, glamor call Mumbai as their home. Mumbai has the choicest of restaurants, hotels, complexes, parks putting any city to shame. Mumbai's landmarks offer the unquantifiable quality of hope and aspiration. It is sometimes hard to not to wryly laugh at this disparity. When you are landing in the Mumbai airport, densely packed rows of slum houses welcome you on both sides of the runway. But get out of the airport, seven star hotels and chauffeurs jostle for your luggage. I always used to wonder - where did the slums disappear suddenly!? Has Mumbai mastered the art of turning the other way?

Fortunately not. Mumbai is easily the most 'humane' city I have ever visited. The inherent level of altruism in Mumbai is surprisingly high. I was once talking to an autorickshaw driver whose vehicle had been badly damaged in the rains. So, I guessed he must be cursing the rains (which are actually pretty pretty bad - the small showers that are passed off as heavy downpours here are another matter!). But in his opinion was the rains were necessary - he is thankful for them - rains keep the Mumbai lakes full of drinking water, and helps the cultivators to grow fruits and vegetables.

I think the local trains have a vital role in leveling the playing field. For most of Mumbai's people, locals are the only affordable way to go from Point A to Point B daily. Executives, contractors, labor or even beggars share the coach. No special treatment. This is quite remarkable as the differences between have and have nots are only too stark elsewhere. The cosmopolitan nature of the city ensures that outsiders and even occasional visitors get assimilated very soon. Mumbai people easily win hands down for being the most helpful people in India. People genuinely try to give you a helping hand. Accounts of heroism in Mumbai in the innumerable tragedies it has so stoically faced are indeed unparalleled. And it is the only city I have been to date where the autorickshaw drivers are not out to fleece you! Indeed, the endearing image of Mumbai is that of the people.

I guess Mumbai allows people do what they please and just live! It offers something for everyone from your slum dweller to your average multi-billionaire to your academic. The city is free of shackles induced by complex rigid histories and unnecessary social barriers that stagnate all too many cities in India. It has made all of them irrelevant to the pressing need of the immediate. It represents the epitome of human drive, hope and magnanimity amidst unbearable wretchedness. Mumbai symbolizes the oasis in the desert. What is there not to love?

---

To end, a humorous post on the demanding skills of basic arithmetic :)

Quotable Quotes

Hello, after a long hiatus.

From our in-house mavericks (note: more fun if said with correct intonation):

• Numbers mean nothing to me.
• CMU is lucky.
• This is Ali. Please leave a message.
• How could I have missed the fruits - esp when they are low-hanging.
  
• Dude, I don't talk puns.
  
• I am super-awesome?
• No.
• Dude, is there water in the bathroom? I am also coming!
• Die. Man. Die. Go Fish.
  
• And so we can unlock the mystery behind AIDS.
• Naaaa, my back hurts, while sitting.
• Sorry Man, sorry!
• Ohh 67F - I am going home!
• Cucumber-Mint Yogurt. Bowl.
• Bhaiyya - aap single hoh?
• Didi- aap single hoh?
• Ohh you got A-? But I thought everyone got A?
• Please warm the cache, thanks.
• Buddy I only used buddy, don't worry buddy.
• OK. That was an awkward pause.
  
• Randomly submitted da.
• Same shit. Different era.
  
• Precis mon. Bum.
  

Try guessing the person for each quote. :)