arxiv: 2605.12457 · v1 · submitted 2026-05-12 · 💻 cs.DS · cs.DM

Recognition: 2 theorem links

· Lean Theorem

Layer-Based Width for PAFP

Samuel German

Pith reviewed 2026-05-13 02:39 UTC · model grok-4.3

classification 💻 cs.DS cs.DM

keywords PAFPforbidden pairsBFS-widthbackward arcsfixed-parameter tractabilitydirected acyclic graphs2-SAT

0 comments

The pith

PAFP is fixed-parameter tractable when the union digraph has small BFS-width from s and few backward arcs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper introduces a layer-based width for analyzing the computational complexity of finding an s-t path that avoids taking both vertices from any forbidden pair. It shows that when the union of the graph and forbidden-pair arcs has small BFS-width b from the source and few backward arcs β, the problem is fixed-parameter tractable in b plus β. This is significant because it permits arbitrary forbidden pairs and graphs with exponentially many s-t paths, expanding beyond earlier tractable cases that limited the forbidden pairs. For DAGs with exact-length layer width at most 2, it further gives a polynomial-time 2-SAT algorithm. The bounds are tight, with NP-completeness for larger widths.

Core claim

If the union digraph has BFS-width b from s and β backward arcs, PAFP is FPT in b+β. For DAGs of BFS-width 2 with k backward input arcs, it is solvable in 2^k |I|^O(1) time. For DAGs of exact-length width 2, it is in P by 2-SAT encoding of fixed-length paths. The union is formed by adding oriented forbidden-pair arcs according to a reachability-compatible order.

What carries the argument

BFS layers in the union digraph G∪F, with b as max layer size and β as the number of backward arcs between layers.

If this is right

PAFP admits an FPT algorithm parameterized by b + β.
PAFP on BFS-width-2 DAGs with k backward arcs is solvable in 2^k |I|^O(1) time.
PAFP on exact-length-width-2 DAGs is polynomial-time decidable.
PAFP is NP-complete on DAGs with BFS-width 2 or exact-length width 3.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Practitioners might search for an ordering of forbidden pairs that minimizes β to apply the FPT result when the resulting b and β are small.
The exact-length width measure could be tested on other length-constrained path problems in DAGs.
Layer-based analysis with backward-arc counts may classify complexity for additional constrained path problems.

Load-bearing premise

There exists a reachability-compatible order on the forbidden pairs that produces a union digraph with small BFS-width and few backward arcs.

What would settle it

A family of PAFP instances with bounded b + β for which no f(b+β) n^O(1) algorithm exists, or an exact-length width-2 DAG where the 2-SAT encoding fails to decide reachability correctly.

Figures

Figures reproduced from arXiv: 2605.12457 by Samuel German.

**Figure 1.** Figure 1: The union digraph G ′∪F′ of the normalized instance I ′ = Normalize(I), taking I to be the boxed structure. The reachable-core forbidden-pair arc b → t is inserted into the output graph according to the internal order ◁. Since the detour into t leaves the spine at p1, while the detour into b leaves later at p7, traversing b → t cannot create a shorter s ′ -to-t route than the direct detour into t. directly… view at source ↗

read the original abstract

The Path Avoiding Forbidden Pairs problem (PAFP) asks whether, in a directed graph $G$ with terminals $s,t$ and a set $\mathcal{F}$ of forbidden vertex pairs, there is an $s$-$t$ path that contains at most one endpoint from each forbidden pair. We initiate the study of PAFP through a layer-based width measure. Our first focus is the union digraph $G\cup\mathcal{F}$, obtained by adding to $G$ one arc per forbidden pair, oriented according to a fixed reachability-compatible order. Let the BFS layer $L_d$ be all vertices at directed shortest-path distance $d$ from $s$, where the BFS-width from $s$ is $\max_d |L_d|$. We show if $G\cup\mathcal{F}$ has BFS-width $b$ from $s$ and only $\beta$ arcs going from a later BFS layer to an earlier one, then PAFP is FPT parameterized by $b+\beta$. The backward-arc hypothesis is essential: we show PAFP remains NP-complete when the union digraph is a DAG with BFS-width 2. We also show if the input DAG has BFS-width at most $2$ and only $k$ backward input arcs, then PAFP can be decided in $2^k |I|^{O(1)}$ time, with unrestricted forbidden pairs. This width-$2$ result is tight: inspection of a classical reduction shows NP-completeness on input DAGs of BFS-width $3$ with no backward input arcs. Moreover, we study exact-length layers in the input graph, where the $d$-th layer consists of the vertices reachable from $s$ by a directed path of length exactly $d$. For DAGs of exact-length width at most $2$, we show PAFP is polynomial-time decidable by a 2-SAT encoding of fixed-length paths. This bound is tight: the same classical reduction yields NP-completeness on DAGs of exact-length width $3$. Unlike previously known polynomial-time regimes for PAFP, which restrict the forbidden-pair set in order to obtain tractability, our two input-graph tractability results allow unrestricted forbidden pairs and input graphs with exponentially many $s$-$t$ paths.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

