Obstructions to within a few vertices or edges of acyclic

Details Obstructions to within a few vertices or edges of acyclic Obstructions to within a few vertices or edges of acyclic

1995-02-14

arxiv.org/abs/math/9502226v1

Mathematics

Combinatorics

16 pages

Scientific paper

Finite obstruction sets for lower ideals in the minor order are guaranteed to exist by the Graph Minor Theorem. It has been known for several years that, in principle, obstruction sets can be mechanically computed for most natural lower ideals. In this paper, we describe a general-purpose method for finding obstructions by using a bounded treewidth (or pathwidth) search. We illustrate this approach by characterizing certain families of cycle-cover graphs based on the two well-known problems: $k$-{\sc Feedback Vertex Set} and $k$-{\sc Feedback Edge Set}. Our search is based on a number of algorithmic strategies by which large constants can be mitigated, including a randomized strategy for obtaining proofs of minimality.

Affiliated with

Also associated with

No associations

Rating

Obstructions to within a few vertices or edges of acyclic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Obstructions to within a few vertices or edges of acyclic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Obstructions to within a few vertices or edges of acyclic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-106376