Algorithms and Discrete Applied Mathematics

Restricted star colouring is a variant of star colouring introduced to design heuristic algorithms to estimate sparse Hessian matrices. For $$ k\in \mathbb {N} $$, a $$ k $$-restricted star ($$ k $$-rs) colouring of a graph $$ G $$ is a function $$ f:V(G)\rightarrow \{0,1,\dots ,k\,-\,1\} $$ such that (i) $$ f(x)\ne f(y) $$ for every edge $$ xy $$ of $$ G $$, and (ii) there is no bicoloured 3-vertex path($$ P_3 $$) in $$ G $$ with the higher colour on its middle vertex. We show that for $$ k\ge 3 $$, it is NP-complete to decide whether a given planar bipartite graph of maximum degree $$ k $$ and girth at least six is $$ k $$-rs colourable, and thereby answer a problem posed by Shalu and Sandhya (Graphs and Combinatorics 2016). In addition, we design an $$ O(n^3) $$ algorithm to test whether a chordal graph is 3-rs colourable.

We consider a variation of arboricity, where a graph is partitioned into p forests and q independent sets. These problems are NP-complete in general, but polynomial-time solvable in the class of cographs; in fact, for each p and q there are only finitely many minimal non-partitionable cographs. In previous investigations it was revealed that when $$p=0$$ or $$p=1$$, these minimal non-partitionable cographs can be uniformly described as one family of obstructions valid for all values of q. We investigate the next case, when $$p=2$$; we provide the complete family of minimal obstructions for $$p=2, q=1$$, and find that they include more than just the natural extensions of the previously described obstructions for $$p=2, q=0$$. Thus a uniform description for all q seems unlikely already in the case $$p=2$$.Our result gives a concrete forbidden induced subgraph characterization of cographs that can be partitioned into two forests and one independent set. Since our proof is algorithmic, we can apply our characterization to complement the recognition algorithm for partitionable cographs by an algorithm to certify non-partitionable cographs by finding a forbidden induced subgraph.

We introduce a new graph-theoretic concept in the area of network monitoring. A set M of vertices of a graph G is a distance-edge-monitoring set if for every edge e of G, there is a vertex x of M and a vertex y of G such that e belongs to all shortest paths between x and y. We denote by $$\mathrm {dem}(G)$$ the smallest size of such a set in G. The vertices of M represent distance probes in a network modeled by G; when the edge e fails, the distance from x to y increases, and thus we are able to detect the failure. It turns out that not only we can detect it, but we can even correctly locate the failing edge.In this paper, we initiate the study of this new concept. We show that for a nontrivial connected graph G of order n, $$1\le \mathrm {dem}(G)\le n-1$$ with $$\mathrm {dem}(G)=1$$ if and only if G is a tree, and $$\mathrm {dem}(G)=n-1$$ if and only if it is a complete graph. We compute the exact value of $$\mathrm {dem}$$ for grids, hypercubes, and complete bipartite graphs.Then, we relate $$\mathrm {dem}$$ to other standard graph parameters. We show that $$\mathrm {dem}(G)$$ is lower-bounded by the arboricity of the graph, and upper-bounded by its vertex cover number. It is also upper-bounded by five times its feedback edge set number.Then, we show that determining $$\mathrm {dem}(G)$$ for an input graph G is an NP-complete problem, even for apex graphs. There exists a polynomial-time logarithmic-factor approximation algorithm, however it is NP-hard to compute an asymptotically better approximation, even for bipartite graphs of small diameter and for bipartite subcubic graphs. For such instances, the problem is also unlikely to be fixed parameter tractable when parameterized by the solution size.

