Algorithmic Lower Bounds for Problems on Decomposable Graphs

Abstract The treewidth and cliquewidth of a graph are central notions in graph theory and graph algorithms. Many NP-hard problems become tractable when the treewidth or cliquewidth of the input graph is bounded by a constant. In this talk I will briefly survey the known algorithmic results for graphs of bounded treewidth and cliquewidth, and give an overview of a line of work that explores the limits of tractability of problems on graphs of bounded treewidth or cliquewidth. Specifically, we will consider the following questions: Which problems are solvable in polynomial time on graphs of bounded treewidth, but require that the degree of the polynomial grows with the treewidth? Which problems are harder on bounded cliquewidth graphs than on bounded treewidth graphs? Can the known algorithms for problems on graphs of bounded treewidth and cliquewidth be improved?

Authors

• Daniel Lokshtanov

Keywords

No keywords are indexed for this paper.