WALCOM: Algorithms and Computation

Tree reconciliation is a general framework for investigating the evolution of strongly dependent systems as hosts and parasites or genes and species, based on their phylogenetic information. Indeed, informally speaking, it reconciles any differences between two phylogenetic trees by means of biological events. Tree reconciliation is usually computed according to the parsimony principle, that is, to each evolutionary event a cost is assigned and the goal is to find tree reconciliations of minimum total cost. Unfortunately, the number of optimal reconciliations is usually huge and many biological applications require to enumerate and to examine all of them, so it is necessary to handle them.In this paper we list some problems connected with the management of such a big space of tree reconciliations and, for each of them, discuss some known solutions.

In this short survey, a number of old and new notions from parameterized complexity are discussed. We start with looking at the W-hierarchy, including the classes W[1], W[2], W[P]. Then, a recent development where problems are shown to be complete for simultaneously non-deterministic time of the form $$f(k)n^c$$ f ( k ) n c and space of the form $$f(k)\log n$$ f ( k ) log n , is discussed. Some consequences and other notions are briefly explored.

Combinatorial reconfiguration arises when we wish to find a step-by-step transformation on the solution space formed by feasible solutions of an instance of a search problem. Many reconfiguration problems have been shown PSPACE-complete, while several algorithmic techniques have been developed. In this talk, I will give a broad introduction of combinatorial reconfiguration.

We study the problem of checking the existence of a step-by-step transformation of d-regular induced subgraphs in a graph, where $$d \ge 0$$ d ≥ 0 and each step in the transformation must follow a fixed reconfiguration rule. Our problem for $$d=0$$ d = 0 is equivalent to Independent Set Reconfiguration, which is one of the most well-studied reconfiguration problems. In this paper, we systematically investigate the complexity of the problem, in particular, on chordal graphs and bipartite graphs. Our results give interesting contrasts to known ones for Independent Set Reconfiguration.

Consider an agent traversing a graph of “gadgets”, each with local state that changes with each traversal by the agent. Prior work has studied the computational complexity of deciding whether the agent can reach a target location given a graph containing many copies of a given type of gadget. This paper introduces new goals and studies examples where the computational complexity of these problems are the same or differ from the original relocation goal. For several classes of gadgets—DAG gadgets, one-state gadgets, and reversible deterministic gadgets—we give a partial characterization of their complexity when the goal is to traverse every gadget at least once. We also study the complexity of reconfiguration, where the goal is to bring the entire system of gadgets to a specified state. We give examples where reconfiguration is a strictly harder problem than relocating the agent, and also examples where relocation is strictly harder. We also give a partial characterization of the complexity of reconfiguration with reversible deterministic gadgets.

We give a complete structure theorem for 1-complex s, t Hamiltonian paths in rectangular grid graphs. We use the structure theorem to design an algorithm to reconfigure one such path into any other in linear time, making a linear number of switch operations in grid cells.

A generic rectangular layout (for short, layout) is a subdivision of an axis-aligned rectangle into axis-aligned rectangles, no four of which have a point in common. Such layouts are used in data visualization and in cartography. The contacts between the rectangles represent semantic or geographic relations. A layout is weakly (strongly) aspect ratio universal if any assignment of aspect ratios to rectangles can be realized by a weakly (strongly) equivalent layout. We give a combinatorial characterization for weakly and strongly aspect ratio universal layouts, respectively. Furthermore, we describe a quadratic-time algorithm that decides whether a given graph G is the dual graph of a strongly aspect ratio universal layout, and finds such a layout if one exists.

We study crossing-free grid morphs for planar tree drawings using the third dimension. A morph consists of morphing steps, where vertices move simultaneously along straight-line trajectories at constant speeds. There is a crossing-free morph between two drawings of an n-vertex planar graph G with $$\mathcal {O}(n)$$ O ( n ) morphing steps, and using the third dimension the number of steps can be reduced to $$\mathcal {O}(\log n)$$ O ( log n ) for an n-vertex tree [Arseneva et al. 2019]. However, these morphs do not bound one practical parameter, the resolution. Can the number of steps be reduced substantially by using the third dimension while keeping the resolution bounded throughout the morph? We present a 3D crossing-free morph between two planar grid drawings of an n-vertex tree in $$\mathcal {O}(\sqrt{n} \log n)$$ O ( n log n ) morphing steps. Each intermediate drawing lies in a 3D grid of polynomial volume.

