Algorithms and Discrete Applied Mathematics

In the classical online bin packing problem, items arriving one by one with a given size not greater than 1 must be packed into unit-capacity bins such that the total size of items packed in a bin does not exceed its capacity; the objective is to minimize the total number of used bins. In this paper, we allow the total size of items packed in a bin to exceed the capacity, and there is a cost for each bin that depends on the total size of items assigned to it; in particular, overloading a bin, i.e., exceeding the capacity of a bin, comes at a prescribed cost. The corresponding goal is to minimize the total cost corresponding to the used bins. We pay 1 to open a bin with capacity 1, and we additionally pay c for each unit with which the bin is overloaded, i.e, the overload cost is linear in the size of the overload.For each c, we present lower bounds on the competitive ratio achievable by deterministic algorithms. Further, we give an algorithm, called First-Fit Algorithm with Fixed Overload (FFO) that achieves the best possible competitive ratio for $$c\le 3/2$$ c ≤ 3 / 2 . Furthermore, we sketch how the lower bounds apply to more general convex cost functions.

We investigate the problem of scheduling trains to minimize max-stretch, where the stretch suffered by a train is the ratio of its actual finishing time to its minimum possible finishing time. This metric is presumably more appropriate for train scheduling because it is fairer. Our target network, introduced in [11], is an in-comb: a unidirectional railway line with equidistant stations, each initially having at most one train; in addition, there can be at most one train poised to enter each station. A train takes unit time to enter a station or to move from one to the next. Trains must move to their destinations such that at any time there can be at most one train at any station and on the track connecting it to the next. We prove that minimizing max-stretch is NP-hard even on this simple network. We also give an O(1)-approximation algorithm. Our problem can also be interpreted as packet scheduling on in-comb, a special case of in-trees. Packet scheduling on general graphs and some special topologies has been studied earlier with different objective functions, e.g., makespan, flowtime, and max-delay, but there has been little work on max-stretch.

For a simple, undirected and connected graph $$G = (V, E)$$ G = ( V , E ) , a total Roman dominating function (TRDF) $$f : V \rightarrow \lbrace 0, 1, 2 \rbrace $$ f : V → { 0 , 1 , 2 } has the property that, every vertex u with $$f(u) = 0$$ f ( u ) = 0 is adjacent to at least one vertex v for which $$f(v) = 2$$ f ( v ) = 2 and the subgraph induced by the set of vertices labeled one or two has no isolated vertices. A total double Roman dominating function (TDRDF) on G is a function $$f : V \rightarrow \lbrace 0, 1, 2, 3 \rbrace $$ f : V → { 0 , 1 , 2 , 3 } such that for every vertex $$v \in V$$ v ∈ V if $$f(v) = 0$$ f ( v ) = 0 , then v has at least two neighbors x, y with $$f(x) = f(y) = 2$$ f ( x ) = f ( y ) = 2 or one neighbor w with $$f(w) = 3$$ f ( w ) = 3 , and if $$f(v) = 1$$ f ( v ) = 1 , then v must have at least one neighbor w with $$f(w) \ge 2$$ f ( w ) ≥ 2 and the subgraph induced by the set $$\{u_i : f(u_i) \ge 1\}$$ { u i : f ( u i ) ≥ 1 } has no isolated vertices. The weight of a T(D)RDF f is the sum $$f(V) = \sum _{v \in V}f(v)$$ f ( V ) = ∑ v ∈ V f ( v ) . The minimum total (double) Roman domination problem (MT(D)RDP) is to find a T(D)RDF of minimum weight of the input graph. In this article, we show that MTRDP and MTDRDP are polynomial time solvable for bounded treewidth graphs, chain graphs and threshold graphs. We design a $$2 (\ln (\varDelta - 0.5) + 1.5)$$ 2 ( ln ( Δ - 0.5 ) + 1.5 ) -approximation algorithm (APX-AL) for the MTRDP and $$3 (\ln (\varDelta - 0.5) + 1.5)$$ 3 ( ln ( Δ - 0.5 ) + 1.5 ) -APX-AL for the MTDRDP, where $$\varDelta $$ Δ is the maximum degree of G, and show that the same cannot have $$(1 - \delta ) \ln |V|$$ ( 1 - δ ) ln | V | ratio APX-AL for any $$\delta > 0$$ δ > 0 unless $$P = NP$$ P = N P . Finally, we show that MT(D)RDP is APX-hard for graphs with $$ \varDelta =5$$ Δ = 5 .

k orthogonal line center problem computes a set of k axis-parallel lines for a given set of points in 2D such that the maximum among the distance between each point to its nearest line is minimized. A 2-factor approximation algorithm and a $$(\frac{7}{4}, \frac{3}{2})$$ ( 7 4 , 3 2 ) bi-criteria approximation algorithm is presented for the problem. Both of them are deterministic approximation algorithms, having sub-quadratic running time and not based on linear programming.

