ABSTRACT. Let $G=(V,E)$ be a simple connected graph with at least two vertices. A proper vertex coloring of $G$ is called a \emph{proper conflict-free coloring} if for every vertex $v\in V$, there exists a color that appears exactly once in the open neighborhood of $v$. The minimum number of colors required for such a coloring is called the \emph{proper conflict-free chromatic number} of $G$ and is denoted by $\chi_{pcf}(G)$.

Proper conflict-free coloring was introduced by Fabrici et al. Later, Caro et al.\ investigated how large $\chi_{pcf}(G)$ can be in comparison to the chromatic number $\chi(G)$. They showed that the ratio $\chi_{pcf}(G)/\chi(G)$ can be arbitrarily large for general graphs, while it remains bounded for certain restricted graph classes. They also conjectured that every connected graph $G$ with maximum degree $\Delta \ge 3$ satisfies $\chi_{pcf}(G) \le \Delta + 1$.

In this paper, we show that the ratio $\chi_{pcf}(G)/\chi(G)$ is bounded by a constant for AT-free graphs, $P_4$-sparse graphs, and split graphs. We further improve the upper bounds on $\chi_{pcf}(G)$ for several subclasses of AT-free graphs, including interval graphs, proper interval graphs, and permutation graphs. Additionally, we strengthen previously known bounds for minor-closed $k$-planar graphs and for $K_t$-minor-free graphs. In most of the cases, we prove that these bounds are tight. We also prove the validity of the $\Delta+1$ conjecture for some of these graph classes.

ABSTRACT. A conflict-free cut F on a connected graph G = (V, E) is defined as a set of edges F \subseteq E such that G-F is disconnected, and no two edges in F are conflicting. The notion of conflicting edges is represented using an associated conflict graph \widehat{G} = (\widehat{V}, \widehat{E}) where \widehat{V} = E. Deciding if a given planar graph G, with an associated conflict graph \widehat{G}, has a conflict-free cut is known to be NP-complete, when G has maximum degree four and \widehat{G} is a line graph of G [Bonsma, JGT 2009].

In this paper, we prove the following for the case when \widehat{G} is 1-regular.

* We completely resolve the complexity of the decision problem when G is planar. Towards this end, we show that (a) there always exists a conflict-free cut when the graph is planar and 4-regular unless it is an octahedron graph, and (b) the decision problem is NP-complete, even in the case when G is planar with maximum degree 5.

* We also show that the decision problem is NP-complete when G is a 3-degenerate graph with maximum degree 5. This completely resolves the complexity status of the problem when G is 3-degenerate.

* We construct families of graphs with 1-regular conflicts that do not have a conflict-free cut.

Our results answer the questions posed in [Rauch, Rautenbach and Souza, IPL 2025].

ABSTRACT. The Path Avoiding Forbidden Pairs (PAFP) problem asks whether, in a directed graph G with terminals s and t and a set F of forbidden vertex pairs, there is an s-t path that includes at most one endpoint from each pair. Most known polynomial-time cases come from restricting the structure of the union graph obtained by adding the forbidden pairs as extra edges, for example by bounding its treewidth.

We initiate the study of PAFP under a layer-based width measure. Let the BFS layer L_d be the set of vertices at directed shortest-path distance d from s, and define the BFS-width from s as max_d |L_d|. We show that PAFP on DAGs remains NP-complete even when the canonical union digraph (obtained by orienting forbidden pairs forward in a fixed deterministic topological order of the DAG) is itself a DAG of BFS-width at most 2. We do this by giving a constructive polynomial-time transformation that converts any DAG PAFP instance into an equivalent DAG PAFP instance whose canonical union digraph has BFS-width at most 2.

We contrast BFS layers with exact-length layers, the set of vertices reachable from s by a directed path of length exactly d. We show that PAFP, when the input graph is a DAG whose exact layers are of size at most 2, is in P. We are not aware of previous polynomial-time results for PAFP that combine unrestricted forbidden pairs with input graphs that may have exponentially many s-t paths; our exact-layer width-2 case is one such regime.

ABSTRACT. A set $S \subseteq V(G)$ is a solid-resolving set of an undirected graph $G$ if each vertex can be distinguished from any vertex subset by their distances from the set $S$. Solid-resolving sets are a generalization of resolving sets, which have been studied extensively in literature. We generalize this concept to digraphs and oriented graphs. In this setting, we first define solid-resolving sets for directed graphs and then consider vertices that must be included in any solid-resolving set. We also study the solid-metric dimension, which is the minimum cardinality of a solid-resolving set for the given digraph. We determine the possible values that the solid-metric dimension can take for common graph classes such as tournaments, directed paths, oriented cycles and also for Cartesian products of oriented paths and cycles. Furthermore, we also show that two digraphs that differ by only one vertex or arc can have solid-metric dimensions that differ by an arbitrary $k$. This indicates that the solid-metric dimension is a global, rather than a local property.

ABSTRACT. In this work, we consider the class of surface-embedded, directed graphs that have at most polynomially many surface non-separating cycles. We show that for this class of graphs, there is a logspace computable, polynomially bounded, skew-symmetric edge weight function, with respect to which any cycle in the graph gets a non-zero weight. As a consequence of our result, we show that reachability in graphs with polynomially many surface non-separating cycles is in UL. Moreover, we also show that computing perfect matching in bipartite graphs that have polynomially many surface non-separating cycles is in SPL.

