From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows
Creators
- 1. Universidade Federal do Ceará
- 2. Lamsade
- 3. Observatoire de la Côte d'Azur
- 4. Université Côte d'Azur
- 5. Research Centre Inria Sophia Antipolis - Méditerranée
- 6. French National Centre for Scientific Research
- 7. Laboratoire d'Informatique, Signaux et Systèmes de Sophia Antipolis
Description
An s-branching flow f in a network N = (D, u), where u is the capacity function, is a flow thatreaches every vertex in V(D) from s while loosing exactly one unit of flow in each vertex other thans. Bang-Jensen and Bessy [TCS, 2014] showed that, when every arc has capacity n − 1, a network Nadmits k arc-disjoint s-branching flows if and only if its associated digraph D contains k arc-disjoints-branchings. Thus a classical result by Edmonds stating that a digraph contains k arc-disjoints-branchings if and only if the indegree of every set X ⊆ V (D) \ {s} is at least k also characterizesthe existence of k arc-disjoint s-branching flows in those networks, suggesting that the larger thecapacities are, the closer an s-branching flow is from simply being an s-branching. This observationis further implied by results by Bang-Jensen et al. [DAM, 2016] showing that there is a polynomialalgorithm to find the flows (if they exist) when every arc has capacity n − c, for every fixed c ≥ 1,and that such an algorithm is unlikely to exist for most other choices of the capacities. In this paper,we investigate how a property that is a natural extension of the characterization by Edmonds' relatesto the existence of k arc-disjoint s-branching flows in networks. Although this property is alwaysnecessary for the existence of the flows, we show that it is not always sufficient and that it is hardto decide if the desired flows exist even if we know beforehand that the network satisfies it. On thepositive side, we show that it guarantees the existence of the desired flows in some particular casesdepending on the choice of the capacity function or on the structure of the underlying graph of D,for example. We remark that, in those positive cases, polynomial time algorithms to find the flowscan be extracted from the constructive proofs.
Translated Descriptions
Translated Description (Arabic)
التدفق الفرعي s f في الشبكة N = (D, u)، حيث u هي دالة السعة، هو تدفق يصل إلى كل قمة في V(D) من s بينما يفقد وحدة تدفق واحدة بالضبط في كل قمة أخرى. أظهر Bang - Jensen و Bessy [TCS، 2014] أنه عندما يكون لكل قوس سعة n -1، فإن الشبكة Nadmits k arc - disjoint s - branching إذا وفقط إذا كان الرسم البياني المرتبط به D يحتوي على k arc - disjoints - branchs. وبالتالي، فإن النتيجة الكلاسيكية التي كتبها إدموندز تشير إلى أن الرسم البياني يحتوي على ك قوس- مفارز- فروع إذا وفقط إذا كانت درجة كل مجموعة X & V (D) \ {s} هي على الأقل ك تميز أيضًا وجود ك قوس- مفصل s - فروع التدفقات في تلك الشبكات، مما يشير إلى أنه كلما كانت القدرات أكبر، كلما كان تدفق الفرع s أقرب من كونه مجرد فرع s. تشير هذه الملاحظة أيضًا إلى النتائج التي توصل إليها بانغ جنسن وآخرون. [DAM، 2016] مما يدل على أن هناك خوارزمية متعددة الحدود للعثور على التدفقات (إن وجدت) عندما يكون لكل قوس سعة n - c، لكل درجة مئوية ثابتة ≥ 1،وأنه من غير المرجح أن توجد مثل هذه الخوارزمية لمعظم الخيارات الأخرى للسعات. في هذه الورقة،نقوم بالتحقيق في كيفية تدفق الخاصية التي تعد امتدادًا طبيعيًا للتوصيف من قبل علاقة إدموندز بوجود فروع قوسية مفصولة في الشبكات. على الرغم من أن هذه الخاصية ضرورية دائمًا لوجود التدفقات، إلا أننا نوضح أنها ليست كافية دائمًا وأنه من الصعب تحديد ما إذا كانت التدفقات المرغوبة موجودة حتى لو كنا نعرف مسبقًا أن الشبكة ترضيها. على الجانب الإيجابي، نوضح أنه يضمن وجود التدفقات المرغوبة في بعض الحالات الخاصة اعتمادًا على اختيار دالة السعة أو على هيكل الرسم البياني الأساسي لـ D،على سبيل المثال. نلاحظ أنه في تلك الحالات الإيجابية، يمكن استخراج خوارزميات الوقت متعددة الحدود للعثور على التدفق من البراهين البناءة.Translated Description (French)
Un flux de branchement s f dans un réseau N = (D, u), où u est la fonction de capacité, est un flux qui atteint chaque sommet de V(D) à partir de s tout en perdant exactement une unité de flux dans chaque sommet. Bang-Jensen et Bessy [TCS, 2014] ont montré que, lorsque chaque arc a une capacité n − 1, un réseau Nadmits k arcs-disjoints s-branchements s'écoule si et seulement si son digraphe associé D contient k arcs-disjoints-branchements. Ainsi, un résultat classique d'Edmonds indiquant qu'un digraphe contient k arcs-disjonctions-branchements si et seulement si le degré de chaque ensemble X V (D) \ {s} est au moins k caractérise également l'existence de k arcs-disjoints s-branchements dans ces réseaux, suggérant que plus les capacités sont grandes, plus un flux s-branchement est proche d'être simplement un s-branchements. Cette observation est en outre impliquée par les résultats de Bang-Jensen et al. [DAM, 2016] montrant qu'il existe un algorithme polynomial pour trouver les flux (s'ils existent) lorsque chaque arc a une capacité n − c, pour chaque c ≥ 1 fixe,et qu'un tel algorithme est peu susceptible d'exister pour la plupart des autres choix de capacités. Dans cet article,nous étudions comment une propriété qui est une extension naturelle de la caractérisation par Edmonds relatesto l'existence de k arcs disjoints s-branchements s'écoule dans les réseaux. Bien que cette propriété soit toujours nécessaire à l'existence des flux, nous montrons qu'elle n'est pas toujours suffisante et qu'il est difficile de décider si les flux souhaités existent même si nous savons à l'avance que le réseau le satisfait. Du côté positif, nous montrons qu'il garantit l'existence des flux souhaités dans certains cas particuliers, en fonction du choix de la fonction de capacité ou de la structure du graphique sous-jacent de D, par exemple. Nous remarquons que, dans ces cas positifs, des algorithmes de temps polynomial pour trouver les flux peuvent être extraits des preuves constructives.Translated Description (Spanish)
Un flujo de ramificación s f en una red N = (D, u), donde u es la función de capacidad, es un flujo que alcanza cada vértice en V(D) desde s mientras pierde exactamente una unidad de flujo en cada vértice distinto. Bang-Jensen y Bessy [TCS, 2014] mostraron que, cuando cada arco tiene capacidad n − 1, una red Nadmits k arc-disjoint s-branching fluye si y solo si su dígrafe asociado D contiene k arc-disjoints-branchings. Por lo tanto, un resultado clásico de Edmonds que afirma que un dígrafocontiene karco-disjuntos-ramificaciones si y solo si el indegrado de cada conjunto X V (D) \ {s} es al menos k también caracteriza la existencia de karco-disjuntos-s-ramificaciones en esas redes, lo que sugiere que cuanto mayores son las capacidades, más cerca está un flujo de s-ramificación de ser simplemente una s-ramificación. Esta observación está implícita además en los resultados de Bang-Jensen et al. [DAM, 2016] que muestra que existe un algoritmo polinomial para encontrar los flujos (si existen) cuando cada arco tiene capacidad n − c, para cada c ≥ 1 fijo,y que es poco probable que exista un algoritmo de este tipo para la mayoría de las otras opciones de las capacidades. En este artículo,investigamos cómo una propiedad que es una extensión natural de la caracterización de Edmonds se relaciona con la existencia de k flujos de ramificación en s de arco disjuntos en redes. Aunque esta propiedad es siempre necesaria para la existencia de los flujos, mostramos que no siempre es suficiente y que es difícil decidir si los flujos deseados existen incluso si sabemos de antemano que la red lo satisface. En el lado positivo, mostramos que garantiza la existencia de los flujos deseados en algunos casos particulares dependiendo de la elección de la función de capacidad o de la estructura del gráfico subyacente de D,por ejemplo. Observamos que, en esos casos positivos, los algoritmos de tiempo polinómico para encontrar los flujos se pueden extraer de las pruebas constructivas.Files
pdf.pdf
Files
(354.6 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:eafa40e49437b01a0e989b78010b27c4
|
354.6 kB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- من التفرعات إلى التدفقات: دراسة لممتلكات شبيهة بإدموندز إلى تدفقات متفرعة مفصولة بالقوس
- Translated title (French)
- Des embranchements aux écoulements : une étude d'une propriété de type Edmonds aux écoulements de branchement en arc-disjoint
- Translated title (Spanish)
- De las ramificaciones a los flujos: un estudio de una propiedad similar a Edmonds a los flujos de ramificación de arco disjuntos
Identifiers
- Other
- https://openalex.org/W4285581559
- DOI
- 10.46298/dmtcs.9302