For a graph $$G=(V,E)$$ G = ( V , E ) with no isolated vertices, a set $$D\subseteq V$$ D ⊆ V is called a semitotal dominating set of G if (i) D is a dominating set of G, and (ii) every vertex in D has another vertex in D at a distance at most two. The minimum cardinality of a semitotal dominating set of G is called the semitotoal domination number of G, and is denoted by $$\gamma _{t2}(G)$$ γ t 2 ( G ) . The Minimum Semitotal Domination problem is to find a semitotal dominating set of G of cardinality $$\gamma _{t2}(G)$$ γ t 2 ( G ) . In this paper, we present some algorithmic results on Semitotal Domination. We show that the decision version of the Minimum Semitotal Domination problem is NP-complete for circle graphs. On the positive side, we show that the Minimum Semitotal Domination problem is polynomial-time solvable for AT-free graphs. We also prove that the Minimum Semitotal Domination for AT-free graphs can be approximated within approximation ratio of 3 in linear-time. Our results answer the open questions posed by Galby et al. in their recent paper.

Graph burning runs on discrete time steps. The aim is to burn all the vertices in a given graph in the least number of time steps. This number is known to be the burning number of the graph. The spread of social influence, an alarm, or a social contagion can be modeled using graph burning. The less the burning number, the faster the spread.Optimal burning of general graphs is NP-Hard. There is a 3-approx-imation algorithm to burn general graphs where as better approximation factors are there for many sub classes. Here we study burning of grids; provide a lower bound for burning arbitrary grids and a 2-approximation algorithm for burning square grids. On the other hand, burning path forests, spider graphs, and trees with maximum degree three is already known to be NP-Complete. In this article we show burning problem to be NP-Complete on connected interval graphs.

In liquid democracy, each voter either votes herself or delegates her vote to some other voter. This gives rise to what is called a delegation graph. To decide the voters who eventually votes along with the subset of voters whose votes they give, we need to resolve the cycles in the delegation graph. This gives rise to the Resolve Delegation to MinMaxWeight problem where we need to find an acyclic sub-graph of the delegation graph such that the number of voters whose votes they give is bounded above by some integer $$\lambda $$ λ . Putting a cap on the number of voters whose votes a voter gives enable the system designer restrict the power of any individual voter. The Resolve Delegation to MinMaxWeight problem is already known to be $$\mathsf {NP}$$ NP -hard. In this paper we study the parameterized complexity of this problem. We show that Resolve Delegation to MinMaxWeight is para- $$\mathsf {NP}\text {-hard}$$ NP -hard with respect to parameters $$\lambda $$ λ , number of sink nodes and the maximum degree of the delegation graph. We also show that Resolve Delegation to MinMaxWeight is $$\mathsf {W[1]}$$ W [ 1 ] -hard even with respect to the treewidth of the delegation graph. We complement our negative results by exhibiting FPT algorithms with respect to some other parameters. We finally show that a related problem, which we call Resolve Fractional Delegation, is polynomial time solvable.

An acyclic r-coloring of a directed graph $$G=(V,E)$$ G = ( V , E ) is a partition of the vertex set V into r acyclic sets. The dichromatic number of a directed graph G is the smallest r such that G allows an acyclic r-coloring. For symmetric digraphs the dichromatic number equals the well-known chromatic number of the underlying undirected graph. This allows us to carry over the $$\text {W}[1]$$ W [ 1 ] -hardness and lower bounds for running times of the chromatic number problem parameterized by clique-width to the dichromatic number problem parameterized by directed clique-width. We introduce the first polynomial-time algorithm for the acyclic coloring problem on digraphs of constant directed clique-width. From a parameterized point of view our algorithm shows that the Dichromatic Number problem is in $$\text {XP}$$ XP when parameterized by directed clique-width and extends the only known structural parameterization by directed modular width for this problem. Furthermore, we apply defineability within monadic second order logic in order to show that Dichromatic Number problem is in $$\text {FPT}$$ FPT when parameterized by the directed clique-width and r. For directed co-graphs, which is a class of digraphs of directed clique-width 2, we even show a linear time solution for computing the dichromatic number.

