## Return to Answer

2 added 230 characters in body

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.

1

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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9453223943710327, "perplexity_flag": "head"}