Let M be a two-dimensional table with each cell weighted by a nonzero positive number. A StreamTable visualization of M represents the columns as non-overlapping vertical streams and the rows as horizontal stripes such that the intersection between a stream and a stripe is a rectangle with area equal to the weight of the corresponding cell. To avoid large wiggle of the streams, it is desirable to keep the consecutive cells in a stream to be adjacent. Let B be the smallest axis-aligned bounding box containing the StreamTable. Then the difference between the area of B and the sum of the weights is referred to as the excess area. We attempt to optimize various StreamTable aesthetics (e.g., minimizing excess area, or maximizing cell adjacencies in streams). If the row permutation is fixed and the row heights are given, then we give an O(rc)-time algorithm to optimizes these aesthetics, where r and c are the number of rows and columns, respectively. If the row permutation is fixed but the row heights can be chosen, then we discuss a technique to compute an aesthetic (but not necessarily optimal) StreamTable by solving a quadratically-constrained quadratic program, followed by iterative improvements. If the row heights are restricted to be integers, then we prove the problem to be NP-hard. If the row permutations can be chosen, then we show that it is NP-hard to find a row permutation that optimizes the area or adjacency aesthetics.

The art gallery problem is to find a set of guards who together can observe every point of the interior of a polygon P. We study a chromatic variant of the problem, where each guard is assigned one of k distinct colors. A chromatic guarding is said to be conflict-free if at least one of the colors seen by every point in P is unique (i.e., each point in P is seen by some guard whose color appears exactly once among the guards visible to that point). In this paper, we consider vertex-to-point guarding, where the guards are placed on vertices of P, and they observe every point of the interior of P. The vertex-to-point conflict-free chromatic art gallery problem is to find a colored-guard set such that (i) guards are placed on P’s vertices, and (ii) any point in P can see a guard of a unique color among all the visible guards. In this paper, it is shown that determining whether there exists a conflict-free chromatic vertex-guard set for a polygon with holes is NP-hard when the number of colors is $$k=2$$ k = 2 .

Motivated by the k-center problem in location analysis, we consider the polygon burning (PB) problem: Given a polygonal domain $$P$$ P with h holes and n vertices, find a set S of k vertices of $$P$$ P that minimizes the maximum geodesic distance from any point in $$P$$ P to its nearest vertex in S. Alternatively, viewing each vertex in S as a site to start a fire, the goal is to select S such that fires burning simultaneously and uniformly from S, restricted to $$P$$ P , consume $$P$$ P entirely as quickly as possible. We prove that PB is NP-hard when k is arbitrary. We show that the discrete k-center of the vertices of $$P$$ P under the geodesic metric on $$P$$ P provides a 2-approximation for PB, resulting in an $$O(n^2 \log n + hkn \log n)$$ O ( n 2 log n + h k n log n ) -time 3-approximation algorithm for PB. Lastly, we define and characterize a new type of polygon, the sliceable polygon. A sliceable polygon is a convex polygon that contains no Voronoi vertex from the Voronoi diagram of its vertices. We give a dynamic programming algorithm to solve PB exactly on a sliceable polygon in $$O(kn^2)$$ O ( k n 2 ) time.

Given a set P of n points in the plane, a unit-disk graph $$G_{r}(P)$$ G r ( P ) with respect to a parameter r is an undirected graph whose vertex set is P such that an edge connects two points $$p, q \in P$$ p , q ∈ P if the (Euclidean) distance between p and q is at most r (the weight of the edge is 1 in the unweighted case and is the distance between p and q in the weighted case). Given a value $$\lambda > 0$$ λ > 0 and two points s and t of P, we consider the following reverse shortest path problem: Compute the smallest r such that the shortest path length between s and t in $$G_r(P)$$ G r ( P ) is at most $$\lambda $$ λ . In this paper, we study the weighted case and present an $$O(n^{{5}/{4}} \log ^{5/2} n)$$ O ( n 5 / 4 log 5 / 2 n ) time algorithm. We also consider the $$L_1$$ L 1 version of the problem where the distance of two points is measured by the $$L_1$$ L 1 metric; we solve the problem in $$O(n \log ^3 n)$$ O ( n log 3 n ) time for both the unweighted and weighted cases.

In this paper, we investigate the complexity of the Maximum Happy Set problem on subclasses of co-comparability graphs. For a graph G and its vertex subset S, a vertex $$v \in S$$ v ∈ S is happy if all v’s neighbors in G are contained in S. Given a graph G and a non-negative integer k, Maximum Happy Set is the problem of finding a vertex subset S of G such that $$|S| = k$$ | S | = k and the number of happy vertices in S is maximized. In this paper, we first show that Maximum Happy Set is NP-hard even for co-bipartite graphs. We then give an algorithm for n-vertex interval graphs whose running time is $$O(k^2n^2)$$ O ( k 2 n 2 ) ; this improves the best known running time $$O(kn^8)$$ O ( k n 8 ) for interval graphs. We also design an algorithm for n-vertex permutation graphs whose running time is $$O(k^3n^2)$$ O ( k 3 n 2 ) . These two algorithmic results provide a nice contrast to the fact that Maximum Happy Set remains NP-hard for chordal graphs, comparability graphs, and co-comparability graphs.