Given a graph G and a positive integer k, the 2-Load Coloring problem is to check whether there is a 2-coloring $$f:V(G) \rightarrow \{r,b\}$$ f : V ( G ) → { r , b } of G such that for every $$i \in \{r,b\}$$ i ∈ { r , b } , there are at least k edges with both end vertices colored i. It is known that the problem is $$\mathsf {NP} $$ NP -complete even on special classes of graphs like regular graphs. Gutin and Jones (Inf Process Lett 114:446-449, 2014) showed that the problem is fixed-parameter tractable by giving a kernel with at most 7k vertices. Barbero et al. (Algorithmica 79:211-229, 2017) obtained a kernel with less than 4k vertices and O(k) edges, improving the earlier result.In this paper, we study the parameterized complexity of the problem with respect to structural graph parameters. We show that 2-Load Coloring cannot be solved in time $$f(w)n^{o(w)}$$ f ( w ) n o ( w ) , unless ETH fails and it can be solved in time $$n^{O(w)}$$ n O ( w ) , where n is the size of the input graph, w is the clique-width of the graph and f is an arbitrary function of w. Next, we consider the parameters distance to cluster graphs, distance to co-cluster graphs and distance to threshold graphs, which are weaker than the parameter clique-width and show that the problem is fixed-parameter tractable (FPT) with respect to these parameters. Finally, we show that 2-Load Coloring is $$\mathsf {NP} $$ NP -complete even on bipartite graphs and split graphs.

The Terrain Guarding problem, a variant of the famous Art Gallery problem, has garnered significant attention over the last two decades in Computational Geometry from the viewpoint of complexity and approximability. Both the continuous and discrete versions of the problem were shown to be NP-Hard in [14] and to admit a PTAS [8, 15]. The biggest unsolved question regarding this problem is if it is fixed-parameter tractable with respect to the size of the guard set. In this paper, we present two theorems that establish a relationship between a restricted case of the Annotated Terrain Guarding problem and the Clique Cover problem in chordal graphs. These theorems were proved in [11] for a special class of terrains called orthogonal terrains and were used to present a FPT algorithm with respect to the parameter that we require for Discrete Orthogonal Terrain Guarding in [2]. We hope that the results obtained in this paper can, in future work, be used to produce such an algorithm for Discrete Terrain Guarding.

A defensive alliance in a graph $$G=(V,E)$$ G = ( V , E ) is a set of vertices S satisfying the condition that every vertex $$v\in S$$ v ∈ S has at least as many neighbours (including itself) in S as it has in $$V{\setminus }S$$ V \ S . We consider the notion of local minimality in this paper. We are interested in locally minimal defensive alliance of maximum size. This problem is known to be NP-hard but its parameterized complexity remains open until now. We enhance our understanding of the problem from the viewpoint of parameterized complexity. The three main results of the paper are the following: (1) when the input graph happens to be a tree, Locally Minimal Strong Defensive Alliance can be solved in polynomial time, (2) Locally Minimal Defensive Alliance is fixed parameter tractable (FPT) when parametrized by neighbourhood diversity, and (3) Locally Minimal Defensive Alliance can be solved in polynomial time for graphs of bounded treewidth.

Given a set of points in the plane, we are interested in matching them with straight line segments. We focus on perfect (all points are matched) non-crossing (no two edges intersect) matchings. Apart from the well known MinMax variant, where the length of the longest edge is minimized, we extend work by looking into different optimization variants such as MaxMin, MinMin and MaxMax. We consider both the monochromatic and bichromatic versions of these problems and by employing diverse techniques we provide efficient algorithms for various input point configurations.

In this paper, we introduce the outlier detection problem in a set of uncertain points. We study two variants of the problems based upon the definition of the outlier. For a given positive integer $$k(<n)$$ k ( < n ) and a set $$\mathfrak {R}$$ R of n regions as the imprecise points, the first type of the outlier detection problem that we study is to locate $$n-k$$ n - k points on distinct regions, such that the size of the smallest axis-aligned bounding box (AABB), the diameter or the smallest enclosing circle (SEC) of the resulting points gets minimized. The uncertainty regions we study are squares or disks, and the excluded k regions are considered as outliers.We also study the covering versions in which the objectives of the SEC and the AABB problems are to find the smallest circle or axis-aligned bounding box, respectively, that covers the area of at least $$n-k$$ n - k regions.In the second-type of outliers, the outliers are those k regions that mostly reduce the uncertainty-induced gap between the lower bound and the upper bound on the size of the output. We give polynomial time algorithms for several variants of the mentioned problems, ranging in running time from $$O(n \log n)$$ O ( n log n ) to $$O(n^{5.5}\log n)$$ O ( n 5.5 log n ) .

