Pith. Sign in

REVIEW

On the Parameterized Complexity of Capacitated Stack and Queue Layouts with Colored Edges

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Thomas Depian, Giuseppe Liotta, Fabrizio Montecchiani, Martin Nöllenburg

Data Structures and Algorithms · Submitted 13 Oct 2026 · 17 references

Pith's verdict: Solid complexity classification for a new variant of linear layouts; deserves a serious referee.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 14, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 5 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv ID2610.18071 (version 1)
Pith IDGXUDSVP4, Pith's permanent record of this paper and its review
CitationFabrizio Montecchiani, Giuseppe Liotta, Martin N\"ollenburg, Thomas Depian. "On the Parameterized Complexity of Capacitated Stack and Queue Layouts with Colored Edges." arXiv:2610.18071 (2026). https://pith.science/paper/GXUDSVP4
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Adding per-color page budgets makes fixed-order stack and queue layouts NP-complete, even when conflict graphs are tiny.

The reading

The paper introduces a generalized model of stack and queue layouts where edges have colors and each page has a per-color budget limiting how many edges of that color it can hold. Even when the vertex order along the spine is fixed—a setting where ordinary (uncolored, uncapacitated) layouts can be found in polynomial time—the capacitated versions become NP-complete for two pages. The authors prove this for both stack and queue layouts, and for queue layouts the hardness persists even when all edges share a single color. They then map out the parameterized complexity landscape with respect to the number of pages, colors, and the structure of the edge-conflict graph, identifying fixed-parameter tractable cases and W[1]-hardness boundaries.

What carries the argument

The edge conflict graph, which captures crossing (stack) or nesting (queue) relations between edges under the fixed vertex order, together with the novel per-color page budgets. For the FPT results, the paper partitions connected components of the conflict graph into equivalence classes based on edge colors and then solves an integer linear program with a bounded number of variables; for the hardness results, it reduces from Monotone Not All Equal 3SAT-E4 (for small components) and from Bin Packing (for monochromatic queue layouts).

Extended reading notes

Core claim

The central finding is that imposing per-color page budgets on already fixed-spine-order stack and queue layouts jumps the decision problem from polynomial time to NP-complete, sharply separating the capacitated from the ordinary case unless P=NP. Specifically, Fixed Order Capacitated 2-Page Stack Layout and Fixed Order Capacitated 2-Page Queue Layout are NP-complete even when every connected component of the conflict graph has at most five vertices and the instance is balanced and tight. For queue layouts, the problem remains NP-complete for monochromatic (single-color) instances with any number of pages, implying W[1]-hardness parameterized by the number of pages. The paper also provides matching fixed-parameter tractable algorithms for combinations of parameters such as number of pages, number of colors, and component size.

Load-bearing premise

The vertex order along the spine is fixed and given as part of the input; if the vertex order could be chosen freely, the problems would already be paraNP-hard from known results, and the fixed-order setting is the only regime where the capacitated version can be meaningfully distinguished from the uncapacitated one.

Editorial extensions

If this is right

  • Fair-allocation constraints (per-color page budgets) turn a polynomial-time layout problem into an NP-complete one, so practical algorithms for capacitated layouts must rely on parameterized or heuristic approaches rather than exact polynomial-time methods.
  • The NP-completeness for two-page stacks with tiny conflict components means that even very local coloring constraints can force global hardness.
  • The monochromatic queue-layout hardness shows that the difficulty does not require multiple colors; capacity alone on a single color can be enough.
  • The FPT algorithms for (ℓ, χ, γ) give a concrete route to solving instances where the conflict graph has small components and few colors, even if numbers of edges or vertices are large.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The results suggest that any variant of linear layouts with per-page color constraints is likely NP-hard in the fixed-order setting, unless the constraint structure is extremely simple (e.g., constant number of colors and constant component size).
  • The monochromatic queue-layout hardness reduces from Bin Packing; that connection may allow transfer of approximation and fixed-parameter results from bin packing to queue layouts with per-page capacities.
  • The ILP-based FPT algorithm could be implementable in practice for conflict graphs with component size up to about 10–20 and a handful of colors, using modern integer programming solvers.
  • The paper leaves open the complexity of capacitated queue layouts parameterized by both number of colors and component size (without also bounding number of pages), which would be the next natural target for FPT-or-XP classification.
Original abstract