Planar graphs can be represented as intersection graphs of different types of geometric objects in the plane, e.g., circles (Koebe, 1936), line segments (Chalopin & Gonçalves, SODA 2009), L-shapes (Gonçalves et al., SODA 2018). For general graphs, however, even deciding whether such representations exist is often $$\mathsf{NP}$$ NP -hard. We consider apex graphs, i.e., graphs that can be made planar by removing one vertex from them. We show, somewhat surprisingly, that deciding whether geometric representations exist for apex graphs is $$\mathsf{NP}$$ NP -hard.More precisely, we show that for every positive integer g, recognizing every graph class $$\mathscr {G}$$ G such that $${\textsc {Pure}}\text {-}{\textsc {2}}\text {-}{\textsc {Dir}}\subseteq \mathscr {G}\subseteq {\textsc {1}}\text {-}{\textsc {String}}$$ P U R E - 2 - D I R ⊆ G ⊆ 1 - S T R I N G is $$\mathsf{NP}$$ NP -hard, even if the inputs are apex graphs of girth at least g. Here, $${\textsc {Pure}}\text {-}{\textsc {2}}\text {-}{\textsc {Dir}}$$ P U R E - 2 - D I R is the class of intersection graphs of axis-parallel line segments (where intersections are allowed only between horizontal and vertical segments), and $${\textsc {1}}\text {-}{\textsc {String}}$$ 1 - S T R I N G is the class of intersection graphs of simple curves (where two curves cross at most once) in the plane. This partially answers an open question raised by Kratochvíl & Pergel (COCOON, 2007).Most known $$\textsf {NP}$$ NP -hardness reductions for these problems are from variants of 3-SAT. We reduce from the Planar Hamiltonian Path Completion problem, which uses the more intuitive notion of planarity. As a result, our proof is much simpler and encapsulates several classes of geometric graphs.

The L(p, q)-Edge-Labelling problem is the edge variant of the well-known L(p, q)-Labelling problem. It is equivalent to the L(p, q)-Labelling problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p, q)-Edge-Labelling was only partially classified in the literature. We complete this study for all $$p,q\ge 0$$ p , q ≥ 0 by showing that whenever $$(p,q)\ne (0,0)$$ ( p , q ) ≠ ( 0 , 0 ) , the L(p, q)-Edge-Labelling problem is NP-complete. We do this by proving that for all $$p,q\ge 0$$ p , q ≥ 0 except $$p=q=0$$ p = q = 0 , there is an integer k so that L(p, q)-Edge-k-Labelling is NP-complete.

We analyze the computational complexity of motion planning through local “input/output” gadgets with separate entrances and exits, and a subset of allowed traversals from entrances to exits, each of which changes the state of the gadget and thereby the allowed traversals. We study such gadgets in the zero-, one-, and two-player settings, in particular extending past motion-planning-through-gadgets work [3, 4] to zero-player games for the first time, by considering “branchless” connections between gadgets that route every gadget’s exit to a unique gadget’s entrance. Our complexity results include containment in L, NL, P, NP, and PSPACE; as well as hardness for NL, P, NP, and PSPACE. We apply these results to show PSPACE-completeness for certain mechanics in Factorio, [the Sequence], and a restricted version of Trainyard, improving the result of [1]. This work strengthens prior results on switching graphs, ARRIVAL [5], and reachability switching games [6].

A Boolean function $$f:\{0,1\}^n\rightarrow \{0,1\}$$ f : { 0 , 1 } n → { 0 , 1 } is k-linear if it returns the sum (over the binary field $$F_2$$ F 2 ) of k coordinates of the input. In this paper, we study property testing of the classes k-Linear, the class of all k-linear functions, and k-Linear $$^*$$ ∗ , the class $$\cup _{j=0}^kj$$ ∪ j = 0 k j -Linear. We give a non-adaptive distribution-free two-sided $$\epsilon $$ ϵ -tester for k-Linear that makes $$O\left( k\log k+\frac{1}{\epsilon }\right) $$ O k log k + 1 ϵ queries. This matches the lower bound known from the literature.We then give a non-adaptive distribution-free one-sided $$\epsilon $$ ϵ -tester for k-Linear $$^*$$ ∗ that makes the same number of queries and show that any non-adaptive uniform-distribution one-sided $$\epsilon $$ ϵ -tester for k-Linear must make at least $$ \tilde{\varOmega }(k)\log n+\varOmega (1/\epsilon )$$ Ω ~ ( k ) log n + Ω ( 1 / ϵ ) queries. The latter bound, almost matches the upper bound $$O(k\log n+1/\epsilon )$$ O ( k log n + 1 / ϵ ) known from the literature. We then show that any adaptive uniform-distribution one-sided $$\epsilon $$ ϵ -tester for k-Linear must make at least $$\tilde{\varOmega }(\sqrt{k})\log n+\varOmega (1/\epsilon )$$ Ω ~ ( k ) log n + Ω ( 1 / ϵ ) queries.

