1
$\begingroup$

I am reading Chapter 9 Approximation Algorithms of Dasgupts et al.'s Algorithm book for vertex cover approximation and they bring up the concept of matchings.

To support this, I am also watching Coursera's Approximation algorithms course by EIT digital.

This video mentions using disjoint edges and would like to confirm that the 2 are actually the same and I am not missing and subtle details.

Coursera's algorithm

$\endgroup$

1 Answer 1

2
$\begingroup$

Two disjoint edges $(a,b)$ and $(c,d)$ are edges that do not share any endpoint, i.e., $\{a,b\} \cap \{c,d\} = \emptyset$. A matching is a set of pairwise disjoint edges.

$\endgroup$
6
  • $\begingroup$ Still not clear. Are they different or the same? $\endgroup$ Apr 9, 2021 at 18:29
  • $\begingroup$ What does pairwise mean/add here? I see each edge as connecting a pair of vertices. $\endgroup$ Apr 9, 2021 at 18:29
  • $\begingroup$ Pairwise means that the condition holds for any distinct pair of edges in the matching. Formally, a set $M$ of edges is a matching if $\forall e_1 = (a,b) \in M, \forall e_2 = (c,d) \in M$, if $e_1 \neq e_2$ then $\{a,b\} \cap \{c,d\} = \emptyset$. $\endgroup$
    – Steven
    Apr 9, 2021 at 18:32
  • $\begingroup$ I am still unclear. The math text is what I don't get. Disjoint edges don't share any vertices but a matching is a set of edges such that each pair of edges picked from the set is disjoint? $\endgroup$ Apr 10, 2021 at 13:00
  • 1
    $\begingroup$ Yes. What's unclear about that? Being disjoint is a property about pairs of edges. A matching is a set in which each distinct pair of edges satisfies that property. $\endgroup$
    – Steven
    Apr 10, 2021 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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