Layer-Based Width for PAFP

arXiv:2605.12457 · cs.DS, cs.DM · Submitted 2026-05-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Layer-Based Width for PAFP".

Jane: Here's the gist of the paper. The Path Avoiding Forbidden Pairs problem (PAFP) asks whether there exists an s–t path that contains at most one endpoint from each pair in F and this study investigates layer-based width measures to determine tractability conditions for PAFP.

Tom: Tractability via Union Digraph Structure The paper shows that if the union digraph has BFS-width b from s and only β arcs going from a later BFS layer to an earlier one, then PAFP is FPT parameterized by b + β.

Jane: The backward-arc hypothesis is essential for this tractability result.

Tom: Furthermore, the union digraph is helpful because inspection of the classical layered reduction shows that PAFP is NP-complete on instances for which the input graph has both BFS-width 3 and no backward arcs.

Paper summary: Tom: So we're looking at this paper called "Layer-Based Width for PAFP". The main idea is using a specific measure called layerbased width to figure out when the Path Avoiding Forbidden Pairs problem becomes efficient.

Jane: That sounds like it’s trying to find some structural property of the graph that lets us solve a pathfinding problem in less time, you know, faster than brute force. What exactly is PAFP about?

Tom: PAFP asks if there's a path from an start vertex s to a terminal vertex t in a directed graph G that only touches one end of any forbidden pair in F. The authors are looking at this through the lens of the union digraph, which they add arcs for every forbidden pair and orient them based on reachability.

Lu: What's interesting is how they use BFS layers to define a BFSwidth from s as the maximum size of any BFS layer L d, which is just all the vertices at directed shortest-path distance d from s. This statistic is used to bound the complexity of PAFP when combined with another structural constraint.

Meng: Wait, so it's not just about the graph structure itself, but how those forbidden pairs are represented in this union digraph? If we have a union digraph with BFSwidth b and only beta arcs going backward between later layers and earlier layers, then PAFP becomes fixed parameter tractable parameterized by b plus beta.

Lalam: So the key condition for tractability seems to be that the union digraph has a bounded BFSwidth b from s and only beta arcs going from a later BFS layer to an earlier one, which they call the backward-arc hypothesis.

Jane: The paper claims this is essential because without those backward arcs, PAFP stays NP-complete even when the union digraph has just a small BFSwidth of two. That seems pretty restrictive for a problem that usually hits hard complexity walls.

Tom: Exactly, and they show that PAFP remains NP-complete on instances where the union digraph has BFSwidth two, which means we can't just rely on the width being small by itself to solve it efficiently.

Paper summary: Meng: Then they introduce a normal form construction that turns any arbitrary DAG instance into something called an "ultra-thin" ladder starting from a fresh start vertex s'. This construction forces the original vertices to appear at controlled shortest-path distances from s'.

Lu: That normal form is used because it compresses the NP-complete instances into ultra-thin structures where the core behavior of the problem can be encoded in those backward arcs. The number of these backward arcs isn't bounded in this normal form, which is why just bounding BFSwidth alone isn't enough for unrestricted PAFP.

Jane: So they show that even with this new structure, you still need to control those backward arcs for the problem to become tractable. That seems like a necessary condition for the complexity result they are aiming for.

Tom: And then they look at exact-length layers, which is a different angle where things get simpler. They show that if you have exact-length layers with a width of at most two, PAFP becomes polynomial time solvable.

Meng: That's good for practical deployment because it means we can actually run the decision algorithm on graphs that might have exponentially many candidate paths, even with totally arbitrary forbidden pairs.

Lalam: The paper also sets some complexity boundaries, showing that PAFP is NP-complete on DAGs with BFSwidth three and no backward arcs, and it confirms that PAFP is NP-complete even when restricted to instances where the input graph has exact-length width at most three.

Jane: It’s interesting because they show a contrast: for input DAGs with BFSwidth two, tractability is recovered when there are at most k backward input arcs, which contrasts with the union digraph result that bounded BFSwidth alone isn't sufficient.