The lexicographic method is a technique that was introduced by Hell and Huang [Journal of Graph Theory, 20(3): 361–374, 1995] as a way to simplify the problems of recognizing and obtaining representations of comparability graphs, proper circular-arc graphs and proper interval graphs. This method gives rise to conceptually simple recognition algorithms and leads to much simpler proofs for some characterization theorems for these classes. Threshold graphs are a class of graphs that have many equivalent definitions and have applications in integer programming and set packing problems. A graph is said to have a threshold cover of size k if its edges can be covered using k threshold graphs. Chvátal and Hammer conjectured in 1977 that given a graph G, a suitably constructed auxiliary graph $$G'$$ has chromatic number equal to the minimum size of a threshold cover of G. Although this conjecture was shown to be false in the general case by Cozzens and Leibowitz, it was shown to be true for graphs having a threshold cover of size 2 by Raschle and Simon [Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC ’95, pages 650–661, 1995]. That is, a graph G has a threshold cover of size 2 if and only if $$G'$$ is bipartite—this is the only known forbidden structure characterization of graphs having a threshold cover of size 2. We show how the lexicographic method can be used to obtain a completely new and much simpler proof for this result. This method also gives rise to a simple new LexBFS-based algorithm for recognizing graphs having a threshold cover of size 2. Although this algorithm is not the fastest known, it is a certifying algorithm that matches the time complexity of the fastest known certifying algorithm for this problem. The algorithm can also be easily adapted to give a certifying recognition algorithm for bipartite graphs that can be covered by two chain subgraphs.

In order to understand underlying structural regularities in a graph, a basic and useful technique, known as modular decomposition, looks for subsets of vertices that have the exact same neighbourhood to the outside. These are known as modules and there exist linear-time algorithms to find them. This notion however is too strict, especially when dealing with graphs that arise from real world data. This is why it is important to relax this condition by allowing some noise in the data. However, generalizing modular decomposition is far from being obvious since most of the proposals lose the algebraic properties of modules and therefore most of the nice algorithmic consequences. In this paper we introduce the notion of $$\epsilon $$-module which seems to be a good compromise that maintains some of the algebraic structure. Among the main results in the paper, we show that minimal $$\epsilon $$-modules can be computed in polynomial time, on the other hand for maximal $$\epsilon $$-modules it is already NP-hard to compute if a graph admits an 1-parallel decomposition, i.e. one step of decomposition of $$\epsilon $$-module with $$\epsilon =1$$.

Let $$G=(V,E)$$ be a simple graph. A set $$D \in V$$ is called a vertex-edge dominating set of G if for each edge $$e=(u,v)\in E$$, either u or v is in D or one vertex from their neighbor is in D. Simply, a vertex $$v\in V$$, vertex-edge dominates every edge (u, v), as well as every edge adjacent to these edges. The vertex-edge dominating problem is to find a minimum vertex-edge dominating set of G. Herein, we study the vertex-edge dominating set problem in unit disk graphs and prove that this problem is NP-hard in that class of graphs. We also show that the problem admits a polynomial time approximation scheme (PTAS) in unit disk graphs.

We study four classical graph problems – Hamiltonian path, Traveling salesman, Minimum spanning tree, and Minimum perfect matching on geometric graphs induced by bichromatic ( and ) points. These problems have been widely studied for points in the Euclidean plane, and many of them are $$\mathsf {NP}$$-hard. In this work, we consider these problems in two restricted settings: (i) collinear points and (ii) equidistant points on a circle. We show that almost all of these problems can be solved in linear time in these constrained, yet non-trivial settings.

A set $$ D \subseteq V_{G} $$ of a graph $$ G = (V_{G},E_{G}) $$ is called a global total k-dominating set of G if D is a total k-dominating set of both G and $$ \overline{G} $$, the complement of G. The Minimum Global Total k-Domination problem is to find a global total k-dominating set of minimum cardinality of the input graph G and Decide Global Total k-Domination problem is the decision version of Minimum Global Total k-Domination problem. The Decide Global Total k -Domination problem is known to be NP-complete for general graphs. In this paper, we study the complexity of the Minimum Global Total k-Domination problem. We show the Decide Global Total k-Domination problem remains NP-complete for bipartite graphs and chordal graphs. Next, we show that the Minimum Global Total k-Domination problem admits a constant approximation algorithm for bounded degree graphs. Finally, we show that the Minimum Global Total k-Domination problem is APX-complete for bounded degree graphs.

In this paper, we study the computational complexity of finding the geodetic number of graphs. A set of vertices S of a graph G is a geodetic set if any vertex of G lies in some shortest path between some pair of vertices from S. The Minimum Geodetic Set (MGS) problem is to find a geodetic set with minimum cardinality. In this paper, we prove that solving MGS is NP-hard on planar graphs with a maximum degree six and line graphs. We also show that unless $$P=NP$$, there is no polynomial time algorithm to solve MGS with sublogarithmic approximation factor (in terms of the number of vertices) even on graphs with diameter 2. On the positive side, we give an $$O\left( \root 3 \of {n}\log n\right) $$-approximation algorithm for MGS on general graphs of order n. We also give a 3-approximation algorithm for MGS on solid grid graphs which are planar.

