W[1]-hardness of M-EPVCB parameterized by the smaller bipartition

Let G=(X,Y,E)G=(X,Y,E) be the edge-weighted bipartite graph in an instance of M-EPVCB, and let X|X| and Y|Y| denote the sizes of its two bipartition classes. The minimum-side hardness conjecture. M-EPVCB is W[1]-hard with respect to the parameter min{X,Y}\min\{|X|,|Y|\}. This would strengthen the known W[1]-hardness result parameterized by k1k_1; the conjecture is posed as a question for future work and remains unresolved in the supplied source.

Sources & referencesView supporting material

Primary source

Vahan Mkrtchyan and Garik Petrosyan, “On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs”, arXiv:2104.11215 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.