Local approximation for maximum H0-free partial subgraph problems

Date

2003

Link to item file

https://hal.archives-ouvertes.fr/hal-00003926

Dewey

Programmation, logiciels, organisation des données

Sujet

Hereditary property; APX-complete; Maximum subgraph problem; Minimum vertex deletion problem; Aproximation algorithms; Local search

Journal issue

Operations Research Letter

Volume

Number

Publication date

2003

Article pages

195-201

Author

Monnot, Jérôme

989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]

Paschos, Vangelis

989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]

Toulouse, Sophie

989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]

Type

Article accepté pour publication ou publié

Abstract (EN)

We deal with max H0-free partial subgraph. We mainly prove that 3-locally optimal solutions achieve approximation ratio (d0+1)/(B+2+n0), where B is the maximum degree on G, d0 the minimum degree on H0, and n0 = (|V(H0)|+1)/d0. Next, we show that this ratio rises up to 3/(B+1) when H0 = K3. Finally, we provide hardness results for max K3-free partial subgraph.