For a graph G, a complete bipartite subgraph of G is called a biclique of G. For a weighted graph $$G=(V,E,w)$$, where each edge $$e\in E$$ has a weight $$w(e)\in \mathbb {R}$$, the Maximum Weighted Edge Biclique (MWEB) problem is to find a biclique H of G such that $$\sum _{e\in E(H)}w(e)$$ is maximum. The decision version of the MWEB problem is known to be NP-complete for bipartite graphs. In this paper, we show that the decision version of the MWEB problem remains NP-complete even if the input graph is a complete bipartite graph. On the positive side, if the weight of each edge is a positive real number in the input graph G, then we show that the MWEB problem is $$O(n^2)$$-time solvable for bipartite permutation graphs, and $$O(m+n)$$-time solvable for chain graphs, which is a subclass of bipartite permutation graphs.

The determining number of a graph $$G = (V,E)$$ is the minimum cardinality of a set $$S\subseteq V$$ such that pointwise stabilizer of S under the action of Aut(G) is trivial. In this paper, we determine the determining number of generalized Petersen graphs and double generalized Petersen graphs.

A connected graph is said to be self-centered if all its vertices have the same eccentricity. The family of generalized Petersen graphs P(n, k), introduced by Coxeter [6] and named by Watkins [18], is a family of cubic graphs of order 2n defined by positive integral parameters n and k, $$n\ge 2k$$. Not all generalized Petersen graphs are self-centered. In this paper, we prove self-centeredness of P(n, k) whenever k divides n and $$k< \frac{n}{2}$$, except the case when n is odd and k is even. We also prove non-self-centeredness of generalized Petersen graphs P(n, k) when n even with $$k=\frac{n}{2}$$; $$n=4m+2$$ with $$k=\frac{n}{2}-1$$ for some positive integer $$m\ge 3$$; $$n\ge 9$$ is odd and $$k=2$$ or $$k=\frac{n-1}{2}$$; and $$n = m(4m+1 )\pm (m+1)$$ with $$k = 4m + 1$$ for any positive integer $$m \ge 2$$. Finally, we make an exhaustive computer search and get all possible values of n and k for which P(n, k) is non-self-centered.

A Roman dominating function (RDF) on a graph G is a labelling $$f: V(G) \rightarrow \{0, 1, 2\}$$ such that every vertex with label 0 has a neighbor with label 2. A vertex u with f(u) = 0 is said to be undefended with respect to f if it is not adjacent to a vertex v with the positive weight. A function $$f:V(G) \rightarrow \{0, 1, 2\}$$ is a weak Roman dominating function (WRDF) if each vertex u with $$f(u) = 0$$ is adjacent to a vertex v with $$f(v) > 0$$ such that the function $$f^{\prime }: V(G) \rightarrow \{0, 1, 2\}$$ defined by $$f^{\prime }(u) = 1$$, $$f^{\prime }(v) = f(v) - 1$$ and $$f^{\prime }(w) = f(w)$$ if $$w \in V - \{u, v\}$$, has no undefended vertex. The Roman bondage number $$b_R(G)$$ of a graph G with maximum degree at least two is the minimum cardinality of all sets $$\ E^{\prime } \subseteq E(G)$$ for which $$\gamma _R(G-E^{\prime }) > \gamma _R(G)$$. We extend this concept to a weak Roman dominating function as follows: The weak Roman bondage number $$b_r(G)$$ of a graph G with maximum degree at least two is the minimum cardinality of all sets $$\ E^{\prime } \subseteq E(G)$$ for which $$\gamma _r$$($$G - E^{\prime }$$) $$> \gamma _r(G)$$. In this paper we determine the exact values of the weak Roman bondage number for paths, cycles and complete bipartite graphs. We obtain bounds for trees and unicyclic graphs and characterize the extremal graphs.

