Algorithmic Meta-Theorems for Graphs of Bounded Vertex Cover

Details Algorithmic Meta-Theorems for Graphs of Bounded Vertex Cover Algorithmic Meta-Theorems for Graphs of Bounded Vertex Cover

2009-10-04

arxiv.org/abs/0910.0582v2

Computer Science

Data Structures and Algorithms

In this version, the algorithmic results have been extended to a new graph width, called neighborhood diversity

Scientific paper

Possibly the most famous algorithmic meta-theorem is Courcelle's theorem, which states that all MSO-expressible graph properties are decidable in linear time for graphs of bounded treewidth. Unfortunately, the running time's dependence on the MSO formula describing the problem is in general a tower of exponentials of unbounded height, and there exist lower bounds proving that this cannot be improved even if we restrict ourselves to deciding FO logic on trees. In this paper we attempt to circumvent these lower bounds by focusing on a subclass of bounded treewidth graphs, the graphs of bounded vertex cover. By using a technique different from the standard decomposition and dynamic programming technique of treewidth we prove that in this case the running time implied by Courcelle's theorem can be improved dramatically, from non-elementary to doubly and singly exponential for MSO and FO logic respectively. Our technique relies on a new graph width measure we introduce, for which we show some additional results that may indicate that it is of independent interest. We also prove lower bound results which show that our upper bounds cannot be improved significantly, under widely believed complexity assumptions. Our work answers an open problem posed by Michael Fellows.

Affiliated with

Also associated with

No associations

Rating

Algorithmic Meta-Theorems for Graphs of Bounded Vertex Cover 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 Algorithmic Meta-Theorems for Graphs of Bounded Vertex Cover, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithmic Meta-Theorems for Graphs of Bounded Vertex Cover will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-665240