Máxima correspondência em um gráfico bipartido

Question

Dado um gráfico bipartido $ g= (v_1 \ cup v_2, e) $ e um conjunto $ v '\ $ \em (v_1 \ cope v_2) $ .Qual é a complexidade de encontrar uma correspondência máxima na $ g $ que usa apenas $ x $ vértices de $ v '$ ?

Answer 1

Definir $ v_i '= v_i \ cap v' $ . Você pode resolver isso, encontrando a correspondência máxima usando no máximo $ k $ vértices da $ v_1 '$ e No máximo $ xk $ de $ v_2 '$ para todos $ k \ in [0, x] $ . Isso, por sua vez, pode ser encontrado com fluxo máximo.

Para encontrar esta correspondência máxima, modificamos a redução usual para o fluxo máximo. Deixe $ s $ ser a fonte e $ t $ a pia. Deixe $ l $ e $ R $ Seja vértices auxiliares. Adicione uma borda de $ S $ para $ l $ com capacidade $ k $ , e uma borda de $ R $ para $ t $ com capacidade $ xk $ . Todas as outras bordas terão capacidade $ 1 $ . Adicione uma borda de $ l $ para cada $ x \ in v_1 '$ , e da $ s $ para cada $ x \ in v_1 \ setminus v_1 '$ . Adicione uma borda de cada $ y \ in v_2 '$ para $ R $ , e de cada $ y \ in v_2 \ setminus v_2 '$ para $ t $ . Para $ (x, y) \ em e $ , adicione uma borda da $ x $ para $ y $ . Agora, o fluxo máximo fornece uma correspondência máxima usando no máximo $ K $ vértices em $ v_1 '$ e < span class="contentor de matemática"> $ xk $ em $ v_2 '$ .

podemos resolver o problema na $ \ mathcal {o} (x \ cdot m) $ onde $ m $ é a complexidade do fluxo máximo. Os problemas máximos de fluxo são muito semelhantes, para que possamos melhorar isso.

Podemos aumentar ou diminuir a capacidade de qualquer borda por $ 1 $ enquanto mantém o fluxo máximo na $ \ mathcal { O} (| E |) $ . Primeiro calcule a correspondência máxima usando sem vértices na $ v '$ . Em seguida, aumente a capacidade da borda da $ s $ para $ l $ por $ x $ . Em seguida, a cada passo aumenta a capacidade da borda da $ R $ para $ t $ e diminuir a capacidade da borda da $ S $ para $ l $ enquanto mantém um fluxo máximo. Saída da maior correspondência produzida. A complexidade será $ \ mathcal {o} (| e | \ sqrt {| v |} + x \ cdot | e |) $ Se usarmos dinic para encontrar a correspondência inicial bipartida.