We propose algorithms to compute the Minkowski sum of a set of convex polytopes in $$\mathbb {R}^d$$ R d . The input and output of the proposed algorithms are the face lattices of the input and output polytopes respectively. We first present the algorithm for the Minkowski sum of two convex polytopes. The time complexity of this algorithm is $$O(d^\omega nm)$$ O ( d ω n m ) where n and m are the face lattice sizes of the two input polytopes and $$\omega $$ ω is the matrix multiplication exponent ( $$\omega \sim 2.373$$ ω ∼ 2.373 ). Our algorithm for two summands is worst-case optimal for fixed d. We generalize this algorithm for r convex polytopes, say $$P_i$$ P i , $$1\le i \le r$$ 1 ≤ i ≤ r . The time complexity of this generalization is $$O(\min \{d^\omega \!N\!M,d^\omega \!r\prod |P_i|\})$$ O ( min { d ω N M , d ω r ∏ | P i | } ) where $$N = \sum |P_i|$$ N = ∑ | P i | is the total size of the face lattices of the r input polytopes and M is the size of the face lattice of their Minkowski sum $$P_1 \oplus \cdots \oplus P_r$$ P 1 ⊕ ⋯ ⊕ P r . Our algorithm for multiple summands is worst-case optimal for fixed $$d \ge 3$$ d ≥ 3 and $$r < d$$ r < d .

Let $$V = \{v_1, \dots , v_n\}$$ V = { v 1 , ⋯ , v n } be a set of n points in the plane and let $$x \in V$$ x ∈ V . An x-loop is a continuous closed curve not containing any point of V, except of passing exactly once through the point x. We say that two x-loops are non-homotopic if they cannot be transformed continuously into each other without passing through a point of V. For $$n=2$$ n = 2 , we give an upper bound $$2^{O(k)}$$ 2 O ( k ) on the maximum size of a family of pairwise non-homotopic x-loops such that every loop has fewer than k self-intersections and any two loops have fewer than k intersections. This result is inspired by a very recent result of Pach, Tardos, and Tóth who proved the upper bounds $$2^{16k^4}$$ 2 16 k 4 for the slightly different scenario when $$x\not \in V$$ x ∉ V .

A k-class domination coloring (k-cd-coloring) is a partition of the vertex set of a graph G into k independent sets $$V_1,\ldots ,V_k$$ V 1 , … , V k , where each $$V_i$$ V i is dominated by some vertex $$u_i$$ u i of G. The least integer k such that G admits a k-cd-coloring is called the cd-chromatic number, $$\chi _{cd}(G)$$ χ cd ( G ) , of G. A subset S of the vertex set of a graph G is called a subclique in G if $$d_G(x,y)\ne 2$$ d G ( x , y ) ≠ 2 for every $$x,y \in S$$ x , y ∈ S . The cardinality of a maximum subclique in G is called the subclique number, $$\omega _s(G)$$ ω s ( G ) , of G.In this paper, we present algorithms to compute an optimal cd-coloring and a maximum subclique of (i) trees with time complexity O(n) and (ii) co-bipartite graphs with time complexity $$O(n^{2.5})$$ O ( n 2.5 ) . This improves $$O(n^3)$$ O ( n 3 ) algorithms by Shalu et al. [2017, 2020]. In addition, we prove tight upper bounds for the subclique number of the class of (i) $$P_5$$ P 5 -free graphs and (ii) double-split graphs.

We study the cut vertex transit function of a connected graph G and discuss its betweenness properties. We show that the cut vertex transit function can be realized as the interval function of a block graph and derive an axiomatic characterization of the cut vertex transit function. We then consider a natural generalization to hypergraphs and identify necessary conditions.

Let $$D=(V,E)$$ D = ( V , E ) be a digraph and $$u ,v\in V(D)$$ u , v ∈ V ( D ) . The metric, maximum distance is defined by $$md(u,v)=\max \{\overrightarrow{d}(u,v), \overrightarrow{d}(v,u)\}$$ m d ( u , v ) = max { d → ( u , v ) , d → ( v , u ) } where $$\overrightarrow{d}(u,v)$$ d → ( u , v ) denote the length of a shortest directed $$u-v$$ u - v path in D. The relationship between the boundary-type sets of the lexicographic product of two digraphs and its factor graphs have been studied in this article.

Closed form expressions for the domination number of an $$n \times m$$ n × m grid have attracted significant attention, and an exact expression has been obtained in 2011 [7]. In this paper, we present our results on obtaining new lower bounds on the connected domination number of an $$n \times m$$ n × m grid. The problem has been solved for grids with up to 4 rows and with 6 rows and the best currently known lower bound for arbitrary m, n is [11]. Fujie [4] came up with a general construction for a connected dominating set of an $$n \times m$$ n × m grid. In this paper, we investigate whether this construction is indeed optimum. We prove a new lower bound of for arbitrary $$m,n \ge 4$$ m , n ≥ 4 .

A pseudoline arrangement graph is a planar graph induced by an embedding of a psuedoline arrangement. We give a simple criterion based on the degree sequence that says when a degree sequence will have a pseudoline arrangement graph as one of its realizations. We then study the eccentricities of vertices in such graphs.

