Edge-minimum walk of modular length in polynomial time

DOI10.4230/LIPICS.ITCS.2025.5MaRDI QIDQ7296632zbMATH OpenFDO

Authors Antoine Amarilli, Benoît Groz, Nicole Wein

Publication date 14 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2025.5

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A half-integral Erd\H{o}s-P\'osa theorem for directed odd cycles
• A note on odd/even cycles
• A trichotomy for regular simple path queries on graphs
• A Trichotomy for Regular Trail Queries
• Approximation algorithms for node-weighted directed Steiner problems
• Characterization of even directed graphs
• Divisible subdivisions
• ETH-hardness of approximating 2-CSPs and directed Steiner network
• Even Cycles in Directed Graphs
• Even cycles in directed graphs
• Finding an Even Simple Path in a Directed Planar Graph
• Finding Even Cycles Even Faster
• Finding smallest witnesses for conjunctive queries
• Modularity of cycles and paths in graphs
• Packing cycles through prescribed vertices under modularity constraints
• Packing cycles with modularity constraints
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
• Parameterized complexity of arc-weighted directed Steiner problems
• Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs
• Permanents, Pfaffian orientations, and even directed circuits
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Pólya's permanent problem
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• Shortest odd paths in undirected graphs with conservative weight functions
• Subexponential parameterized directed Steiner network problems on planar graphs: a complete classification
• The complexity landscape of fixed-parameter directed Steiner network problems
• The complexity of determining a shortest cycle of even length
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• The directed subgraph homeomorphism problem
• The Even Cycle Problem for Planar Digraphs
• The even-path problem for graphs and digraphs
• The shortest even cycle problem is tractable
• Tight bounds for divisible subdivisions

This page was built for publication: Edge-minimum walk of modular length in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296632)