EPSRC Reference: 
EP/X030989/1 
Title: 
New perspectives towards Woodall's Conjecture and the Generalised BergeFulkerson Conjecture 
Principal Investigator: 
Abdi, Dr A 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematics 
Organisation: 
London School of Economics & Pol Sci 
Scheme: 
New Investigator Award 
Starts: 
01 October 2023 
Ends: 
30 September 2026 
Value (£): 
422,542

EPSRC Research Topic Classifications: 
Fundamentals of Computing 
Logic & Combinatorics 
Mathematical Aspects of OR 


EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
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 minmax 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 FlowMin 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 realworld networks that involve vertices (or nodes) and edges (or links) connecting them. If the links are directed (i.e. oneway), then we deal with a digraph (short for directed graph). The proposed research focuses on two conjectured minmax 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 oneway 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 twoway traffic in certain roads, but would like to do so on the fewest possible roads. After this optimisation problem was addressed in an influential minmax 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 twoway) 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 BergeFulkerson Conjecture (GBFC), also posed in the late 1970s. The origins of the conjecture come from the famous FourColour 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 socalled rgraph, twice the minimum degree is equal to the maximum number of perfect matchings such that every edge is used exactly twice. (An rgraph is a graph on an rregular 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 socalled ideal setcovering linear programming formulation, and the goal is to find an optimal solution to the dual linear program with a finite floating point representation.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
http://www.lse.ac.uk 