8
$\begingroup$

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. :-)

$\endgroup$
  • 1
    $\begingroup$ 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)? $\endgroup$ – Jukka Suomela Aug 20 '11 at 10:55
  • 1
    $\begingroup$ 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$. $\endgroup$ – Jukka Suomela Aug 20 '11 at 11:09
  • $\begingroup$ 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$. $\endgroup$ – Peng Zhang Aug 20 '11 at 11:25
  • 2
    $\begingroup$ 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... $\endgroup$ – Jukka Suomela Aug 20 '11 at 11:28
  • 2
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Aug 23 '11 at 6:39
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Peng Zhang Aug 20 '11 at 23:24
  • $\begingroup$ 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. $\endgroup$ – Peng Zhang Aug 20 '11 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.