Approximate min-max relations on plane graphs
Let G be a plane graph, let ?(G) (resp. ??(G)) be the minimum number of vertices (resp. edges) that meet all cycles ofG, and let ?(G) (resp. ??(G)) be the maximum number of vertex-disjoint (resp. edge-disjoint) cycles inG. In this note we show that ?(G)?3?(G) and ??(G)?4??(G)?1; our proofs are constructive, which yield polynomial-time algorithms for finding corresponding objects with the desired properties.
approximate min-max relation plane graph cycle feedback set