Stack and queue layouts are two extensively studied and complementary linear representations of graphs. A stack (queue) layout $\langle \prec, \sigma \rangle$ of a graph $G$ consists of a total ordering $\prec$ of its vertices and of a partitioning $\sigma$ of its edges into pages, such that no two independent edges on the same page cross (nest). We propose a generalized model with colored edges (one color per edge) and capacitated pages. Namely, the input graph is equipped with colored edges and a prescribed budget for each page-color pair $(p,c)$ - this budget determines the maximum number of edges of color $c$ that page $p$ can accept. This model is motivated by fair allocation scenarios where budgets can be used to control the share of monochromatic edges on each page. Unfortunately, it is known that deciding whether a stack (queue) layout exists is NP-hard already with two (one) pages. Thus, we focus on the fixed-order setting - where the linear order $\prec$ is part of the input - for which an ordinary 2-page stack or $\ell$-page queue layout can be computed in polynomial time. Despite the restrictive setting, we show that both capacitated problems are NP-complete already for two pages. Furthermore, we study the complexity of the problems when parameterized by the number of pages, colors, and/or the structure of the edge conflict graph with respect to the fixed linear order $\prec$. Our analysis paints a detailed complexity landscape and uncovers a surprisingly intricate interplay between the considered parameters.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-14: 1 request, 7,655 input tokens.

What the abstract itself states, as probabilities: claims first 0.07 · states limitation 0.73 · human participants 0.02 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.72 · compares with prior results 0.79 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

Stack and queue layouts are two extensively studied and complementary linear representations of graphs. A stack (queue) layout $\langle \prec, \sigma \rangle$ of a graph $G$ consists of a total ordering $\prec$ of its vertices and of a partitioning $\sigma$ of its edges into pages, such that no two independent edges on the same page cross (nest). We propose a generalized model with colored edges (one color per edge) and capacitated pages. Namely, the input graph is equipped with colored edges and a prescribed budget for each page-color pair $(p,c)$ - this budget determines the maximum number of edges of color $c$ that page $p$ can accept. This model is motivated by fair allocation scenarios where budgets can be used to control the share of monochromatic edges on each page. Unfortunately, it is known that deciding whether a stack (queue) layout exists is NP-hard already with two (one) pages. Thus, we focus on the fixed-order setting - where the linear order $\prec$ is part of the input - for which an ordinary 2-page stack or $\ell$-page queue layout can be computed in polynomial time. Despite the restrictive setting, we show that both capacitated problems are NP-complete already for two pages. Furthermore, we study the complexity of the problems when parameterized by the number of pages, colors, and/or the structure of the edge conflict graph with respect to the fixed linear order $\prec$. Our analysis paints a detailed complexity landscape and uncovers a surprisingly intricate interplay between the considered parameters.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 Stack and queue layouts are two extensively studied and complementary linear representations of graphs. background 1.00 0.04 0.02 asserted 1.00
s1 A stack (queue) layout $\langle \prec, \sigma \rangle$ of a graph $G$ consists of a total ordering $\prec$ of its vertices and of a partitioning $\sigma$ of its edges into pages, such that no two independent edges on the same page cross (nest). background 1.00 0.05 0.02 asserted 1.00
s2 We propose a generalized model with colored edges (one color per edge) and capacitated pages. contribution 0.88 0.91 0.04 asserted 0.99
s3 Namely, the input graph is equipped with colored edges and a prescribed budget for each page-color pair $(p,c)$ - this budget determines the maximum number of edges of color $c$ that page $p$ can accept. method 0.72 0.52 0.04 asserted 1.00
s4 This model is motivated by fair allocation scenarios where budgets can be used to control the share of monochromatic edges on each page. interpretation 0.36 0.24 0.03 asserted 0.85
s5 Unfortunately, it is known that deciding whether a stack (queue) layout exists is NP-hard already with two (one) pages. background 0.98 0.04 0.04 asserted 1.00
s6 Thus, we focus on the fixed-order setting - where the linear order $\prec$ is part of the input - for which an ordinary 2-page stack or $\ell$-page queue layout can be computed in polynomial time. background 0.52 0.09 0.05 asserted 1.00
s7 Despite the restrictive setting, we show that both capacitated problems are NP-complete already for two pages. result 0.99 0.95 0.53 asserted 1.00
s8 Furthermore, we study the complexity of the problems when parameterized by the number of pages, colors, and/or the structure of the edge conflict graph with respect to the fixed linear order $\prec$. contribution 0.96 0.88 0.06 asserted 0.87
s9 Our analysis paints a detailed complexity landscape and uncovers a surprisingly intricate interplay between the considered parameters. interpretation 0.67 0.92 0.17 asserted 0.98

