PaperlayerView exact revision on arXiv

Source-linked AI summary

An Algorithm for Linear Parametric Minimum Cycle Mean Problem

Yuki Nishida

arXiv:2609.29234v1cs.DM

TL;DR

The paper addresses the relatively little-studied parametric minimum cycle mean problem for edge costs a(e) − b(e)t. It adapts parametric shortest-path methods to find its breakpoints and minimum mean cycles. The resulting algorithm runs in O((m + n log n)n^2W) time, and the approach also computes tropical eigenvectors.

  • Problem

    The parametric minimum cycle mean problem has received little attention, despite the importance of minimum cycle means to discrete-event-system performance.

    Source: §1 · p. 1

  • Method

    The algorithm extends parametric shortest-path tree updates by adjusting costs to keep each detected zero-cost cycle at zero while searching for later cycles.

    Source: §1.1 · p. 2

  • Results

    O((m + n log n)n^2W) time solves the parametric MCM for n vertices, m edges, and maximum absolute slope coefficient W.

    Source: §1.1 · p. 2, §3.1 · p. 13

  • Takeaways & Limitations

    The method also computes tropical eigenvectors as shortest-path trees are updated, providing cyclic schedules alongside eigenvalues.

    Source: §1.1 · p. 2, §6 · p. 16

    The symbolic Karp method’s time-complexity improvement is limited to cases where m is much smaller than n log n.

    Source: §5 · p. 16

Abstract

from arXiv · show

The minimum cycle mean problem (MCM) on weighted digraphs is the problem of finding the minimum value of the cycle mean, that is, the ratio of the cost to the length, over all cycles. Despite its wide range of applications to discrete event systems, the parametric counterpart of the MCM has received relatively little attention in the literature, unlike other parametric problems in network optimization. In this paper, we consider the linear parametric MCM, where all edges $e$ have cost $a(e)-b(e)t$ with parameter $t$. We propose an algorithm to solve the linear parametric MCM in $O((m+n\log n)n^2W)$ time, where $n$ is the number of vertices, $m$ is the number of edges, and $W$ is the maximum absolute value of the coefficients $b(e) \in \mathbb{Z}$. The central technique of the proposed method is the algorithm for the parametric shortest path problem. The MCM is closely related to spectral theory in the tropical semiring, where the ``$\min$'' operation is regarded as addition and ``$+$'' as multiplication. By exploiting the connection between them, we provide a method to compute the eigenvalues and eigenvectors of tropical parametric matrices.

1 Introduction

The paper addresses the little-studied single-parameter minimum cycle mean problem, where each edge cost is a(e) − b(e)t. It develops an algorithm based on parametric shortest paths and connects its results to tropical eigenvectors.

1.1 Our results

  • O((m + n log n)n^2W) time solves the general parametric MCM by repeatedly modifying edge costs to keep each detected zero-cost cycle from becoming negative.The algorithm continues updating shortest-path trees until it finds all breakpoints and corresponding minimum mean cycles.Source: §1.1 · p. 2
  • O(n^2W) bounds both the number of cycle-mean breakpoints and, for each vertex pair, shortest-path changes under the dynamically updated costs.Source: §1.1 · p. 2
  • Tropical eigenvectors, which correspond to cyclic schedules, can be computed successively as shortest-path trees are updated.The paper uses the connection between minimum cycle means and tropical eigenvalues, and between shortest paths and tropical eigenvectors.Source: §1.1 · p. 2

1.2 Related works

  • Earlier parametric MCM studies covered restricted tropical or mean-payoff settings, [16], and multiparametric cases,, motivating an efficient general single-parameter algorithm.Related work also discusses synchronous dataflow and tropical interval matrices [4], [5, 33].Source: §1.2 · p. 3
  • General parametric-search methods also apply: Eisner–Severance has O(mn^3W) overall complexity, while Gusfield’s method finds breakpoints sequentially in polynomial time.Source: §1.2 · p. 3

2 Preliminaries

This section establishes the cycle-mean and parametric shortest-path formulations used in the paper. It describes how shortest-path trees change as the parameter increases and how their updates identify breakpoints.

2.1 Parametric minimum cycle mean problems

  • For edge costs a(e) − b(e)t, the parametric MCM finds intervals and corresponding cycles that minimize the cycle mean throughout each interval.Source: §2.1 · p. 4

2.2 Parametric shortest path algorithms

  • The parametric single-sink shortest-path problem finds parameter intervals and rooted trees that remain shortest-path trees throughout those intervals.A shortest-path tree consists of shortest paths to a fixed root.Source: §2.2 · p. 5
  • As t increases, the current tree remains shortest until the minimum edge key; paths with b(P) no greater than b(Tv) cannot overtake the current v-r path.Source: §2.2 · p. 5
  • At the next breakpoint, an edge replaces the tree edge leaving its tail unless it closes a zero-cost cycle, which ends the shortest-path-tree updates.Source: §2.2 · p. 5
  • Young et al. maintain key values with a Fibonacci heap and give an O((m + n log n)nW) time bound for integer slope coefficients bounded by W.Source: §2.2 · p. 6

3 Algorithms for parametric minimum cycle mean

This section presents an algorithm for the parametric minimum cycle mean problem, using cost normalization and a parametric shortest-path method to locate breakpoints, and analyzes its correctness and running time, including a refined bound when only a few edges are parametric.