Traditional online algorithms are designed to make decisions online in the face of uncertainty to perform well in comparison with the optimal offline algorithm for the worst-case inputs. On the other hand, machine learning algorithms try to extrapolate the pattern from the past inputs to predict the future and take decisions online on basis of the predictions to perform well for the average-case inputs. There have been recent studies to augment traditional online algorithms with machine learning oracles to get better performance for all the possible inputs. The machine learning augmented online algorithms perform provably better than the traditional online algorithms when the error of the machine learning oracle is low for the worst-case inputs and all other average-case inputs.In this paper, we integrate the advantages of the traditional online algorithms and the machine learning algorithms in the context of a novel variant of the ski rental problem. Firstly, we propose the ski rental problem with a discount: in this problem, the rent of the ski, instead of being fixed over time, varies as a function of time. Secondly, we discuss the design and performance evaluation of the online algorithms with machine learning advice to solve the ski rental problem with a discount. Finally, we extend this study to the situation where multiple independent machine learning advice is available. This algorithm design framework motivates to redesign of several online algorithms by augmenting them with one or more machine learning oracles to improve the performance.

Given a graph $$G = (V,E)$$ G = ( V , E ) , a threshold function $$t~ :~ V \rightarrow \mathbb {N}$$ t : V → N and an integer k, we study the Harmless Set problem, where the goal is to find a subset of vertices $$S \subseteq V$$ S ⊆ V of size at least k such that every vertex v in V has less than t(v) neighbors in S. We enhance our understanding of the problem from the viewpoint of parameterized complexity. Our focus lies on parameters that measure the structural properties of the input instance. We show that the Harmless Set problem with majority thresholds is W[1]-hard when parameterized by the treewidth of the input graph. On the positive side, we obtain a fixed-parameter tractable algorithm for the problem with respect to neighbourhood diversity.

A T-graph (a special case of a chordal graph) is the intersection graph of connected subtrees of a suitable subdivision of a fixed tree T. We deal with the isomorphism problem for T-graphs which is GI-complete in general – when T is a part of the input and even a star. We prove that the T-graph isomorphism problem is in FPT when T is the fixed parameter of the problem. This can equivalently be stated that isomorphism is in FPT for chordal graphs of (so-called) bounded leafage. While the recognition problem for T-graphs is not known to be in FPT wrt. T, we do not need a T-representation to be given (a promise is enough). To obtain the result, we combine a suitable isomorphism-invariant decomposition of T-graphs with the classical tower-of-groups algorithm of Babai, and reuse some of the ideas of our isomorphism algorithm for $$S_d$$ S d -graphs [MFCS 2020].

Chordal graphs are intersection graphs of subtrees of a tree, while interval graphs are intersection graphs of subpaths of a path. Undirected path graphs are an intermediate class of graphs, defined as the intersection graphs of paths of a tree. It is known that Dominating Set, Connected Dominating Set, and Steiner Tree are $$\mathsf {W}[2]$$ W [ 2 ] -hard on chordal graphs, when parameterized by the size of the solution, and are polynomial-time solvable on interval graphs. As for the undirected path graphs, all these problems are known to be $$\mathsf {NP}$$ NP -complete, and when parameterized by the size of the solution, no classification in the parameterized complexity theory is known apart from the trivial $$\mathsf {XP}$$ XP classification. We prove that Dominating Set, Connected Dominating Set, and Steiner Tree are $$\mathsf {FPT}$$ FPT for undirected path graphs when parameterized by the size of the solution, and that they continue to be $$\mathsf {FPT}$$ FPT for general chordal graphs when parameterized by the size of the solution plus the vertex leafage of the graph, provided a tree model with optimal vertex leafage is given. We show a relation between the parameterization of Min-LC-VSP problems by the leafage of the graph versus the vertex leafage plus the size of a solution.

