W[1]-hardness of M-EPVCB parameterized by the degree deficit
W[1]-hardness of M-EPVCB parameterized by the degree deficit
Let be the graph in an instance of M-EPVCB, and let denote its maximum degree. The degree-deficit hardness conjecture. M-EPVCB is W[1]-hard with respect to the parameter . The paper presents this as a suspected strengthening of its discussion of the parameter ; no resolution is given 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.