Abstract
We present a special case of the Directed Steiner Network problem with maximum demand p that can be solved in tine O(n^O(p)). We use the Exponential time Hypothesis to show that this problem can not be solved in time f(p)*n^o(p) for any function f..
Then we consider approximation algorithm. As an example consider the Directed Steiner tree problem. We show that it can can be approximated within \ln n/2 in time 2^O(sqrt{n}) but not in time 2^o(\sqrt{n}). This gives a tight (up low order factors in the exponent) running time for this kind of approximation. In fact, we give a tight running time for c\ln n approximation For the Directed Steiner tree problem for any c<1..
The ETH can be useful in different scenarios. We study a well known problem in network design that admits an O(log n) approximation and log log n lower bound under Pneq NP. We show that assuming the ETH. We can give a tight hardness Omega( log n).