3 Algorithms for parametric minimum cycle mean

  • Starting from a minimum-mean cycle at a sufficiently small t0, the algorithm adjusts costs to keep the minimum cycle mean zero and uses parametric shortest paths to find successive breakpoints.At each breakpoint it identifies another zero-cost cycle, then repeats the cost adjustment and breakpoint search.Source: §3 · pp. 6, 9

3.1 Theoretical analysis of Algorithm 1

  • The tree-path key computation takes O(n) time, while computing a vertex key and a minimizing edge takes O(deg+(v)) time.Source: §3.1 · p. 9
  • The initial minimum cycle remains optimal for t ≤ t0, and adjusted costs are continuous across breakpoints while the rooted shortest-path tree is maintained.On each breakpoint interval, the corresponding zero-cost cycle attains the minimum cycle mean.Source: §3.1 · pp. 9, 10, 13
  • The minimum cycle mean is the minimum of at most (n^2 + 2n)W linear polynomials.Source: §3.1 · p. 11
  • For each vertex v, the algorithm updates its shortest path Tv at most 2(|Lv| − 1) times.Source: §3.1 · p. 12
  • Algorithm 1 solves the parametric MCM in O((m + n log n)n2W) time.Source: §3.1 · p. 13
  • O((m + n log n)n^2W) is the overall time complexity of Algorithm 1.The analysis maintains vertex keys with a Fibonacci heap.Source: §3.1 · p. 14
  • When every edge has b(e) ∈ {−1, 0, 1}, Algorithm 1 runs in O((m + n log n)n^2) time.Source: §3.1 · p. 14
  • O(mn + K) is a refined running-time bound for Algorithm 1, useful when only a few edges are parametric.K is given in terms of vertex degrees, log n, and |L_v|.Source: §3.1 · p. 14

4 Parametric tropical eigenvectors

The section connects tropical matrix eigenproblems to minimum cycle means, then gives parametric algorithms for eigenvalues and eigenvectors. The eigenvalue is piecewise linear in the parameter, while computing the eigenvector requires additional work based on shortest-path trees.

4 Parametric tropical eigenvectors

  • The tropical semiring uses min as addition and ordinary addition as multiplication, and its matrix eigenproblem is understood through the graph's minimum cycle mean.For a strongly connected graph, the matrix eigenvalue is unique; a column of the shifted matrix closure is an eigenvector when its index lies on a minimum mean cycle.Source: §4 · p. 14
  • A matrix over the tropical semiring represents a weighted digraph, and its powers encode minimum walk costs while its closure encodes shortest-path costs when no negative-cost cycle exists.The graph has an edge for each finite matrix entry, with that entry as its cost.Source: §4 · p. 14

4.1 Parametric algorithm

  • The eigenvalue of C(t) is piecewise linear in t and can be computed in O((m + n log n)n^2W) time.Here, W is the maximum absolute parameter coefficient among finite matrix entries.Source: §4.1 · p. 15
  • The eigenvector components are piecewise linear in t and can be computed in O((m + n log n)n^3W) time.For each interval, a column of the closure of the shifted matrix gives an eigenvector when its index lies on the minimum mean cycle; the corresponding shortest-path tree is rooted at that vertex.Source: §4.1 · p. 15

5 Comparison to the symbolic Karp’s method

The section compares symbolic Karp’s method with the proposed parametric-shortest-path approach. Symbolic Karp has a potentially lower bound only when m is much smaller than n log n, while the proposed approach may be faster in practice and also adapts to tropical eigenproblems.

5 Comparison to the symbolic Karp’s method

  • The symbolic method represents walk costs as tropical Laurent polynomials and computes F_v(ℓ) terms iteratively, requiring O(mn^2W) time.The coefficients track the minimum a(P) among walks with a given b(P) value.Source: §5 · pp. 15–16
  • Symbolic Karp’s O(mn^2W) time is not significantly better overall; its improvement is limited to cases where m is much smaller than n log n.The comparison also notes that the proposed algorithm’s worst-case bound may overstate its expected computation time for instances where parametric shortest paths are faster in practice.Source: §5 · p. 16
  • Symbolic Karp must compute all F_v(ℓ) terms, with computation time proportional to the total number of pairs in the sets L′_v.Those sets contain the (walk length, b(P)) pairs for walks of length at most n − 1.Source: §5 · p. 16
  • Algorithm 1 also adapts to tropical eigenproblems because its dynamic cost updates suit the shortest-path computation used for tropical eigenvectors.The computation of tropical eigenvectors is reduced to shortest paths with the modified cost function.Source: §5 · p. 16

6 Concluding remarks

The proposed algorithm solves parametric MCM in O((m + n log n)n^2W) time and can be faster when breakpoint counts are small. It also computes tropical eigenvectors as a byproduct, although their stated worst-case complexity is higher.

6 Concluding remarks

  • The algorithm solves parametric MCM in O((m + n log n)n^2W) time, with substantially lower runtime when minimum-mean-cycle or shortest-path-tree breakpoint counts are small.The stated complexity is O((m + n log n)n^2W) in general.Source: §6 · p. 16
  • Using shortest-path trees, the algorithm computes tropical eigenvectors of a parametric matrix as a byproduct of computing its eigenvalues.The stated worst-case time for tropical eigenvectors is O((m + n log n)n^3W), and improving it through partial shortest-path optimality remains future work.Source: §6 · p. 16
Loading 2609.29234v1…