# An interesting variant of maximum matching problem

Given a graph $G(V,E)$, the classic maximum matching problem is choosing the maximum subset of edges $M$ s.t., for each edge $(u,v) \in M$, $d(u)=d(v)=1$.

Has anybody studied the following variant? For each edge $(u,v) \in M$ , $\left( \left(d(u) < c\right) \lor \left(d(v) < c\right) \right)$ holds, where c is a constant. We call this constraint a degree-constraint.

The classic constraint is an conjunction on degree with constant 1. The new variant is an disjunction on degree with constant $c$.

The problem on $c=2$ is already $NP-complete$ as shown by Jukka Suomela. I am interested in the potential approximation algorithms. A simple greedy algorithm is selecting maximum star subgraph iteratively until no star subgraph (i.e., no edge(a special star) ) can be selected. But this algorithm performs bad even when $G$ is a tree when $c=3$. There is a inner star whose center has degree $x$, and there are $x$ outer stars each center has degree $x$ and connected to the center of the inner star. The optimum value is $2*x+(x-2)*(x-1)$ by selecting $x-2$ edges from each of $x-2$ outer stars and 2 complete outer stars. The value produced by the greeedy algorithm is $x+1*x$ by selecting the inner star and one edge from every outer star.

The greedy algorithm above is $2\sqrt{n-1}$ approximation, where $n=|V|$. I want to find better approximation algorithm of this algorithm or prove its hardness of approximation.

Furthermore, I want to know the complexity class of this problem in the framework of parameterized complexity. Maybe it bears reasonable fixed parameter algorithm.

• So if $c = 1$, you want to find a subgraph that consists of disjoint stars? And, for example, in $K_{n,n}$ the optimal solution then consists of exactly two stars ($2n-2$ edges)? – Jukka Suomela Aug 20 '11 at 10:55
• The case of $c=1$ seems to be closely related to the dominating set problem: in a graph with $n$ nodes, you can find a solution with $n-k$ edges iff you have a dominating set of size $k$. – Jukka Suomela Aug 20 '11 at 11:09
• Yes. Not $c=1$ but $c=2$ is your instance. Thank you very much. It is exacly what I want to ask about. Has anybody studied this variant before? My current problem is on bipartite graph with $c=3$. – Peng Zhang Aug 20 '11 at 11:25
• Well, many people have studied dominating sets. :) Hard to solve, hard to approximate, even on bipartite graphs. I would assume that the case of a larger $c$ is not any easier... – Jukka Suomela Aug 20 '11 at 11:28
• It's a little confusing to see a bounty attached to a question with an accepted answer. You'd have been better of issuing the new question separately. unfortunately, now that you've attached a bounty, I don't think that's possible. – Suresh Venkat Aug 23 '11 at 6:39

(As it seems that the connection is not completely obvious, I will write an extended version of the above comments as an answer.)

I will focus on the case of $c = 2$. In that case, the problem can be rephrased as follows:

• Let $G = (V,E)$ be a graph. The task is to find a maximum-size $M \subseteq E$ such that the following constraint is satisfied: for each $\{u,v\} \in M$, either $u$ is incident to at most $1$ edge in $M$, or $v$ is incident to at most $1$ edge in $M$, or both.

Equivalently:

• The subgraph induced by $M$ has to have the property that all neighbours of a non-leaf node (degree > 1) are leaf nodes (degree = 1).

Equivalently:

• The subgraph induced by $M$ consists of node-disjoint stars.

In what follows I will interpret unmatched nodes (nodes not incident to any edge in $M$) as stars with 0 edges. Hence a feasible solution partitions the set of nodes into node-disjoint stars.

Now if the number of such stars is $k$, then the number of edges in $M$ is exactly $n-k$: there are $n-k$ leaf nodes that are connected to a star center. Therefore maximising the number of edges in $M$ is equivalent to minimising then number of stars.

Now it is straightforward to see that we have a solution with $k$ such stars iff we have a dominating set of size $k$:

1. Assume that we are given $k$ such stars. Then we can find a dominating set of size $k$: simply take the centers of the stars (in a star with 1 edge you can pick a node arbitrarily).
2. Assume that we are given a dominating set $D$ with $|D| = k$. Then we can simply connect each node in $V \setminus D$ to one node in $D$. These edges form a family of $k$ stars.

Therefore solving the problem optimally in a certain graph family $F$ is exactly as hard as finding a minimum dominating set in the same graph family $F$. In particular, the problem is NP-hard even in the case of bipartite graphs.

(However, (in)approximability results related to dominating sets cannot be directly applied here. In essence, we have changed the objective function from $\min |D|$ to $\max n-|D|$.)

• Great. (in)approximability results related to dominating sets cannot be directly applied here just like the infeasibility to apply (in)approximability of vertex cover to independent set. – Peng Zhang Aug 20 '11 at 23:24
• For $c=3$, it is also $NP-complete$. We will reduce $( G(V,E),c=2)$ to $( G'(V \cup \{v\} , E \cup \{(u,v)\}, u \in V), c=3)$. $G$ has a $K$ solution iff $G'$ has a $K$ solution. – Peng Zhang Aug 20 '11 at 23:33