Our work is motivated by the challenges presented in preparing arrays of atoms for use in quantum simulation [10]. The recently-developed process of loading atoms into traps results in approximately half of the traps being filled. To consolidate the atoms so that they form a dense and regular arrangement, such as all locations in a grid, atoms are rearranged using moving optical tweezers. Time is of the essence, as the longer that the process takes and the more that atoms are moved, the higher the chance that atoms will be lost in the process. Viewed as a problem on graphs, we wish to solve the problem of reconfiguring one arrangement of tokens (representing atoms) to another using as few moves as possible. Because the problem is NP-complete on general graphs as well as on grids [4], we focus on the parameterized complexity for various parameters, considering both undirected and directed graphs, and tokens with and without labels. For unlabelled tokens, the problem is fixed-parameter tractable when parameterized by the number of tokens, the number of moves, or the number of moves plus the number of vertices without tokens in either the source or target configuration, but intractable when parameterized by the difference between the number of moves and the number of differences in the placement of tokens in the source and target configurations. When labels are added to tokens, however, most of the tractability results are replaced by hardness results.

We consider the problem of controlling the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusion where each node has a threshold that measures the node’s resistance to the contagion. We study the parameterized complexity of the problem: Given a network, a set of initially contaminated nodes, and two integers k and $$\ell $$ ℓ , is it possible to limit the diffusion to at most k other nodes of the network by immunizing at most $$\ell $$ ℓ nodes? We consider several parameters associated with the input, including the bounds k and $$\ell $$ ℓ , the maximum node degree $$\varDelta $$ Δ , the treewidth, and the neighborhood diversity of the network. We first give W[1] or W[2]-hardness results for each of the considered parameters. Then we give fixed-parameter algorithms for some parameter combinations.

Given a graph $$G=(V,E)$$ G = ( V , E ) and an integer k, the Minimum Membership Dominating Set (MMDS) problem seeks to find a dominating set $$S \subseteq V$$ S ⊆ V of G such that for each $$v \in V$$ v ∈ V , $$|N[v] \cap S|$$ | N [ v ] ∩ S | is at most k. We investigate the parameterized complexity of the problem and obtain the following results about MMDS: 1. W[1]-hardness of the problem parameterized by the pathwidth (and thus, treewidth) of the input graph. 2. W[1]-hardness parameterized by k on split graphs. 3. An algorithm running in time $$2^{\mathcal {O}(\mathbf{vc} )} |V|^{\mathcal {O}(1)}$$ 2 O ( vc ) | V | O ( 1 ) , where $$\mathbf{vc} $$ vc is the size of a minimum-sized vertex cover of the input graph. 4. An ETH-based lower bound showing that the algorithm mentioned in the previous item is optimal.

Popular matchings have been intensively studied recently as a relaxed concept of stable matchings. By applying the concept of popular matchings to branchings in directed graphs, Kavitha et al. introduced popular branchings. In a directed graph $$G=(V_G,E_G)$$ G = ( V G , E G ) , each vertex has preferences over its incoming edges. For branchings $$B_1$$ B 1 and $$B_2$$ B 2 in G, a vertex $$v\in V_G$$ v ∈ V G prefers $$B_1$$ B 1 to $$B_2$$ B 2 if v prefers its incoming edge of $$B_1$$ B 1 to that of $$B_2$$ B 2 , where having an arbitrary incoming edge is preferred to having none, and $$B_1$$ B 1 is more popular than $$B_2$$ B 2 if the number of vertices that prefer $$B_1$$ B 1 is greater than the number of vertices that prefer $$B_2$$ B 2 . A branching B is called a popular branching if there is no branching more popular than B. Kavitha et al. proposed an algorithm for finding a popular branching when the preferences of each vertex are given by a strict partial order. The validity of this algorithm is proved by utilizing classical theorems on the duality of weighted arborescences. In this paper, we generalize popular branchings to weighted popular branchings in vertex-weighted directed graphs in the same manner as weighted popular matchings by Mestre. We give an algorithm for finding a weighted popular branching, which extends the algorithm of Kavitha et al., when the preferences of each vertex are given by a total preorder and the weights satisfy certain conditions. Our algorithm includes elaborated procedures resulting from the vertex-weights, and its validity is proved by extending the argument of the duality of weighted arborescences.

