In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori and the edges arrive one at a time. The goal is to maintain a fractional vertex cover of the tree, i.e., an assignment of fractional weights from [0,1] to the vertices such that the weights of endpoints of every edge sum up to at least one. After each edge arrival, we need to modify the fractional vertex cover to cover the new edge as well. However, we can only increase the values assigned to vertices. The problem was studied before (in the vertex arrival model) by Wang and Wong, who motivated it as a generalization of the ski-rental problem, but also (more importantly) by its close connection to the dual online matching problem. They presented a 1.901-competitive algorithm for general graphs in the vertex arrival model. We present an 11/6 ≈ 1.83-competitive algorithm for trees in the more general edge arrival model. In addition, we study the fractional vertex cover problem in an incremental model, where we again seek a fractional vertex cover after every update, but all the updates to the tree are known to the algorithm a priori. In this model, we give a 1.5-competitive algorithm and provide a matching lower bound.

Hons, Klimošová, Mikšaník, Tkadlec, Tyomkyn and the second author proved that, for every integer 𝓁 ≥ 1, every directed graph with minimum out-degree at least 3.23 ⋅ 𝓁 contains a (2,𝓁)-spider (a 1-subdivision of the in-star with 𝓁 leaves) as a subgraph. Hons et al. also conjectured that the bound on the minimum out-degree can be further improved to 2 𝓁. In this note, we confirm this conjecture by showing that every directed graph with minimum out-degree at least 2𝓁 contains a (2, 𝓁)-spider as a subgraph. This result is best possible, as the complete directed graph with 2𝓁 vertices does not contain a (2,𝓁)-spider.

In a graph G, a k-attack A is any set of at most k vertices and l-defense D is a set of at most l vertices. We say that defense D counters attack A if each a in A can be matched to a distinct defender d in D with a equal to d or a adjacent to d in G. In the defensive domination problem, we are interested in deciding, for a graph G and positive integers k and l given on input, if there exists an l-defense that counters every possible k-attack on G. Defensive domination is a natural resource allocation problem and can be used to model network robustness and security, disaster response strategies, and redundancy designs. The defensive domination problem is naturally in the complexity class $Σ^P_2$. The problem was known to be NP-hard in general, and polynomial-time algorithms were found for some restricted graph classes. In this note we prove that the defensive domination problem is $Σ^P_2$-complete. We also introduce a natural variant of the defensive domination problem in which the defense is allowed to be a multiset of vertices. This variant is also $Σ^P_2$-complete, but we show that it admits a polynomial-time algorithm in the class of interval graphs. A similar result was known for the original setting in the class of proper interval graphs.

The treewidth is a structural parameter that measures the tree-likeness of a graph. Many algorithmic and combinatorial results are expressed in terms of the treewidth. In this paper, we study the treewidth of outer $k$-planar graphs, that is, graphs that admit a straight-line drawing where all the vertices lie on a circle, and every edge is crossed by at most $k$ other edges. Wood and Telle [New York J. Math., 2007] showed that every outer $k$-planar graph has treewidth at most $3k + 11$ using so-called planar decompositions, and later, Auer et al. [Algorithmica, 2016] proved that the treewidth of outer $1$-planar graphs is at most $3$, which is tight. In this paper, we improve the general upper bound to $1.5k + 2$ and give a tight bound of $4$ for $k = 2$. We also establish a lower bound: we show that, for every even $k$, there is an outer $k$-planar graph with treewidth $k+2$. Our new bound immediately implies a better bound on the cop number, which answers an open question of Durocher et al. [GD 2023] in the affirmative. Our treewidth bound relies on a new and simple triangulation method for outer $k$-planar graphs that yields few crossings with graph edges per edge of the triangulation. Our method also enables us to obtain a tight upper bound of $k + 2$ for the separation number of outer $k$-planar graphs, improving an upper bound of $2k + 3$ by Chaplick et al. [GD 2017]. We also consider outer min-$k$-planar graphs, a generalization of outer $k$-planar graphs, where we achieve smaller improvements.

