Linearly-growing reductions of Karp's 21 NP-complete problems (Q1713202)

Suppose that for two NPTIME-computable problems \(P\) and \(Q\), \(P\) is PTIME-reducible to \(Q\) via a function \(f\) such that there exists a constant \(C\) such that for every input \(x\) to \(P\) occupying space \(|x|\), the space \(|f(x)|\) of the consequent input to \(Q\) is at most \(C|x| + C\). We might write ``\(P \;{\leq}_L\; Q\)'', although this is not the nomenclature used in the article (which appears to be that ``\(Q\) is in the linear orbit of \(P\)''), but it is observed there that this relation is reflexive and transitive. The article contains demonstrations that among the 21 NP-complete problems in [\textit{R. M. Karp}, in: 50 years of integer programming 1958--2008. From the early years to the state-of-the-art. Papers based on the presentations at the special session at the 12th combinatorial optimization workshop AUSSOIS 2008. Berlin: Springer. 219--241 (2010; Zbl 1187.90014)], there are six (0-1 Integer Programming, Feedback Node Set, Undirected Hamiltonian Cycle, Chromatic Number, Clique Cover, and Job Sequencing) such that each of the others may be reduced to one of the six. Each demonstration is a construction of a reduction \(f\) as above, and the article raises the question of whether there is a finite ``kernel'' of NP-complete problems such that for every NP-computable \(P\), there exists \(Q\) in the kernel such that \(P \;{\leq}_L\; Q\). The article also raises the question of whether or not \({\leq}_L\) is symmetric. This interesting notion does raise a number of theoretical issues not addressed in the article. For example, if \({\leq}_L\) is not symmetric, then if we mod out \({\leq}_L\)-equivalence we get a poset of equivalence classes we might call ``\(L\)-degrees'' analogous to the degrees of \textit{R. E. Ladner} [J. Assoc. Comput. Mach. 22, 155--171 (1975; Zbl 0322.68028)]. What does that poset look like? What could we say about two NP-complete problems in different degrees, either comparable or incomparable? And, considering that all this is moot if \(\mathrm P = \mathrm{NP}\), if \(\mathrm P \neq \mathrm{NP}\) then these \(L\)-degrees partition the polynomial time degrees of [Ladner, loc. cit.]: what does that partition look like? Unfortunately, many of the reductions in this article appear incomplete. For example, there are a number of ways to represent a graph of \(N\) vertices and \(e\) edges as a string of \(0\)s and \(1\)s, some far more compact than others, and for some of the more compact ones (e.g. listing indices of endpoints of edges in a sparse graph), the space occupied by a typical encoding of an \(N\)-vertex \(e\)-edge graph could be substantially smaller than the worst-case estimate. This problem is partially addressed in the last reduction (of Chromatic Number to Clique Cover), but the reader should take care.