It is a notorious open question whether integer programs (IPs) with an integer coefficient matrix M whose subdeterminants are all bounded by a constant Δ in absolute value can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from M, one obtains a submatrix A that is the transpose of a network matrix.

We show that every n-vertex planar graph is contained in the graph obtained from a fan by blowing up each vertex by a complete graph of order ). Equivalently, every n-vertex planar graph G has a set X of ) vertices such that G — X has bandwidth ). This result holds in the more general setting of graphs contained in the strong product of a bounded treewidth graph and a path, which includes bounded genus graphs, graphs excluding a fixed apex graph as a minor, and k-planar graphs for fixed k. These results are obtained using two ingredients. The first is a new local sparsification lemma, which shows that every n-vertex planar graph G has a set of O ((n log n )/D ) vertices whose removal results in a graph with local density at most D. The second is a generalization of a method of Feige and Rao, that relates bandwidth and local density using volume-preserving Euclidean embeddings.

We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k =0 (bipartite graphs) and for k =1. We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b -matching.

Abstract. A well-known result due to Caro (1979) and Wei (1981) states that every graph [Formula: see text] has an independent set of size at least [Formula: see text], where [Formula: see text] denotes the degree of vertex [Formula: see text]. Alon, Kahn, and Seymour (1987) showed the following generalization: For every [Formula: see text], every graph [Formula: see text] has a [Formula: see text]-degenerate induced subgraph with at least [Formula: see text] vertices. In particular, for [Formula: see text], every graph [Formula: see text] with no isolated vertices has an induced forest with at least [Formula: see text] vertices. Akbari et al. (2019) conjectured that if [Formula: see text] has minimum degree at least 2, then one can even find an induced linear forest of that order in [Formula: see text], that is, a forest where each component is a path. In this paper, we prove this conjecture and show a number of related results. In particular, if there is no restriction on the minimum degree of [Formula: see text], we show that there are infinitely many “best possible” functions [Formula: see text] such that [Formula: see text] is a lower bound on the maximum order of a linear forest in [Formula: see text], and we give a full characterization of all such functions [Formula: see text].

We prove that for every planar graph X of treedepth h, there exists a positive integer c such that for every X-minor-free graph G, there exists a graph H of treewidth at most f (h) such that G is isomorphic to a subgraph of H ⊠ Kc. This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour (JCTB, 1986), and treedepth is the optimal parameter in such a result. As an example application, we use this result to improve the upper bound for weak coloring numbers of graphs excluding a given graph as a minor.

We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension k as a subposet. This applies in particular to posets whose cover graphs have bounded treewidth, as the cliquewidth of a poset is bounded in terms of the treewidth of the cover graph. For the latter posets, we prove a stronger statement: every such poset with sufficiently large dimension contains the Kelly example of dimension k as a subposet. Using this result, we obtain a full characterization of the minor-closed graph classes C such that posets with cover graphs in C have bounded dimension: they are exactly the classes excluding the cover graph of some Kelly example. Finally, we consider a variant of poset dimension called Boolean dimension, and we prove that posets with bounded cliquewidth have bounded Boolean dimension.

Abstract. The circumference of a graph [Formula: see text] with at least one cycle is the length of a longest cycle in [Formula: see text]. A classic result of Birmelé [ J. Graph Theory, 43 (2003), pp. 24–25] states that the treewidth of [Formula: see text] is at most its circumference minus 1. In case [Formula: see text] is 2-connected, this upper bound also holds for the pathwidth of [Formula: see text]; in fact, even the treedepth of [Formula: see text] is upper bounded by its circumference (Briański et al. [ Treedepth vs circumference, Combinatorica, 43 (2023), pp. 659–664]). In this paper, we study whether similar bounds hold when replacing the circumference of [Formula: see text] by its cocircumference, defined as the largest size of a bond in [Formula: see text], an inclusionwise minimal set of edges [Formula: see text] such that [Formula: see text] has more components than [Formula: see text]. In matroidal terms, the cocircumference of [Formula: see text] is the circumference of the bond matroid of [Formula: see text]. Our first result is the following “dual” version of Birmelé’s theorem: The treewidth of a graph [Formula: see text] is at most its cocircumference. Our second and main result is an upper bound of [Formula: see text] on the pathwidth of a 2-connected graph [Formula: see text] with cocircumference [Formula: see text]. Contrary to circumference, no such bound holds for the treedepth of [Formula: see text]. Our two upper bounds are best possible up to a constant factor.