Cops and robber is a well-studied two player pursuit-evasion game played on a graph. In this game, a set of cops, controlled by the first player, tries to capture the position of a robber, controlled by the second player. The cop number of a graph is the minimum number of cops required to capture the robber in the graph. We show that the cop number for butterfly networks and for solid grids is two.

The b-chromatic number b(G) of a graph G is the maximum k for which G has a proper vertex coloring using k colors such that each color class contains at least one vertex adjacent to a vertex of every other color classes. In this paper, we mainly investigate on one of the open problems given in [1]. As a consequence, we obtain an upper bound for the b-chromatic number of some powers of hypercube. This turns out to be the improvement of the existing bounds.

In this paper, we study the chromatic number for graphs with forbidden induced subgraphs. We improve the existing $$\chi $$ χ -binding functions for some subclasses of $$2K_2$$ 2 K 2 -free graphs, namely $$\{2K_2, H\}$$ { 2 K 2 , H } -free graphs where $$H\in \{HVN, K_5-e, K_1 + C_4\}$$ H ∈ { H V N , K 5 - e , K 1 + C 4 } . In addition, for $$p\ge 3$$ p ≥ 3 , we find the polynomial $$\chi $$ χ -binding functions for several subclasses of $$pK_2$$ p K 2 -free graphs, namely $$\{pK_2, H\}$$ { p K 2 , H } -free graphs where $$H\in \{HVN, gem, diamond, K_5-e, dart, C_4, K_1 + C_4, \overline{P_5}\}$$ H ∈ { H V N , g e m , d i a m o n d , K 5 - e , d a r t , C 4 , K 1 + C 4 , P 5 ¯ } .

A median of a profile of vertices (a sequence of vertices) on a connected graph is a vertex that minimizes the sum of the distances to the elements in the profile. The median function has as output the set of medians of a profile. Median function is an important consensus function for the location of a desirable facility in a network. The axiomatic characterization of the median function is studied by several authors on special classes of graphs like trees and median graphs. In this paper, we determine the median sets of all types of profiles and obtain an axiomatic characterization for the median function on block graphs, an immediate generalization of trees.

Let G be a graph with no isolated vertices. A k-coupon coloring of G is an assignment of k colors to the vertices of G such that every vertex contains vertices of all k colors in its neighborhood. The coupon chromatic number of G, denoted $$\chi _c (G)$$ χ c ( G ) , is the maximum k for which a k-coupon coloring exists. In this paper, we present an upper bound for the coupon chromatic number of Cartesian product of graphs G and H in terms of |V(G)| and |V(H)|. Further, we prove that if G and H are bipartite graphs then $$G\square H$$ G □ H has a coupon coloring with $$2\min \{\chi _c(G),\chi _c(H)\}$$ 2 min { χ c ( G ) , χ c ( H ) } colors. As consequences, for any positive integer n, we obtain the coupon chromatic number and total domination number of n-dimensional torus $$\mathop {\square }\limits _{i=1}^{n} C_{k_i}$$ □ i = 1 n C k i with some suitable conditions to each $$k_i$$ k i , which turns out to be a generalization of the result due to S. Gravier [Total domination number of grid graphs, Discrete Appl. Math. 121 (2002) 119–128]. Finally, for any $$r\ge 0, d\ge 2$$ r ≥ 0 , d ≥ 2 , we obtain the coupon coloring for the Hamming graph $$K_d\square K_d\square \cdots \square K_d$$ K d □ K d □ ⋯ □ K d ( $$2^r$$ 2 r times).

Betweenness centrality is a centrality measure based on the overall amount of shortest paths passing through a given vertex. A graph is betweenness-uniform if all its vertices have the same betweenness centrality. We study the properties of betweenness-uniform graphs. In particular, we show that every connected betweenness-uniform graph is either a cycle or a 3-connected graph. Also, we show that betweenness uniform graphs of high maximal degree have small diameter.

