Fiorini, Samuel, Joret, Gwenael ORCID: 0000-0002-7157-6694 and Schaudt, Oliver (2020). Improved approximation algorithms for hitting 3-vertex paths. Math. Program., 182 (1-2). S. 355 - 368. HEIDELBERG: SPRINGER HEIDELBERG. ISSN 1436-4646

Full text not available from this repository.

Abstract

We study the problem of deleting a minimum cost set of vertices from a given vertex-weighted graph in such a way that the resulting graph has no induced path on three vertices. This problem is often calledcluster vertex deletionin the literature and admits a straightforward 3-approximation algorithm since it is a special case of the vertex cover problem on a 3-uniform hypergraph. Recently, You, Wang, and Cao described an efficient 5/2-approximation algorithm for the unweighted version of the problem. Our main result is a 9/4-approximation algorithm for arbitrary weights, using the local ratio technique. We further conjecture that the problem admits a 2-approximation algorithm and give some support for the conjecture. This is in sharp contrast with the fact that the similar problem of deleting vertices to eliminate all triangles in a graph is known to be UGC-hard to approximate to within a ratio better than 3, as proved by Guruswami and Lee.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Fiorini, SamuelUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Joret, GwenaelUNSPECIFIEDorcid.org/0000-0002-7157-6694UNSPECIFIED
Schaudt, OliverUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-328290
DOI: 10.1007/s10107-019-01395-y
Journal or Publication Title: Math. Program.
Volume: 182
Number: 1-2
Page Range: S. 355 - 368
Date: 2020
Publisher: SPRINGER HEIDELBERG
Place of Publication: HEIDELBERG
ISSN: 1436-4646
Language: English
Faculty: Unspecified
Divisions: Unspecified
Subjects: no entry
Uncontrolled Keywords:
KeywordsLanguage
Computer Science, Software Engineering; Operations Research & Management Science; Mathematics, AppliedMultiple languages
URI: http://kups.ub.uni-koeln.de/id/eprint/32829

Downloads

Downloads per month over past year

Altmetric

Export

Actions (login required)

View Item View Item