Given two vertices u, v in a graph G, a shortest (u, v)-path in G is called an (u, v)-geodesic. Let $$I_G[u, v]$$ denote the set of all vertices in G lying on some (u, v)-geodesic. Given a set $$T\subseteq V(G)$$, let $$I_G[T]=\cup _{u,v \in T}I_G[u, v]$$. If $$I_G[T]=T$$, we call T a convex set. The convex hull, denoted by $$\langle T \rangle _G$$, is the smallest convex set containing T. A subset T of vertices of a graph G is a hull set if $$\langle T \rangle _G=V(G)$$. Moreover, T is a geodetic if $$I_G[T]=V(G)$$. The hull number h(G) of a graph G is the minimum size of a hull set. The geodetic number g(G) of G is the minimum size of a geodetic set. The shadow graph, denoted by S(G), of a graph G is the graph obtained from G by adding a new vertex $$v^{\prime }$$ for each vertex v of G and joining $$v'$$ to the neighbors of v in G. In this paper, we study the geodetic and hull numbers of shadow graphs. Bounds for the geodetic and hull numbers of shadow graphs are obtained and for several classes exact values are determined. Graphs G for which $$g(S(G))\in \{2, 3\}$$ are characterized.

Indicated coloring is a slight variant of the game coloring which was introduced by Grzesik [6]. In this paper, we show that for any graphs G and H, G[H] is k-indicated colorable for all $$k\ge \mathrm {col}(G)\mathrm {col}(H)$$. Also, we show that for any graph G and for some classes of graphs H with $$\chi (H)=\chi _i(H)=\ell $$, G[H] is k-indicated colorable if and only if $$G[K_\ell ]$$ is k-indicated colorable. As a consequence of this result we show that if $$G\in \mathcal {G}=\Big \{$$Chordal graphs, Cographs, $$\{P_5,C_4\}$$-free graphs, Complete multipartite graphs$$\Big \}$$ and $$H\in \mathcal {F}=\Big \{$$Bipartite graphs, Chordal graphs, Cographs, $$\{P_5,K_3\}$$-free graphs, $$\{P_5,Paw\}$$-free graphs, Complement of bipartite graphs, $$\{P_5,K_4,Kite,Bull\}$$-free graphs, connected $$\{P_6,C_5,\overline{P_5},K_{1,3}\}$$-free graphs which contain an induced $$C_6$$, $$\mathbb {K}[C_5](m_1, m_2 ,\ldots ,m_5)$$, $$\{P_5,C_4\}$$-free graphs, connected $$\{P_5,\overline{P_2\cup P_3},\overline{P_5},$$ $$Dart\}$$-free graphs which contain an induced $$C_5\Big \}$$, then G[H] is k-indicated colorable for every $$k\ge \chi (G[H])$$. This serves as a partial answer to one of the questions raised by Grzesik in [6].

Given a graph H, a graph G is called H-critical if G does not admit a homomorphism to H, but any proper subgraph of G does. Observe that $$K_{k-1}$$-critical graphs are the classic k-(colour)-critical graphs. This work is a first step towards extending questions of extremal nature from k-critical graphs to H-critical graphs. Besides complete graphs, the next classic case is odd cycles. Thus, given integers $$l\ge k$$ we ask: what is the smallest order $$\eta (k,l)$$ of a $$C_{2l+1}$$-critical graph of odd-girth at least $$2k+1$$? Denoting this value by $$\eta (k,l)$$, we show that $$\eta (k,l)=4k$$ for $$l\le k\le \frac{3l+i-3}{2}$$ ($$2k=i\bmod 3$$) and that $$\eta (3,2)=15$$. The latter is to say that a smallest graph of odd-girth 7 not admitting a homomorphism to the 5-cycle is of order 15 (there are at least 10 such graphs on 15 vertices).

