Changes
Created page with '<onlyinclude> In a bipartite graph, can we decide in polynomial time what is the maximum number of edges that can be covered by ''k'' nodes? </onlyinclude> ==Remarks== This que…'
<onlyinclude>
In a bipartite graph, can we decide in polynomial time what is the maximum number of edges that can be covered by ''k'' nodes?
</onlyinclude>
==Remarks==
This question was asked by B. Simeone. In general graphs, the problem is in some sense more difficult than vertex cover: it was shown by Guo et al.<ref>J. Guo, R. Niedermeier, S. Wernicke, ''Parameterized complexity of vertex cover variants'', [http://dx.doi.org/10.1007/s00224-007-1309-3 DOI link]. [http://theinf1.informatik.uni-jena.de/publications/generalized-vertex-cover-tcs06.pdf Author link].</ref> to be <nowiki>W[1]</nowiki>-complete (where ''k'' is the parameter), while [[Wikipedia:Vertex cover|Vertex cover]] is fixed parameter tractable.
==References==
<references/>
[[Category:Matchings]]
[[Category:Open Problems]]
In a bipartite graph, can we decide in polynomial time what is the maximum number of edges that can be covered by ''k'' nodes?
</onlyinclude>
==Remarks==
This question was asked by B. Simeone. In general graphs, the problem is in some sense more difficult than vertex cover: it was shown by Guo et al.<ref>J. Guo, R. Niedermeier, S. Wernicke, ''Parameterized complexity of vertex cover variants'', [http://dx.doi.org/10.1007/s00224-007-1309-3 DOI link]. [http://theinf1.informatik.uni-jena.de/publications/generalized-vertex-cover-tcs06.pdf Author link].</ref> to be <nowiki>W[1]</nowiki>-complete (where ''k'' is the parameter), while [[Wikipedia:Vertex cover|Vertex cover]] is fixed parameter tractable.
==References==
<references/>
[[Category:Matchings]]
[[Category:Open Problems]]
