Fractional vs. integer solution of a maximal matching

Question

If we know that it takes at least $t$ steps to compute a fractional maximal matching, does it then also take at least $t$ steps to compute a integer maximal matching?

Answer 1

I presume that "it takes at least $t$ steps to ..." means "every algorithm to ... takes at least $t$ steps".

By definition, an integer maximal matching is a fractional maximal matching, and there is always an integer maximal matching. Thus every algorithm for integer maximal matching is an algorithm for fractional maximal matching, so the statement is true.

On the other hand, if you had in mind a particular algorithm (call it A) for fractional maximal matching and a different algorithm (B) for integer maximal matching, it is quite possible that A takes more steps than B for some instances.