suppose there are a bunch of countries, each containing a set of cities, and each city has an elevation (all distinct).

also suppose someone on a glider wants to visit exactly one city from every country. obviously, since she's on a glider, she can only go from higher elevation to lower elevation cities. moreover, she wants to visit the countries in a fixed, predetermined order, so there is some country 1, country 2, ... country k.

furthermore, suppose a villian is trying to stop her from visiting all these countries, by shutting down the airport in some cities. since this is a lot of work, the villian wants to shut down the minimum number of airports necessary (there is just 1 airport per city, and yes, the glider must land at an airport). this takes some thinking -- you might notice that shutting down all the airports in the country with the least cities is not always the best strategy

the villian's plan is as follows. start with a counter at 0. sort all cities by elevation, high to low. now greedily find some path which goes a city in every country, simply by reading the list of cities left to right, and taking the first city which can be visited in each country. if there is no such path, then we are done. if there is such a path, cross out all those cities and increment our counter

to be clear what the algorithm is, if the first city is in country 2, and the second city is in country 1, and the third city is in country 2, then the villian must pick the second and third city, *not* the first and second.

claim: the counter tells us exactly the minimum number of airports which need to be shut down. unfortunately for the villian, it's a nonconstructive answer. (i'm aware there are constructive answers, but i'm interested about this algorithm specifically).

question: can this claim be proved? or a counter example be found?

ideas: the counter gives us a lower bound, since at least one airport from each path found must be shut down. then we must show it is an upper bound. i tried nested induction on the number of countries and the number of cities with ... not much success. does anyone else have some ideas?

here's an outline of my attempted induction : consider the lowest elevation city. if it is not in the last country, then the counter gives the right answer, becaues that city can be safely ignored, as the glider has no reason to visit it. otherwise, suppose that lowest city increases our counter by one. we will simply shut down the airport at that city, "decrease" our counter by one, and by induction, we know the counter is correct for this reduced problem. the tricky case is when the lowest city is not in a path which caused the counter to increase by one. then, if we decide to ignore it, we may run into problems. i tried to induct on the number of countries as well as the number of cities here, but that didn't end up solving the issue.

## vertex cut / graph / combinatorics problem

**Moderators:** gmalivuk, Moderators General, Prelates

- Xanthir
- My HERO!!!
**Posts:**5336**Joined:**Tue Feb 20, 2007 12:49 am UTC**Location:**The Googleplex-
**Contact:**

### Re: vertex cut / graph / combinatorics problem

Just to remove the word-problem aspect:

You have a list of sets, each of which contains an arbitrary number of arbitrary integers. Someone wants to select one number from each set, in list order, to form a monotonically decreasing sequence of integers, and you want to stop them by removing the minimum number of integers from the collection.

Right?

I think your proof is a correct lower bound. Using a slightly different method:

For each country, in order:

1. Remove from the country's city list any cities that are lower than the lowest city in country i+1.

2. Remove from the country's city list any cities that are higher than the highest (remaining) cities in country i-1.

Then the answer is the smallest number of cities left in a country. (And gives you a constructive answer - shut down the remaining cities in that smallest-number-left country, ignoring any other cities that might be in that country.)

My method projects the "ribbon" of possible routes through the country list, and finds where it gets narrowest. Yours strips layers off of that ribbon, one city per country at a time, and finds when the ribbon becomes disconnected, which is when you've removed exactly as many cities as are in the narrowest portion of the ribbon.

You have a list of sets, each of which contains an arbitrary number of arbitrary integers. Someone wants to select one number from each set, in list order, to form a monotonically decreasing sequence of integers, and you want to stop them by removing the minimum number of integers from the collection.

Right?

I think your proof is a correct lower bound. Using a slightly different method:

For each country, in order:

1. Remove from the country's city list any cities that are lower than the lowest city in country i+1.

2. Remove from the country's city list any cities that are higher than the highest (remaining) cities in country i-1.

Then the answer is the smallest number of cities left in a country. (And gives you a constructive answer - shut down the remaining cities in that smallest-number-left country, ignoring any other cities that might be in that country.)

My method projects the "ribbon" of possible routes through the country list, and finds where it gets narrowest. Yours strips layers off of that ribbon, one city per country at a time, and finds when the ribbon becomes disconnected, which is when you've removed exactly as many cities as are in the narrowest portion of the ribbon.

