Assigning Channels Via the Meet-in-the-Middle Approach
Łukasz Kowalik, Arkadiusz Socała · Algorithmica · 2015
We study the complexity of the Channel Assignment problem. By applying the meet-in-the-middle approach we get an algorithm for the $$\ell $$ -bounded Channel Assignment (when the edge weights are bounded by $$\ell $$ ) running in time $$O^*((2\sqrt{\ell +1})^n)$$ . This is the first algorithm which breaks the $$(O(\ell ))^n$$ barrier. We extend this algorithm to the counting variant, at the cost of slightly higher polynomial factor. Very recently the second author showed that Channel Assignment does not admit a $$O(c^n)$$ -time algorithm, for a constant c independent of $$\ell $$ . We consider a similar question for Generalized $$T$$ -Coloring, a CSP problem that generalizes Channel Assignment. We show that Generalized $$T$$ -Coloring does not admit a $$2^{2^{o\left( \sqrt{n}\right) }} \mathrm{poly}(r)$$ -time algorithm, where r is the size of the instance.