15
The desired property holds for Independent Set (and probably other problems) in graphs of suitably bounded tree width.
Fix any constant $\epsilon>0$ and consider the Independent Set problem restricted to graphs of tree width at most $n \log_2(1+\epsilon) = \Theta(\epsilon n)$, where $n$ is the number of vertices. Call this problem $\Pi_\epsilon$.
Lemma ...
11
An actual factual reference is
K. Ko. Some observations on the probabilistic algorithms and NP-hard problems. Information Processing Letters, 14(1):39–43, 1982.
(When I first saw this result --- I don't remember where it was now --- it was called "Ko's Theorem". Googling suggests that another theorem has that name as well...)
5
In general, if the number of adjacent edges, which have the same color, is bounded by a constant, say d. Then, the isomorphism problem for n-vertex graphs can be solved in n^(cd) for some constant c. In your case, d=1. See for example, Proposition 4.5 in CANONICAL LABELING OF GRAPHS by Babai and Luks. Actually, they considered vertex coloring, but the same ...
3
We can create such problem by padding assuming ETH. Take an np-complete problem L such that L is decidable in time $O(2^n)$, by padding L with some dummies 1 create $L' = \{1^{n-(log_21.01)n} x:|x|=(log_21.01)n \land x \in L\}$ it is easy to prove that $L'$ is complete for np and the running time of $L'$ is exactly $O(1.01^n)$.
2
Your bound is correct, for exactly the reasons you give. It is also unimprovable in general. Suppose that each function is multiplication by a large constant, where both constants are subwords of some infinite incomprehensible sequence. If you could compress the composition, you would be able to compress at least one of the constants—a contradiction.
Edit: ...
2
Parameterized complexity
It might worth adding an answer since no one mentioned this area.
A comprehensible, well written quite recent book is
Parameterized Algorithms, M. Cygan et al., 2015
Another book is
Parameterized complexity, R. Downey and M. Fellows, 1999
Meanwhile the former presents a comprehensible text about most of the used methods and ...
Only top voted, non community-wiki answers of a minimum length are eligible