Given a graph, the classical Ramsey number R(k, l) is the least number of vertices that need to be in the graph for the existence of a clique of size k or an independent set of size l. Finding R(k, l) exactly has been a notoriously hard problem. Even R(k, 3) has not been determined for all values of k. Hence finding the Ramsey number for subclasses of graphs is an interesting question. It is known that even for claw-free graphs, finding Ramsey number is as hard as for general graphs for infinite number of cases. Line graphs are an important subclass of claw-free graphs. The question with respect to line graph L(G) is equivalent to the minimum number of edges the underlying graph G needs to have for the existence of a vertex with degree k or a matching of size l. Chvátal and Hanson determined this exactly for line graphs of simple graphs. Later Balachandran and Khare gave the same bounds with a different proof. In this paper we find Ramsey numbers for line graph of multi graphs thereby extending the results of Chvátal and Hanson. Here we determine the maximum number of edges that a multigraph can have, when its matching number, multiplicity, and maximum degree are bounded, and characterize such graphs.

The $$\varDelta $$-interval of $$u,v \in V (G)$$, $$I_{\varDelta }(u,v)$$, is the set formed by u, v and every w in V(G) such that $$\{u, v, w\}$$ is a triangle $$(K_3)$$ of G. A set S of vertices such that $$I_{\varDelta } (S)=V(G)$$ is called a $$\varDelta $$-set. $$\varDelta $$-number is the minimum cardinality of a $$\varDelta $$-set. $$\varDelta $$-graph is a graph with all the vertices lie on some triangles. If a block graph is a $$\varDelta $$-graph, then we say that it is a block $$\varDelta $$-graph. A set $$S\subseteq V (G)$$ is $$\varDelta $$-convex if there is no vertex $$u \in V(G)\setminus S$$ forming a triangle with two vertices of S. The convexity number of a graph G with respect to the $$\varDelta $$-convexity is the maximum cardinality of a proper convex subset of G. We have given an exact value for the convexity number of block $$\varDelta $$-graphs with diameter $${\le }3$$, block $$\varDelta $$-graphs with diameter $${>}3$$ and the two standard graph products (Strong, Lexicographic products), a bound for Cartesian product. Also discussed some bounds for $$\varDelta $$-number and a realization is done for the $$\varDelta $$-number and the hull number.

In this paper, we study the Cartesian product of signed graphs as defined by Germina, Hameed and Zaslavsky (2011). Here we focus on its algebraic properties and look at the chromatic number of some products. One of our main result is the unicity of the prime factor decomposition of signed graphs. This leads us to present an algorithm to compute this decomposition in quasi-linear time. Both these results use their counterparts for ordinary graphs as building blocks. We also study the signed chromatic number of graphs with underlying graph of the form $$P_n \ \square \ P_m$$, of products of signed paths, of products of signed complete graphs and of products of signed cycles, that is the minimum order of a signed graph to which they admit a homomorphism.

A graph G is said to be k-distinguishable if every vertex of the graph can be colored from a set of k colors such that no non-trivial automorphism fixes every color class. The distinguishing number D(G) is the least integer k for which G is k-distinguishable. If for each $$v\in V(G)$$ we have a list L(v) of colors, and we stipulate that the color assigned to vertex v comes from its list L(v) then G is said to be $$\mathcal {L}$$-distinguishable where $$\mathcal {L}=\{L(v)\}_{v\in V(G)}$$. The list distinguishing number of a graph, denoted $$D_l(G)$$, is the minimum integer k such that every collection of lists $$\mathcal {L}$$ with $$|L(v)|=k$$ admits an $$\mathcal {L}$$-distinguishing coloring. In this paper, we prove that when a connected graph G is prime with respect to the Cartesian product then $$D_l(G^r) = D(G^r)$$ for $$r \ge 3$$ where $$G^r$$ is the Cartesian product of the graph G taken r times. The $$p^{th}$$ power of a graph (Some authors use $$G^p$$ to denote the pth power of G, to avoid confusion with the notation of Cartesian power of graph G we use $$G^{[p]}$$ for the pth power of G.) G is the graph $$G^{[p]}$$, whose vertex set is V(G) and in which two vertices are adjacent when they have distance less than or equal to p. We determine $$D_l(Q_n^{[p]})$$ for all $$n \ge 7, p \ge 1$$, where $$Q_n=K_2^n$$ is the hypercube of dimension n.

The paper investigates relationship between algebraic expressions and graphs. Our intent is to simplify graph expressions and eventually find their shortest representations. We describe the decomposition method for generating expressions of complete st-dags (two-terminal directed acyclic graphs) and estimate the corresponding expression complexities. Using these findings, we present an $$2^{O\left( \log ^{2}n\right) }$$ upper bound of a length of the shortest expression for every st-dag of order n.

