Hof, P. van 't and Paulusma, Daniel and Woeginger, G.J. (2009) 'Partitioning graphs into connected parts.', *Theoretical computer science.*, 410 (47-49). pp. 4834-4843.

## Abstract

The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing prespecified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The Longest Path Contractibility problem asks for the largest integer ℓ for which an input graph can be contracted to the path Pℓ on ℓ vertices. We show that the computational complexity of the Longest Path Contractibility problem restricted to Pℓ-free graphs jumps from being polynomially solvable to being NP-hard at ℓ=6, while this jump occurs at ℓ=5 for the 2-Disjoint Connected Subgraphs problem. We also present an exact algorithm that solves the 2-Disjoint Connected Subgraphs problem faster than for any n-vertex Pℓ-free graph. For ℓ=6, its running time is . We modify this algorithm to solve the Longest Path Contractibility problem for P6-free graphs in time.

Item Type: | Article |
---|---|

Keywords: | Graph partition, Edge contraction, Path, Exact algorithm. |

Full text: | Full text not available from this repository. |

Publisher Web site: | http://dx.doi.org/10.1016/j.tcs.2009.06.028 |

Record Created: | 14 Oct 2009 10:20 |

Last Modified: | 02 Apr 2013 16:53 |

Social bookmarking: | Export: EndNote, Zotero | BibTex |

Usage statistics | Look up in GoogleScholar | Find in a UK Library |