Fixed-Parameter Tractability of Maximum Colored Path and Beyond - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2023

Fixed-Parameter Tractability of Maximum Colored Path and Beyond

Résumé

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We give a randomized algorithm, that given a colored $n$ -vertex undirected graph, vertices $s$ and $t$, and an integer $k$, finds an $(s,t)$ -path containing at least $k$ different colors in time $2^{k}n^{\mathcal{O}(1)}$. This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman on finding a path through $k$ specified vertices. It also implies the first $2^{k}n^{\mathcal{O}(1)}$ time algorithm for finding an $(s,t)$-path of length at least $k$ . Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an $n$ -vertex undirected graph $G$ , a matroid $M$ whose elements correspond to the vertices of $G$ and which is represented over a finite field of order $q$, a positive integer weight function on the vertices of $G$ , two sets of vertices $S,T\subseteq V(G)$ , and integers $p,k,w$, and the task is to find $p$ vertex-disjoint paths from $S$ to $T$ so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\) , while minimizing the sum of the lengths of the paths. We give a $2^{p+\mathcal{O}(k^{2}\log(q+k))}n^{\mathcal{O}(1)}w$ time randomized algorithm for this problem.

Dates et versions

lirmm-04830092 , version 1 (10-12-2024)

Identifiants

Citer

Fedor Fomin, Petr Golovach, Tuukka Korhonen, Kirill Simonov, Giannos Stamoulis. Fixed-Parameter Tractability of Maximum Colored Path and Beyond. SODA 2023 - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, Jan 2023, Florence, Italy. pp.3700-3712, ⟨10.1137/1.9781611977554.ch142⟩. ⟨lirmm-04830092⟩
0 Consultations
0 Téléchargements

Altmetric

Partager

More