Minimizing the weighted completion times ($P \mid \mid Σw_j C_j$) and weighted number of tardy jobs ($P \mid \mid Σw_j U_j$) on multiple identical machines are two classical NP-hard scheduling problems. As shown by Lenté et al. (2014), both problems can be solved in time ${O}^{\star}(3^n)$. In this paper, we improve these bounds to ${O}(2.755^n)$ and ${O}^{\star}(2^n)$, respectively. Our algorithm for $P \mid \mid Σw_j C_j$ exploits the meet-in-the-middle paradigm and an efficient data structure answering linear programming queries. Additionally, when the number of machines is at most $6$, we show that the running time for $P \mid \mid Σw_j C_j$ can further be improved. Both scheduling problems are generalizations of the classical Bin Packing problem, which can be solved in ${O}^{\star}(2^n)$ time. Improving this running time is an important open question. We show that, when assuming the Asymptotic Rank Conjecture (ARC), Bin Packing can be solved in time ${O}((2-\varepsilon)^n)$ for some $\varepsilon >0$. Our algorithm makes use of two main ingredients: the recent ${O}((2-\varepsilon)^n)$-time algorithm of Nederlof et al. [SICOMP'23] for Bin Packing when the number of bins is a fixed constant, and the ${O}((2-\varepsilon)^n)$-time algorithm of Björklund et al. [SODA'25] for special instances of the $3$-way Partitioning problem when assuming ARC.

For a constant $η\geq 0$, Pathwidth-$η$ Deletion is the problem of deciding whether, for a given graph $G$ and integer $k$, there is a set $S \subseteq V(G)$ of size at most $k$ such that the pathwidth of $G - S$ is at most $η$. The problems Treewidth-$η$ Deletion and Treedepth-$η$ Deletion are defined similarly for the parameters treewidth and treedepth, respectively. A landmark result of Fomin et al. [FOCS, 2012] shows that, for any constant $η$, all three problems admit a kernel on $O(k^{c(η)})$ vertices, where $c(η)$ is a constant depending on $η$. Giannopoulou et al. [ACM TALG, 2017] show that, in some sense, this result is optimal for Treewidth-$η$ Deletion: for $η\geq 2$ and even when parameterizing by the size of a vertex cover $M$ of the input graph, there is no kernel of size $O(|M|^{\frac{η+1}{2}-\varepsilon})$, for any $\varepsilon > 0$. Contrasting this result, they prove that Treedepth-$η$ Deletion admits a uniform polynomial kernel, that is, a kernel of size $O(k^c)$ for a constant $c$ that is independent of $η$. In comparison, the question whether Pathwidth-$η$ Deletion admits a uniform polynomial kernel has been neglected in the literature. As treewidth and pathwidth tend to behave similarly, it is natural to expect that no uniform kernel exists when parameterizing by the size of a vertex cover. Surprisingly, we show this not to be the case. More concretely, we prove the existence of a uniform polynomial kernel for Pathwidth-$η$ Deletion when parameterizing by (1) the solution size $k$ plus the size of a set $M$ such that $G - M$ has bounded treedepth; (2) the (vertex-deletion) distance to pathwidth-$1$ graphs; (3) the distance to the class of graphs with treedepth at most $η+ 1$. This leads us to conjecture that Pathwidth-$η$ Deletion admits a uniform kernel when parameterizing by the solution size $k$.

In the content-oblivious model, communication is limited to sending content-less pulses over asynchronous channels. Despite this extreme restriction, Censor-Hillel et al. (Dist. Comp., 2023) showed that any computation can be simulated on 2-edge-connected graphs, assuming a designated leader. Subsequent work investigated the necessity of this assumption. Frei et al. (DISC 2024, Dist. Comp. 2026) and Chalopin et al. (DISC 2025) designed content-oblivious leader-election algorithms for rings, thereby eliminating the need for an initial leader. Non-uniform leader election is possible on 2-edge-connected graphs (Chalopin et al., DISC 2025).

In content-oblivious computation, n nodes wish to compute a given task over an asynchronous network that suffers from an extremely harsh type of noise, which corrupts the content of all messages across all channels. In a recent work, Censor-Hillel, Cohen, Gelles, and Sela (Distributed Computing, 2023) showed how to perform arbitrary computations in a content-oblivious way in 2-edge connected networks but only if the network has a distinguished node (called root) to initiate the computation. Our goal is to remove this assumption, which was conjectured to be necessary. Achieving this goal essentially reduces to performing a content-oblivious leader election since an elected leader can then serve as the root required to perform arbitrary content-oblivious computations. We focus on ring networks, which are the simplest 2-edge connected graphs. On oriented rings, we obtain a leader election algorithm with message complexity $$O(n \cdot \textsf{ID}_{\max })$$ , where $$\textsf{ID}_{\max }$$ is the maximal assigned ID. As it turns out, this dependency on $$\textsf{ID}_{\max }$$ is inherent: we show a lower bound of $$\Omega (n \log {\textsf{ID}_{\max }})$$ messages for content-oblivious leader election algorithms. We also extend our results to non-oriented rings. Here, however, the algorithm does not terminate but only quiescently stabilizes: all nodes eventually settle on an internal decision and stop receiving messages. Preliminary versions of parts of this research have appeared at the conferences PODC 2024 as a brief announcement and at DISC 2024 as a full paper.

