Tight Paths and Tight Pairs in Weighted Directed Graphs

José Luis Balcázar · 2025

Read Tight Paths and Tight Pairs in Weighted Directed Graphs by José Luis Balcázar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-09966.txt.

Introduction

José Luis Balcázar, writing alone, presents a 2025 math paper on tight paths in directed graphs where each edge has a weight. A tight path is a route that meets a set bound in a strict way. The paper also treats tight pairs, a simpler form of the same problem.

The problems come from data analysis, where methods need basic antecedents in closure spaces. An antecedent is an earlier fact that supports a later one. Balcázar sets out the problems in clear form and then weighs several algorithms for them. He compares how the methods work, which helps readers pick an approach. The paper serves readers in graph theory and formal data analysis.

Catalog record

CREATORJosé Luis Balcázar
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-09966

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tight Paths and Tight Pairs in Weighted Directed Graphs José Luis Balcázar Abstract We state the graph-theoretic computational problem of finding tight paths in a directed, edge-weighted graph, as well as its simplification of finding tight pairs. These problems are motivated by the need of algorithms that find so-called basic antecedents in closure spaces, in one specific approach to data analysis. We discuss and compare several algorithms to approach these problems. 1 The general problem Consider a finite directed graph G=(V,E,d) on a set V of vertices, with edges E\subseteq V\times V and positive costs (or distances) d:E\to I\!\!R^{+} on the edges. A path in G is a sequence of vertices, p=(u_{1},\ldots,u_{k}) , with 1\leq k and (u_{i},u_{i+1})\in E for 1\leq i<k . The length of the path is k . The extreme case of a single node, k=1 , is still considered a (very short) path of length 1. We call p^{\prime}=(u_{i},\ldots,u_{j}) with 1\leq i\leq j\leq k a subpath of p . It is a proper subpath if, besides, p^{\prime}\neq p , that is, either 1<i or j<k (or both). In general, paths may not be necessarily simple, that is, repeated passes through the same vertex are allowed. The cost of a path p=(u_{1},\ldots,u_{k}) is the sum d(p)=\sum_{1\leq i<k}d(u_{i},u_{i+1}) of the costs of its edges. Clearly, d(p)=0 if p has length 1. Definition 1 Given a graph G and a threshold value \gamma\in I\!\!R with \gamma\geq 0 , a tight path (u_{1},\ldots,u_{k}) , is a path p in G such that 1. d(p)\leq\gamma but 2. every extension of p into p^{\prime} by adding a new edge at either end, (u_{0},u_{1})\in E or (u_{k},u_{k+1})\in E , leads to d(p^{\prime})>\gamma . (Of course, this might hold vacuously if no such extension is possible.) Example 2 Consider G on V=\{A,B,C,D,E\} with edges and costs (A,B):2 , (B,C):1 , (C,E):1 , (A,D):1 and (D,E):2 (see Figure 1 ). For threshold 3, the tight paths are (A,B,C) , (B,C,E) and (A,D,E) . Figure 1: Graph for example 2 . Example 3 Consider G on V=\{A,B,C,D,E\} with edges and costs (A,B):2 , (B,C):1 , (C,A):1 , (A,D):1 , (D,E):2 , and (E,A):1 (see Figure 2 ). For threshold 4, the tight paths are (A,B,C,A) , (A,D,E,A) , (B,C,A,B) , (B,C,A,D) , (C,A,B,C) , (C,A,D,E) , (D,E,A,D) , (E,A,D,E) , and (E,A,B,C) . At threshold 5, we find (A,B,C,A,D) , (D,E, A,B) , and others (a total of 9, all of length 5 except one). For larger thresholds, tight paths can go through the complete loops twice or more, or also alternate between them repeatedly. Figure 2: Graph for example 3 . Proposition 4 Every vertex belongs to at least one tight path. Proof. For any vertex u\in V , we grow a tight path edge-wise. View initially u as a path of length 1, hence, cost 0\leq\gamma . As long as the path at hand is not tight, it can be extended into a longer one with cost still bounded by \gamma , never losing u along the way, until tightness is reached. An alternative formulation of the same intuition of a tight path could be to consider subpaths of paths longer by more than one additional edge: a proper subpath of a tight path would not be tight. Both approaches are equivalent: Proposition 5 Given graph G with positive edge costs and threshold \gamma\in I\!\!R with \gamma\geq 0 , a path p in G is tight if and only if d(p)\leq\gamma and d(p^{\prime})>\gamma for every p^{\prime} that has p as a proper subpath. Proof. This is easily argued. Assume that p is tight: if p is a proper subpath of p^{\prime} , at least one additional edge is present in p^{\prime} ; moreover, either one such additional edge comes after the last vertex of p , or before its first vertex. Then, as p is tight, the cost of p plus the cost of that extra edge is already beyond the cutoff and the cost of p^{\prime} is at least that sum. The converse is proved by simply considering p^{\prime} that extends p by one edge at the beginning or at the end. Note that the condition that costs are positive is relevant to this argument. This paper focuses on the problem: given G and \gamma as indicated, find all the tight paths. We consider also a variant motivated by earlier work in the data analysis field, discussed next. 2 A case of acyclic vertex-weighted graphs In the context of a study of how partial implications can be obtained from closure spaces associated to transactional datasets [ 1 , 6 ] , a close relative of tight paths arises; actually, an interesting particular case. There, the graph is naturally acyclic, weights actually apply to vertices, and edge costs are obtained from the vertices’ weights (we develop a bit more this motivating connection below). More precisely, we focus now on the following particular case: our input graph is G=(V,E,w) , with vertex weights w:V\to I\!\!R^{+} . Moreover, the following inequality is assumed to hold: for all (u,v)\in E , w(u)<w(v) ; a fortiori , G is acyclic. Then, costs are set on the edges as weight differences between the endpoints, d((u,v))=w(v)-w(u) for every edge (u,v) , and tight paths are to be found on this graph for a cutoff value provided separately as before. Note that, by the assumed inequality about weights in edge endpoints, all these costs will be strictly positive, hence we fulfill the conditions of the general case. However, now, tight paths correspond to tight “vertex pairs” in the sense that, for a pair (u,v) , the weights of all the paths from u to v coincide, and depend only on the weights of the endpoints. Thus, we speak of “tight pairs” instead, as endpoints of tight paths. That fact is easy to see but we report here a proof for the sake of completeness. Lemma 6 Given graph G with vertex weights w where w(u)<w(v) for all (u,v)\in E and corresponding edge costs d((u,v))=w(v)-w(u) , the cost of a path is d(u,u_{2},\ldots,u_{k-1},v)=w(v)-w(u) . Proof. We prove it by induction on the length of the path. For length 1, u=v and indeed the cost is w(u)-w(u)=0 . Assume k>1 , and d(u,u_{2},\ldots,u_{k-1})=w(u_{k-1})-w(u) as inductive hypothesis. Then d(u,u_{2},\ldots,u_{k-1},v) is: d(u,u_{2},\ldots,u_{k-1})+d((u_{k-1},v))=w(u_{k-1})-w(u)+w(v)-w(u_{k-1})=w(v)-w(u). Note that, for k=2 , that is, for a path consisting of a single edge, this boils down exactly to how the cost of the edge has been defined. Example 7 The graph in Figure 3 comes from a closure space associated to a toy dataset. The construction of the closure space provides us (after a minimal preprocessing) with the labels shown in the vertices. We then compute the differences to obtain the costs for the edges and reach the particular case of a vertex-weighted acyclic graph discussed in this section; edge costs are shown only for clarity. It is a simple matter to check out some of the equalities stated by Lemma 6 in this example. We will explain later how to work directly with the vertex labels instead, in algorithmic terms, avoiding the edge-labeling process. Figure 3: Graph for example 7 . 2.1 Correspondence tightening Our next aim is to describe

Read the complete text