ABSTRACT. We consider the problem of minimizing the weighted makespan on a single machine with restarts. Restarts are similar to preemptions but weaker: a job can be interrupted, but then it has to be run again from the start instead of resuming at the point of interruption later. The objective is to minimize the weighted makespan, defined as the maximum weighted completion time of jobs. We establish a lower bound of 1.4656 on the competitive ratio achievable by deterministic online algorithms. For the case where all jobs have identical processing times, we design and analyze a deterministic online algorithm that improves the competitive ratio to better than 1.3098. Finally, we prove a lower bound of 1.2344 for this case.

ABSTRACT. In the online unweighted knapsack problem, items arrive sequentially and must be accepted or rejected immediately for a bounded-capacity knapsack, aiming to maximize the total size of accepted items. When decisions are irrevocable, no algorithm achieves a constant competitive ratio. An essential relaxation that circumvents this impossibility is to allow previously accepted items to be removed from the knapsack (a.k.a. removal). In this work, we investigate possible further improvements on the competitive ratio with removal by bringing together two other previously proposed model extensions: knowledge of an upper bound on the item sizes (a.k.a. bound awareness) and ability to reinsert previously rejected items (a.k.a. recourse). Our contributions are twofold. First, we establish close upper and lower bounds on the competitive ratio under bound awareness, removal and recourse. We show that significant improvements on the best known competitive ratio are possible when the upper bound on the item sizes is not too restrictive and only few uses of recourse are available. Second, we introduce the notion of adaptive online algorithms which don’t require to know any upper bound on the item sizes but still achieve performance guarantees comparable to the ones obtained under the bound awareness model.

ABSTRACT. We study a problem of online target coverage by a drone or a sensor that is equipped with a camera or an antenna of fixed angle of view. The targets to be monitored appear at arbitrary positions on a line barrier in an online manner. When a new target appears, the drone has to move to a location that covers the newly arrived target, as well as already existing targets. The objective is to design a coverage algorithm that optimizes the total length of the drone's trajectory. Our results are reported in terms of an algorithm's competitive ratio, i.e., the worst-case ratio (over all inputs) of its cost to that of an optimal offline algorithm. In terms of upper bounds, we present three online algorithms and prove bounds on their competitive ratios for every $\alpha \in [0, \pi/2]$. The best of them, called \FA is significantly better than the other two for $\pi/6 < \alpha < \pi/3$. In particular, for $\alpha=\pi/4$, its worst case, \FA has competitive ratio $1.25$, while the other two have competitive ratio $\sqrt{2}$. Finally, we prove a lower bound on the competitive ratio of online algorithms for a drone with half-angle $\alpha \in [0, \pi/4]$; this bound is a function of $\alpha$ that achieves its maximum value at $\alpha = \pi/4$ equal to $(1+\sqrt{2})/2 \approx 1.207$.

ABSTRACT. We study two related problems on simple, undirected graphs: Edge Deletion to Cactus and Spanning Tree to Cactus. Edge Deletion to Cactus has been known to be NP-hard on general graphs at least since 1988. In their recent work where they showed—inter alia—that Edge Deletion to Cactus is NP-hard even when restricted to bipartite graphs, Koch et al. (Disc. Appl. Math., 2024) posed the complexity of Spanning Tree to Cactus as an open problem. Our first main result is that Spanning Tree to Cactus can be solved in polynomial time. We use the polynomial-time algorithm for Spanning Tree to Cactus as a black box to obtain an exact algorithm that solves Edge Deletion to Cactus in O*(n^(n−2)) time, where n is the number of vertices in the input graph and the O*() notation hides polynomial factors. This is a significant improvement over the brute-force algorithm for Edge Deletion to Cactus that enumerates all subsets of the edge set. We further improve the running time for Edge Deletion to Cactus to O*(3^n) using dynamic programming; this is our second main result. To the best of our knowledge, this is the fastest known exact-exponential algorithm for Edge Deletion to Cactus.

ABSTRACT. We consider the well-studied problem of finding a spanning tree with minimum average distance between vertex pairs (called a MAD tree). This is a classic network design problem which is known to be NP-hard. While approximation algorithms and polynomial-time algorithms for some graph classes are known, the parameterized complexity of the problem has not been investigated so far.

We start a parameterized complexity analysis with the goal of determining the border of algorithmic tractability for the MAD tree problem. To this end, we provide a linear-time algorithm for graphs of constant modular width and a polynomial-time algorithm for graphs of bounded treewidth; the degree of the polynomial depends on the treewidth. That is, the problem is in FPT with respect to modular width and in XP with respect to treewidth. Moreover, we show it is in FPT when parameterized by vertex integrity or by an above-guarantee parameter. We complement these algorithms with NP-hardness on split graphs.

ABSTRACT. The Maximum (Minimum) Leaf Spanning Tree problem asks for a spanning tree with the largest (smallest) number of leaves. As spanning trees are often computed using graph search algorithms, it is natural to restrict this problem to the set of search trees of some particular graph search, e.g., find the Breadth-First Search (BFS) tree with the largest number of leaves. We study this problem for Generic Search (GS), BFS and Lexicographic Breadth-First Search (LBFS) using search trees that connect each vertex to its first neighbor in the search order (first-in trees) just like the classic BFS tree. In particular, we analyze the complexity of these problems, both in the classical and in the parameterized sense. Among other results, we show that the minimum and maximum leaf problems are in FPT for the first-in trees of GS, BFS and LBFS when parameterized by the number of leaves in the tree. However, when these problems are parameterized by the number of internal vertices of the tree, they are W[1]-hard for the first-in trees of GS, BFS and LBFS.