CS Paper Radar

Scalable Exact Path Selection via Structure-Aware Search for Virtual Payment Channels

Jiangnan Luo, Zhebei Shen, Yuan Zhang, Sheng Zhong

cs.DC ·submitted 2026-08-23 08:06 UTC · v1
published

Abstract

Virtual Payment Channels (VPCs) enable efficient off-chain transactions in Payment Channel Networks (PCNs), but their performance depends on selecting high-quality underlying paths. Existing approaches either rely on simplified metrics or incur high computational cost. We study VPC path selection under generalized monotone metrics and propose a structure-aware exact solver based on quadtree search. By exploiting monotonicity and distance plateau properties, our method prunes large regions of the capacity-constrained search space while preserving optimality, significantly reducing the number of shortest-path computations. We further instantiate the framework with a composite metric that integrates economic cost and security risk, enabling flexible trade-offs across application scenarios. Experiments on synthetic graphs and real-world Lightning Network topologies (up to 12,552 nodes) show 2--5 orders of magnitude speedup over prior work, with consistent sub-100ms latency.

Comment
10 pages, 9 figures. To appear in the Proceedings of the 55th International Conference on Parallel Processing (ICPP 2026)

Closest papers

Nearest neighbours by meaning across the whole index.

Employing the Structural Power to Achieve Supply-Demand Balanced Payment Channel Networks

cs.NI ·2026-09-03 ·Shuyao Xiao, Shengling Wang, Hongwei Shi, Weicheng Wang, Anlin Chen
similarity 0.60
Abstract

Blockchain technology faces scalability challenges because transactions must be validated and recorded across the network. Payment channel networks (PCNs) improve efficiency by moving transactions off-chain and recording only critical interactions on the mainnet. However, PCNs require pre-deposited channel balances (supply) to match transaction demands (demand), and insufficient balances cause supply shortages. Existing approaches, including transaction path optimization and channel balance allocation, address this problem but incur high costs due to dynamic adaptation to fluctuating demands. We reveal a correlation between balance deficits in PCNs and network topology by uncovering the structural organization of liquidity allocation. This enables supply-demand conflicts to be mitigated from a static topological perspective through channel reconfiguration, without additional balance replenishment. We further introduce payment topological entropy (PTE), an information-theoretic metric that quantifies each node's deviation from the global average connection pattern and captures structural properties of balance supply. Based on PTE, we design MaxPTE, a topology optimization algorithm that reorganizes balance allocation across channels through structural reconfiguration, aligning static balance distribution with dynamic transaction demand. Extensive experiments show that MaxPTE reduces balance deficits by 27.25%, increases average maximum flow by 12.23%, and decreases transaction failure probability by 25.96%, outperforming existing benchmarks. The method also remains robust across diverse balance-demand distributions, improving supply-demand balance without prior demand prediction.

0.21

Nonuniform Buy-at-Bulk Network Design: Improved Approximation and LP Integrality Gap

cs.DS ·2026-11-04 ·Iman Gholami, MohammadTaghi Hajiaghayi
theory similarity 0.59
Abstract

In nonuniform buy-at-bulk network design, we are given an undirected graph and $h$ terminal pairs with positive demands, and we must route every demand at minimum total cost when each network resource has two independent parameters: a fixed buying price paid once if the resource is used, and a per-unit rental cost (or physical length) paid proportionally to the traffic it carries. Unlike the uniform-cost or single-sink variants, the general multicommodity problem allows unrelated buying and rental metrics across arbitrary source--sink pairs, arbitrary demands, and both edge and node resources. We give a deterministic polynomial-time $O(\log^2 h / (\log\log h)^2)$-approximation algorithm for undirected nonuniform buy-at-bulk network design. The guarantee holds for edge costs, node costs, and their combination, and applies to arbitrary positive rational demands with no dependence on the number of vertices or the numerical demand ratio. This improves upon the $O(\log^4 h)$ bound of Chekuri, Hajiaghayi, Kortsarz, and Salavatipour (2010) for unrestricted instances. Our result also establishes the same $O(\log^2 h / (\log\log h)^2)$ upper bound on the integrality gap of the natural affine multicommodity flow LP, bounding integral buying and rental costs separately against their fractional counterparts and preserving zero rental budgets exactly.

