Réduire le débit maximum à l'appariement bipartite?

9

Il existe une réduction célèbre et élégante du problème de correspondance bipartite maximale au problème de flux maximal: nous créons un réseau avec un nœud source , un nœud terminal et un nœud pour chaque élément à mettre en correspondance, puis ajoutons des bords appropriés.st

Il existe certainement un moyen de réduire le débit maximal à une correspondance bipartite maximale en temps polynomial, car les deux peuvent être résolus individuellement en temps polynomial. Cependant, existe-t-il une "belle" réduction du temps polynomial du débit maximal (dans les graphiques généraux) à la correspondance bipartite maximale?

templatetypedef
la source
Vous posez des questions sur le flux réseau dans un graphique bipartite ou dans des graphiques généraux?
DW
Je pensais au débit maximum dans les graphiques généraux.
templatetypedef
1
Les réductions de poly-temps à l'intérieur de P sont ennuyeuses: il suffit de résoudre l'instance et de choisir l'une des deux instances codées en dur. Je sais que ce n'est pas ce que vous voulez, mais pouvez-vous préciser plus précisément ce que c'est?
Raphael
@Raphael Le dernier paragraphe de ma question faisait allusion à ce que vous avez mentionné, car oui, il y a clairement une réduction non intéressante dans le sens de ce que vous avez dit. Je recherche une réduction plus conforme à la réduction de l'appariement au débit maximal - une transformation structurelle qui préserve les caractéristiques essentielles. Pensez à quelque chose dans le sens des réductions effectuées pour prouver la dureté NP plutôt que la réduction triviale de «résoudre le problème et produire une instance».
templatetypedef
Les réductions de gadgets ne sont-elles généralement pas linéaires? C'est ce que je veux dire: essayez de trouver une classe plus restreinte qui nous empêche de "tricher". (On ne sait pas trop ce que "préserver les caractéristiques essentielles" devrait signifier.)
Raphael

Réponses:

7

Curieusement, aucune réduction de ce type n'est connue. Cependant, dans un article récent, Madry (FOCS 2013), a montré comment réduire le débit maximal dans les graphiques de capacité unitaire à (logarithmiquement de nombreuses instances de) correspondance maximale dans les graphiques bipartites.b

Dans le cas où vous n'êtes pas familier avec le problème de correspondance maximale , il s'agit d'une généralisation de la correspondance, définie comme suit: l'entrée est un graphique (dans notre cas, un graphique bipartite), G = ( V , E ) , et un ensemble de demandes intégrales pour chaque sommet, la demande du sommet v étant notée b v . Le but est de trouver un plus grand ensemble possible d'arêtes S tel qu'aucun sommet v ne possède plus de b v arêtes dans S incident sur vbg=(V,E)vbvSvbvSv. C'est un exercice simple pour généraliser la réduction de l'appariement bipartite aux débits maximums et montrer une réduction similaire de l' appariement bipartite aux débits maximums. (Un des) le (s) résultat (s) surprenant (s) de l'article de Madry est que, dans un certain sens, ces problèmes sont équivalents, ce qui donne une réduction simple qui réduit le débit maximal dans les graphiques de capacité unitaire (généralement, les graphiques où la somme des capacités, | u | 1 est linéaire dans le nombre d'arêtes, m ) à un problème de correspondance b dans un graphe avec O ( m ) nœuds, sommets et somme des demandes.b|u|1mbO(m)

Si vous êtes intéressé par les détails, reportez-vous à la section 3, jusqu'au théorème 3.1 et à la section 4 (et la preuve de correction dans l'annexe C) de la version ArXiv du document de Madry, ici . Si la terminologie n'est pas évidente, voir la section 2.5 pour un récapitulatif concernant le problème de correspondance , et gardez à l'esprit que u e est la capacité du bord e dans l'instance de flux max d'origine.buee

dwajc
la source
-2

Voici donc un essai pour répondre à votre question:

Le théorème de Konig sur les appariements bipartites s'est avéré et par conséquent réduit à l'aide du théorème Max-Flow Min-Cut. Le théorème de Konig énonce ce qui suit. Si G est un graphe biparti, alors max {| M | : M est une correspondance} = min {| C | : C est une couverture}. Preuve. La partie max {| M |} ≤ {| C |} est triviale. Soit P et Q les classes de bipartition de G. Nous ajoutons deux sommets, r et s à G, et des arcs rp pour chaque et qs pour chaque q Q , et un bord direct pq de p P à q Q . Il s'agit d'un digraphe G . On définit les capacités u (rp) = 1, u (pq) = pPqQpPqQgeEFXgFXpqMg(QR)|QR|

Je veux dire que c'est tout à mon avis que vous avez posé dans la question et c'est ma réponse potentielle :).

marcincuber
la source
2
Notez que vous pouvez utiliser LaTeX ici pour composer les mathématiques d'une manière plus lisible. Voir ici pour une courte introduction.
DW
1
Pouvez-vous préciser comment cela répond à la question? Construisez-vous un algorithme pour résoudre le problème du débit maximal dans les graphiques généraux, en utilisant un algorithme pour une correspondance bipartite maximale? Si oui, quel est l'algorithme? Il semble que tout ce que vous faites est de montrer comment résoudre le problème de débit maximal pour le cas spécial des graphes bipartites dans le cas spécial où toutes les capacités sont 1 . Mais bien sûr, ce problème est trivialement équivalent à la correspondance maximale, comme la question l'explique déjà, donc je ne vois pas comment cela ajoute quelque chose de nouveau. Je ne vois pas non plus en quoi le théorème de Konig ou les couvertures de sommets sont pertinents.
DW
La réduction dans ce cas est la clé pour répondre à l'ensemble de questions. Et je crois que c'est exactement ce que recherche @templatetypedef. Je ne pense pas que la réduction du temps polynomial par rapport au débit maximal (dans les graphiques généraux) serait différente. J'y repenserai et ajouterai peut-être quelque chose de plus, mais je vois à peine pourquoi nous aurions besoin de différentes instances pour avoir une réduction plus générale. Mais des points justes.
marcincuber
Il s'agit de la réduction standard des manuels de la correspondance bipartite au débit maximal. La question demande une réduction dans la direction opposée: DU DEBIT MAXIMUM A LA CORRESPONDANCE BIPARTITE.
JeffE