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;
}
