arXiv preprint ·
On the Parameterized Complexity of Capacitated Stack and Queue Layouts with Colored Edges
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Stack and queue layouts are two extensively studied and complementary linear representations of graphs. A stack (queue) layout $\langle \prec, σ\rangle$ of a graph $G$ consists of a total ordering $\prec$ of its vertices and of a partitioning $σ$ 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 authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Geometric Kernel Diversity: An Axiomatic Diversity Measure in Euclidean Space
Ellipsoids from Tangents
FPTAS for Polygonal Multi-Robot Motion Planning
The Geometry of Hierarchical Navigation: Accuracy and Query Cost for Point Process Input
Geometric Hashing in MPC with Applications to Clustering and Stochastic Embeddings
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.