1
$\begingroup$

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?

1 Answers 1

2

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^*$.

  • 0
    Thank you very much for this nice and easy to understand proof. I really was making my life more difficult than needed.2011-07-05