Abstract. A well-studied continuous model of graphs, introduced by Dearing and Francis [Transportation Science, 1974], considers each edge as a continuous unit-length interval of points. In the problem [Formula: see text]-Tour defined within this model, the objective is to find a shortest tour that comes within a distance of [Formula: see text] of every point on every edge. This problem was introduced in the predecessor to this article and shown to be essentially equivalent to the Chinese Postman problem for [Formula: see text], to the graphic Travel Salesman Problem (TSP) for [Formula: see text], and close to first vertex cover and then dominating set for even larger [Formula: see text]. Moreover, approximation algorithms for multiple parameter ranges were provided. In this article, we provide complementing inapproximability bounds and examine the fixed-parameter tractability of the problem. On the one hand, we show the following: (1) For every fixed [Formula: see text], the problem [Formula: see text]-Tour is APX-hard, while for every fixed [Formula: see text], the problem has no polynomial-time [Formula: see text]-approximation unless [Formula: see text]. Our techniques also yield the new result that TSP remains APX-hard on cubic (and even cubic bipartite) graphs. (2) For every fixed [Formula: see text], the problem [Formula: see text]-Tour is fixed-parameter tractable (FPT) when parameterized by the length of a shortest tour, while it is W[2]-hard for every fixed [Formula: see text] and para-NP-hard for [Formula: see text] being part of the input. On the other hand, if [Formula: see text] is considered to be part of the input, then an interesting nontrivial phenomenon occurs when [Formula: see text] is a constant fraction of the number of vertices: (3) If [Formula: see text] is part of the input, then the problem can be solved in time [Formula: see text], where [Formula: see text]; however, assuming the exponential-time hypothesis (ETH), there is no algorithm that solves the problem and runs in time [Formula: see text].

A well-studied continuous model of graphs, introduced by Dearing and Francis [Transportation Science, 1974], considers each edge as a continuous unit-length interval of points. For $δ\geq 0$, we introduce the problem $δ$-Tour, where the objective is to find the shortest tour that comes within a distance of $δ$ of every point on every edge. It can be observed that 0-Tour is essentially equivalent to the Chinese Postman Problem, which is solvable in polynomial time. In contrast, 1/2-Tour is essentially equivalent to the Graphic Traveling Salesman Problem (TSP), which is NP-hard but admits a constant-factor approximation in polynomial time. We investigate $δ$-Tour for other values of $δ$, noting that the problem's behavior and the insights required to understand it differ significantly across various $δ$ regimes. We design polynomial-time approximation algorithms summarized as follows: (1) For every fixed $0 < δ< 3/2$, the problem $δ$-Tour admits a constant-factor approximation. (2) For every fixed $δ\geq 3/2$, the problem admits an $O(\log{n})$-approximation. (3) If $δ$ is considered to be part of the input, then the problem admits an $O(\log^3{n})$-approximation. This is the first of two articles on the $δ$-Tour problem. In the second one we complement the approximation algorithms presented here with inapproximability results and related to parameterized complexity.

In content-oblivious computation, n nodes wish to compute a given task over an asynchronous network that suffers from an extremely harsh type of noise, which corrupts the content of all messages across all channels. In a recent work, Censor-Hillel, Cohen, Gelles, and Sela (Distributed Computing, 2023) showed how to perform arbitrary computations in a content-oblivious way in 2-edge connected networks but only if the network has a distinguished node (called root) to initiate the computation.

In content-oblivious computation, n nodes wish to compute a given task over an asynchronous network that suffers from an extremely harsh type of noise, which corrupts the content of all messages across all channels. In a recent work, Censor-Hillel, Cohen, Gelles, and Sela (Distributed Computing, 2023) showed how to perform arbitrary computations in a content-oblivious way in 2-edge connected networks but only if the network has a distinguished node (called root) to initiate the computation. Our goal is to remove this assumption, which was conjectured to be necessary. Achieving this goal essentially reduces to performing a content-oblivious leader election since an elected leader can then serve as the root required to perform arbitrary content-oblivious computations. We focus on ring networks, which are the simplest 2-edge connected graphs. On oriented rings, we obtain a leader election algorithm with message complexity O(n*ID_max), where ID_max is the maximal assigned ID. As it turns out, this dependency on $ID_max$ is inherent: we show a lower bound of Omega(n*log(ID_max/n)) messages for content-oblivious leader election algorithms. We also extend our results to non-oriented rings, where nodes cannot tell which channel leads to which neighbor. In this case, however, the algorithm does not terminate but only reaches quiescence.