New layer widths give FPT and poly-time regimes for PAFP but the main FPT claim depends on an auxiliary order that the input does not provide and whose computation is not shown to be FPT.

read the letter

The core of this paper is a pair of layer-based width measures for the Path Avoiding Forbidden Pairs problem. One uses BFS layers on the union digraph after orienting forbidden pairs via a reachability-compatible order; if that union has BFS-width b and only β backward arcs, PAFP is FPT in b+β by dynamic programming over layers. The other uses exact-length layers on the input DAG and gives a 2-SAT encoding that solves the problem in polynomial time when the exact-length width is at most 2. Both results allow arbitrary forbidden pairs, which is an improvement over earlier tractable cases that had to restrict F. The matching hardness statements, obtained by inspecting a classical reduction, show NP-completeness already at width 3 for both measures. That tightness is useful and cleanly presented.

Referee Report

3 major / 2 minor

Summary. The paper studies the Path Avoiding Forbidden Pairs (PAFP) problem using layer-based width measures. It claims that if a reachability-compatible order exists such that the union digraph G∪F has BFS-width b from s and only β backward arcs, then PAFP is FPT parameterized by b+β. For DAGs of exact-length width at most 2, PAFP is polynomial-time decidable via 2-SAT encoding of fixed-length paths. Tightness is shown via NP-completeness on BFS-width 3 and exact-length width 3 instances, including when the union is a DAG of BFS-width 2.

Significance. If the results hold, they provide new tractability regimes for PAFP that permit unrestricted forbidden pairs F, in contrast to prior work that obtains tractability by restricting F. The BFS-layer DP and exact-length 2-SAT approach are standard techniques but yield FPT and polynomial-time algorithms under these width parameters on the input graph or union. The tightness results via classical reductions strengthen the claims by showing the width thresholds are sharp.

major comments (3)

[Abstract / main FPT result] The main FPT claim (Abstract) is stated conditionally on the existence of a reachability-compatible order orienting the |F| arcs so that G∪F has BFS-width b and small β backward arcs. The standard PAFP input is only (G,s,t,F); no FPT procedure is indicated for computing such an order (or showing one with small b+β always exists), and the number of linear extensions of the reachability relation can be exponential. This makes the FPT guarantee apply only to an augmented problem or under an unstated assumption, which is load-bearing for the central algorithmic result.
[Abstract / exact-length width result] The polynomial-time result for exact-length width ≤2 (Abstract) relies on a 2-SAT encoding of fixed-length paths, but the abstract provides no explicit variables, clauses, or recurrence showing how the width-2 structure bounds the instance size. The tightness claim (NP-completeness on exact-length width 3) invokes 'the same classical reduction' without specifying which reduction or verifying that it preserves exact-length width exactly 3.
[Abstract / BFS-width 2 NP-completeness] The NP-completeness claim for the union digraph being a DAG of BFS-width 2 (Abstract) is contrasted with the FPT result for input DAGs of BFS-width 2 with k backward input arcs (solvable in 2^k |I|^O(1) time). Clarification is needed on how backward arcs from F are distinguished from input arcs in the reduction and why β cannot be bounded in the hardness construction.

minor comments (2)

[Abstract] The abstract uses both mathcal{F} and F for the forbidden set; standardize notation.
[Abstract] Define 'backward arcs' explicitly on first use in the abstract for readers unfamiliar with the layer orientation.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments highlight opportunities to improve clarity in the abstract and distinctions between results. We address each major comment below and will make targeted revisions to the manuscript.

read point-by-point responses

Referee: [Abstract / main FPT result] The main FPT claim (Abstract) is stated conditionally on the existence of a reachability-compatible order orienting the |F| arcs so that G∪F has BFS-width b and small β backward arcs. The standard PAFP input is only (G,s,t,F); no FPT procedure is indicated for computing such an order (or showing one with small b+β always exists), and the number of linear extensions of the reachability relation can be exponential. This makes the FPT guarantee apply only to an augmented problem or under an unstated assumption, which is load-bearing for the central algorithmic result.

