0
$\begingroup$

This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani. Specifically, the problem statement is:

Give a linear-time algorithm that takes as input a tree and determines whether it has a perfect matching: a set of edges that touches each node exactly once.

In the context of this book:

  • A tree is an undirected, connected and acyclic graph.
  • A linear-time algorithm on a graph $G = (V,E)$ is something that runs on $O(|V| + |E|)$ time.

Thinking on the problem, the following seemed promising:

Of course, the tree must have an even number of nodes, otherwise we can exit early and report that there is no perfect matching. Additionally, if at any point we find an isolated vertex, we can can do the same.

Since we're dealing with a tree, we can search for a leaf $v$, a node with a single incident edge $(u,v)$. This edge must be in the perfect matching, for it's the only one that matches $v$.
We then remove the vertices $u$ and $v$ from $T$, along with all edges that involve them, and repeat the process.

If we remove all vertices in this manner, we have found a perfect matching.

Notice that, while the removal may disconnect the graph, it will remain acyclic and this is what matters. Disconnecting the graph essentially splits the tree into multiple trees, so the iteration continues to make sense even in this case.

Now, this problem shows up in the chapter about greedy algorithms, so this approach seems like a natural fit.

Moreover, searching on the topic I've found that a tree has at most one perfect matching (see, for instance, this). In other words, if it has one, it is unique, so the algorithm must produce the one if it exists.

However, when actually thinking about implementation, I don't really see how this runs in $O(|V| + |E|)$. The naive approach appearcs to be quadratic, because at each step we need to scan for a leaf and update the graph, and neither of these take constant time. I'm mostly thinking of adjacency list representation, but this seems to hold true for adjacency matrix as well.

I've also toyed with precomputing and updating degree values for vertices, but haven't nailed it.

Searching more on the topic, I've come across this link, which suggests what's essentially the same algorithm to solve the same problem (number 2 on the exam). However, in the statement and solution, they only claim it to run in polynomial time.

How would one implement this algorithm in linear time, or else design another algorithm to solve the problem in linear time? What do we assume about data structures or operation complexities involved?


EDIT: Following on sdcvvc's suggestion, here's some C++-esque pseudocode implementing his idea. I think this works.

enum class MatchStatus
{
    HAS_MATCH,
    ROOT_NEEDS_MATCHING,
    CANNOT_MATCH
}

bool hasMatching(tree t)
{ return hasMatching(t.root) == MatchStatus::HAS_MATCH; }

MatchStatus hasMatching(node treeRoot)
{
    // Keep track of whether the current node (root of the current (sub)tree)
    // is matched to some child node
    bool isMatched = false;

    for(node subTreeRoot : treeRoot.children)
    {
        MatchStatus subTreeStatus = hasMatching(subTreeRoot);

        if(subTreeStatus == MatchStatus::CANNOT_MATCH)
            return MatchStatus::CANNOT_MATCH;

        // The subtree has a perfect matching *except* its root needs to be matched
        else if(subTreeStatus == MatchStatus::ROOT_NEEDS_MATCHING)
        {
            if(isMatched)
                // Current node is already matched
                // The subtree root needs a match but cannot be matched
                return MatchStatus::CANNOT_MATCH;

            else
                // Match the current node to subTreeRoot
                isMatched = true;
        }
            
//      else if(childStatus == MatchStatus::HAS_MATCH)
//          continue;
    }

    return isMatched ? MatchStatus::HAS_MATCH : MatchStatus::ROOT_NEEDS_MATCHING;
}
$\endgroup$
4
  • $\begingroup$ Constructing the perfect matching might require more time than simply determining whether it has one... The original question you quote asks you to determine if there is one, and it can probably be decided by a parity argument on the degrees. $\endgroup$
    – JimN
    Nov 28 '21 at 16:54
  • $\begingroup$ Also, scanning everything to find a leaf node can be improved by putting all nodes in a priority queue and maintaining that -- O(log(n)) for each scan. Perhaps a Prufer sequence representation could speed up leaf discovery further. $\endgroup$
    – JimN
    Nov 28 '21 at 16:55
  • $\begingroup$ @JimN Regarding parity arguments, the last problem here suggests something like that might be possible (although I don't see how to exactly apply it). However, that seems to run counter to the 'greed algorithm' solution that the chapter implies. $\endgroup$ Nov 28 '21 at 17:10
  • $\begingroup$ My answer can be used to determine in construct in linear time, which is optimal. Maybe there's a more clever characterization but you can't just look at degrees: you can construct two trees with degrees 1,1,1,2,2,3 where one has a matching and the other does not. $\endgroup$
    – sdcvvc
    Nov 28 '21 at 17:21
2
$\begingroup$

Suppose you remove vertices of degree 1 as long as possible, but with an additional constraint: you never disconnect the graph. If you think about it, either you will succeed in removing all vertices (the tree has a matching), or you will end up with a single vertex (which cannot be covered), or you'll be stuck with this situation:

 ...
  |
  *
 / \
 * *

i.e. a vertex with two (or more) leaves, which does not have a matching no matter what is the rest of the graph.

You can classify trees into (A) coverable, (B) coverable except the root and (C) inherently uncoverable.

Suppose you've computed the status of trees $T_1,\dots,T_n$ and would like to compute the status of the tree consisting of a vertex connected to $T_1,\dots,T_n$. If any of $T_i$ is (C), then the result is (C). If all $T_i$ are (A), then the result is coverable except for the root (B). If there is one (B) and everything else is (A), then you can match that vertex with the root and the result is (A). Finally, if the tree is connected to more than one (B), it can't be covered (C). This is a recursive traversal of the tree, which can be done in linear time.

$\endgroup$
1
  • $\begingroup$ I think this works, and I can even write some c++-esque pseudocode to go along with it. Have added it as an edit to the opening question. $\endgroup$ Nov 28 '21 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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