Consider the following natural variation of the degree realization problem. Let $$G=(V, E)$$ G = ( V , E ) be a simple undirected graph of order n. Let $$f \in \mathbb {R}_{\ge 0}^{n}$$ f ∈ R ≥ 0 n be a vector of vertex requirements, and let $$w\in \mathbb {R}_{\ge 0}^{n}$$ w ∈ R ≥ 0 n be a vector of provided services at the vertices. Then w satisfies f on G if the constraints $$\sum _{j \in N(i)} w_j = f_i$$ ∑ j ∈ N ( i ) w j = f i are satisfied for all $$i \in V$$ i ∈ V , where N(i) denotes the neighborhood of i. Given a requirements vector f, the Weighted Graph Realization problem asks for a suitable graph G and a vector w of provided services that satisfy f on G.In [7] it is observed that any requirement vector where n is even can be realized. If n is odd, the problem becomes much harder. For the unsolved cases, the decision of whether f is realizable or not can be formulated as whether $$f_n$$ f n (the largest requirement) lies within certain intervals. In [5] some intervals are identified where f can be realized, and their complements form $$\frac{n-3}{2}$$ n - 3 2 connected intervals (“unknown domains”) which we give odd indices $$k = 1,3,\ldots , n-4$$ k = 1 , 3 , … , n - 4 . The unknown domain for $$k=1$$ k = 1 is shown to be unrealizable.Our main result presents structural properties that a graph must have if it realizes a vector in one of these unknown domains for $$k \ge 3$$ k ≥ 3 . The unknown domains are characterized by inequalities which we translate to graph properties. Our analysis identifies several realizable sub-intervals, and shows that each of the unknown domains has at least one sub-interval that cannot be realized.

We propose a new representation of k-partite, k-uniform hypergraphs (i.e. a hypergraph with a partition of vertices into k parts such that each hyperedge contains exactly one vertex of each type; we call them k-hypergraphs for short) by a finite set P of points in $$\mathbb {R}^d$$ R d and a parameter $$\ell \le d-1$$ ℓ ≤ d - 1 . Each point in P is covered by $$k={d\atopwithdelims ()\ell }$$ k = d ℓ many axis-aligned affine $$\ell $$ ℓ -dimensional subspaces of $$\mathbb {R}^d$$ R d , which we call $$\ell $$ ℓ -subspaces for brevity. We interpret each point in P as a hyperedge that contains each of the covering $$\ell $$ ℓ -subspaces as a vertex. The class of $$(d,\ell )$$ ( d , ℓ ) -hypergraphs is the class of k-hypergraphs that can be represented in this way, where $$k={d\atopwithdelims ()\ell }$$ k = d ℓ . The resulting classes of hypergraphs are fairly rich: Every k-hypergraph is a $$(k,k-1)$$ ( k , k - 1 ) -hypergraph. On the other hand, $$(d,\ell )$$ ( d , ℓ ) -hypergraphs form a proper subclass of the class of all $$d\atopwithdelims ()\ell $$ d ℓ -hypergraphs for $$\ell <d-1$$ ℓ < d - 1 .In this paper we give a natural structural characterization of $$(d,\ell )$$ ( d , ℓ ) -hypergraphs based on vertex cuts. This characterization leads to a polynomial-time recognition algorithm that decides for a given $$d\atopwithdelims ()\ell $$ d ℓ -hypergraph whether or not it is a $$(d,\ell )$$ ( d , ℓ ) -hypergraph and that computes a representation if existing. We assume that the dimension d is constant and that the partitioning of the vertex set is prescribed.

We introduce a variant of the graph coloring problem, which we denote as Budgeted Coloring Problem (BCP). Given a graph G, an integer c and an ordered list of integers $$\{b_1, b_2, \ldots , b_c\}$$ { b 1 , b 2 , … , b c } , BCP asks whether there exists a proper coloring of G where the i-th color is used to color at most $$b_i$$ b i many vertices. This problem generalizes two well-studied graph coloring problems, Bounded Coloring Problem (BoCP) and Equitable Coloring Problem (ECP), and as in the case of other coloring problems, BCP is NP-hard even for constant values of c. So we study BCP under the paradigm of parameterized complexity, particularly with respect to (structural) parameters that specify how far (the deletion distance) the input graph is from a tractable graph class. We show that BCP is FPT (fixed-parameter tractable) parameterized by the vertex cover size. This generalizes a similar result for ECP and immediately extends to the BoCP, which was earlier not known. We show that BCP is polynomial time solvable for cluster graphs generalizing a similar result for ECP. However, we show that BCP is FPT, but unlikely to have polynomial kernel, when parameterized by the deletion distance to clique, contrasting the linear kernel for ECP for the same parameter. While the BoCP is known to be polynomial time solvable on split graphs, we show that BCP is NP-hard on split graphs. We also show that BCP is NP-hard on co-cluster graphs, contrasting the polynomial time algorithm for ECP and BoCP. Finally we present an $$\mathcal {O}^*(2^{|V(G)|})$$ O ∗ ( 2 | V ( G ) | ) algorithm for the BCP, generalizing the known algorithm with a similar bound for the standard chromatic number.

