0

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?

user136457
  • 2,560
  • 1
  • 22
  • 41
  • Context, please. What do you mean by a fractional maximal matching? Is an integer maximal matching a special case of a fractional maximal matching? – Robert Israel Dec 28 '16 at 18:42
  • I'm sorry! Consider a graph $G=(V,E)$. A fractional maximal matching is an assignment of values $x_e \in [0,1]$ to edges $e \in E$ such that for ell edges $e = {u,v} \in E$ we either have $\sum_{e \in E \colon u \in e} x_e =1$ or $\sum_{e\in E \colon v \in e} x_e = 1$ (maximality) and for all $v \in V$ we have $\sum_{e \in E \colon v \in e} x_e \leq 1$.

    An integer maximal matching is an assignment $x_e \in {0,1}$ such that for every vertex $v \in V$ we have $\sum_{e\in E \colon v \in e} x_e\leq 1$.

     – user136457 Dec 28 '16 at 18:48
  • 1
    Presumably you want the maximality condition for the integer case as well. – Robert Israel Dec 28 '16 at 20:51

1 Answers1

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.

Robert Israel
  • 448,999