Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal

Details Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal

2010-07-30

arxiv.org/abs/1007.5450v1

Computer Science

Data Structures and Algorithms

Scientific paper

We obtain a number of lower bounds on the running time of algorithms solving problems on graphs of bounded treewidth. We prove the results under the Strong Exponential Time Hypothesis of Impagliazzo and Paturi. In particular, assuming that SAT cannot be solved in (2-\epsilon)^{n}m^{O(1)} time, we show that for any e > 0; {\sc Independent Set} cannot be solved in (2-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Dominating Set} cannot be solved in (3-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Max Cut} cannot be solved in (2-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Odd Cycle Transversal} cannot be solved in (3-e)^{tw(G)}|V(G)|^{O(1)} time, For any $q \geq 3$, $q$-{\sc Coloring} cannot be solved in (q-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Partition Into Triangles} cannot be solved in (2-e)^{tw(G)}|V(G)|^{O(1)} time. Our lower bounds match the running times for the best known algorithms for the problems, up to the e in the base.

Affiliated with

Also associated with

No associations

Rating

Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-700759