Local approximation for maximum H0-free partial subgraph problems

Monnot, Jérôme; Paschos, Vangelis; Toulouse, S.

Monnot, Jérôme; Paschos, Vangelis; Toulouse, S. (2003), Local approximation for maximum H0-free partial subgraph problems, Operations Research Letter, 31, 3, p. 195-201

Type

Article accepté pour publication ou publié

External document link

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

Date

2003

Journal name

Operations Research Letter

Volume

Number

Pages

195-201

Metadata

Show full item record

Author(s)

Monnot, Jérôme

Paschos, Vangelis
Toulouse, S.

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.

Subjects / Keywords

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