Abstract. Alon, Seymour, and Thomas [ J. Amer. Math. Soc., 3 (1990), pp. 801–808] proved that every [Formula: see text]-vertex graph excluding [Formula: see text] as a minor has treewidth less than [Formula: see text]. Illingworth, Scott, and Wood [ Product Structure of Graphs with an Excluded Minor, preprint, arXiv:2104.06627 , 2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth [Formula: see text], where each vertex is blown up by a complete graph of order [Formula: see text]. Solving an open problem of Illingworth, Scott, and Wood [2022], we prove that the treewidth bound can be reduced to 4 while keeping blowups of order [Formula: see text]. As an extension of the Lipton–Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to 2, which is best possible. We generalize this result for [Formula: see text]-minor-free graphs, with blowups of order [Formula: see text]. This setting includes graphs embeddable on any fixed surface.

Abstract. This is a corrigendum for the article “Orthogonal Tree-Decompositions of Graphs” [SIAM J. Discrete Math. 32(2):839–863, 2018].

We describe a polynomial-time algorithm which, given a graphGwith treewidtht, approximates the pathwidth ofGto within a ratio of \(O(t\sqrt {\log t})\) . This is the first algorithm to achieve anf(t)-approximation for some functionf. Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at leastth+2 has treewidth at leasttor contains a subdivision of a complete binary tree of heighth+1. The boundth+2 is best possible up to a multiplicative constant. This result was motivated by, and implies (withc=2), the following conjecture of Kawarabayashi and Rossman (SODA’18): there exists a universal constantcsuch that every graph with pathwidth Ω(kc) has treewidth at leastkor contains a subdivision of a complete binary tree of heightk. Our main technical algorithm takes a graphGand some (not necessarily optimal) tree decomposition ofGof widtht′ in the input, and it computes in polynomial time an integerh, a certificate thatGhas pathwidth at leasth, and a path decomposition ofGof width at most (t′+1)h+1. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of heighth. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC’05) for treewidth.

We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than$k$vertex-disjoint odd cycles, where$k$is any constant. Previously, polynomial-time algorithms were only known for$k=0$(bipartite graphs) and for$k=1$. We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b-matching.

We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of . This is the first algorithm to achieve an f(t)-approximation for some function f. Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least th + 2 has treewidth at least t or contains a subdivision of a complete binary tree of height h + 1. The bound th + 2 is best possible up to a multiplicative constant. This result was motivated by, and implies (with c = 2), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant c such that every graph with pathwidth Ω(kc) has treewidth at least k or contains a subdivision of a complete binary tree of height k. Our main technical algorithm takes a graph G and some (not necessarily optimal) tree decomposition of G of width t′ in the input, and it computes in polynomial time an integer h, a certificate that G has pathwidth at least h, and a path decomposition of G of width at most (t′ + 1)h + 1. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of height h. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC'05) for treewidth.

A metric graph is a pair (G, d), where G is a graph and d: E(G) → R≥ 0 is a distance function. Let p∈ [1 ,∞] be fixed. An isometric embedding of the metric graph (G, d) in ℓpk=(Rk,dp) is a map ϕ: V(G) → Rk such that dp(ϕ(v) ,ϕ(w)) = d(vw) for all edges vw∈ E(G). The ℓp-dimension of G is the least integer k such that there exists an isometric embedding of (G, d) in ℓpk for all distance functions d such that (G, d) has an isometric embedding in ℓpK for some K. It is easy to show that ℓp-dimension is a minor-monotone property. In this paper, we characterize the minor-closed graph classes C with bounded ℓp-dimension, for p∈ { 2 ,∞}. For p= 2 ,we give a simple proof that C has bounded ℓ2-dimension if and only if C has bounded treewidth. In this sense, the ℓ2-dimension of a graph is ‘tied’ to its treewidth. For p= ∞, the situation is completely different. Our main result states that a minor-closed class C has bounded ℓ∞-dimension if and only if C excludes a graph obtained by joining copies of K4 using the 2-sum operation, or excludes a Möbius ladder with one ‘horizontal edge’ removed.

We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an n -vertex planar graph G is assigned a (1 + o(1)) log 2 n -bit label and the labels of two vertices u and v are sufficient to determine if uv is an edge of G . This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer n , there exists a graph U n with n 1+o(1) vertices such that every n -vertex planar graph is an induced subgraph of U n . These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k -planar graphs.