The concept of p-ordering for a prime p was introduced by Manjul Bhargava (in his PhD thesis) to develop a generalized factorial function over an arbitrary subset of integers. This notion of p-ordering provides a representation of polynomials modulo prime powers, and has been used to prove properties of roots sets modulo prime powers. We focus on the complexity of finding a p-ordering given a prime p, an exponent k and a subset of integers modulo $$p^k$$ p k .Our first algorithm gives a p-ordering for a set of size n in time $$\widetilde{\mathcal {O}}(nk\log p)$$ O ~ ( n k log p ) , where set is considered modulo $$p^k$$ p k . The subsets modulo $$p^k$$ p k can be represented concisely using the notion of representative roots (Panayi, PhD Thesis, 1995; Dwivedi et al., ISSAC, 2019); a natural question is, can we find a p-ordering more efficiently given this succinct representation. Our second algorithm achieves precisely that, we give a p-ordering in time $$\widetilde{\mathcal {O}}(d^2k\log p + nk \log p + nd)$$ O ~ ( d 2 k log p + n k log p + n d ) , where d is the size of the succinct representation and n is the required length of the p-ordering. Another contribution is to compute the structure of roots sets for prime powers $$p^k$$ p k , when k is small. The number of root sets have been given before (Dearden and Metzger, Eur. J. Comb., 1997; Maulick, J. Comb. Theory, Ser. A, 2001), we explicitly describe all the root sets for $$k\le 4$$ k ≤ 4 .

In the multiway cut problem we are given a weighted undirected graph $$G=(V,E)$$ G = ( V , E ) and a set $$T \subseteq V$$ T ⊆ V of k terminals. The goal is to find a minimum weight set of edges $$E' \subseteq E$$ E ′ ⊆ E with the property that by removing $$E'$$ E ′ from G all the terminals become disconnected. In this paper we present a simple local search approximation algorithm for the multiway cut problem with approximation ratio $$2-\frac{2}{k}$$ 2 - 2 k . We present an experimental evaluation of the performance of our local search algorithm and show that it greatly outperforms the isolation heuristic of Dalhaus et al. and it has similar performance as the much more complex algorithms of Calinescu et al., Sharma and Vondrak, and Buchbinder et al. which have the currently best known approximation ratios for this problem.

This paper is concerned with a new variant of Traditional Bin Packing (TBP) called Priority-Based Bin Packing with Subset Constraints (PBBP-SC). In a TBP instance, we are given a collection of items $$\{a_{1}, a_{2}, \ldots a_{n}\}$$ { a 1 , a 2 , … a n } , with $$a_{i} \in (0, 1)$$ a i ∈ ( 0 , 1 ) and a collection of unit-size bins $$\{B_{1}, B_{2}, \ldots , B_{m} \}$$ { B 1 , B 2 , … , B m } . One problem associated with TBP is the bin minimization problem. The goal of this problem is to pack the items in as few bins as possible. In a PBBP-SC instance, we are given a collection of unit-size items and a collection of bins of varying capacities. Associated with each item is a positive integer which is called its priority. The priority of an item indicates its importance in a (possibly infeasible) packing. As with the traditional case, these items need to be packed in the fewest number of bins. What complicates the problem is the fact that each item can be assigned to only one of a select set of bins, i.e., the bins are not interchangeable. We investigate several problems associated with PBBP-SC. Checking if there is a feasible assignment to a given instance is one problem. Finding a maximum priority assignment in case of the instance being infeasible is another. Finding an assignment with the fewest number of bins to pack a feasible instance is a third. We derive a number of results from both the algorithmic and computational complexity perspectives for these problems.

In this paper, we study three applications of recursion to problems in coding and random permutations. First, we consider locally recoverable codes with partial locality and use recursion to estimate the minimum distance of such codes. Next we consider weighted lattice representative codes and use recursive subadditive techniques to obtain convergence of the minimum code size. Finally, we obtain a recursive relation involving cycle moments in random permutations and as an illustration, evaluate recursions for the mean and variance.

In the first part of the paper we consider binary input channels that are not necessarily stationary and show how positive rates can be achieved using codes constrained to be within predetermined dictionaries. We use a Gilbert-Varshamov-like argument to obtain the desired rate achieving codes. Next we study the corresponding problem for channels with arbitrary alphabets and use conflict-set decoding to show that if the dictionaries are contained within “nice” sets, then positive rates are achievable.

The square conjecture claims that the number of distinct squares in a word is at most equal to the length of the word. While the conjecture is still open, there have been attempts to define patterns representing a collection of words with a large number of distinct squares. We study the properties of words having the maximum number of distinct squares. These properties are then used to define general criteria to characterize dense patterns. We show that there are infinitely many dense patterns by giving a pattern generator and use the rate of introduction of new squares to compare any two dense patterns. We also give a new dense pattern, P, and prove that it is better than the earlier patterns.

A set of n drones with limited communication capacity is deployed to monitor a terrain partitioned into n pairwise disjoint closed trajectories, one per drone. In our setting, there is a communication link between two trajectories if they are close enough, and drones can communicate provided they visit the link at the same time. Over time, one or more drones may fail and the ability to communicate and stay connected decreases. In this paper we study two properties related to communication: isolation and connectivity. First, we provide efficient algorithms, both centralized and decentralized, for determining the connected components induced by the set of surviving drones. Second, we study isolation and connectivity under a probabilistic failure model and show that, in the case of grids, the system is quite robust in the sense that it can tolerate a large probability of failure before drones become isolated and the system loses full connectivity.

