An interesting variant of maximum matching problem

Question

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.

Thanks a lot for your comment and answer in advance. :-)

Answer 1

(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|$.)