We study counting problems for several types of orientations of chordal graphs: source-sink-free orientations, sink-free orientations, acyclic orientations, and bipolar orientations, and, for the latter two, we also present linear-time uniform samplers. Counting sink-free, acyclic, or bipolar orientations are known to be #P-complete for general graphs, motivating our study on a restricted, yet well-studied, graph class. Our main focus is source-sink-free orientations, a natural restricted version of sink-free orientations related to strong orientations, which we introduce in this work. These orientations are intriguing, since despite their similarity, currently known FPRAS and sampling techniques (such as Markov chains or sink-popping) that apply to sink-free orientations do not seem to apply to source-sink-free orientations. We present fast polynomial-time algorithms counting these orientations on chordal graphs. Our approach combines dynamic programming with inclusion-exclusion (going two levels deep for source-sink-free orientations and one level for sink-free orientations) throughout the computation. Dynamic programming counting algorithms can be typically used to produce a uniformly random sample. However, due to the negative terms of the inclusion-exclusion, the typical approach to obtain a polynomial-time sampling algorithm does not apply in our case. Obtaining such an almost uniform sampling algorithm for source-sink-free orientations in chordal graphs remains an open problem.Little is known about counting or sampling of acyclic or bipolar orientations, even on restricted graph classes. We design efficient (linear-time) exact uniform sampling algorithms for these orientations on chordal graphs. These algorithms are a byproduct of our counting algorithms, but unlike in other works that provide dynamic-programming-based samplers, we produce a random orientation without computing the corresponding count, which leads to a faster running time than the counting algorithm (since it avoids manipulation of large integers).

For a constant $$t \ge 1$$ t ≥ 1 , a t-spanner of a connected graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most t times its distance in G. We address two problems on spanners: the minimum t-spanner problem (MinS $$_t$$ t ), and a minimization version of the tree t-spanner problem (TreeS $$_t$$ t ). MinS $$_t$$ t seeks a t-spanner with minimum number of edges. TreeS $$_t$$ t is a decision problem concerning the existence of a t-spanner that is a tree. The concept of spanner was introduced by Peleg & Ullman in 1989, in a context regarding the construction of optimal synchronizers for the hypercube. MinS $$_t$$ t is known to be $$\textsc {NP}$$ NP -hard for every $$t \ge 2$$ t ≥ 2 even on some bounded-degree graphs. TreeS $$_t$$ t is polynomially solvable for $$t=2$$ t = 2 and $$\textsc {NP}$$ NP -complete for $$t \ge 4$$ t ≥ 4 , but its complexity for $$t=3$$ t = 3 remains open.We investigate both MinS $$_3$$ 3 and TreeS $$_2$$ 2 on the class of subcubic graphs. We prove that MinS $$_3$$ 3 can be solved in polynomial time, using a similar technique as the one used by Cai & Keil (1994) for $$t=2$$ t = 2 . This result also gives an alternative algorithm to solve TreeS $$_3$$ 3 in polynomial time. Additionally, we study TreeS $$_2$$ 2 from a polyhedral point-of-view and show a complete linear characterization of the associated polytope. This result, interesting on its own right, gives a polynomial-time algorithm to solve a natural minimization version of TreeS $$_2$$ 2 on subcubic graphs with costs assigned to its edges.

Bundling crossings is a strategy which can enhance the readability of graph drawings. In this paper we consider bundlings for families of pseudosegments, i.e., simple curves such that any two have share at most one point at which they cross. Our main result is that there is a polynomial-time algorithm to compute an 8-approximation of the bundled crossing number of such instances (up to adding a term depending on the facial structure). This 8-approximation also holds for bundlings of good drawings of graphs. In the special case of circular drawings the approximation factor is 8 (no extra term), this improves upon the 10-approximation of Fink et al. [6]. We also show how to compute a $$\frac{9}{2}$$ 9 2 -approximation when the intersection graph of the pseudosegments is bipartite.

