Research map / Learning theory and algorithms / Combinatorial and search optimization

Locally Rainbow Paths

AAAI 2024 · Learning theory and algorithms › Combinatorial and search optimization · approach: Globally optimal geometric optimization · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces locally rainbow paths/walks in vertex-colored digraphs and gives complexity results: NP-hardness for r≥2, a 2^{O(r log r)} n^{O(1)} algorithm for walks (ETH-tight), and FPT results for detour length plus r.

Problem

Finding a path or walk of bounded length between two vertices in a vertex-colored digraph such that any two equally colored vertices are separated by at least r differently colored vertices (locally rainbow constraint); generalizes rainbow paths and properly colored paths.

Approach

Generalizes rainbow path constraints to a local r-window constraint, solves the walk variant via ordered representative families (an ordered extension of set-family representative sketches) and shows ETH-tight running time, while paths with small detour are FPT in r plus detour length.

Key results

• Finding a locally rainbow walk is solvable in (r·e)^{ωr}·ℓm time, and a 2^{o(r log r)} n^{O(1)} algorithm is impossible under ETH.
• Finding a locally rainbow path is NP-hard for every fixed r≥2 and remains NP-hard for shortest paths (detour 0).
• Path variant is FPT parameterized by detour length k plus r, with running time r^{O(r+k)}·ℓ n^2 m.

Surprising findings

• Local rainbowness with r=2 is NP-hard for paths, while the walk variant is polynomial-time-like FPT, and for symmetric digraphs with r=2 shortest walks are solvable in linear time.

Limitations

• Path variant NP-hard even for r=2 and for shortest paths, so no general efficient algorithm.
• Path algorithms for detour length have running time r^{O(r+k)} with high polynomial factors (n^2 m).

Experimental setup

Builds on: representative families (Fomin, Lokshtanov, Panolan, Saurabh) Bollobás Two Families Theorem detour length parameterization of paths

Closest papers by meaning

• Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · similarity 0.80)
• Paths, Proofs, and Perfection: Developing a Human-Interpretable Proof System for Constrained Shortest Paths (AAAI 2024 · similarity 0.79)
• Solving Multiagent Path Finding on Highly Centralized Networks (AAAI 2025 · similarity 0.78)
• The Query Complexity of Local Search in Rounds on General Graphs (NeurIPS 2026 · similarity 0.78)
• How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs (AAAI 2025 · similarity 0.78)
• Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks (AAAI 2025 · similarity 0.78)