We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an n-vertex planar graph G is assigned a (1+o(1))log2n-bit label and the labels of two vertices u and v are sufficient to determine if uv is an edge of G. This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer n, there exists a graph Un with n1+o(1)vertices such that every n-vertex planar graph is an induced subgraph of Un. These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k-planar graphs.

Consider the family of graphs without k node-disjoint odd cycles, where k is a constant. Determining the complexity of the stable set problem for such graphs G is a long-standing problem. We give a polynomial-time algorithm for the case that G can be further embedded in a (possibly nonorientable) surface of bounded genus. Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes. To this end, we show that 2-sided odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed surface. This extends the fact that odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed orientable surface (Kawarabayashi & Nakamoto, 2007). Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost nonnegative integer circulation of a certain homology class, which turns out to be efficiently solvable in our case.

We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al. [66] from 1992. The key to the proof is a new structural tool called layered partitions , and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. [31] that graphs in a proper minor-closed class have low treewidth colourings.

A classic theorem of Erdös and Pósa [ Canad. J. Math., 17 (1965), pp. 347--352] states that every graph has either $k$ vertex-disjoint cycles or a set of $O(k \log k)$ vertices meeting all its cycles. While the standard proof revolves around finding a large “frame” in the graph (a subdivision of a large cubic graph), an alternative way of proving this theorem is to use a ball packing argument of Kühn and Osthus [ Random Structures Algorithms, 22 (2003), pp. 213--225] and Diestel and Rempel [ Combinatorica, 25 (2005), pp. 111--116]. In this paper, we argue that the latter approach is particularly well suited for studying edge variants of the Erdös--Pósa theorem. As an illustration, we give a short proof of a theorem of Bruhn, Heinlein, and Joos [ Combinatorica, 39 (2019), pp. 1--36] that cycles of length at least $\ell$ have the so-called edge-Erdös--Pósa property. More precisely, we show that every graph $G$ contains either $k$ edge-disjoint cycles of length at least $\ell$ or an edge set $F$ of size $O(k\ell \cdot \log (k\ell))$ such that $G-F$ has no cycle of length at least $\ell$. For fixed $\ell$, this improves on the previously best known bound of $O(k^2 \log k +k\ell)$.

We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalizes a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class.

A proper edge coloring of a graph is adjacent vertex distinguishing if no two adjacent vertices see the same set of colors. Using a clever application of the local lemma, Hatami [ J. Combin. Theory Ser. B, 95 (2005), pp. 246--256] proved that every graph with maximum degree $\Delta$ and no isolated edge has an adjacent vertex distinguishing edge coloring with $\Delta + 300$ colors, provided $\Delta$ is large enough. We show that this bound can be reduced to $\Delta + 19$. This is motivated by the conjecture of Zhang, Liu, and Wang [ Appl. Math. Lett., 15 (2002), pp. 623--626] that $\Delta + 2$ colors are enough for $\Delta \geqslant 3$.

We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath, Leighton and Rosenberg from 1992. The key to the proof is a new structural tool called layered partitions, and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes.

Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f : ℕ → ℝ such that for all k ∊ ℕ and all graphs G, either G contains k vertex-disjoint subgraphs each containing H as a minor, or there is a subset X of at most f(k) vertices such that G–X has no H-minor. We prove that this remains true with f(k) = ck log k for some constant c = c(H). This bound is best possible, up to the value of c, and improves upon a recent result of Chekuri and Chuzhoy [STOC 2013], who established this with f(k) = ck logd k for some universal constant d. The proof is constructive and yields a polynomial-time O(log OPT)-approximation algorithm for packing subgraphs containing an H-minor.

Let $W_t$ denote the wheel on t+1 vertices. We prove that for every integer $t \geq 3$ there is a constant $c=c(t)$ such that for every integer $k \geq 1$ and every graph $G$, either $G$ has $k$ vertex-disjoint subgraphs each containing $W_t$ as a minor, or there is a subset $X$ of at most $c k \log k$ vertices such that $G-X$ has no $W_t$ minor. This is best possible, up to the value of $c$. We conjecture that the result remains true more generally if we replace $W_t$ with any fixed planar graph $H$.