(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

### Re: vertex cut / graph / combinatorics problem

I'm not quite sure that works out

for example, consider 3 countries and the elevation of their cities:

country 1 has 10 5 4

country 2 has 9 8 3 2

country 3 has 7 6 1

then your method removes nothing, and shuts down 3 airports (either in country 1 or 3)

whereas the greedy strategy removes the path 10, 9, 7 and then 5, 3, 1, and the stops, so the counter is at 2

and indeed, the airports which must be shut down are 10 and 1, so 2 suffices.

for example, consider 3 countries and the elevation of their cities:

country 1 has 10 5 4

country 2 has 9 8 3 2

country 3 has 7 6 1

then your method removes nothing, and shuts down 3 airports (either in country 1 or 3)

whereas the greedy strategy removes the path 10, 9, 7 and then 5, 3, 1, and the stops, so the counter is at 2

and indeed, the airports which must be shut down are 10 and 1, so 2 suffices.

- Xanthir
- My HERO!!!
**Posts:**5336**Joined:**Tue Feb 20, 2007 12:49 am UTC**Location:**The Googleplex-
**Contact:**

### Re: vertex cut / graph / combinatorics problem

Ah, you're right. I can't just treat all the cities in a country as equally projecting.

(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

### Re: vertex cut / graph / combinatorics problem

It follows from the generalized max-flow min-cut theorem that the minimum number of airports required to be destroyed equals the maximum number of airport-disjoint paths that visit every country in order. Call this number M.

Call two paths p1 and p2 crossing if p1 visits a higher airport than p2 in one country, while p2 visits a higher country than p1 in another country. Then if we have an example { p1, p2, ..., pM } of M airport-disjoint paths that visit every country in order, we can construct an example { q1, q2, ..., qM } of such airport-disjoint paths where no two paths qi and qj cross, as follows. Let aij be the j-th highest airports visited in country i, among the original maximum set { p1, ..., pM} of paths. Then let qj visit aij for all countries i. It should be clear that these don't cross. And we know that aij is below a(I-1)j, because by the pigeon-hole principle, at least one of the original paths goes from an airport at or below a(I-1)j to an airport at or above aij.

Now I have to wave my hands really fast, and say that each path qi of these non-crossing airport-disjoint paths visits only cities at or below the corresponding path generated by >-)'s villain, so that if M were bigger than the number of the villain's paths, path qM would still be available after the villain crossed out all of the villain's paths, contradicting the description of the villain's plan of continuing crossing out paths until no paths are left.

Call two paths p1 and p2 crossing if p1 visits a higher airport than p2 in one country, while p2 visits a higher country than p1 in another country. Then if we have an example { p1, p2, ..., pM } of M airport-disjoint paths that visit every country in order, we can construct an example { q1, q2, ..., qM } of such airport-disjoint paths where no two paths qi and qj cross, as follows. Let aij be the j-th highest airports visited in country i, among the original maximum set { p1, ..., pM} of paths. Then let qj visit aij for all countries i. It should be clear that these don't cross. And we know that aij is below a(I-1)j, because by the pigeon-hole principle, at least one of the original paths goes from an airport at or below a(I-1)j to an airport at or above aij.

Now I have to wave my hands really fast, and say that each path qi of these non-crossing airport-disjoint paths visits only cities at or below the corresponding path generated by >-)'s villain, so that if M were bigger than the number of the villain's paths, path qM would still be available after the villain crossed out all of the villain's paths, contradicting the description of the villain's plan of continuing crossing out paths until no paths are left.

### Re: vertex cut / graph / combinatorics problem

wow, that looks like a pretty solid proof to me, thanks!

for the last part, we can do it rigorously by induction

clearly, the first path of the villian is at least as high as q1 in all countries

then when considering the qk and vk (the villian's kth path), we know that q(k-1) <= v(k-1)

then delete all cities at or "above" v(k-1) in each country, and we can see that vk is the highest possible path, in this new instance, and therefore as high as qk.

actually, another extremely easy way to see this in the max-flow version is that the villian's greedy routing is essentially equivalent to the ford fulkerson algorithm, which does end up finding correct answer. after the villian's greedy routing, there is no augmenting path possible -- if there is any such path, we can do some things to it, such as collapsing visits to multiple cities inside one country into just one visit, and then the villians should've already found that path, so it can't happen

for the last part, we can do it rigorously by induction

clearly, the first path of the villian is at least as high as q1 in all countries

then when considering the qk and vk (the villian's kth path), we know that q(k-1) <= v(k-1)

then delete all cities at or "above" v(k-1) in each country, and we can see that vk is the highest possible path, in this new instance, and therefore as high as qk.

actually, another extremely easy way to see this in the max-flow version is that the villian's greedy routing is essentially equivalent to the ford fulkerson algorithm, which does end up finding correct answer. after the villian's greedy routing, there is no augmenting path possible -- if there is any such path, we can do some things to it, such as collapsing visits to multiple cities inside one country into just one visit, and then the villians should've already found that path, so it can't happen

### Who is online

Users browsing this forum: No registered users and 6 guests