Tom: That suggests that controlling the flow of forbidden pairs across those layers is a key parameter for tractability in the case of small BFSwidth, specifically two.

Lu: And they prove that this tractability holds even when there are exponentially many candidate paths and completely arbitrary forbidden pairs, which is a big deal for how we think about path problems under constraints.

Paper summary: Meng: On the practical side, they also establish a model checking framework based on the bounded treewidth of the underlying undirected union or constraint graph. They show that this can be decided in time g of k times I O one, where g is some function of k and I is the number of forbidden pairs.

Jane: That means we can use model checking on these constrained structures to decide PAFP on instances with bounded treewidth, which gives us a concrete computational path forward.

Tom: The normalization mapping they introduce also outputs valid PAFP instances where the union digraph has a BFSwidth at most two b plus two beta minus one, and every arc in that specific set lies in the original edge set.

Lu: They prove that this normalization mapping is equisatisfiable, meaning an original instance is a YES-instance if and only if the normalized instance is a YES-instance, which validates that their structural compression actually preserves the answer.

Jane: So they are showing that PAFP's tractability depends on either having bounded BFSwidth with bounded backward arcs or having exact-length width two, and both of those conditions lead to efficient algorithms.

Tom: The authors confirm the tightness of these width bounds by pointing to classical reductions, such as the NP-completeness results on input DAGs of BFSwidth three with no backward input arcs, and the Gabow–Maheshwari–Osterweil reduction for exact-length width three.

Meng: One limitation they point out is that the promise elw of G from s being less than or equal to two is actually stricter than the bfsw, which means we need to be careful about which graph parameter we use when looking for tractability.

Lu: The normal form construction successfully encodes core arcs as backward arcs, and this confirms that structural control over path exploration is what leads to efficient algorithms for PAFP.

Jane: It seems like the main contribution here is showing that the complexity landscape of PAFP is very sensitive to these specific structural constraints imposed on the input graph. This gives us a clearer map for when we can expect polynomial time solutions.

Conclusion: Tom: So we’ve been looking at "Layer-Based Width for PAFP" and now we’re at the end of this paper to wrap things up with Tom and Jane.

Jane: It seems like this whole study is focused on how graph structure, specifically these layers and widths, dictates whether a pathfinding problem like PAFP is solvable quickly.

Tom: Exactly, they’re trying to find those specific structural checkpoints—like bounded BFSwidth or exact-length width—that make the problem tractable.

Jane: What the authors show is that if you have a union digraph with bounded BFSwidth and you control those backward arcs, then PAFP becomes fixed parameter tractable.

Tom: That condition about controlling the backward arcs is what separates a hard problem from one that can be solved efficiently when the graph structure is constrained.

Jane: They also found that for exact-length layers with width two, PAFP becomes polynomial time solvable, and they proved that this holds even if there are exponentially many paths or totally arbitrary forbidden pairs.

Tom: It’s interesting because it shows you don't always need a massive graph to have a hard problem; sometimes the local structure around the start vertex is what matters most.

Jane: The authors confirm these limits by showing where it stays NP-complete, like on graphs with BFSwidth three and no backward arcs, which sets clear boundaries for what’s hard.

Tom: So for someone just listening, this paper means that understanding the geometry of the graph—how layers are stacked—gives you a roadmap to knowing if you can find an efficient solution.

Jane: It’s about finding those right structural properties so we know when we can expect a fast answer and when we have to prepare for something much slower.

Tom: And this leads us into how they use model checking on these constrained graphs, which is the next big thing.

University of California, San Diego

cs.DS, cs.DM

Submitted: 2026-05-12

Updated: 2026-11-10

Comments: This version strengthens the backward arc theorem of the previous version by achieving FPT while bounding the BFS-width and the maximum over all BFS-layer cuts of the minimum of the number of heads crossing the BFS-layer cut and the number of tails crossing the BFS-layer cut, whereas the older theorem bounded the BFS-width with the total number of backward arcs in the union digraph

