Maximização da Cardinalidade \ (f\) -Correspondência em Tempo \ (O (n^2/3m) \)

Apresentamos um algoritmo que encontra uma correspondência de máxima cardinalidade \ (f\) em um grafo simples em tempo \ (O (n^2/3m) \). Aqui \ (f: V\) é uma função dada e uma \ (f\) -correspondência é um subgrafo no qual cada vértice \ (v V\) tem grau \ (f (v) \). Este resultado generaliza uma sequência de algoritmos que se concentram em grafos bipartidos simples. O caso bipartido é baseado na noção de grafo de nível, introduzida por Dinic para fluxo de rede. Em grafos gerais, essa noção se perde: os vértices não têm mais níveis únicos, e há muitos níveis para analisar o grafo de nível correspondente como grafos bipartidos (\ ( (n^2) \) vs. \ (n\) ). Usamos níveis “naturais” para provar propriedades de trilhas de aumento mais curtas (por exemplo, fórmulas para o comprimento da trilha). Usamos níveis “encurtados” para derivar o limite de tempo do algoritmo. O algoritmo, não modificado, é também eficiente em multigrafos, alcançando tempo \ (O (\f (V), n\ m) \) para \ (f (V) =ₕf (v) \). O caso especial \ (f 1\) mostra que o algoritmo duplica o limite de tempo clássico para a correspondência de máxima cardinalidade, \ (O (n m) \).