I am working on exact algorithms for an NP-hard problem $P$. I was able to get a $(1.75^n$) time algorithm for split graphs. When it comes to bipartite graphs, the problem becomes hard to tackle. Now, I want to prove that there is no sub-exponential algorithm for the problem on bipartite graphs. So to prove this, I have to provide a reduction from 3-SAT, which doesn't admit a $2^{o(n)}$ algorithm. I have reduced 3-SAT ($m$ clauses, $n$ varibales) to $P$ ($G'$ with $n'$ vertices) such that
(1) the reduction is done polynomial time.
(2) the size of the reduced instance $n'$ is $m+n^3$.
(3) 3-SAT is satisfiable if and only if $G'$ satisfy the necessary condition for the problem $P$
(4) $G'$ is bipartite
Now, can i say that the problem $P$ does not admit a $2^{o(n)}$ time algorithm for bipartite graphs? My main question is: does the reduction has anything to do with the size of the reduced instance, $n'$.


1 Answer 1


Yes, obviously the lower bounds you get depend on the size of the reduction. Second thing is, you have no lower bounds as we don't know if P = NP. You have a conditional lower bound.

Under ETH, your problem cannot be solved in time $2^{o(\sqrt[3]{n})}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.