Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Task: Given an Independence Oracle and a Basis Super-Set Oracle I want to proove, that they are polynomial equivalent for Matroids.

First I tried to update my knowledge about the topic. Let $(E,\mathcal{F})$ be a Matroid.

The Independence Oracle decides if a given set $F\subset E$ whether $F$ is in $\mathcal{F}$ or not. We learned the Best-In-Greedy-Algorithm:

Given a weight function $c:E\to\mathbb{R}_+$ sort $E=\{e_1,\dots ,e_n\}$ such that $c(e_1)\geq\dots\geq c(e_n)$. Define $F:=\emptyset$. Iterate above (the sorted) $E$ in descending order and add $e_i$ to the set $F$ if $(F\cup\{e_i\})\in\mathcal{F}$.

The Basis Super-Set Oracle decides for a given set $F\subset E$ wether it contains a Basis or not. We learned the Worst-Out-Greedy-algorithm:

Given a weight function $c:E\to\mathbb{R}_+$ sort $E=\{e_1,\dots ,e_n\}$ such that $c(e_1)\leq\dots\leq c(e_n)$. Define $F:=E$. Iterate above (the sorted) $E$ in ascending order and remove $e_i$ from the set $F$ if $(F\setminus\{e_i\})$ still contains a Basis.

The book Combinatorial Optimization - Theory and Algorithms written by Korte & Vygen states:

It is easy to see that the Best-In-Greedy for the Maximization Problem for $(E, \mathcal{F}, c)$ corresponds to the Worst-Out-Greedy for the Minimization Problem for $(E,\mathcal{F}^{*},$ $c)$: adding an element to $F$ in the Best-In-Greedy corresponds to removing an element from $F$ in the Worst-Out-Greedy.

Well for me it is not easy to see. I would appreciate any hints how to proove the task.

To prove, that both Oracles are polynomial equivalent I figured out, that I have to show whether one can be simulated by polynomial-time oracle algorithm using the other. Let $I$ be an instance for the Independence Oracle and $B$ be an instance of the Basis Super-Set Oracle. What I think is, that I have to find a polynomial from $I$ to $B$ and vice versa and to show, that every oracle is able solve the transformed Instance of the other one. Am I on the right path? If yes, what how do I realize a proof like this one?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

I think that you're making it too hard. Is $\mathcal F^*$ the dual matroid whose basis elements are the sets $E \setminus B$ s.t. $B$ is a basis in $\mathcal F$? If so, let $\cal B$ be the set of bases of $\cal F$, and let $\mathcal B^* = \{E \setminus B:B \in \mathcal B\}$, the set of bases in $\mathcal F^*$. Let $F \subseteq E$; then $F \in \mathcal F$ iff there is a $B \in \mathcal B$ s.t. $F \subseteq B$ iff there is a $B \in \mathcal B$ s.t. $E \setminus B \subseteq E \setminus F$ iff there is a $B' \in \mathcal B^*$ s.t. $B' \subseteq E \setminus F$. (In the last step just let $B' = E \setminus B$.) In other words, $F$ is independent in $\mathcal F$ iff $E \setminus F$ contains a basis in $\mathcal F^*$. What happens to $E \setminus F$ when you add an element $e$ to $F$? The element $e$ is removed from $E \setminus F$, right? You should now be able to convince yourself that carrying out the first algorithm in $\mathcal F$, adding elements one at a time to $F$, is essentially the same thing as carrying out the second algorithm on $E \setminus F$ in $\mathcal F^*$, removing one element at a time from $E \setminus F$. It's just a question of whether you're looking at $F$ to see whether it's independent in $\mathcal F$ or at $E \setminus F$ to see whether it contains a basis in $\mathcal F^*$.

share|improve this answer
    
Thank you very much for this nice and easy to understand proof. I really was making my life more difficult than needed. –  Aufwind Jul 5 '11 at 23:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.