Authors: We agree the result is conditional on the existence of a reachability-compatible order yielding BFS-width b and β backward arcs in G∪F. This defines a structural parameterization of PAFP by b+β; the algorithm we give (BFS-layer DP) takes the order as auxiliary input and runs in f(b+β)·|I|^O(1) time. We do not claim an FPT algorithm for discovering such an order, nor that small b+β is always achievable. This is standard for width-based parameters where the witness (here the order) may be hard to compute. To remove any ambiguity we will revise the abstract to state explicitly that the FPT result holds for instances admitting such an order (i.e., the parameterization is by the minimum b+β over valid orders). revision: yes
Referee: [Abstract / exact-length width result] The polynomial-time result for exact-length width ≤2 (Abstract) relies on a 2-SAT encoding of fixed-length paths, but the abstract provides no explicit variables, clauses, or recurrence showing how the width-2 structure bounds the instance size. The tightness claim (NP-completeness on exact-length width 3) invokes 'the same classical reduction' without specifying which reduction or verifying that it preserves exact-length width exactly 3.

Authors: The abstract is space-limited; the full 2-SAT construction appears in Section 4. For exact-length width 2 each layer contains at most two vertices, so we introduce O(n) variables per layer (one per possible vertex at each exact distance) together with clauses enforcing adjacency, exact-length progress, and at-most-one-endpoint per forbidden pair. The resulting 2-SAT instance is polynomial in |I|. For tightness, the classical reduction is the standard PAFP NP-completeness reduction from 3-SAT (or Hamiltonian Path on cubic graphs) used in prior literature; we will name it explicitly and add a short verification that the constructed DAGs have exact-length layers of size exactly 3. We will insert a clarifying sentence (or footnote) in the abstract referencing the section and confirming width preservation. revision: yes
Referee: [Abstract / BFS-width 2 NP-completeness] The NP-completeness claim for the union digraph being a DAG of BFS-width 2 (Abstract) is contrasted with the FPT result for input DAGs of BFS-width 2 with k backward input arcs (solvable in 2^k |I|^O(1) time). Clarification is needed on how backward arcs from F are distinguished from input arcs in the reduction and why β cannot be bounded in the hardness construction.

Authors: The two results operate on different objects. The FPT result assumes the input graph G itself is a DAG of BFS-width 2 containing exactly k backward arcs (with respect to its own BFS layering); F may add only forward arcs. The DP tracks the k backward arcs with 2^k states. The hardness result constructs instances where the union G∪F is itself a DAG (hence β=0) of BFS-width 2; the reduction orients every arc of F forward so that no backward arc appears in the union. Consequently β is zero yet the problem remains NP-complete. We will add a short explanatory paragraph (in the introduction or the hardness section) that explicitly distinguishes “backward arcs of G” from “backward arcs of the union” and notes that the hardness instances have β=0 by construction while still being hard. revision: yes

Circularity Check

0 steps flagged

No circularity; FPT and poly-time claims use standard DP and 2-SAT

full rationale

The paper's central results rest on explicit algorithmic constructions: dynamic programming over BFS layers of the union digraph (parameterized by width b and backward arcs β) and a direct 2-SAT encoding for exact-length width-2 DAGs. These are standard techniques applied to the input (G,s,t,F) and do not reduce to quantities defined in terms of the target PAFP decision. The reachability-compatible order is an auxiliary device used only in the conditional 'if' statement; the paper does not claim an FPT procedure to discover it or redefine any parameter via the result itself. No self-citations, fitted inputs, or ansatzes appear in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The paper relies on standard definitions from graph theory and introduces new width measures as the primary technical contribution.

axioms (2)

standard math BFS layers are defined by directed shortest-path distances from s.
Used to define BFS-width and backward arcs.
domain assumption A reachability-compatible order exists for orienting forbidden-pair arcs.
Required to construct the union digraph with controlled backward arcs.

invented entities (2)

BFS-width of the union digraph no independent evidence
purpose: Parameter for FPT algorithm
Newly defined measure combining graph layers and forbidden-pair arcs.
Exact-length width no independent evidence
purpose: Parameter for polynomial-time 2-SAT reduction
Newly defined measure on exact path lengths in DAGs.

pith-pipeline@v0.9.0 · 5715 in / 1449 out tokens · 73989 ms · 2026-05-13T02:39:16.318967+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
Theorem 1: FPT for bounded union BFS-width b and β backward arcs; Theorem 12: PT via 2-SAT for exact-length width ≤2 on DAGs
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
BFS layers L_d, exact-length layers E_G(s,d), backward arcs B^-_H(s)

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

Journal of Algorithms12(2), 308–340 (1991)

Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. Journal of Algorithms12(2), 308–340 (1991). https://doi.org/10.1016/0196- 6774(91)90006-K

work page doi:10.1016/0196- 1991
[2]

Algorithmica81(4), 1561–1583 (2019)

