An O( OPT)-approximation for covering and packing minor models of _r

Abstract: Given two graphs

G

and

H

, we define

e x t s f {v - c o v e r}_{H} (G)

(resp.

e x t s f {e - c o v e r}_{H} (G)

) as the minimum number of vertices (resp. edges) whose removal from

G

produces a graph without any minor isomorphic to

H

. Also

e x t s f {v - p a c k}_{H} (G)

(resp.

e x t s f {v - p a c k}_{H} (G)

) is the maximum number of vertex- (resp. edge-) disjoint subgraphs of

G

that contain a minor isomaorphic to

H

. We denote by

h e t a_{r}

the graph with two vertices and

r

parallel edges between them. When

H = h e t a_{r}

, the parameters

e x t s f {v - c o v e r}_{H}

,

e x t s f {e - c o v e r}_{H}

,

e x t s f {v - p a c k}_{H}

, and

e x t s f {v - p a c k}_{H}

are NP-hard to compute (for sufficiently big values of

r

). Drawing upon combinatorial results in [Minors in graphs of large

h e t a_{r}

-girth, Chatzidimitriou et al., arXiv:1510.03041], we give an algorithmic proof that if

e x t s f {v - p a c k}_{h e t a_{r}} (G) l e q k

, then

e x t s f {v - c o v e r}_{h e t a_{r}} (G) = O (k l o g k)

, and similarly for

e x t s f {v - p a c k}_{h e t a_{r}}

and

e x t s f {e - c o v e r}_{h e t a_{r}}

. In other words, the class of graphs containing

h e t a_{r}

as a minor has the vertex/edge ErdH{o}s-P'osa property, for every positive integer

r

. Using the algorithmic machinery of our proofs, we introduce a unified approach for the design of an

O (l o g m O P T)

-approximation algorithm for

e x t s f {v - p a c k}_{h e t a_{r}}

,

e x t s f {v - c o v e r}_{h e t a_{r}}

,

e x t s f {v - p a c k}_{h e t a_{r}}

, and

e x t s f {e - c o v e r}_{h e t a_{r}}

that runs in

O (n c d o t l o g (n) c d o t m)

steps. Also, we derive several new ErdH{o}s-P'osa-type results from the techniques that we introduce.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)