Fixed parameter tractable Integer Programming and $FPP$

Question

1. Integer programming is $NP$ complete however fixed parameter tractable in number of variables. Is the fixed parameter version in parametrized analogue of $P$-complete or in parametrized analogue of $NC$? (Update: It is not known)

2. What are some examples of problems that are $NP$ complete but whose fixed parameter version is in parametrized analogue of $P$ and provably in parametrized analogue of $P$ complete and problems that are $NP$ complete but whose fixed parameter version is in parametrized analogue of $P$ and provably in parametrized analogue of $NC$? Is there a theory behind such classification? (resolved by Ronald de Haan).

Answer 1

You're confusing decision problems (in the classical sense) with parameterized decision problems. Classical decision problems are subsets of $\Sigma^*$, whereas parameterized decision problems are often considered as subsets of $\Sigma^* \times \mathbb{N}$ (see [1, Chapter 2]). Classical complexity classes (such as NC, P and NP) are sets of classical decision problems, and parameterized complexity classes (such as FPT) are sets of parameterized decision problems. (If $Q \subseteq \Sigma^* \times \mathbb{N}$ is a parameterized decision problem, then the unparameterized version of $Q$ denotes the classical decision problem $Q' = \{ x\ |\ (x,k) \in Q \}$.)

Integer linear programming (ILP) is a classical decision problem (that is, the variant you're referring to: deciding whether there exists a feasible integer solution that achieves at least a certain value of the objective function). If you consider a parameterized variant of this problem (e.g., when taking as parameter the number of variables), it is a parameterized decision problem. So asking whether the problem of ILP parameterized by the number of variables is P-complete or in NC does not make sense. What you should be asking is whether it is complete for a parameterized analogue of P, or whether it is contained in a parameterized analogue of NC.

The parameterized complexity class FPT (consisting of all parameterized decision problems that are fixed-parameter tractable) is the parameterized analogue of P. One possible appropriate parameterized analogue of NC is the parameterized complexity class FPP (see [2]). FPP consists of all parameterized decision problems that are solvable in time $f(k) \cdot (\log n)^c$ by a parallel algorithm with at most $f(k) \cdot n^c$ processors, for some computable function $f$ and some constant $c$, where $n$ is the input size and $k$ is the parameter value.

To answer question (2): an example of a parameterized decision problem that is FPT-complete and whose unparameterized version is NP-complete, is the problem of satisfiability of propositional logic formulas in CNF, parameterized by the size of the smallest strong backdoor to Horn (see, e.g., [3]). Essentially, this problem is FPT-complete (under an appropriate parameterized variant of log-space reductions) because satisfiability for propositional Horn formulas is P-complete (under log-space reductions).

For any NP-complete decision problem, you can come up with a parameterized version that is in FPP: take as parameter the size of the input. Then the problem is (trivially) solvable in time $f(k)$ (for some exponential function $f$) on a single processor. Basically, such an algorithm can solve the problem in brute force in time $f(k)$. You're probably asking for natural parameterized variants of NP-complete problems that are in FPP.

References

[1] Downey, Rodney G., and Michael R. Fellows. Fundamentals of parameterized complexity. Springer, 2013.

[2] Cesati, Marco, and Miriam Di Ianni. Parameterized parallel complexity. European Conference on Parallel Processing. Springer, Berlin, Heidelberg, 1998.

[3] Gaspers, Serge, and Stefan Szeider. Backdoors to satisfaction. In: The Multivariate Algorithmic Revolution and Beyond. Pages 287-317. Springer, 2012.