Bannister, M.J., Devanny, W.E., Dujmović, V., Eppstein, D., Wood, D.R.: Track layouts, layered path decompositions, and leveled planarity. Algorithmica81(4), 1561–1583 (2019). https://doi.org/10.1007/s00453-018-0487-5

work page doi:10.1007/s00453-018-0487-5 2019
[3]

In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A

Bezáková, I., Curticapean, R., Dell, H., Fomin, F.V.: Finding Detours is Fixed- Parameter Tractable. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol. 80, pp. 54:1–54:14. Schloss Dagstuhl – Lei...

work page doi:10.4230/lipics.icalp.2017.54 2017
[4]

Theoretical Computer Science511, 117–136 (2013)

Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernel bounds for path and cycle problems. Theoretical Computer Science511, 117–136 (2013). https://doi.org/10.1016/j.tcs.2012.09.006

work page doi:10.1016/j.tcs.2012.09.006 2013
[5]

Journal of Combinatorial Theory, Series B127, 111–147 (2017)

Dujmović, V., Morin, P., Wood, D.R.: Layered separators in minor-closed graph classes with applications. Journal of Combinatorial Theory, Series B127, 111–147 (2017). https://doi.org/10.1016/j.jctb.2017.05.006

work page doi:10.1016/j.jctb.2017.05.006 2017
[6]

In: Benoit, A., Kaplan, H., Wild, S., Herman, G

Eppstein, D., Goodrich, M.T., Liu, S.A.: Bandwidth vs BFS width in matrix re- ordering, graph reconstruction, and graph drawing. In: Benoit, A., Kaplan, H., Wild, S., Herman, G. (eds.) 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), vol. 351, pp. 69:1–69:17. Schloss Dagstuhl – Leibniz-Zen...

work page doi:10.4230/lipics.esa.2025.69 2025
[7]

IEEE Transactions on Software Engineering2(3), 227–231 (1976)

Gabow,H.N.,Maheshwari,S.N.,Osterweil,L.J.:Ontwoproblemsinthegeneration of program test paths. IEEE Transactions on Software Engineering2(3), 227–231 (1976). https://doi.org/10.1109/TSE.1976.233819

work page doi:10.1109/tse.1976.233819 1976
[8]

Discrete Applied Mathematics157(13), 2871–2876 (2009)

Kolman, P., Pangrác, O.: On the complexity of paths avoiding for- bidden pairs. Discrete Applied Mathematics157(13), 2871–2876 (2009). https://doi.org/10.1016/j.dam.2009.03.018

work page doi:10.1016/j.dam.2009.03.018 2009
[9]

Discrete Applied Mathematics161(10–11), 1506–1512 (2013)

Kováč, J.: Complexity of the path avoiding forbidden pairs problem re- visited. Discrete Applied Mathematics161(10–11), 1506–1512 (2013). https://doi.org/10.1016/j.dam.2012.12.022, early version available as arXiv:1111.3996

work page doi:10.1016/j.dam.2012.12.022 2013
[10]

2023.Parallel Programming for Multicore and Cluster Systems(3 ed.)

Kovač,J.,Vinař,T.,Brejová,B.:PredictinggenestructuresfrommultipleRT-PCR tests. In: Algorithms in Bioinformatics (WABI 2009). Lecture Notes in Computer Science, vol. 5724, pp. 181–193. Springer (2009). https://doi.org/10.1007/978-3- 642-04241-6_16

work page doi:10.1007/978-3- 2009
[11]

Krause, K.W., Smith, R.W., Goodwin, M.A.: Optimal software test planning throughautomatednetworkanalysis.In:Proceedingsofthe1973IEEESymposium on Computer Software Reliability. pp. 18–22. IEEE (1973)

work page 1973
[12]

Journal of Computer and System Sciences76(2), 103–114 (2010)

Samer, M., Szeider, S.: Constraint satisfaction with bounded treewidth re- visited. Journal of Computer and System Sciences76(2), 103–114 (2010). https://doi.org/10.1016/j.jcss.2009.04.003

work page doi:10.1016/j.jcss.2009.04.003 2010
[13]

Dis- crete Applied Mathematics74(1), 85–92 (1997)

Yinnone, H.: On paths avoiding forbidden pairs of vertices in a graph. Dis- crete Applied Mathematics74(1), 85–92 (1997). https://doi.org/10.1016/S0166- 218X(96)00017-0 A Well-definedness of the output ofNormalize Claim 14 (Normalizeoutputs validP AFPinstances).LetI= (G= (V, E), s, t,F)be aPAFPinstance whereGis a DAG, and letI ′ = Normalize(I) = (G′ = (V ...

work page doi:10.1016/s0166- 1997