0.25

Online Network Design with Additive Delays and Poisson Arrivals

cs.DS ·2026-11-10 ·Tianhang Lu, Runtian Ren, Shengcai Liu
hot direction similarity 0.58
Abstract

We study online service systems in which requests arrive at locations in a network. A service may open a facility and connect customers, buy a subtree linking them to a root, or send a mobile server to visit them. Combining requests can save opening, network, or travel costs, but each request pays its own waiting time. The objective is the sum of these spatial costs and individual delays. We assume independent Poisson arrivals of known rates. The algorithms know how often requests occur, but observe them only upon arrival. We show that these rates suffice to make fixed spatial choices that compete with an offline optimum free to adapt to the realized input. We obtain long-run ratios of expectations below $27.249$ for facility location in finite metrics, $94.415$ for multi-root aggregation on trees, and $24.326$ for online service on trees. All three algorithms are deterministic; the multi-root algorithm also has polynomial-time preprocessing on rational inputs. The proofs connect rate-based spatial choices with lower bounds on unavoidable purchase, movement, and waiting costs. All main proofs are self-contained, and every guarantee includes the full cost of completing finite inputs.

0.28

Tracing Money Flows in the Multi-Token Cryptocurrency Network

cs.SI cs.CEcs.CYcs.ET+1 ·2026-10-12 ·Natkamon Tovanich, Célestin Coquidé
similarity 0.55
Abstract · 14 pages, 4 figures, 1 table, 19 references, 15th International Conference on Complex Networks and Their Applications

Tracing money flows in cryptocurrency transaction networks is challenging because funds can move across accounts, transactions, and token layers. We propose a transaction-aware graph in which nodes represent account--asset states within transactions, while edges encode observed transfers, inferred asset transformations, and temporal inter-transaction sequences. Applied to Aave borrow--repay flows, we compare graph construction and edge-pruning strategies and extract shortest paths using a heuristic weighting. Our results reveal a trade-off between reachability and interpretability and uncover frequent token sequences underlying how borrowed assets are transformed before repayment. This work lays a foundation for general, interpretable multi-token flow tracing.

0.33

Online Vertex Connectivity Augmentation

cs.DS ·2026-11-11 ·Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski
similarity 0.53
Abstract · 35 pages

Network design problems form a classic subfield of online algorithms, but almost nothing is known about their more challenging vertex-connectivity variants. We initiate the study of online vertex-connectivity network design for arbitrary demand pairs by considering the fundamental problem of connectivity augmentation. In an instance of \emph{Online Vertex Connectivity Augmentation} (OVCA), we are given a $k$-vertex-connected graph $F$ and a set of additional purchasable edges (with costs). Demand pairs $(s_1,t_1),(s_2,t_2),\dots$ then arrive online. Upon each arrival, the algorithm must irrevocably purchase edges so that $s_i$ and $t_i$ become $(k{+}1)$-vertex-connected in the union of $F$ with all edges purchased so far. Our main contribution is an $O((k+\log n)\log n)$-competitive online algorithm for OVCA. We also give an offline $O(k+\log n)$-approximation algorithm. We obtain our algorithms via a structural dichotomy on the minimum vertex cuts of $F$. We note that some dependence on $k$ in the approximation ratio is necessary -- i.e., the problem is hard to approximate within any $\mathrm{polylog}(n)$ factor independent of $k$ -- which shows a separation from the edge-connectivity setting. Finally, specializing to $k=1$, our methods yield the first polylogarithmic-competitive online algorithm for a vertex-connectivity survivable network design problem, namely an $\widetilde O(\log^3 n)$-competitive algorithm for online $\{1,2\}$-VC-SNDP (i.e., an SNDP variant where each demand pair comes with a vertex-connectivity requirement of $1$ or $2$).