A vertex subset R of an oriented graph $$\overrightarrow{G}$$ is a relative oriented clique if each pair of non-adjacent vertices of R is connected by a directed 2-path. The relative oriented clique number $$\omega _{ro}(\overrightarrow{G})$$ of $$\overrightarrow{G}$$ is the maximum value of |R| where R is a relative oriented clique of $$\overrightarrow{G}$$. Given a family $$\mathcal {F}$$ of oriented graphs, the relative oriented clique number is $$\omega _{ro}(\mathcal {F}) = \max \{\omega _{ro}(\overrightarrow{G})|\overrightarrow{G} \in \mathcal {F}\}$$. For the family $$\mathcal {P}_4$$ of oriented triangle-free planar graphs, it was conjectured that $$\omega _{ro}(\mathcal {P}_4)=10$$. In this article, we prove the conjecture.

We characterize the optimal solution to the LP relaxation of the standard formulation for the minimum satisfiability problem. Based on the characterization, we give a $$O(nm^2)$$ combinatorial algorithm to solve the fractional version of the minimum satisfiability problem optimally where n(m) is the number of variables (clauses). As a by-product, we obtain a $$2(1-1/2^k)$$ approximation algorithm for the minimum satisfiability problem where k is the maximum number of literals in any clause. We also give a simple linear time 2 approximation algorithm.

We introduce a model for train routing on railway systems. Trains route through a network over time from a start to an end depot. They occupy consecutive nodes and edges corresponding to their length and block each other. We study the case where the depots are part of the network (internal) and the case where the depots are not part of the network (external).The problem is a generalization of packet routing without buffers. We consider two different kinds of optimization problems. In the first, trains are only allowed to wait on predefined paths and in the second, trains are additionally allowed to shunt, i.e., change direction. In both cases, we are interested in minimizing the overall makespan.For waiting instances, we find NP-hardness results even on unidirectional paths. We also show W[1]-hardness and lower bounds on the running time using the Exponential Time Hypothesis. For shunting instances, we show PSPACE-completeness results on honeycomb graphs and transfer the previously shown NP-hardness results. We present a polynomial time algorithm for a special subclass of unidirectional paths.

An orientation of an undirected graph G is an assignment of exactly one direction to each edge of G. Converting two-way traffic networks to one-way traffic networks and bidirectional communication networks to unidirectional communication networks are practical instances of graph orientations. In these contexts minimising the diameter of the resulting oriented graph is of prime interest. The n-star network topology was proposed as an alternative to the hypercube network topology for multiprocessor systems by Akers and Krishnamurthy [IEEE Trans. on Computers (1989)]. The n-star graph $$S_n$$ consists of n! vertices, each labelled with a distinct permutation of [n]. Two vertices are adjacent if their labels differ exactly in the first and one other position. $$S_n$$ is an $$(n-1)$$-regular, vertex-transitive graph with diameter $$\lfloor 3(n-1)/2\rfloor $$. Orientations of $$S_n$$, called unidirectional star graphs and distributed routing protocols over them were studied by Day and Tripathi [Information Processing Letters (1993)] and Fujita [The First International Symposium on Computing and Networking (CANDAR 2013)]. Fujita showed that the (directed) diameter of this unidirectional star graph $$\overrightarrow{S_n}$$ is at most $$\lceil 5n/2\rceil + 2$$.In this paper, we propose a new distributed routing algorithm for the same $$\overrightarrow{S_n}$$ analysed by Fujita, which routes a packet from any node s to any node t at an undirected distance d from s using at most $$\min \{4d+4, 2n+4\}$$ hops. This shows that the (directed) diameter of $$\overrightarrow{S_n}$$ is at most $$2n+4$$. We also show that the diameter of $$\overrightarrow{S_n}$$ is at least 2n when $$n \ge 7$$, thereby showing that our upper bound is tight up to an additive factor.

The gathering on meeting points problem requires the robots to gather at one of the pre-defined meeting points. This paper investigates a discrete version of the problem where the robots and meeting nodes are deployed on the nodes of an anonymous infinite square grid. The robots are identical, autonomous, anonymous, and oblivious. They operate under an asynchronous scheduler. Robots do not have any agreement on a global coordinate system. Initial configurations, for which the problem is unsolvable, have been characterized. A deterministic distributed algorithm has been proposed to solve the problem, for the rest of the configurations.

