Is there a polynomial time algorithm for min max maximal matching problem? 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?
 A: 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.