What kind of paper the classifier reports this is: theoretical result 0.99 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 2. Parameterized complexity of (a) FoCap2PSl (Section 3) and (b) FoCapQl (Section 4) when parameterized by the number of pages ℓ, the number of colors χ, the number of connected components λ in the conflict graph, and/or their maximum size γ. The result for FoCapQl marked with ∗ applies only if ℓ = 2. Moreover, note that ℓ = 2 holds for every instance of FoCap2PSl and, therefore, we omit the parameter in (a). ≺ a d e (c)c a b c e (a) (b) ab ac cd de bc bd be ce d b
Figure 4. Gadgets representing (a) the variable x in its true state and (b) the clause c = (x∨y∨z) where x and z are set to true and y to false in the reduction for Theorem 4. Each of the remaining four edges is part of a clause gadget for a clause c ∈ C with x ∈ c; recall that x appears in exactly four clauses. The variable gadget enforces four of eight edges to be on the same page. We can set the budget for col(x) such that the four remaining edges must be on the same page independent of their location along the spine. This allows us to transport the variable assignment from the variable…
Figure 6. The vector gadget which features the number gadgets for 3, 1, and 5, respectively. pages, we can use an additional edge in color d + 1 to force all of these edges to be placed on the same page. Placing them on the first page represents membership in the solution set S ′ ⊆ S and by appropriately setting the budget for both pages, we can ensure equivalence between the solutions to both problems. Number Gadget. The number gadget for an integer x ∈ N, x ≥ 1, consists of the vertices ux and v i x , i ∈ [x], arranged in the order ux ≺ v 1 x ≺ . . . ≺ v x x . We connect ux with every v i x…
Figure 7. An instance of FoCap2PSl constructed for the instance (S = {s1, s2, s3, s4},t = (2, 2, 2)) of Multidimensional Subset Sum. The layout depicts the solution S ′ = {s1, s3}
Figure 8. Gadgets representing (a) the variable x in its true state and (b) the clause c = (x∨y∨z) where x and z are set to true and y to false in the reduction for Theorem 19. 4 Fixed Order Queue Layouts In this section, we investigate queue layouts with fixed spine order ≺. It is well-known that an ℓ-page queue layout with spine order ≺ exists if and only if ≺ does not induce an (ℓ + 1)-rainbow, i.e., a set of ℓ + 1 pairwise nesting edges [29]. Heath and Rosenberg [29] provided an efficient algorithm to construct such a queue layout (if it exists). However, in their algorithm they employ a…
Figure 9. The item gadget for an item x ∈ S and with k = 4. Although the constructed instance is monochromatic, we color edges from the rainbow and the item purple and blue, respectively. ≺ ≺ ≺ p1 p2 p3 x1 x2 x3 x4 x5
Figure 10. The constructed instance of FoCapQl for an instance ({x1, x2, x3, x4, x5}, w, 3, 4) of Bin Packing with w(x1) = 3, w(x2) = w(x3) = 2, w(x4) = 1, and w(x5) = 4. For illustration purposes, we color rainbow and item edges purple and blue, respectively. Each bold edge represents k · η = 15 edges. Gray bands indicate the different items and pages are stacked vertically. closure of this and the above-defined relations; see the blue edges in
Figure 11. Visualization of Lemma 27. Observe that only the edges uv and x1y1 are nesting. The edges uv and uy1 are not nesting although y1 ≺ v. Note that y1 ≺ v implies uy1 < uv. ▶ Lemma 27. Let uv, xy ∈ E be two edges such that u ≺ v, x ≺ y and uv < xy. The edges uv and xy are nesting if and only if y ≺ v. Proof. Let uv, xy ∈ E be two edges as in the statement. (⇒) Assume that the two edges are nesting, which means that we have u ≺ x ≺ y ≺ v or x ≺ u ≺ v ≺ y. Only the former is possible by uv < xy, which completes this direction. (⇐) Assume that we have y ≺ v. From uv < xy we get that u ⪯ x…

Showing 8 of the paper's 11 figures. See all figures in the PDF ↗ Figures reproduced from arXiv:2610.18071 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.