← All problems

Alternating k-linkage problem in acyclic 2-edge-coloured graphs

Given a finite graph G=(V,E)G=(V,E) with an edge-colouring c:E→{1,2}c:E\to\{1,2\} and no alternating cycle, and given kk prescribed ordered pairs (s1,t1),…,(sk,tk)(s_1,t_1),\ldots,(s_k,t_k) of vertices, decide whether there exist vertex-disjoint paths PiP_i from sis_i to tit_i such that consecutive edges of every PiP_i have different colours. The fixed-parameter version asks whether, for every fixed kk, this problem can be solved in polynomial time in ∣V∣|V|.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

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, kk, is fixed.

October 2026 claimed algorithm

Jørgen Bang-Jensen, Stéphane Bessy, and Amadeus Reinald report an nO(k)n^{O(k)}-time algorithm for the alternating linkage problem, implying polynomial time for fixed kk. This is a specialist preprint claim and remains unverified.

Current status (as of October 2026): A preprint claims the fixed-kk 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.