Journal ref: 37th International Workshop on Combinatorial Algorithms (IWOCA 2026), Lecture Notes in Computer Science, vol. 16587, pp. 311-326, Springer (2026)

DOI: 10.1007/978-3-032-27732-9_22

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: The Path Avoiding Forbidden Pairs problem (PAFP) asks whether there exists an s–t path that contains at most one endpoint from each pair in F and this study investigates layer-based width measures…

Key concepts

Union Digraph Structure
This involves creating a new graph by combining the original graph's structure with the forbidden pairs. Analyzing this union digraph helps determine tractability conditions. Specifically, if the union digraph has a bounded BFS-width and only a limited number of arcs go from later layers to earlier ones, PAFP becomes fixed-parameter tractable.
Exact-Length Width
This parameter measures how well the graph can be decomposed into layers where paths have a controlled length. When the exact-length width is at most 2, PAFP becomes polynomial-time solvable. This result is significant because it guarantees efficiency even when dealing with an exponential number of possible s-t paths.
Backward Arcs Hypothesis
This hypothesis suggests that for tractability based on union digraph structure, the presence of only a few arcs going from later BFS layers back to earlier ones is essential. This condition, combined with bounded BFS-width, is a key requirement for proving that PAFP is fixed-parameter tractable.
Normal Form Construction
This technique transforms any general PAFP instance into a simpler 'ultra-thin' ladder structure starting from a fresh vertex. This construction forces original vertices to appear at specific shortest distances, allowing researchers to control the structure and analyze the complexity more effectively.

Terminology

Summary

The Path Avoiding Forbidden Pairs problem (PAFP) asks whether there exists an s–t path that contains at most one endpoint from each pair in F and this study investigates layer-based width measures to determine tractability conditions for PAFP. p. 0

Tractability via Union Digraph Structure

The paper shows that if the union digraph has BFS-width b from s and only β arcs going from a later BFS layer to an earlier one, then PAFP is FPT parameterized by b + β. The backward-arc hypothesis is essential for this tractability result. p. 0 Furthermore, the union digraph is helpful because inspection of the classical layered reduction shows that PAFP is NP-complete on instances for which the input graph has both BFS-width 3 and no backward arcs. p. 3

Normal Form Construction and Hardness

The study introduces a normal form that turns an arbitrary DAG PAFP instance into an “ultra-thin” ladder from a fresh start vertex s'. This construction forces original vertices to appear at controlled shortest-path distances from s'. The number of such backward arcs is not bounded in the normal form, which explains why bounded BFS-width alone cannot imply tractability for unrestricted PAFP. p. 3

Exact-Length Layers and Polynomial Time Solvability

For exact-length layers, the paper demonstrates that PAFP is polynomial-time solvable when elw(G, s) ≤ 2. This result is tight because a classical reduction yields NP-completeness on DAGs of exact-length width 3. p. 0

Complexity Boundaries and Tightness

The paper establishes several complexity boundaries, including the NP-hardness of PAFP on DAGs with BFS-width 3 and no backward arcs. It also shows that PAFP remains NP-complete when restricted to instances where G is a DAG and bfsw(G, s) ≤ 2. p. 3 The exact-length width 3 result confirms that PAFP is NPcomplete on DAGs G with elw(G, s) ≤ 3. p. 3

Input Graph Width and Tractability

The paper proves that for input BFS-width 2 DAGs, tractability is recovered when there are at most k backward input arcs. This result contrasts with the union-digraph result by showing that bounded BFS-width alone does not suffice for tractability when the forbidden-pair set is unrestricted. p. 3

Exact-Length Width 2 Solvability

The exact-length width 2 result proves that PAFP on DAGs of exact-length width at most 2 is polynomial-time decidable. This tractability holds even for instances with exponentially many candidate paths and completely arbitrary forbidden pairs. p. 0