This paper studies graphs that have two tree decompositions with the property that every bag from the first decomposition has a bounded-size intersection with every bag from the second decomposition. We show that every graph in each of the following classes has a tree decomposition and a linear-sized path decomposition with bounded intersections: (1) every proper minor-closed class, (2) string graphs with a linear number of crossings in a fixed surface, (3) graphs with linear crossing number in a fixed surface. Here “linear size” means that the total size of the bags in the path decomposition is $O(n)$ for $n$-vertex graphs. We then show that every $n$-vertex graph that has a tree decomposition and a linear-sized path decomposition with bounded intersections has $O(\sqrt{n})$ treewidth. As a corollary, we conclude a new lower bound on the crossing number of a graph in terms of its treewidth. Finally, we consider graph classes that have two path decompositions with bounded intersections. Trees and outerplanar graphs have this property. But for the next most simple class, series parallel graphs, we show that no such result holds.

The following is a corrigendum to [ Orthogonal tree decompositions of graphs, SIAM J. Discrete Math., 32 (2018), pp. 839--863].

We prove that every connected graph $G$ with $m$ edges contains a set $X$ of at most $\frac{3}{16}(m + 1)$ vertices such that $G-X$ has no $K_4$ minor, or, equivalently, has treewidth at most 2. This bound is best possible. Connectivity is essential: If $G$ is not connected, then only a bound of $\frac{1}{5}m$ can be guaranteed.

The assortment problem in revenue management is the problem of deciding which subset of products to offer to consumers in order to maximise revenue. A simple and natural strategy is to select the best assortment out of all those that are constructed by fixing a threshold revenue π and then choosing all products with revenue at least π. This is known as the revenue-ordered assortments strategy. Our first contribution is an analysis of the performance of the revenue-ordered assortments strategy making only minimal assumptions about the underlying discrete choice model: We assume that consumers behave rationally, in the sense that the probability of choosing a specific product x ∈ S when given a choice set S cannot increase if S is enlarged. This rationality assumption, known as regularity, is satisfied by almost all models studied in the revenue management and choice theory literature. This includes in particular all random utility models, as well as other models introduced recently such as the additive perturbed utility model, the hitting fuzzy attention model, and models obtained using a non-additive random utility function. We provide three types of revenue guarantees for revenue-ordered assortments: If there are k distinct revenues r1, r2, ..., rk associated with the products (listed in increasing order), then revenue-ordered assortments approximate the optimum revenue to within a factor of (A) 1/k; (B) 1/(1 + ln(rk/r1)), and (C) 1/(1 + ln υ), where υ is defined with respect to an optimal assortment S* as the ratio between the probability of just buying a product and that of buying a product with highest revenue in S*. These three guarantees are in general incomparable, that is, (A), (B), or (C) can be the largest depending on the instance. We also show that the three bounds (A), (B), and (C) are exactly tight, in the sense that none of the bounds remains true if multiplied by a factor (1+ ε) for any ε > 0.

Let $G$ be a graph and $p \in [1, \infty]$. The parameter $f_p(G)$ is the least integer $k$ such that for all $m$ and all vectors $(r_v)_{v \in V(G)} \subseteq \mathbb{R}^m$, there exist vectors $(q_v)_{v \in V(G)} \subseteq \mathbb{R}^k$ satisfying $\|r_v-r_w\|_p=\|q_v-q_w\|_p$ for all $vw\in E(G).$ It is easy to check that $f_p(G)$ is always finite and that it is minor monotone. By the graph minor theorem of Robertson and Seymour [J. Combin. Theory Ser. B, 92 (2004), pp. 325--357], there are a finite number of excluded minors for the property $f_p(G) \leq k$. In this paper, we determine the complete set of excluded minors for $f_\infty(G) \leq 2$. The two excluded minors are the wheel on five vertices and the graph obtained by gluing two copies of $K_4$ along an edge and then deleting that edge. We also show that the same two graphs are the complete set of excluded minors for $f_1(G) \leq 2$. In addition, we give a family of examples that show that $f_\infty$ is unbounded on the class of planar graphs and $f_\infty$ is not bounded as a function of tree-width.

We prove that every planar poset $P$ of height $h$ has dimension at most $192h+96$. This improves on previous exponential bounds and is best possible up to a constant factor. We complement this result with a construction of planar posets of height $h$ and dimension at least $(4/3)h-2$.

We prove that posets of bounded height whose cover graphs belong to a fixed class with bounded expansion have bounded dimension. Bounded expansion, introduced by Nešetřil and Ossona de Mendez as a model for sparsity in graphs, is a property that is naturally satisfied by a wide range of graph classes, from graph structure theory (graphs excluding a minor or a topological minor) to graph drawing (e.g. graphs with constant book thickness). Therefore, our theorem generalizes a number of results including the most recent one for posets of bounded height with cover graphs excluding a fixed graph as a topological minor (Walczak, SODA 2015). We also show that the result is in a sense best possible, as it does not extend to nowhere dense classes; in fact, it already fails for cover graphs with locally bounded treewidth.

