ABSTRACT. Bounded integer compositions are fundamental combinatorial objects employed in cryptography, yet lacking a unified theoretical treatment and efficient implementations for combinatorial (un)ranking. We propose generic algorithms that allow us to describe proposals found in the literature as specific parameter sets. Consequently, we are able to provide a single proof of correctness that applies simultaneously to all derived algorithms; characterize a number of ad-hoc optimizations with respect to our generic framework; and discuss the storage complexity of pre-computed combinatorial count tables. Furthermore, drawing on Gaussian limit laws from analytic combinatorics, we propose performance and storage optimizations for the particular case of uniform random inputs to (un)ranking algorithms, a common setting in cryptographic applications. To validate our results, we give portable low-level implementations ready for use by algorithm designers, filling a practical gap in the literature.

ABSTRACT. Mixed-radix words can be generated in worst-case O(1)-time per word. The most well-known of these loopless algorithms use reflected Gray code order where a single digit changes by ±1, or modular Gray code order where the changes are +1 modulo the base of the digit. Both orders have simple greedy descriptions that modify the rightmost possible digit, and they have the same change sequence as lexicographic order. For example, 000, 001, 002, 010, 011, 012 is the lexicographic order for words with bases 1, 2, 3. Its change sequence (i.e., number of digits that change) is 1, 1, 2, 1, 1 so this is the sequence of indices that change by ±1 in the reflected Gray code 000, 001, 002, 012, 011, 010 or cyclically by +1 in the modular Gray code 000, 001, 002, 012, 010, 011.

We generalize the algorithms by allowing them to start at any rank (i.e., any position in their respective orders). This is done by unranking their full internal state including the current word and associated data structures (e.g., focus pointers). This allows the loopless algorithms to be run in parallel across any number of processors.

We also consider the mixed-radix words that are greater than or equal to a given word w in lexicographic order. We show that these words can be generated greedily by a simple generalization of the modular Gray code: start from w then repeatedly increment (cyclically) the rightmost digit that creates a new word greater than w. For example, given w = 220 and bases 4, 3, 2 the Gray code is 220, 221, 321, 320, 300, 301, 311, 310. Furthermore, we translate this simple greedy description into a loopless algorithm that can also be parallelized.