We consider a graph coloring algorithm that processes vertices in order taken uniformly at random and assigns colors to them using First-Fit strategy. We show that this algorithm uses, in expectation, at most (1+o(1))⋅ln n / ln ln n different colors to color any forest with n vertices. We also construct a family of forests that shows that this bound is best possible.

A \emph{mixed interval graph} is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particularly interested in scenarios where edges and arcs are defined by the geometry of intervals. In a proper coloring of a mixed interval graph $G$, an interval $u$ receives a lower (different) color than an interval $v$ if $G$ contains arc $(u,v)$ (edge $\{u,v\}$). Coloring of mixed graphs has applications, for example, in scheduling with precedence constraints; see a survey by Sotskov [Mathematics, 2020]. For coloring general mixed interval graphs, we present a $\min \{ω(G), λ(G)+1 \}$-approximation algorithm, where $ω(G)$ is the size of a largest clique and $λ(G)$ is the length of a longest directed path in $G$. For the subclass of \emph{bidirectional interval graphs} (introduced recently for an application in graph drawing), we show that optimal coloring is NP-hard. This was known for general mixed interval graphs. We introduce a new natural class of mixed interval graphs, which we call \emph{containment interval graphs}. In such a graph, there is an arc $(u,v)$ if interval $u$ contains interval $v$, and there is an edge $\{u,v\}$ if $u$ and $v$ overlap. We show that these graphs can be recognized in polynomial time, that coloring them with the minimum number of colors is NP-hard, and that there is a 2-approximation algorithm for coloring.

We consider vehicle routing problems that occur in practice in the context of long-distance ride-sharing. On the one hand, the instances of our problems share the helpful property that the passengers travel in roughly the same geographical direction. On the other, the required cost function has ordering-dependent components. For two such problems, we provide heuristic algorithms employing a dynamic programming optimization of a sliding window in appropriate linear orders. In the first, exemplary problem, we route a single vehicle. In the second, we route a fleet of vehicles with a coordinated stopover and exchange of passengers. The size of the sliding window allows for trade-offs between solution qualities and processing times. Both algorithms are effective and efficient on data sets representing actual travel requests from Hoper, a commercial ride-sharing service operated by Teroplan S.A. in Poland.

For a hypergraph $H$, let $q(H)$ denote the expected number of monochromatic edges when the color of each vertex in $H$ is sampled uniformly at random from the set of size 2. Let $s_{\min}(H)$ denote the minimum size of an edge in $H$. Erdős asked in 1963 whether there exists an unbounded function $g(k)$ such that any hypergraph $H$ with $s_{\min}(H) \geq k$ and $q(H) \leq g(k)$ is two colorable. Beck in 1978 answered this question in the affirmative for a function $g(k) = Θ(\log^* k)$. We improve this result by showing that, for an absolute constant $δ>0$, a version of random greedy coloring procedure is likely to find a proper two coloring for any hypergraph $H$ with $s_{\min}(H) \geq k$ and $q(H) \leq δ\cdot \log k$.

For a graph G, a function $$\psi $$ is called a bar visibility representation of G when for each vertex $$v \in V(G)$$ , $$\psi (v)$$ is a horizontal line segment (bar) and $$uv \in E(G)$$ iff there is an unobstructed, vertical, $$\varepsilon $$ -wide line of sight between $$\psi (u)$$ and $$\psi (v)$$ . Graphs admitting such representations are well understood (via simple characterizations) and recognizable in linear time. For a directed graph G, a bar visibility representation $$\psi $$ of G, additionally, for each directed edge (u, v) of G, puts the bar $$\psi (u)$$ strictly below the bar $$\psi (v)$$ . We study a generalization of the recognition problem where a function $$\psi '$$ defined on a subset $$V'$$ of V(G) is given and the question is whether there is a bar visibility representation $$\psi $$ of G with $$\psi |V' = \psi '$$ . We show that for undirected graphs this problem together with closely related problems are $$\mathsf {NP}$$ -complete, but for certain cases involving directed graphs it is solvable in polynomial time.