Is there a polynomial time algorithm for min max maximal matching problem?

Question

I'm interested in the following problem.

Given a general graph $G = (V,E)$, and edge weights $w_e$, the min-max maximal matching finds a maximal matching $M$ such that $max_{e \in M} w_e$ is minimized.

Is there a polynomial-time algorithm for this problem? Will a simple greedy work?

Answer 1

No hope of a polynomial-time algorithm; a decision version of this problem is NP-complete.

We can reduce from the dominating set problem. Given a graph $G$ and an integer $k \le |V(G)|$, suppose that we want to test if $G$ has a dominating set of size $k$. Then construct an instance of min-max maximal matching as follows:

• Give each edge of $G$ weight $1$.
• Create $k$ vertices $a_1,a_2,\dots,a_k$.
• From each vertex $a_i$ to each vertex of $G$, add an edge of weight $0$.

Now we ask: is there a maximal matching in the resulting graph of max weight $0$ (as opposed to $1$)?

If $M$ is such a matching, then it can only use the edges between $a_1, \dots, a_k$ and $V(G)$. In particular, it has size at most $k$. Because it's maximal, there can be no edge of $G$ without an endpoint in $M$, so $M \cap V(G)$ is a dominating set of $G$. Conversely, if a dominating set of size $k$ exists, then matching its vertices to $a_1, a_2, \dots, a_k$ gives a max-weight-$0$ maximal matching.

So a polynomial-time algorithm for min-max maximal matching would also solve the dominating set problem in polynomial time.