Consider a team of $$k \le n$$ k ≤ n autonomous mobile robots initially placed at a node of an arbitrary graph G with n nodes. The dispersion problem asks for a distributed algorithm that allows the robots to reach a configuration in which each robot is at a distinct node of the graph. If the robots are anonymous, i.e., they do not have any unique identifiers, then the problem is not solvable by any deterministic algorithm. However, the problem can be solved even by anonymous robots if each robot is given access to a fair coin which they can use to generate random bits. In this setting, it is known that the robots require $$\varOmega (\log {\varDelta })$$ Ω ( log Δ ) bits of memory to achieve dispersion, where $$\varDelta $$ Δ is the maximum degree of G. On the other hand, the best known memory upper bound is $$min \{\varDelta , max\{\log {\varDelta }, \log {D}\}\}$$ m i n { Δ , m a x { log Δ , log D } } (D = diameter of G), which can be $$\omega (\log {\varDelta })$$ ω ( log Δ ) , depending on the values of $$\varDelta $$ Δ and D. In this paper, we close this gap by presenting an optimal algorithm requiring $$O(\log {\varDelta })$$ O ( log Δ ) bits of memory.

The problem of finding maximum (or minimum) witnesses of the Boolean product of two Boolean matrices (MW for short) has a number of important applications, in particular the all-pairs lowest common ancestor (LCA) problem in directed acyclic graphs (dags). The best known upper time-bound on the MW problem for $$n\times n$$ n × n Boolean matrices of the form $$O(n^{2.575})$$ O ( n 2.575 ) has not been substantially improved since 2006. In order to obtain faster algorithms for this problem, we study quantum algorithms for MW and approximation algorithms for MW (in the standard computational model). Some of our quantum algorithms are input or output sensitive. Our fastest quantum algorithm for the MW problem, and consequently for the related problems, runs in time $$\tilde{O}(n^{2+\lambda /2})=\tilde{O}(n^{2.434})$$ O ~ ( n 2 + λ / 2 ) = O ~ ( n 2.434 ) , where $$\lambda $$ λ satisfies the equation $$\omega (1, \lambda , 1) = 1 + 1.5 \, \lambda $$ ω ( 1 , λ , 1 ) = 1 + 1.5 λ and $$\omega (1, \lambda , 1)$$ ω ( 1 , λ , 1 ) is the exponent of the multiplication of an $$n \times n^{\lambda }$$ n × n λ matrix by an $$n^{\lambda } \times n$$ n λ × n matrix. Next, we consider a relaxed version of the MW problem (in the standard model) asking for reporting a witness of bounded rank (the maximum witness has rank 1) for each non-zero entry of the matrix product. First, by adapting the fastest known algorithm for maximum witnesses, we obtain an algorithm for the relaxed problem that reports for each non-zero entry of the product matrix a witness of rank at most $$\ell $$ ℓ in time $$\tilde{O}((n/\ell )n^{\omega (1,\log _n \ell ,1)}).$$ O ~ ( ( n / ℓ ) n ω ( 1 , log n ℓ , 1 ) ) . Then, by reducing the relaxed problem to the so called k-witness problem, we provide an algorithm that reports for each non-zero entry C[i, j] of the product matrix C a witness of rank $$O(\lceil W_C(i,j)/k\rceil )$$ O ( ⌈ W C ( i , j ) / k ⌉ ) , where $$W_C(i,j)$$ W C ( i , j ) is the number of witnesses for C[i, j], with high probability. The algorithm runs in $$\tilde{O}(n^{\omega }k^{0.4653} +n^{2+o(1)}k)$$ O ~ ( n ω k 0.4653 + n 2 + o ( 1 ) k ) time, where $$\omega =\omega (1,1,1)$$ ω = ω ( 1 , 1 , 1 ) .

