Paths and Cycles of Large Rank in Frameworks
We provide fixed-parameter tractable (FPT) algorithms for the following generalization of the fundamental Longest Path and Longest Cycle problems. Following Lovász, we call by a framework a pair \((G,M)\), where \(G\) is an undirected graph and \(M\) is a matroid whose elements are the vertices of \(G\). Then for a framework \((G,M)\) and integer \(k\), the Max Rank Path/Cycle problem asks whether there is a path/cycle in \(G\) whose vertices form a set of rank at least \(k\) in \(M\).
Max Rank Path/Cycle encompasses several fundamental problems about paths and cycles in graphs. When \(M\) is a uniform matroid of rank \(|V(G)|\), then Max Rank Path/Cycle becomes the problem of finding a path (or cycle) with at least \(k\) vertices, one of the most studied problems in parameterized complexity. Other notable special cases of Max Rank Path/Cycle are the problems of finding a cycle containing at least \(k\) terminal vertices and a path in a colored graph containing at least \(k\) different colors.
The main results of our paper are two theorems about Max Rank Path/Cycle. The first theorem gives a randomized FPT algorithm when matroid \(M\) is representable over a finite field (with parameter \(k\) and the order of the field). This implies, for example, the first FPT algorithm for finding a path containing at least \(k\) different colors. The second theorem establishes a deterministic FPT algorithm for planar graphs and matroids representable over finite fields or rationals.
Joint work with Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen.