Fast FPT algorithms for vertex subset and vertex partitioning problems using neighborhood unions

Details Fast FPT algorithms for vertex subset and vertex partitioning problems using neighborhood unions Fast FPT algorithms for vertex subset and vertex partitioning problems using neighborhood unions

2009-03-27

arxiv.org/abs/0903.4796v3

Computer Science

Data Structures and Algorithms

The new version has runtimes expressed by number of equivalence classes, but no other changes

Scientific paper

We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods across a cut of a graph. Boolean-width is similar to rank-width, which is related to the number of $GF[2]$-sums (1+1=0) of neighborhoods instead of the boolean-sums (1+1=1) used for boolean-width. We give algorithms for a large class of NP-hard vertex subset and vertex partitioning problems that are FPT when parameterized by either boolean-width, rank-width or clique-width, with runtime single exponential in either parameter if given the pertinent optimal decomposition. To compare boolean-width versus rank-width or clique-width, we first show that for any graph, the square root of its boolean-width is never more than its rank-width. Next, we exhibit a class of graphs, the Hsu-grids, for which we can solve NP-hard problems in polynomial time, if we use the right parameter. An $n \times \frac{n}{10}$ Hsu-grid on ${1/10}n^2$ vertices has boolean-width $\Theta(\log n)$ and rank-width $\Theta(n)$. Moreover, any optimal rank-decomposition of such a graph will have boolean-width $\Theta(n)$, i.e. exponential in the optimal boolean-width. A main open problem is to approximate the boolean-width better than what is given by the algorithm for rank-width [Hlin\v{e}n\'y and Oum, 2008]

Affiliated with

Also associated with

No associations

Rating

Fast FPT algorithms for vertex subset and vertex partitioning problems using neighborhood unions 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 Fast FPT algorithms for vertex subset and vertex partitioning problems using neighborhood unions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast FPT algorithms for vertex subset and vertex partitioning problems using neighborhood unions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-21533