Skip to main content
added 230 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

This problem seems pretty hard. Let $G$ be a bipartite graph with bipartition $(A,B)$. One easy case to consider is if each vertex in $A$ has degree $k$ and we seek a maximum $(1, k)$ matching. For each $a \in A$, if we let $N(a)$ be the set of neighbours of $a$, then we seek a maximum size subfamily $\mathcal{S}$ of

{ $N(a) : a \in A$ },

such that any two members of $\mathcal{S}$ are disjoint. I believe this problem is polynomially equivalent to maximum-clique, so even in this easy case your problem is still hard. However, maximum-clique is polynomially solvable for perfect graphs, so perhaps this is a partial answer to your question.

Another way to go is to look for good approximation algorithms, say by adapting approximation algorithms for maximum-clique.

Edit. A general comment is that if we restrict to a class of graphs with bounded tree-width, then your problem is indeed polynomial. This works for many NP-hard problems.

This problem seems pretty hard. Let $G$ be a bipartite graph with bipartition $(A,B)$. One easy case to consider is if each vertex in $A$ has degree $k$ and we seek a maximum $(1, k)$ matching. For each $a \in A$, if we let $N(a)$ be the set of neighbours of $a$, then we seek a maximum size subfamily $\mathcal{S}$ of

{ $N(a) : a \in A$ },

such that any two members of $\mathcal{S}$ are disjoint. I believe this problem is polynomially equivalent to maximum-clique, so even in this easy case your problem is still hard. However, maximum-clique is polynomially solvable for perfect graphs, so perhaps this is a partial answer to your question.

Another way to go is to look for good approximation algorithms, say by adapting approximation algorithms for maximum-clique.

This problem seems pretty hard. Let $G$ be a bipartite graph with bipartition $(A,B)$. One easy case to consider is if each vertex in $A$ has degree $k$ and we seek a maximum $(1, k)$ matching. For each $a \in A$, if we let $N(a)$ be the set of neighbours of $a$, then we seek a maximum size subfamily $\mathcal{S}$ of

{ $N(a) : a \in A$ },

such that any two members of $\mathcal{S}$ are disjoint. I believe this problem is polynomially equivalent to maximum-clique, so even in this easy case your problem is still hard. However, maximum-clique is polynomially solvable for perfect graphs, so perhaps this is a partial answer to your question.

Another way to go is to look for good approximation algorithms, say by adapting approximation algorithms for maximum-clique.

Edit. A general comment is that if we restrict to a class of graphs with bounded tree-width, then your problem is indeed polynomial. This works for many NP-hard problems.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

This problem seems pretty hard. Let $G$ be a bipartite graph with bipartition $(A,B)$. One easy case to consider is if each vertex in $A$ has degree $k$ and we seek a maximum $(1, k)$ matching. For each $a \in A$, if we let $N(a)$ be the set of neighbours of $a$, then we seek a maximum size subfamily $\mathcal{S}$ of

{ $N(a) : a \in A$ },

such that any two members of $\mathcal{S}$ are disjoint. I believe this problem is polynomially equivalent to maximum-clique, so even in this easy case your problem is still hard. However, maximum-clique is polynomially solvable for perfect graphs, so perhaps this is a partial answer to your question.

Another way to go is to look for good approximation algorithms, say by adapting approximation algorithms for maximum-clique.