Model Checking Framework

The tractability result based on bounded treewidth of the underlying undirected union/constraint graph relies on an MSO model-checking problem. The Gaifman graph of this structure is exactly U[RG], and the problem can be decided in time g(k) · I O(1). p. 0 This framework applies to PAFP on IG if it has a safe directed s-t path. p. 2

Output Validity

The normalization mapping Normalize outputs valid PAFP instances. This ensures that G' is a DAG and that the union digraph G' U F' is equal to (V', E'). The level function in the normalized instance shows that bfsw(H, s') ≤ 2 and the path decomposition of U[RG] has width at most 2b + 2β - 1. The final proof shows that every arc in A≺G′ (F′) lies in E' and bfsw(H, s') ≤ 2.

Equisatisfiability of Normalization

The paper proves that the original instance I is a YES-instance if and only if the normalized instance I' is a YES-instance. This involves showing that any safe path in G corresponds to a safe path in I'. The reverse direction shows that every safe s'-t path in H implies the existence of a safe s-t path in G.

Tightness and Reductions

The tightness of the width bounds is demonstrated through classical reductions; for instance, NP-completeness on input DAGs of BFS-width 3 with no backward input arcs. Similarly, the exact-length width 3 result is tight because the same classical reduction yields NP-completeness on DAGs of exact-length width 3. p. 0 The paper also notes that the promise elw(G, s) ≤ 2 is stricter than bfsw(G, s) ≤ 2. p. 4 The tight bound for exact-length width 3 is also shown via the Gabow–Maheshwari–Osterweil reduction. p. 3

Summary of Key Findings

The paper provides structural results linking PAFP tractability to graph parameters like BFS-width and exact-length width, while simultaneously showing that the necessary condition of bounded backward arcs is crucial for tractability when the union digraph's BFS-width is bounded. The introduction of a normal form successfully compresses NP-complete instances into ultra-thin structures with controlled BFS layers, demonstrating that core behavior can be encoded in backward arcs. p. 3 This work establishes that structural control over path exploration, measured by these width parameters, can lead to efficient algorithms for PAFP. p. 2 The paper concludes by showing that the complexity landscape of PAFP is highly sensitive to the specific structural constraints imposed on the input graph and forbidden pairs. p. 1

Tractability Summary

The paper establishes two main avenues for tractability: one based on bounded BFS-width of the union digraph combined with bounded backward arcs, and another based on input graph properties like exact-length width 2. The latter provides a polynomial-time island even for instances with exponentially many s–t paths. p. 4

Hardness Summary

The paper confirms that PAFP remains NP-complete even in ultra-thin regimes, such as DAGs of BFS-width at most 2. Furthermore, it shows that PAFP is hard on DAG instances with BFS-width ≤ 3 and no backward arcs. p. 3 The tightness of these hardness results is confirmed by classical reductions. p. 1

Input Graph Parameterization

The paper highlights that for input DAGs of BFS-width at most 2, tractability is recovered when the number of backward input arcs is bounded by k. This suggests that controlling the flow of forbidden pairs across BFS layers is a key parameter for tractability in this setting. p. 0 The exact-length width 2 result shows that the local structure of paths, rather than just the overall graph width, can yield polynomial time solvability. p. 0

Model Checking Application

The bounded-treewidth framework is used to show that PAFP on instances with bounded treewidth of the underlying undirected union/constraint graph can be decided in time g(k) · I O(1). This framework is equivalent to a fixed monadic second-order formula over a relational structure whose Gaifman graph is U[RG]. p. 1 This demonstrates that PAFP can be solved via model checking on structures derived from the input graph. p. 4

Tightness Summary

The tightness of the width bounds is confirmed by classical reductions, such as those showing NP-completeness on DAGs of BFS-width 3 with no backward input arcs. The exact-length width 3 result is also tight via the Gabow–Maheshwari–Osterweil reduction. p. 3 The promise elw(G, s) ≤ 2 is shown to be stricter than bfsw(G, s) ≤ 2. p. 4 The paper confirms that the normal form construction correctly captures the complexity by encoding core arcs as backward arcs. p. 3