For a graph $$G=(V,E)$$ G = ( V , E ) , a collection $$\mathcal {P}$$ P of vertex-disjoint (simple) paths is called a path cover of G if every vertex $$v\in V$$ v ∈ V is contained in exactly one path of $$\mathcal {P}$$ P . The Path Cover problem (PC for short) is to find a minimum cardinality path cover of G. In this paper, we introduce generalizations of PC, where each path is associated with a weight (cost or profit). Our problem, Minimum (Maximum) Weighted Path Cover (MinPC (MaxPC)), is defined as follows: Let $$U=\{0,1,\dots ,n-1\}$$ U = { 0 , 1 , ⋯ , n - 1 } . Given a graph $$G=(V,E)$$ G = ( V , E ) and a weight function $$f:U\rightarrow \mathbb {R}\cup \{+\infty , -\infty \}$$ f : U → R ∪ { + ∞ , - ∞ } , which defines a weight for each path in its length, MinPC (MaxPC) is to find a path cover $$\mathcal {P}$$ P of G such that the total weight of the paths in $$\mathcal {P}$$ P is minimized (maximized). Let L be a subset of U, and $$P^{L}$$ P L be the set of paths such that each path is of length $$\ell \in L$$ ℓ ∈ L . We especially consider $$\textsf {Min}P^{L}\textsf {PC}$$ Min P L PC with 0–1 cost, i.e., the cost function is $$f(\ell ) = 1$$ f ( ℓ ) = 1 if $$\ell \in L$$ ℓ ∈ L ; otherwise $$f(\ell ) = 0$$ f ( ℓ ) = 0 . We also consider $$\textsf {Max}P^{L}\textsf {PC}$$ Max P L PC with $$f(\ell ) = \ell +1$$ f ( ℓ ) = ℓ + 1 , if $$\ell \in L$$ ℓ ∈ L ; otherwise $$f(\ell ) = 0$$ f ( ℓ ) = 0 . That is, $$\textsf {Max}P^{L}\textsf {PC}$$ Max P L PC is to maximize the number of vertices contained in the paths with length $$\ell \in L$$ ℓ ∈ L in a path cover. In this paper, we first show that $$\textsf {Min}P^{\{0,1,2\}}\textsf {PC}$$ Min P { 0 , 1 , 2 } PC is NP-hard for planar bipartite graphs of maximum degree three. This implies that (i) for any constant $$\sigma \ge 1$$ σ ≥ 1 , there is no polynomial-time approximation algorithm with approximation ratio $$\sigma $$ σ for $$\textsf {Min}P^{\{0,1,2\}}\textsf {PC}$$ Min P { 0 , 1 , 2 } PC unless P $$=$$ = NP, and (ii) $$\textsf {Max}P^{\{3,\dots ,n-1\}}\textsf {PC}$$ Max P { 3 , ⋯ , n - 1 } PC is NP-hard for the same graph class. Next, (iii) we present a polynomial-time algorithm for $$\textsf {Min}P^{\{0,1,\dots ,k\}}\textsf {PC}$$ Min P { 0 , 1 , ⋯ , k } PC on graphs with bounded treewidth for a fixed k. Lastly, (iv) we present a 4-approximation algorithm for $$\textsf {Max}P^{\{3,\dots ,n-1\}}\textsf {PC}$$ Max P { 3 , ⋯ , n - 1 } PC , which becomes a 2.5-approximation for subcubic graphs.

We study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessellation approximates the 2-dimensional space, we study three types of shortest paths: a weighted shortest path $$ SP_w (s,t) $$ S P w ( s , t ) , which is a shortest path from s to t in the space; a weighted shortest vertex path $$ SVP_w (s,t) $$ S V P w ( s , t ) , which is a shortest path where the vertices of the path are vertices of the tessellation; and a weighted shortest grid path $$ SGP_w (s,t) $$ S G P w ( s , t ) , which is a shortest path whose edges are edges of the tessellation. The ratios $$ \frac{\Vert SGP_w (s,t)\Vert }{\Vert SP_w (s,t)\Vert } $$ ‖ S G P w ( s , t ) ‖ ‖ S P w ( s , t ) ‖ , $$ \frac{\Vert SVP_w (s,t)\Vert }{\Vert SP_w (s,t)\Vert } $$ ‖ S V P w ( s , t ) ‖ ‖ S P w ( s , t ) ‖ , $$ \frac{\Vert SGP_w (s,t)\Vert }{\Vert SVP_w (s,t)\Vert } $$ ‖ S G P w ( s , t ) ‖ ‖ S V P w ( s , t ) ‖ provide estimates on the quality of the approximation.Given any arbitrary weight assignment to the faces of a triangular tessellation, we prove upper and lower bounds on the estimates that are independent of the weight assignment. Our main result is that $$ \frac{\Vert SGP_w (s,t)\Vert }{\Vert SP_w (s,t)\Vert } = \frac{2}{\sqrt{3}} \approx 1.15 $$ ‖ S G P w ( s , t ) ‖ ‖ S P w ( s , t ) ‖ = 2 3 ≈ 1.15 in the worst case, and this is tight.