New perspectives towards Woodall's Conjecture and the Generalised Berge-Fulkerson Conjecture

伍德尔猜想和广义伯奇-富尔克森猜想的新视角

• 批准号: EP/X030989/1
• 负责人: Ahmad Abdi
• 金额: $ 53.84万
• 依托单位: London School of Economics and Political Science
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2024
• 资助国家: 英国
• 起止时间: 2024 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FX030989%2F1
• 关键词: New; perspectives; towards; Woodall; Conjecture

Combinatorial Optimisation is a rich area at the intersection of Combinatorics, Operational Research, and Theoretical Computer Science. The advent of the greedy algorithm, efficient algorithms and polyhedral characterisations of maximum matchings in graphs, the theory of perfect matrices and perfect graphs, and the incredible computational benchmarks on the travelling salesman problem are just some of the highlights of the area. Combinatorial Optimisation has long served as a complementary toolkit to Integer and Linear Programming, and only by taking this perspective would one achieve the true power of the area. Combinatorial Optimisation, as suggested by the title, benefits heavily from connections to Combinatorics and Optimisation.Nowhere is this connection more manifest than in a min-max theorem which, broadly speaking, states that the minimum of an optimisation problem is equal to the maximum of a dual optimisation problem. A case in point is the Max Flow-Min Cut theorem of Ford and Fulkerson, a result that that takes its roots in railroad logistics between Russia and Eastern Europe during the Cold War. The theorem shows that the maximum volume flow in a network that can be sent from a source to a sink node equals the minimum capacity of the links we need to cut to isolate the sink from the source. Graphs are abstract models of real-world networks that involve vertices (or nodes) and edges (or links) connecting them. If the links are directed (i.e. one-way), then we deal with a digraph (short for directed graph). The proposed research focuses on two conjectured min-max relations on (di)graphs.The first of these is known as Woodall's Conjecture, posed in the late 1970s. One can think of a digraph as a network of one-way roads in a city; it is strongly connected if one can drive from any location to any other one. To guarantee this requirement, the council may enable two-way traffic in certain roads, but would like to do so on the fewest possible roads. After this optimisation problem was addressed in an influential min-max theorem by Lucchesi and Younger in 1978, Woodall proposed the natural "dual" variant. It conjectures that in any digraph, the minimum size of a dijoin (roads to be turned two-way) equals the maximum number of disjoint dicuts (two parts of the city, one way separated). The conjecture remains unresolved despite significant interest, and efforts to tackle it have led to some crucial developments in the broader area, more specifically to the frameworks of Totally Dual Integral systems and Submodular Flows in Integer and Linear Programming, and Combinatorial Optimisation.The second unsolved problem is the Generalised Berge-Fulkerson Conjecture (GBFC), also posed in the late 1970s. The origins of the conjecture come from the famous Four-Colour Problem: Given a map of regions, known formally as a planar graph, are four colours sufficient to colour the regions such that any two regions sharing a border are assigned different colours? After this question was answered affirmatively by Appel and Haken, GBFC arose as a natural extension to all graphs. The conjecture states that in a so-called r-graph, twice the minimum degree is equal to the maximum number of perfect matchings such that every edge is used exactly twice. (An r-graph is a graph on an r-regular graph with some mild parity and connectivity conditions.) The study of this conjecture has shaped the topic of Matching Theory, important in the subject area of Graph Theory. The conjecture is also intimately linked to the Chinese Postman Problem and the famous Travelling Salesman Problem.The project proposal takes advantage of a previously unexplored synergy between the two problems, ultimately due to a basic common thread: in both problems we are given a so-called ideal set-covering linear programming formulation, and the goal is to find an optimal solution to the dual linear program with a finite floating point representation.

组合优化是组合学、运筹学和理论计算机科学交叉领域的一个丰富领域。贪婪算法的出现、高效算法和图最大匹配的多面体特征、完美矩阵和完美图的理论以及旅行商问题上令人难以置信的计算基准只是该领域的一些亮点。组合优化长期以来一直作为整数和线性规划的补充工具包，只有从这个角度来看，人们才能发挥该领域的真正力量。正如标题所示，组合优化从组合学和优化的联系中受益匪浅。这种联系在最小-最大定理中最为明显，从广义上讲，该定理指出优化问题的最小值等于优化问题的最大值对偶优化问题。福特和富尔克森的最大流量-最小切割定理就是一个典型的例子，该定理源于冷战期间俄罗斯和东欧之间的铁路物流。该定理表明，网络中可以从源节点发送到汇聚节点的最大流量等于我们需要切断以将汇聚节点与源节点隔离的链路的最小容量。图是现实世界网络的抽象模型，涉及顶点（或节点）和连接它们的边（或链接）。如果链接是有向的（即单向），那么我们处理有向图（有向图的缩写）。拟议的研究重点是（有向）图上的两个猜想的最小-最大关系。其中第一个被称为伍德尔猜想，于 20 世纪 70 年代末提出。人们可以将有向图视为城市中的单向道路网络；如果一个人可以从任何一个地方开车到另一个地方，那么它就是紧密相连的。为了保证这一要求，市政府可能会在某些道路上启用双向交通，但希望在尽可能少的道路上实现这一点。 Lucchesi 和 Younger 于 1978 年在一个有影响力的最小-最大定理中解决了这个优化问题后，Woodall 提出了自然的“对偶”变体。它推测在任何有向图中，二连接（双向转向的道路）的最小尺寸等于不相交二切割（城市的两个部分，单向分开）的最大数量。尽管人们对此很感兴趣，但这个猜想仍然没有得到解决，解决这个猜想的努力已经在更广泛的领域带来了一些关键的发展，更具体地说是整数和线性规划中的全对偶积分系统和子模流以及组合优化的框架。问题是同样在 20 世纪 70 年代末提出的广义 Berge-Fulkerson 猜想 (GBFC)。这个猜想的起源来自著名的四色问题：给定一张区域地图（正式称为平面图），四种颜色是否足以对区域进行着色，以便共享边界的任何两个区域都被分配不同的颜色？在 Appel 和 Haken 给出肯定的回答后，GBFC 作为所有图的自然延伸而出现。该猜想指出，在所谓的 r 图中，最小度数的两倍等于完美匹配的最大数量，使得每条边都恰好使用两次。 （r 图是 r 正则图上的图，具有一些温和的奇偶性和连通性条件。）这个猜想的研究形成了匹配理论的主题，在图论的学科领域中很重要。该猜想也与中国邮递员问题和著名的旅行商问题密切相关。该项目提案利用了两个问题之间以前未探索过的协同作用，最终归因于一个基本的共同点：在这两个问题中，我们都给出了一个如此-称为理想的集合覆盖线性规划公式，目标是找到具有有限浮点表示的对偶线性规划的最优解。