Final Conclusion

The overall finding is that PAFP's tractability is highly dependent on structural properties, specifically requiring either bounded BFS-width of the union digraph with bounded backward arcs, or exact-length width 2 of the input graph. The research provides a comprehensive analysis of how these parameters interact to define the complexity landscape of PAFP. p. 6 p. 6

Reference List

Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. p. 2 Journal of Algorithms 12(2), 308–340 (1991) <ref:2605. p. 012457#pg8>

Bannister, M.J., Devanny, W.E., Dujmović, V., Eppstein, D., Wood, D.R.: Track layouts, layered path decompositions, and leveled planarity. p. 2 Algorithmica 81(4), 1561–1583 (2019) <ref:2605. p. 012457#pg9>

Bezáková, I., Curticapean, R., Dell, H., Fomin, F.V.: Finding Detours is FixedParameter Tractable. p. 1 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 – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2017) <ref:2605. p. 012457#pg10>

Bodlaender, H.L., Jansen, B. p. 1M.P., Kratsch, S. p. 1: Kernel bounds for path and cycle problems. p. 1 Theoretical Computer Science 511, 117–136 (2013)

Dujmović, V., Morin, P., Wood, D.R.: Layered separators in minor-closed graph classes with applications. p. 2 Journal of Combinatorial Theory, Series B 127, 111–147 (2017)

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

Gabow, H.N., Maheshwari, S.N., Osterweil, L.J.: On two problems in the generation of program test paths. p. 1 IEEE Transactions on Software Engineering 2(3), 227–231 (1976)

Kolman, P., Pangrác, O. p. 4: On the complexity of paths avoiding forbidden pairs. p. 0 Discrete Applied Mathematics 157(13), 2871–2876 (2009)

Kováč, J.: Complexity of the path avoiding forbidden pairs problem revisited. p. 0 Discrete Applied Mathematics 161(10–11), 1506–1512 (2013)

Kováč, J., Vinař, T., Brejová, B.: Predicting gene structures from multiple RT-PCR tests. p. 1 In: Algorithms in Bioinformatics (WABI 2009). p. 1 Lecture Notes in Computer Science, vol. 5724, pp. 181–193 Springer (2009)

Yinnone, H.: On paths avoiding forbidden pairs of vertices in a graph. p. 1 Discrete Applied Mathematics 74(1), 85–92 (1997)

The overall finding is that PAFP's tractability is highly dependent on structural properties, specifically requiring either bounded BFS-width of the union digraph with bounded backward arcs or exact-length width 2 of the input graph. The research provides a comprehensive analysis of how these parameters interact to define the complexity landscape of PAFP.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. The system can solve Path Avoiding Forbidden Pairs (PAFP) instances in fixed-parameter tractable time parameterized by a combination of BFS-width of the union digraph and backward arcs between BFS layers, specifically in time f(b + beta) I O(1).

  2. The system can decide PAFP on input DAGs with BFS-width at most 2 and a bounded number of backward input arcs in time 2k I O(1), where k is the number of s-backward input arcs.

  3. The system can solve PAFP instances on DAGs where the exact-length width from s is at most 2 in deterministic polynomial time by reducing it to a 2-sat problem, yielding a running time of O(nm + n squared + fn3).

  4. The system can handle unrestricted forbidden pairs and exponentially many s-t paths in the input graph while maintaining tractability if the input graph is a DAG of BFS-width 2 with at most k backward arcs, or if the union digraph has bounded BFS-width and bounded backward arcs.

  5. The system can be used to construct an equivalent PAFP instance with a union digraph having BFS-width at most 2 from any arbitrary DAG PAFP instance using the Normalize mapping, which is polynomial-time computable.

Sources

Related papers