0.18

Certified Bank-Aware Fast-Path Coverage for Hardware-Constrained NDN Forwarding Lookup

cs.AR cs.NI ·2026-08-28 ·Amirreza Khorasanian
similarity 0.53
Abstract · 19 pages, 7 figures. Extended preprint

Named Data Networking (NDN) replaces address-based forwarding with longest-prefix lookup over variable-length hierarchical names, creating a difficult fit with bounded hardware fast paths. We formulate this problem as certified fast-path coverage. An offline mapper selects a prefix-closed set of parser-visible trie nodes and a separate set of action-equivalence certificates under a shared budget. A certificate relates a selected shallow FIB prefix to a deeper true-LPM class with the same forwarding action; applying the shortcut requires a sound class guard, while uncertain traffic falls back to an exact path. We present BPC-Greedy, a certificate-aware placement heuristic, and BPC-Portfolio, a multi-strategy wrapper spanning exact-heavy, repair-based, and shallow-shortcut constructions. The formulation exposes a tree-closure knapsack structure for prefix placement, exact top-k certificate selection for a fixed selected set under uniform certificate cost, and a separate bank-feasibility layer. On a synthetic parser-depth sweep and a 50k replay of public NDN testbed names under a reproducible synthetic forwarding-action snapshot, modeled certified coverage increases from 46.48% for the best exact-prefix-only bank-aware baseline to 64.06% at total budget M=48. These results characterize placement opportunity under the stated model: the evaluator uses the known true LPM as an oracle-style guard, certificate-table bank traffic is not modeled, and no claim is made about synthesized latency, area, or throughput.

0.31

Optimizing Multi-Tier Intermediation in Programmatic Advertising: A DAG-Based Mechanism for Supply Path Optimization

cs.AI ·2026-11-08 ·Amelia Bădică, Costin Bădică
benchmark similarity 0.53
Abstract

Digital programmatic advertising operates through complex, multi-hop supply chains. The opacity of these intermediary networks leads to significant efficiency losses, often referred to as the ``ad-tech tax.'' While current industry practices utilize heuristic Supply Path Optimization (SPO) to trim inefficient routes, they fail to optimize the equilibrium of the entire network. This paper extends previous work on Directed Acyclic Graph (DAG) intermediation models by applying them to traceable programmatic supply chains mapped via the OpenRTB SupplyChain object. We introduce multi-attribute utility functions and Mixed-Integer Linear Programming (MILP) to account for substitutable routing (OR nodes) and percentage-based fee structures. Furthermore, we outline a computational methodology and experimental framework using public \texttt{schain} and \texttt{sellers.json} data to benchmark optimal Nash social welfare against current uncoordinated market outcomes.

0.33

Trim: Fee Level Matters More Than Skew in Lightning Routing

cs.NI cs.CRcs.GTeess.SY ·2026-10-26 ·Huiping Sun, Peilu Guo, Yiming Zhu, Yueqi Wu, Zhong Chen
similarity 0.53
Abstract

Lightning routing nodes lend their channel balance for a posted fee. Operators' tools move that fee with the balance around a hand-set level, and which part of the fee drives revenue is unclear. We present Trim, which models a channel as a two-sided inventory with costly refills. Its optimal fee is a level, set by demand and replenishment, plus a balance skew, the shadow price of liquidity. The level is first order: no fee rule beats the ceiling demand and replenishment set, and on exactly solved channels the best flat fee comes within $1.6\%$ of the optimum at the median, whereas a level off by a factor of two loses tens of percent. The skew is second-order insurance: it adds at most what the flow-balancing flat fee loses to refused forwards. So the level should be chosen: Trim's rule traces the revenue--success frontier, posts one level on every channel, and adds a skew only where refills stay frequent and costly. On a 2026 snapshot with synthetic payments, no tuned tool beats that frontier by over a few percent, and a skew changes gross revenue by a few percent.

0.24