We show that connected graphs admit sublinear longest path transversals. This improves an earlier result of Rautenbach and Sereni and is related to the fifty-year-old question of whether connected graphs admit longest path transversals of constant size. The same technique allows us to show that 2-connected graphs admit sublinear longest cycle transversals.

First-Fit is a greedy algorithm for partitioning the elements of a poset into chains. Let $\mathrm{FF}(w,Q)$ be the maximum number of chains that First-Fit uses on a $Q$-free poset of width $w$. A result due to Bosek, Krawczyk, and Matecki states that $\mathrm{FF}(w,Q)$ is finite when $Q$ has width at most $2$. We describe a family of posets $\mathcal{Q}$ and show that the following dichotomy holds: if $Q\in\mathcal{Q}$, then $\mathrm{FF}(w,Q) \le 2^{c(\log w)^2}$ for some constant $c$ depending only on $Q$, and if $Q\not\in\mathcal{Q}$, then $\mathrm{FF}(w,Q) \ge 2^w - 1$.

In a graph G whose vertices contain pebbles, a pebbling move $uv$ removes two pebbles from u and adds one pebble to a neighbor v of u. The optimal pebbling number ${\widehat{\pi}}(G)$ is the minimum k such that there exists a distribution of k pebbles to G so that for any target vertex r in G, there is a sequence of pebbling moves which places a pebble on r. The pebbling number $\pi(G)$ is the minimum k such that for all distributions of k pebbles to G and for any target vertex r, there is a sequence of pebbling moves which places a pebble on r. We explore the computational complexity of computing ${\widehat{\pi}}(G)$ and $\pi(G)$. In particular, we show that deciding whether ${\widehat{\pi}}(G)\leq k$ is NP‐complete. Furthermore, we prove that deciding whether $\pi(G)\leq k$ is ${\Pi_2^{\mathrm{P}}}$‐complete and therefore both NP‐hard and coNP‐hard. Additionally, we provide a characterization of when an unordered set of pebbling moves can be ordered to form a valid sequence of pebbling moves.