Alternating k-linkage problem in acyclic 2-edge-coloured graphs
Given a finite graph with an edge-colouring and no alternating cycle, and given prescribed ordered pairs of vertices, decide whether there exist vertex-disjoint paths from to such that consecutive edges of every have different colours. The fixed-parameter version asks whether, for every fixed , this problem can be solved in polynomial time in .
References
- Acyclic 2-edge-coloured graphs: polynomial-time linkages and colouring hardness — arXiv — Jørgen Bang-Jensen, Stéphane Bessy, Amadeus Reinald
Source: arXiv
Progress summary
A new specialist preprint claims to solve the fixed-parameter version of this path-routing problem in acyclic two-coloured graphs, but the claim has not been independently checked.
The problem asks whether prescribed vertex-disjoint paths with alternating edge colours can be found efficiently in acyclic two-edge-coloured graphs. The reported result claims polynomial-time solvability when the number of paths, , is fixed.
October 2026 claimed algorithm
Jørgen Bang-Jensen, Stéphane Bessy, and Amadeus Reinald report an -time algorithm for the alternating linkage problem, implying polynomial time for fixed . This is a specialist preprint claim and remains unverified.
Current status (as of October 2026): A preprint claims the fixed- problem is solved in the stated acyclic two-edge-coloured setting, while independent verification is not recorded.
Sources
Solutions 0
No solutions have been posted yet.