αβ-Bcore (αβ-Bcore)

Input

An undirected bipartite graph $G = (A \cup B, E)$, a vertex $v$, and integers $\alpha$ and $\beta$.

Problem

Is $v$ contained in the $(\alpha,\beta)$-bcore of $G$?

Definitions

The $(\alpha,\beta)$-bcore of a graph is its maximum subgraph such that each vertex in $A$ has degree at least $\alpha$ and each vertex in $B$ has degree at least $\beta$. It is unique.

Status

$\P$-complete (Couto and Fernandes [1]).

Remarks

The reduction to show hardness is from AM2CVP, and it is given in [1] for dynamic algorithms, though it easily translates to $\P$-completeness.

This is a generalization of the k-Core for directed graphs.