For efficient design of parallel algorithms on multiprocessor architectures with memory banks, simultaneous access to a specified subgraph of a graph data structure by multiple processors requires that the data items belonging to the subgraph reside in distinct memory banks. Such “conflict-free” access to parallel memory systems and other applied problems motivate the study of rainbow coloring of a graph, in which there is a fixed template $$\mathcal{T}$$ T (or a family of templates), and one seeks to color the vertices of an input graph G with as few colors as possible, so that each copy of $$\mathcal{T}$$ T in G is rainbow colored, i.e., has no two vertices the same color. In the above example, the data structure is modeled as the host graph G, and the specified subgraph as the template $$\mathcal{T}$$ T . We call such coloring a template-driven rainbow coloring (or TR-coloring). For large data sets, it is also important to ensure that no memory bank (color) is overloaded, i.e., the coloring is as balanced as possible. Additionally, for fast access to data, it is desirable to quickly determine the address of a memory bank storing a data item. For arbitrary topology of G and $$\mathcal{T}$$ T , finding an optimal and balanced TR-coloring is a challenging problem. This paper focuses on rainbow coloring of proper interval graphs (as hosts) for cycle templates. In particular, we present an $$O(k\cdot |V|+|E|)$$ O ( k · | V | + | E | ) time algorithm to find a TR-coloring of a proper interval graph G with respect to k-length cycle template, $$C_k$$ C k . Our algorithm produces a coloring that is (i) optimal, i.e., it uses minimum possible number of colors in any TR-coloring; (ii) balanced, i.e, the vertices are evenly distributed among the different color classes; and (iii) explicit, i.e., the color assigned to a vertex can be computed by a closed form formula in constant time.

In the minimum consistent subset (MCS) problem, a connected simple undirected graph $$G=(V,E)$$ G = ( V , E ) is given whose each node is colored by one of the colors $$\{c_1,c_2,\ldots , c_k\}$$ { c 1 , c 2 , … , c k } , and the objective is to compute a subset $$\mathcal{C} \subseteq V$$ C ⊆ V such that for each node $$v \in V$$ v ∈ V , its set of nearest neighbors in $$\mathcal{C}$$ C (with respect to the hop-distance) contains at least one vertex of the same color as v. The decision version of the MCS problem is NP-complete for general graphs. Even for planar graphs, the problem remains NP-complete. We will consider some simple graph classes like path, caterpillar, bi-chromatic spider, bi-chromatic comb, etc., and propose polynomial-time algorithms for solving the problem on those graphs.

We study a variation of the graph partition problem on colored graphs called the problem. We are given a connected non-unicolor graph G where the vertices in G have colored either or and a positive integer k. The $$k$$ k -BCGP problem seeks a partition of G into k non-empty connected subgraphs such that each subgraph is as balanced (contains the same number of red and blue vertices) as possible i.e., minimizing the maximum across all k connected subgraphs where the unbalancedness of a connected subgraph of G is defined as the absolute difference between the number of red and blue vertices in that subgraph.We target some special classes of graphs namely, paths, trees, bipartite graphs, planar bipartite graphs, and chordal graphs with different values of k. For each of these classes either we prove NP-hardness or design a polynomial-time algorithm. More specifically, on the positive side, we design a polynomial-time algorithm for the $$k$$ k -BCGP problem on paths. For trees, we present a polynomial-time algorithm only for any fixed k. On the negative side, we prove that the $$k$$ k -BCGP problem is NP-hard for the bipartite graphs when the value of k is 2. For planar bipartite graphs, we prove the NP-hardness of the $$k$$ k -BCGP problem where k is a part of the input. We further prove that the $$k$$ k -BCGP problem is also NP-hard for the chordal graphs when $$k=2$$ k = 2 . We also show that these NP-hard problems do not admit any constant factor approximation algorithms.

A Roman dominating function (RDF) of a graph $$ G=(V,E) $$ G = ( V , E ) is a function $$f : V \rightarrow \{0, 1, 2\}$$ f : V → { 0 , 1 , 2 } such that every vertex assigned the value 0 is adjacent to a vertex assigned the value 2. A global Roman dominating function (GRDF) of a graph $$ G=(V,E) $$ G = ( V , E ) is a function $$f : V \rightarrow \{0, 1, 2\}$$ f : V → { 0 , 1 , 2 } such that f is a Roman dominating function of both G and its complement $$ \overline{G} $$ G ¯ . The weight of f is $$f(V) =\varSigma _{u\in V} f(u)$$ f ( V ) = Σ u ∈ V f ( u ) . The minimum weight of a GRDF in a graph G is known as global Roman domination number of G and is denoted by $$\gamma _{gR}(G)$$ γ gR ( G ) . Minimum Global Roman Domination is to find a global Roman dominating function of minimum weight and Decide Global Roman Domination is the decision version of Minimum Global Roman Domination. In this paper, we show that Decide Global Roman Domination is NP-complete for bipartite graphs and chordal graphs. We also show that Minimum Global Roman Domination cannot be approximated within a factor of $$ (\frac{1}{2}-\epsilon )\ln \vert V \vert $$ ( 1 2 - ϵ ) ln | V | for any $$ \epsilon >0 $$ ϵ > 0 unless $$ \textsf {P}=\textsf {NP} $$ P = NP . On the positive side, we propose an $$O(\ln |V|)$$ O ( ln | V | ) -approximation algorithm for Minimum Global Roman Domination for any graph $$G=(V,E)$$ G = ( V , E ) .