The approximability of the weighted Hamiltonian path completion problem on a tree

Given a graph, the Hamiltonian path completion problem is to find an augmenting edge set such that the augmented graph has a Hamiltonian path. In this paper, we show that the Hamiltonian path completion problem will unlikely have any constant ratio approximation algorithm unless NP = P. This problem...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2005-09, Vol.341 (1), p.385-397
Main Authors: Wu, Quincy, Lu, Chin Lung, Lee, Richard Chia-Tung
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Approximation algorithm
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Fully polynomial-time approximation scheme
Graph theory
Hamiltonian path completion problem
Mathematics
Sciences and techniques of general use
Strongly NP-hard
Theoretical computing
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a graph, the Hamiltonian path completion problem is to find an augmenting edge set such that the augmented graph has a Hamiltonian path. In this paper, we show that the Hamiltonian path completion problem will unlikely have any constant ratio approximation algorithm unless NP = P. This problem remains hard to approximate even when the given subgraph is a tree. Moreover, if the edge weights are restricted to be either 1 or 2, the Hamiltonian path completion problem on a tree is still NP-hard. Then it is observed that this problem is strongly NP-hard, so it does not have any fully polynomial-time approximation scheme (FPTAS) unless NP=P. When the given tree is a k-tree, we give an approximation algorithm with performance ratio 1.5.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2005.03.043