ABSTRACT. A hypergraph $H$ is said to be \emph{linear} if every pair of vertices lies in at most one hyperedge. Given a family $\mathcal{F}$ of $r$-uniform hypergraphs, an $r$-uniform hypergraph $H$ is said to be \emph{$\mathcal{F}$-free} if it contains no member of $\mathcal{F}$ as a subhypergraph. The \emph{linear Tur\'{a}n number} $ex_r^{\mathrm{lin}}(n,\mathcal{F})$ denotes the maximum number of hyperedges in an $\mathcal{F}$-free linear $r$-uniform hypergraph on $n$ vertices.

Gy\'arf\'as, Ruszink\'o, and S\'ark\"ozy~[\emph{Linear Tur\'an numbers of acyclic triple systems}, European J.\ Combin.\ (2022)] initiated the study of bounds on the linear Tur\'an number for acyclic $3$-uniform linear hypergraphs.

In this paper, we extend the study of linear Tur\'{a}n number for acyclic systems to higher uniformity. We first give a construction for linear $r$-uniform tree with $k$ edges that yields the lower bound $ ex_r^{\mathrm{lin}}(n,T_k^r)\ge {n(k-1)}/{r}, $ under mild divisibility and existence assumptions. Next, we study hypertrees with four edges. We prove the exact bound $ ex_r^{\mathrm{lin}}(n,B_4^r)\le {(r+1)n}/{r} $ and characterize the extremal hypergraph class, where $B_4^r$ is formed from $S_3^r$ by appending a hyperedge incident to a degree-one vertex. We also prove the bound $ ex_r^{\mathrm{lin}}(n,E_4^r)\le {(2r-1)n}/{r} $ for the crown $E_4^r$. Finally, we give a construction showing $ ex_r^{\mathrm{lin}}(n,P_4^r)\ge {(r+1)n}/{r} $ under suitable assumptions and conclude with a conjecture on sharp upper bound for $P_4^r$.

ABSTRACT. A linkage L consists of a graph G=(V,E) and an edge-length function l. Deciding whether L can be realized as a planar straight-line embedding in R^2 with edge length l(e) for all e in E is ETR-complete [Abel et al., JoCG'25], even if l ≡ 1, but a considerable part of L is rigid. In this paper, we study the computational complexity of the realization question for structurally simpler, less rigid linkages inside an open polygonal domain P, where the placement of some vertices may be specified in the input. We show XP-membership and W[1]-hardness with respect to the size of G, even if l ≡ 1 and no vertex positions are prescribed. Furthermore, we consider the case where G is a path with prescribed start and end position and l ≡ 1. Despite the absence of any rigid components, we obtain NP-hardness in general, and provide a linear-time algorithm for arbitrary l if G has only three edges and P is convex.

ABSTRACT. For illustration, suppose we have to compute a shortest path in a graph between two vertices, but the edge weights are uncertain. All we know is that the weight $w_e$ of every edge $e$ belongs to some interval $[\ell_e, h_e]$. In this setting, for every fixed edge $e$, we can define two thresholds $T_e^+, T_e^-$ such that $e$ belongs to every shortest path if $w_e < T_e^+$ and to none if $w_e > T_e^-$. We study the problem of computing these thresholds, for various set selection problems. In particular we show that the problem is easy for the minimum spanning tree problem and the maximum weight matching problem on trees. In contrast we show that the problem is NP-hard for the shortest path problem and for the minimum cost perfect matching problem.

ABSTRACT. A spanner of a temporal graph is a subset of arcs that allows a given set of source vertices to reach every vertex. A spanner is minimal if no arc can be removed without destroying this reachability. Our focus is on enumerating all minimal spanners of a given directed temporal graph. We study several variants of this problem, depending on the choice of sources: ONE2ALL, where a single vertex must reach all others; MANY2ALL, where a constant number of vertices must reach all others; and ALL2ALL, where every vertex must reach every other vertex. We focus on directed temporal graphs and analyze how the complexity of these enumeration problems depends on both the number of sources and the temporality of the input graph, that is, the number of labels per arc. For the case of two sources and temporality one, we present a reverse search algorithm that efficiently enumerates all minimal spanners. In contrast, we show that increasing the number of sources and the temporality makes the enumeration problem harder than enumerating hypergraph transversals. Moreover, we prove that even for temporality one, the ALL2ALL variant admits no output-sensitive unless \P=\NP.

ABSTRACT. Computing paths in graph structures is a fundamental operation in a wide range of applications, from transportation networks to data analysis. The beer path problem, which captures the option of visiting points of interest, such as gas stations or convenience stores, prior to reaching the final destination, has been recently introduced and extensively studied in static graphs. However, existing approaches do not account for temporal information (for example, transit service schedules), which is often crucial in real-world scenarios. In this work, we introduce the notion of beer paths in temporal graphs, where edges are time-dependent and beer vertices are active only at specific times. We formally define the problems of computing earliest-arrival, latest-departure, fastest, and shortest temporal beer paths and propose efficient algorithms for all of them under both edge stream and adjacency list representations. We show that the time complexity of each of our algorithms is aligned with that of the corresponding standard temporal pathfinding algorithm, thus preserving efficiency. We also present preprocessing techniques that enable efficient query answering under dynamic conditions, for example new openings or closings of shops. We achieve this either through appropriate precomputation of selected paths or by transforming a temporal graph into an equivalent static graph.

ABSTRACT. Inversion of a directed graph D with respect to a vertex subset X is the directed graph obtained from D by reversing the direction of every arc whose both endpoints lie in X. More generally, the inversion of D with respect to a tuple (X1, X2, . . . , Xℓ) of vertex subsets is defined as the directed graph obtained by successively applying inversions with respect to X1, X2, . . . , Xℓ. Such a tuple is called a decycling family of D if the resulting graph is acyclic.

In the k-Inversion problem, the input consists of a directed graph D and an integer k, and the task is to decide whether D admits a decycling family of size at most k. Alon et al. (SIAM J. Discrete Math., 2024) proved that the problem is NP-complete for every fixed value of k, thereby ruling out XP algorithms, and presented a fixed-parameter tractable (FPT) algorithm parameterized by k for tournament inputs.

In this paper, we generalize their algorithm to a broader variant of the problem on tournaments and subsequently use this result to obtain an FPT algorithm for k-Inversion when the underlying undirected graph of the input is a block graph. Furthermore, we obtain an algorithm for k-Inversion running in time 2^O(k\cdot tw) · n^O(1), where tw denotes the treewidth of the underlying graph.

ABSTRACT. In an oriented graph $\vec{G}$, the {\it inversion} of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endvertices in $X$. The {\it $(\leq p)$-inversion graph} of a labelled graph $G$, denoted by ${\mathcal{I}}^{\leq p}(G)$, is the graph whose vertices are the labelled orientations of $G$ in which two labelled orientations $\vec{G}_1$ and $\vec{G}_2$ of $G$ are adjacent if and only if there is a set $X$ with $|X|\leq p$ whose inversion transforms $\vec{G}_1$ into $\vec{G}_2$. In this paper, we study the {\it $(\leq p)$-inversion diameter} of a graph, denoted by $\id^{\leq p}(G)$, which is the diameter of its $(\leq p)$-inversion graph. We show that there exists a smallest number $\Psi_p$ with $\frac{1}{4}p - \frac{3}{2} \leq \Psi_p \leq \frac{1}{2}p^2$ such that $\id^{\leq p}(G) \leq \left\lceil\frac{|E(G)|}{\lfloor p/2\rfloor}\right \rceil + \Psi_p$ for all graph $G$. We then establish better upper bounds for several families of graphs and in particular trees and planar graphs. Let us denote by $\id^{\leq p}_{\cal T}(n)$ (resp. $\id^{\leq p}_{\cal P}(n)$) the maximum $(\leq p)$-inversion diameter of a tree (resp. planar graph) of order $n$. For trees, we show $\id^{\leq 3}_{\cal T}(n) = \left\lceil \frac{n-1}{2}\right\rceil$, $\id^{\leq 4}_{\cal T}(n)=\frac{3}{8}n + \Theta(1)$, $\id^{\leq 5}_{\cal T}(n)= \frac{2}{7}n + \Theta(1)$, and $\id^{\leq p}_{\cal T}(n) \leq \frac{n-1}{p- c\sqrt{p}} + 2$ with $c = \sqrt{2 + \sqrt{2}}$ for all $p\geq 6$. For planar graphs, we prove $\id^{\leq 3}_{\cal P}(n) \leq \frac{11n}{6} - \frac{8}{3}$, $\id^{\leq 4}_{\cal P}(n) \leq \frac{4n}{3} + \frac{10}{3}$, and $\id^{\leq p}_{\cal P}(n) \leq \left\lceil\frac{3n-6}{\lfloor p/2\rfloor}\right \rceil + 8\lfloor p/2\rfloor - 8$ for all $p\geq 6$.

ABSTRACT. We investigate the problem of reversing colors in bicolored graphs using the operation of local inversion. A bicoloration of a graph G=(V,E) assigns each vertex a color from the set {-1,1}. A local inversion at a vertex v reverses the colors of all neighbors of v and complements the subgraph induced by these neighbors, while leaving v and all other vertices unchanged. This operation was introduced by Sabidussi~(Discrete Mathematics, 1987), who proved that any bicolored graph on n vertices without isolated vertices can be color-reversed using at most 6n+3 local inversions. He further showed that any bicolored graph can be transformed into any other bicolored graph on the same underlying graph using at most 9n local inversions. More recently, Porte et~al.\ (CALDAM 2026) improved these bounds to 4n-3 for color reversal and to floor of(11n-3)/2] for transforming one bicolored graph into another. In this paper, we further improve these results by showing that any bicolored graph on n vertices without isolated vertices can be color-reversed using at most 3n local inversions, and that this bound is tight for complete graphs on at least three vertices. Moreover, we show that any bicolored graph can be transformed into another bicolored graph on the same underlying graph using at most 5n-3 local inversions.

ABSTRACT. In this paper, we study the parameterized complexity of several variants of scheduling with precedence constraints between jobs. Namely, we consider the single machine setting with minimum, maximum or exact delay values on top of the precedence constraints. Such scheduling problems are related to several decades-old problems with open parameterized complexity status, notably Shuffle Product and Directed Bandwidth. We obtain XNLP-completeness results for both problems, and derive implications to scheduling with minimum (resp. maximum) delays parameterized by the width of the directed acyclic graph giving the precedence constraints, and/or by the maximum delay value in the input. Regarding Directed Bandwidth, we also settle the case of trees by showing XNLP-completeness parameterized by the target value. On top of giving an answer to several open questions in the literature, each of independent interest, these results highlight the relevancy of both scheduling and class XNLP in studying the parameterized complexity of computer science problems. In particular, Shuffle Product is an unusual and promising addition to the list of XNLP-complete problems.

ABSTRACT. Clique coloring of a graph is a relaxation of proper vertex coloring that requires every maximal clique to contain at least two distinct colors. In this paper, we introduce and study an optimization variant called \textsc{Minimum Clique Bicoloring}, which restricts the available colors to white and black and asks to minimize the number of black-colored vertices, and can be viewed as a coloring-type counterpart of the classical minimum clique transversal problem. We show that \MCBC is \SigmaTwoP-hard even on weakly chordal graphs, and \NP-complete on cubic planar graphs and on $k$-sun-free chordal graphs for every fixed $k \ge 4$. On split graphs, we further relate \MCBC to the minimum clique transversal problem by showing that any polynomial-time algorithm for the latter yields one for \MCBC. Regarding parameterized complexity, we also show that the problem is \WTwo-hard when parameterized by the number of black vertices $k$, but fixed-parameter tractable (\FPT) with respect to clique-width. Furthermore, we present a polynomial-time algorithm for \MCBC on totally unimodular graphs, and, as consequences of our structural and parameterized results, we obtain polynomial-time solvability on several further well-studied graph classes. Finally, we give an exact exponential algorithm running in $O^*(2^{n})$ time, which improves on a straightforward $O^*((2 \cdot 3^{1/3})^{n})$ approach based on maximal-clique enumeration, where $n$ is the number of vertices. These results nearly pinpoint the boundary between polynomial-time solvability and intractability of \MCBC on standard graph classes; the remaining main gap concerns strongly chordal graphs.