An empty pentagon in a point set $P$ in the plane is a set of five points in $P$ in strictly convex position with no other point of $P$ in their convex hull. We prove that every finite set of at least $328\ell^2$ points in the plane contains an empty pentagon or $\ell$ collinear points. This is optimal up to a constant factor since the $(\ell -1)\times(\ell-1)$ square lattice contains no empty pentagon and no $\ell$ collinear points. The previous best known bound was doubly exponential.

The $c$-pumpkin is the graph with two vertices linked by $c \geq 1$ parallel edges. A $c$-pumpkin-model in a graph $G$ is a pair $\{A, B\}$ of disjoint subsets of vertices of $G$, each inducing a connected subgraph of $G$, such that there are at least $c$ edges in $G$ between $A$ and $B$. We focus on hitting and packing $c$-pumpkin-models in a given graph in the realm of approximation algorithms and parameterized algorithms. We give a fixed-parameter tractable (FPT) algorithm running in time $2^{\mathcal{O}(k)} n^{\mathcal{O}(1)}$ deciding, for any fixed $c \geq 1$, whether all $c$-pumpkin-models can be hit by at most $k$ vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex Set, which correspond to the cases $c=1,2$ respectively. Finally, we present an $\mathcal{O}(\log n)$-approximation algorithm for both the problems of hitting all $c$-pumpkin-models with a smallest number of vertices and packing a maximum number of vertex-disjoint $c$-pumpkin-models.

Let $g(t)$ be the minimum number such that every graph $G$ with average degree $d(G) \geq g(t)$ contains a $K_{t}$-minor. Such a function is known to exist, as originally shown by Mader. Kostochka and Thomason independently proved that $g(t) \in \Theta(t\sqrt{\log t})$. This paper shows that for all fixed $\epsilon > 0$ and fixed sufficiently large $t \geq t(\epsilon)$, if $d(G) \geq (2+\epsilon)g(t)$, then we can find this $K_{t}$-minor in linear time. This improves a previous result by Reed and Wood who gave a linear-time algorithm when $d(G) \geq 2^{t-2}$.

It is known that the First-Fit algorithm for partitioning a poset $P$ into chains uses relatively few chains when $P$ does not have two incomparable chains each of size $k$. In particular, if $P$ has width $w$, then Bosek, Krawczyk, and Szczypka [SIAM J. Discrete Math., 23 (2010), pp. 1992--1999], proved an upper bound of $ckw^{2}$ on the number of chains used by First-Fit for some constant $c$, while Joret and Milans [Order, 28 (2011), pp. 455--464] gave one of $ck^{2}w$. In this paper we prove an upper bound of the form $ckw$. This is most possible up to the value of $c$.

In the Stackelberg network pricing problem, one has to assign tariffs to a certain subset of the arcs of a given transportation network. The aim is to maximize the amount paid by the user of the network, knowing that the user will take a shortest st-path once the tariffs are fixed. (Roch et al., Networks, 46 (2005), 57–67) proved that this problem is NP-hard, and gave an O(log m)-approximation algorithm, where m denote the number of arcs to be priced. In this note, we show that the problem is also APX-hard. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 117–120 2011

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set $P$, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of $P$. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical.

We consider the problem of partial order production: arrange the elements of an unknown totally ordered set T into a target partially ordered set S by comparing a minimum number of pairs in T. Special cases include sorting by comparisons, selection, multiple selection, and heap construction. We give an algorithm performing $ITLB+o(ITLB)+O(n)$ comparisons in the worst case. Here, n denotes the size of the ground sets, and $ITLB$ denotes a natural information-theoretic lower bound on the number of comparisons needed to produce the target partial order. Our approach is to replace the target partial order by a weak order (that is, a partial order with a layered structure) extending it, without increasing the information-theoretic lower bound too much. We then solve the problem by applying an efficient multiple selection algorithm. The overall complexity of our algorithm is polynomial. This answers a question of Yao [SIAM J. Comput., 18 (1989), pp. 679–689]. We base our analysis on the entropy of the target partial order, a quantity that can be efficiently computed and provides a good estimate of the information-theoretic lower bound.

Proceedings of the 41st annual ACM Symposium on Theory of Computing STOC 2009, Bethesda, Maryland, 31 mai–2 juin 2009