Temporal graphs are introduced to model dynamic networks where the set of edges and/or nodes can change with time. In this paper, we define 0-1 timed matching for temporal graphs, and address the problem of finding the maximum 0-1 timed matching for bipartite temporal graphs. We show that the problem is NP-Complete for bipartite temporal graphs even when each edge is associated with exactly one time interval. We also show that the problem is NP-Complete for rooted temporal trees even when each edge is associated with at most three time intervals. Finally, we propose an $$O(n^3)$$ time algorithm for the problem on a rooted temporal tree with n nodes when each edge is associated with exactly one time interval.

Arbitrary Pattern Formation is a widely studied problem in autonomous robot systems. The problem asks to design a distributed algorithm that moves a team of autonomous, anonymous and identical mobile robots to form any arbitrary pattern given as input. The majority of the existing literature investigates this problem for robots with unobstructed visibility. In a few recent works, the problem has been studied in the obstructed visibility model, where the view of a robot can be obstructed by the presence of other robots. However, in these works, the robots have been modelled as dimensionless points in the plane. In this paper, we have considered the problem in the more realistic setting where the robots have a physical extent. In particular, the robots are modelled as opaque disks. Furthermore, the robots operate under a fully asynchronous scheduler. They do not have access to any global coordinate system, but agree on the direction and orientation of one coordinate axis. Each robot is equipped with an externally visible light which can assume a constant number of predefined colors. In this setting, we have given a complete characterization of initial configurations from where any arbitrary pattern can be formed by a deterministic distributed algorithm.

A weak order is a way to rank n objects where ties are allowed. In this paper, we extend the prefer-larger and the prefer-opposite algorithms for de Bruijn sequences to provide the first known greedy universal cycle constructions for weak orders.

Continuous and discrete models [1, 5] for firefighting problems are well-studied in Theoretical Computer Science. We introduce a new, discrete, and more general framework based on a hexagonal cell graph to study firefighting problems in varied terrains. We present three different firefighting problems in the context of this model; for two of which, we provide efficient polynomial time algorithms and for the third, we show NP-completeness. We also discuss possible extensions of the model and their implications on the computational complexity.

We study a variant of the Student-Project Allocation problem with lecturer preferences over Students where ties are allowed in the preference lists of students and lecturers (spa-st). We investigate the concept of strong stability in this context. Informally, a matching is strongly stable if there is no student and lecturer l such that if they decide to form a private arrangement outside of the matching via one of l’s proposed projects, then neither party would be worse off and at least one of them would strictly improve. We describe the first polynomial-time algorithm to find a strongly stable matching or report that no such matching exists, given an instance of spa-st. Our algorithm runs in $$O(m^2)$$ time, where m is the total length of the students’ preference lists.

Let G and H be respectively a graph and a hypergraph defined on a same set of vertices, and let F be a fixed graph. We say that G F-overlays a hyperedge S of H if F is a spanning subgraph of the subgraph of G induced by S, and that it F-overlays H if it F-overlays every hyperedge of H. Motivated by structural biology, we study the computational complexity of two problems. The first problem, $$(\varDelta \le k)$$ F-Overlay, consists in deciding whether there is a graph with maximum degree at most k that F-overlays a given hypergraph H. It is a particular case of the second problem Max $$(\varDelta \le k)$$ F-Overlay, which takes a hypergraph H and an integer s as input, and consists in deciding whether there is a graph with maximum degree at most k that F-overlays at least s hyperedges of H.We give a complete polynomial/$$\mathcal {NP}$$-complete dichotomy for the Max $$(\varDelta \le k)$$-F-Overlay problems depending on the pairs (F, k), and establish the complexity of $$(\varDelta \le k)$$ F-Overlay for many pairs (F, k).

Many well-known $$\mathsf {NP}$$-hard algorithmic problems on directed graphs resist efficient parameterizations with most known width measures for directed graphs, such as directed treewidth, DAG-width, Kelly-width and many others. While these focus on measuring how close a digraph is to an oriented tree resp. a directed acyclic graph, in this paper, we investigate directed modular width as a parameter, which is closer to the concept of clique-width. We investigate applications of modular decompositions of directed graphs to a wide range of algorithmic problems and derive FPT algorithms for several well-known digraph-specific $$\mathsf {NP}$$-hard problems, namely minimum (weight) directed feedback vertex set, minimum (weight) directed dominating set, digraph colouring, directed Hamiltonian path/cycle, partitioning into paths, (capacitated) vertex-disjoint directed paths, and the directed subgraph homeomorphism problem. The latter yields a polynomial-time algorithm for detecting topological minors in digraphs of bounded directed modular width. Finally we illustrate that other structural digraph parameters, such as directed pathwidth and cycle-rank can be computed efficiently using directed modular width as a parameter.

We consider the minimum power spanning tree (MPST) problem with general and unit demands from a parameterized perspective. The case of unit demands is equivalent to the problem of finding a spanning tree with the smallest possible vertex cover (MCST). We show that MPST is W[1]-hard when parameterized by the vertex cover of the input graph, and is W[2]-hard when parameterized by the solution size—the latter holds even in the case of unit demands. For the special case of unit demands, however, we demonstrate an FPT algorithm when parameterized by treewidth. In the context of kernelization, we show that even MCST is unlikely to admit a polynomial kernel under standard complexity-theoretic assumptions when parameterized by the vertex cover of the input graph.

Conflict free q-Colouring of a graph G refers to the colouring of a subset of vertices of G using q colours such that every vertex has a neighbour of unique colour. In this paper, we study the Minimum Conflict free q-Colouring problem. Given a graph G and a fixed constant q, Minimum Conflict free q-Colouring is to find a Conflict free q-Colouring of G that minimises the number of coloured vertices. We study the Minimum Conflict free q-Colouring problem parameterized by the treewidth of G. We give an FPT algorithm for this problem and also prove running time lower bounds under Exponential Time Hypothesis (ETH) and Strong Exponential Time Hypothesis (SETH).

We introduce and study a new graph representation where vertices are embedded in three or more dimensions, and in which the edges are drawn on the projections onto the axis-parallel planes. We show that the complete graph on n vertices has a representation in $$\lceil \sqrt{n/2}+1 \rceil $$ planes. In 3 dimensions, we show that there exist graphs with $$6n-15$$ edges that can be projected onto two orthogonal planes, and that this is best possible. Finally, we obtain bounds in terms of parameters such as geometric thickness and linear arboricity. Using such a bound, we show that every graph of maximum degree 5 has a plane-projectable representation in 3 dimensions.

Let P be a set of points in general position in the plane. A halving line of P is a line passing through two points of P and cutting the remaining $$n-2$$ points in a half (almost half if n is odd). Generalized configurations of points and their representations using allowable sequences are useful for bounding the number of halving lines.We study a problem of finding generalized configurations of points maximizing the number of halving pseudolines. We develop algorithms for optimizing generalized configurations of points using the new notion of partial allowable sequence and the problem of computing a partial allowable sequence maximizing the number of k-transpositions. It can be viewed as a sorting problem using transpositions of adjacent elements and maximizing the number of transpositions at position k.We show that this problem can be solved in $$O(nk^n)$$ time for any $$k>2$$, and in $$O(n^k)$$ time for $$k=1, 2$$. We develop an approach for optimizing allowable sequences. Using this approach, we find new bounds for halving pseudolines for even n, $$n\le 100$$.

Let P be a set n points in a d-dimensional space. Tverberg theorem says that, if n is at least $$(k-1)(d+1)$$, then P can be partitioned into k sets whose convex hulls intersect. Partitions with this property are called Tverberg partitions. A partition has tolerance t if the partition remains a Tverberg partition after removal of any set of t points from P. A tolerant Tverberg partition exists in any dimensions provided that n is sufficiently large. Let N(d, k, t) be the smallest value of n such that tolerant Tverberg partitions exist for any set of n points in $$\mathbb {R}^d$$. Only few exact values of N(d, k, t) are known.In this paper, we study the problem of finding Radon partitions (Tverberg partitions for $$k=2$$) for a given set of points. We develop several algorithms and found new lower bounds for N(d, 2, t).