Algorithms and Discrete Applied Mathematics

The hypercube has been used in numerous problems related to interconnection networks due to its simple structure and communication properties. The locally twisted cube is an important class of hypercube variants with the same number of nodes and connections per node, but has only half the diameter and better graph embedding capability as compared to its counterpart. The embedding problem plays a significant role in parallel and distributed systems. In this paper we devise an optimal embedding of the n-dimensional locally twisted cube onto a grid network.

In this article, we consider a collection of geometric problems involving points colored by two colors (red and blue), referred to as bichromatic problems. The motivation behind studying these problems is two fold; (i) these problems appear naturally and frequently in the fields like Machine learning, Data mining, and so on, and (ii) we are interested in extending the algorithms and techniques for single point set (monochromatic) problems to bichromatic case. For all the problems considered in this paper, we design low polynomial time exact algorithms. These algorithms are based on novel techniques which might be of independent interest.

The concept of convex polygon-offset distance function was introduced in 2001 by Barequet, Dickerson, and Goodrich. Using this notion of point-to-point distance, they showed how to compute the corresponding nearest- and farthest-site Voronoi diagram for a set of points. In this paper we generalize the polygon-offset distance function to be from a point to any convex object with respect to an m-sided convex polygon, and study the nearest- and farthest-site Voronoi diagrams for sets of line segments and convex polygons. We show that the combinatorial complexity of the nearest-site Voronoi diagram of n disjoint line segments is O(nm), which is asymptotically equal to that of the Voronoi diagram of n point sites with respect to the same distance function. In addition, we generalize this result to the Voronoi diagram of disjoint convex polygonal sites. We show that the combinatorial complexity of the nearest-site Voronoi diagram of n convex polygonal sites, each having at most k sides, is $$O(n(m+k))$$O(n(m+k)). Finally, we show that the corresponding farthest-site Voronoi diagram is a tree-like structure with the same combinatorial complexity.

This paper considers the problem of gathering a set of asynchronous robots on the two dimensional plane under the additional requirement that the maximum distance traversed by the robots should be minimized. One of the implications of this optimization criteria is the energy efficiency for the robots. The results of this paper are two folds. First, it is proved that multiplicity detection capability is not sufficient to solve the constrained gathering problem for a set of oblivious robots even when the robots are fully synchronous. The problem is then studied for the robots having O(1) bits persistent memory and a distributed algorithm is proposed for the problem in this model for a set of $$n\ge 5$$n≥5 robots. The proposed algorithm uses only two bits of persistent memory.

We study the classical problem of sorting when comparison between certain pair of elements are forbidden. Along with the set of elements V, the input to our problem is an undirected graph G(V, E), whose edges represent the pairs that can be directly compared in constant time. We call this the comparison graph. It is also possible that the set of elements forms a partial-order, and not a total-order in which case, the sorting problem is the problem of determining all possible relations in the partial order, i.e. determining the (transitive) orientations of the edges of the graph.If q is the number of edges missing in the graph, we first give a sorting algorithm that takes comparisons improving on the recent upper bound of . We also show the first lower bound by giving a graph and an orientation by an adversary where comparisons are necessary. Then, we give an algorithm (independent of q) when the comparison graph is from a special class of graphs like chordal or comparability graphs. Finally, we make some remarks regarding the complexity of sorting with forbidden comparisons when the elements form a total order.

Centrality indices assign values to the vertices of a graph such that vertices with higher values are considered more central. Triggered by a recent result on the preservation of the vicinal preorder in rankings obtained from common centrality indices, we review and extend notions of domination among vertices. These may serve as building blocks for new concepts of centrality that extend more directly, and more coherently, to more general types of data such as multilayer networks. We also give efficient algorithms to construct the associated partial rankings.

We present a low-constant approximation for metric k-median on an insertion-only stream of n points using $$O(\epsilon ^{-3} k \log n)$$O(ϵ-3klogn) space. In particular, we present a streaming $$(O(\epsilon ^{-3} k \log n), 2 + \epsilon )$$(O(ϵ-3klogn),2+ϵ)-bicriterion solution that reports cluster weights. It is well-known that running an offline algorithm on this bicriterion solution yields a $$(17.66 + \epsilon )$$(17.66+ϵ)-approximation.Previously, there have been two lines of research that trade off between space and accuracy in the streaming k-median problem. To date, the best-known $$(k,\epsilon )$$(k,ϵ)-coreset construction requires $$O(\epsilon ^{-2} k \log ^4 n)$$O(ϵ-2klog4n) space [8], while the best-known $$O(k \log n)$$O(klogn)-space algorithm provides only a $$(O(k \log n), 1063)$$(O(klogn),1063)-bicriterion [3]. Our work narrows this gap significantly, matching the best-known space while significantly improving the accuracy from 1063 to $$2+\epsilon $$2+ϵ. We also provide a matching lower bound, showing that any $${\text {polylog}}(n)$$polylog(n)-space streaming algorithm that maintains an $$(\alpha ,\beta )$$(α,β)-bicriterion must have $$\beta \ge 2$$β≥2.Our technique breaks the stream into segments defined by jumps in the optimal clustering cost, which increases monotonically as the stream progresses. By a storing an accurate summary of recent segments and a lower-space summary of older segments, our algorithm maintains a $$(O(\epsilon ^{-3} k \log n), 2 + \epsilon )$$(O(ϵ-3klogn),2+ϵ)-bicriterion solution for the entire input.

We present a general approach for analyzing structural parameters of a relational event graph within arbitrary query time intervals using colored range query data structures. Relational event graphs generally represent social network datasets, where each graph edge carries a timestamp. We provide data structures based on colored range searching to efficiently compute several graph parameters (e.g., density, neighborhood overlap, h-index).

The axiomatic approach with the interval function and induced path transit function of a connected graph is an interesting topic in metric and related graph theory. In this paper, we introduce a new axiom:(bp) for any $$ x,y,z \in V$$x,y,z∈V, $$R(x,y)=\{x,y\} \Rightarrow y\in R(x,z)$$R(x,y)={x,y}⇒y∈R(x,z) or $$x\in R(y,z)$$x∈R(y,z).We study axiom (bp) on the interval function and the induced path transit function of a connected, simple and finite graph. We present axiomatic characterizations of the interval function of bipartite graphs and complete bipartite graphs. Further, we present an axiomatic characterization of the induced path transit function of a tree or a 4-cycle.

Winner determination problem under Chamberlin-Courant system deals with the problem of selecting a fixed-size assembly from a set of candidates that minimizes the sum of misrepresentation values. This system does not restrict the candidates to have a minimum number of votes to be selected. The problem is known to be NP-hard. In this paper, we consider domination analysis of a 2-Opt heuristic for this problem. We show that the 2-Opt heuristic produces solutions no worse than the average solution in polynomial time. We also show that the domination number of the 2-Opt heuristic is at least $${m-1 \atopwithdelims ()k-1}k^{n-1}$$m-1k-1kn-1 for n voters and m candidates.

Structural parameterizations for hard problems have proven to be a promising venture for discovering scenarios where the problem is tractable. In particular, when a problem is already known to be polynomially solvable for some class of inputs, then it is natural to parameterize by the distance of a general instance to a tractable class. In the context of graph algorithms, parameters like vertex cover, twin cover, treewidth and treedepth modulators, and distances to various special graph classes are increasingly popular choices for hard problems.Our main focus in this work is the Graph Motif problem, which involves finding a connected induced subgraph in a vertex colored graph that respects a given palette. This problem is known to be hard in the traditional setting even for fairly structured classes of graphs. In particular, Graph Motif is known to be $$\mathsf {W[1]}$$W[1]-hard when parameterized by the distance to split graphs, and para-$$\mathsf {NP}$$NP-hard when parameterized by the distance to co-graphs (which are the class of -free graphs). On the other hand, it is known to be $$\mathsf {FPT}$$FPT when parameterized by the distance to a clique or the distance to an independent set (or equivalently, vertex cover). Towards finding the boundary of tractability, we consider parameterizing the problem by the distance to threshold graphs, which are graphs that are both split and -free. Note that this is a natural choice of an intermediate parameter in that it is larger than the parameters for which the problem is hard and smaller than the ones for which the problem is tractable. Our main contribution is an $$\mathsf {FPT}$$FPT algorithm for the Graph Motif problem when parameterized by the distance to threshold graphs. We also address some related structural parameterizations for Chromatic Number. Here, we show that the problem admits a polynomial kernel when parameterized by the vertex deletion distance to a clique.

An (m, n)-colored mixed graph G is a graph with its arcs having one of the m different colors and edges having one of the n different colors. A homomorphism f of an (m, n)-colored mixed graph G to an (m, n)-colored mixed graph H is a vertex mapping such that if uv is an arc (edge) of color c in G, then f(u)f(v) is an arc (edge) of color c in H. The $$(\textit{m,n})$$(m,n)-colored mixed chromatic number$$\chi _{(m,n)}(G)$$χ(m,n)(G) of an (m, n)-colored mixed graph G is the order (number of vertices) of a smallest homomorphic image of G. This notion was introduced by Nešetřil and Raspaud (2000, J. Combin. Theory, Ser. B 80, 147–155). They showed that $$\chi _{(m,n)}(G) \le k(2m+n)^{k-1}$$χ(m,n)(G)≤k(2m+n)k-1 where G is a acyclic k-colorable graph. We prove the tightness of this bound. We also show that the acyclic chromatic number of a graph is bounded by $$k^2 + k^{2 + \lceil \log _{(2m+n)} \log _{(2m+n)} k \rceil }$$k2+k2+⌈log(2m+n)log(2m+n)k⌉ if its (m, n)-colored mixed chromatic number is at most k. Furthermore, using probabilistic method, we show that for connected graphs with maximum degree $$\varDelta $$Δ its (m, n)-colored mixed chromatic number is at most $$2(\varDelta -1)^{2m+n} (2m+n)^{\varDelta -\min (2m+n, 3)+2}$$2(Δ-1)2m+n(2m+n)Δ-min(2m+n,3)+2. In particular, the last result directly improves the upper bound $$2\varDelta ^2 2^{\varDelta }$$2Δ22Δ of oriented chromatic number of graphs with maximum degree $$\varDelta $$Δ, obtained by Kostochka et al. (1997, J. Graph Theory 24, 331–340) to $$2(\varDelta -1)^2 2^{\varDelta }$$2(Δ-1)22Δ. We also show that there exists a connected graph with maximum degree $$\varDelta $$Δ and (m, n)-colored mixed chromatic number at least $$(2m+n)^{\varDelta /2}$$(2m+n)Δ/2.

We solve a min-max movement problem in which there are n sensors in path network in plane, where any sensor communicates only with its two immediate neighbors and only at a given maximum communication distance $$\lambda $$λ. We need to move sensors so that each sensor is in the communication range of its two neighbors, keeping the path topology intact. We present an $$O(n^3)$$O(n3) algorithm for min-max movement problem in a convex path-network which minimizes the maximum movement among the sensors. We also generalize our algorithm for ring, non-convex path, tethered and heterogeneous networks.

In this paper we show that the problem of deciding whether the visibility graph of a point set is 5-colourable, is NP-complete. We give an example of a point visibility graph that has chromatic number 6 while its clique number is only 4.

A $$P_3$$P3-decomposition of a graph is a partition of the edges of the graph into paths of length two. We give a simple necessary and sufficient condition for a semi-complete multigraph, that is a multigraph with at least one edge between each pair of vertices, to have a $$P_3$$P3-decomposition. We show that this condition can be tested in strongly polynomial-time, and that the same condition applies to a larger class of multigraphs. We give a similar condition for a $$P_3$$P3-decomposition of a semi-complete directed graph. In particular, we show that a tournament admits a $$P_3$$P3-decomposition iff its outdegree sequence is the degree sequence of a simple undirected graph.

In this paper, a set of generators (in a unique from) called the distinguished set of generators, of a cyclic code C of length $$n = 2^k$$n=2k (where k is a natural number) over $$Z_8$$Z8 is obtained. This set of generators is used to find the rank of the cyclic code C. It is proved that the rank of a cyclic code C of length $$n=2^k$$n=2k over $$Z_8$$Z8 is equal to $$n-v$$n-v, where v is the degree of a minimal degree polynomial in C. Then a description of all MHDR (maximum hamming distance with respect to rank) cyclic codes of length $$n=2^k$$n=2k over $$Z_8$$Z8 is given. An example of the best codes over $$Z_8$$Z8 of length 4 having largest minimum Hamming, Lee and Euclidean distances among all codes of the same rank is also given.

Let $$G=(V,E)$$G=(V,E) be a graph and $$\varGamma $$Γ be an abelian group both of order n. For $$D \subset \{0,1,\ldots , diam(G)\}$$D⊂{0,1,…,diam(G)}, the D-distance neighbourhood of a vertex v in G is defined to be the set $$N_D(v)=\{x \in V \ | \ d(x,v) \in D\}$$ND(v)={x∈V|d(x,v)∈D}. A bijection $$f: V \rightarrow \varGamma $$f:V→Γ is called a $$(\varGamma , D)$$(Γ,D)-distance magic labeling of G if there exists an $$\alpha \in \varGamma $$α∈Γ such that $$\sum _{x \in N_D(v)} f(x)=\alpha $$∑x∈ND(v)f(x)=α for every $$v \in V$$v∈V. In this paper we study $$(\varGamma , D)$$(Γ,D)-distance magic labeling of the graph $$C_n^r$$Cnr for $$D=\{d\}$$D={d}. We obtain $$(\varGamma , \{d\})$$(Γ,{d})-distance magic labelings of $$C_n^r$$Cnr with respect to certain classes of abelian groups. We also obtain necessary conditions for existence of such labelings.

Broadcasting is an information disseminating process of distributing a message from an originator vertex v of graph $$G=(V,E)$$G=(V,E) to all of its vertices. The broadcast time of vertex v is the minimum possible time required to broadcast from v in graph G. A graph G on n vertices is called broadcast graph if broadcasting from any originator in G can be accomplished in $$\lceil \log n\rceil $$⌈logn⌉ time. A broadcast graph with the minimum number of edges is called minimum broadcast graph. The number of edges in a minimum broadcast graph on n vertices is denoted by B(n). Finding the values of B(n) is very difficult. A large number of papers present techniques to construct broadcast graphs and to obtain upper bounds on B(n). In this paper, we first find new dimensional broadcast schemes for Knödel graphs, and then use them to give a general upper bound on B(n) for almost all odd n.

We consider the problem of updating the visibility polygon of a point located within the given simple polygon as that polygon is modified with the incremental addition of new vertices to it. In particular, we propose the following two semi-dynamic algorithms: Given a simple polygon P defined with n vertices and a point $$p \in P$$p∈P, our preprocessing algorithm computes the visibility polygon of p in P and constructs relevant data structures in O(n) time; for every vertex v added to the current simple polygon, our visibility polygon updation algorithm takes $$O((k+1)\lg {n})$$O((k+1)lgn) time in the worst-case to update the visibility polygon of p in the new simple polygon resulted from adding v. Here, k is the change in combinatorial complexity of visibility polygon of p due to the addition of new vertex v.Given a simple polygon P defined with n vertices and an edge pq of P, our preprocessing algorithm computes the weak visibility polygon of pq in P and constructs relevant data structures in O(n) time; for every vertex v added to the current simple polygon, our weak visibility updation algorithm takes $$O((k+1)\lg {n})$$O((k+1)lgn) time in the worst-case to update the weak visibility polygon of pq in the new simple polygon resulted from adding v. Here, k is the change in combinatorial complexity of shortest path tree rooted at p added to the change in combinatorial complexity of shortest path tree rooted at q, wherein both these changes are due to the addition of new vertex v.

In this paper we consider Euclidean liar’s domination problem, a variant of dominating set problem. In the Euclidean liar’s domination problem, a set $$\mathcal{P}=\{p_1,p_2,\ldots ,p_n\}$$P={p1,p2,…,pn} of n points are given in the Euclidean plane. For $$p \in \mathcal{P}$$p∈P, N[p] is a subset of $$\mathcal{P}$$P such that for any $$q \in N[p]$$q∈N[p], the Euclidean distance between p and q is less than or equal to 1. The objective of the Euclidean liar’s domination problem is to find a subset $$D (\subseteq \mathcal{P})$$D(⊆P) of minimum size having the following properties: (i) $$|N[p_i] \cap D| \ge 2$$|N[pi]∩D|≥2 for $$1 \le i \le n$$1≤i≤n, and (ii) $$|(N[p_i] \cup N[p_j]) \cap D| \ge 3$$|(N[pi]∪N[pj])∩D|≥3 for $$i\ne j, 1\le i,j \le n$$i≠j,1≤i,j≤n. We first propose a simple $$O(n\log n)$$O(nlogn) time $$\frac{63}{2}$$632-factor approximation algorithm for the liar’s domination problem. Next we propose approximation algorithms to improve the approximation factor to $$\frac{732}{k}$$732k for $$3 \le k \le 183$$3≤k≤183, and $$\frac{846}{k}$$846k for $$3 \le k\le 282$$3≤k≤282. The running time of the algorithms is $$O(n^{k+1}\varDelta )$$O(nk+1Δ), where $$\varDelta = \max \{|N[p]| : p\in \mathcal{P}\}$$Δ=max{|N[p]|:p∈P}.

For the Restricted Assignment Problem the best known polynomial algorithm is a 2-approximation by Lenstra, Shmoys and Tardos [7]. Even for the case with only two different processing times the ratio above has merely been improved by a tiny margin [2].In some cases where the restrictions on one or both job sizes are somewhat structured, simple combinatorial algorithms are known that provide better approximation ratios than the algorithm above.In this paper we study two classes of structured restrictions, that we refer to as the Inclusion Chain Class and the Two Partition Class. We present a 1.5-approximation for each of them.

We address the complexity of finding a vertex with specific (or maximum) (out)degree in undirected graphs, directed graphs and in tournaments in a model where we count only the probes to the adjacency matrix of the graph. Improving upon some earlier bounds, using adversary arguments, we show that the following problems require $${n \atopwithdelims ()2}$$n2 probes to the adjacency matrix of an n node graph:determining whether a given directed graph has a vertex of outdegree k (for a non-negative integer $$k \le (n+1)/2$$k≤(n+1)/2);determining whether an undirected graph has a degree 0 or 1 vertex;finding the maximum (out)degree in a directed or an undirected graph, andfinding all vertices with the maximum outdegree in a tournament.A property of a simple graph is elusive, if any algorithm to determine the property requires all the relevant probes to the adjacency matrix of the graph in the worst case. So the above results imply that determining whether a directed graph has a vertex of (out)degree k (for a non-negative integer $$k \le (n+1)/2$$k≤(n+1)/2) or an undirected graph has a vertex of degree 0 or 1 vertex are elusive properties.In contrast, we show that one can find a maximum outdegree in a tournament using at most $${n \atopwithdelims ()2} -1$$n2-1 probes. By substantially improving a known lower bound, we show that, for this problem $${n \atopwithdelims ()2} -2$$n2-2 probes are necessary if n is odd, and $${n \atopwithdelims ()2} -n/2 -2$$n2-n/2-2 probes are necessary if n is even. For determining the existence of a vertex with degree $$k > 1$$k>1 in an undirected graph, we give a lower bound of $$.42n^2$$.42n2 improving on the earlier lower bound of $$.25n^2$$.25n2.

Given a graph G, a non-negative integer k, and a weight function that maps each vertex in G to a positive real number, the Maximum Weighted Budgeted Independent Set (MWBIS) problem is about finding a maximum weighted independent set in G of cardinality at most k. A special case of MWBIS, when the weight assigned to each vertex is equal to its degree in G, is called the Maximum Independent Vertex Coverage (MIVC) problem. In other words, the MIVC problem is about finding an independent set of cardinality at most k with maximum coverage.Håstad in [Clique is hard to approximate within $$n^{1-\epsilon }$$n1-ϵ. Foundations of Computer Science, 1996.] showed that there is no $$\frac{1}{n^{1-\epsilon }}$$1n1-ϵ-factor approximation algorithm for the well-known Maximum Weighted Independent Set (MWIS) problem, where $$\epsilon > 0$$ϵ>0, assuming NP-hard problems have no randomized polynomial time algorithms. Being a generalization of the MWIS problem, the above-mentioned inapproximability result applies to MWBIS too. Due to the existence of such inapproximability results for MWBIS in general graphs, in this paper, we restrict our study of MWBIS to the class of bipartite graphs. We show that, unlike MWIS, the MIVC (and thereby the MWBIS) problem in bipartite graphs is NP-hard. Then, we show that the MWBIS problem admits an easy, greedy $$\frac{1}{2}$$12-factor approximation algorithm in the class of bipartite graphs, which matches the integrality gap of a natural LP relaxation. This rules out the possibility of any LP-based algorithm that uses the natural LP relaxation to yield a better factor of approximation.

Hitting and Covering problems have been extensively studied in the last few decades and have applications in diverse areas. While the hitting and covering problems are NP-hard for most settings, they are polynomial solvable for intervals. Demand hitting is a generalization of the hitting problem, where there is an integer demand associated with each object, and the demand hitting set must contain at least as many points as the demand of each object. In this paper, we consider the demand hitting and covering problems for intervals that have no containment. For the unweighted setting, we give a simple greedy algorithm. In the weighted setting, we model this problem as a min-cost max flow problem using a non-trivial reduction and solve it using standard flow algorithms.

Graph coloring problem asks to assign a color to every vertex such that adjacent vertices get different color. There have been different ways to generalize classical graph coloring problem. Among them, we study (k, i)-coloring of a graph. In (k, i)-coloring, every vertex is assigned a set of k colors so that adjacent vertices share at most i colors between them. The (k, i)-chromatic number of a graph is the minimum number of total colors used to assign a proper (k, i)-coloring. It is clear that (1, 0)-coloring is equivalent to the classical graph coloring problem. We extend the study of exact and parameterized algorithms for classical graph coloring problem to (k, i)-coloring of graphs. Given a graph with n vertices and m edges, we design algorithms that take$$\mathcal {O}(2^{kn}\cdot n^{{\mathcal O}(1)})$$O(2kn·nO(1)) time to determine the (k, 0)-chromatic number.$$\mathcal {O}(4^n \cdot n^{{\mathcal O}(1)})$$O(4n·nO(1)) time to determine the (k, k-1)-chromatic number.$$\mathcal {O}(2^{kn}\cdot k^{im} \cdot n^{{\mathcal O}(1)})$$O(2kn·kim·nO(1)) time to determine the (k, i)-chromatic number.We prove that (k, i)-coloring is fixed parameter tractable when parameterized by the size of the vertex cover or the treewidth of the graph. We also provide some observations on (k, i)-colorings on perfect graphs.

Graphs (1-skeletons) of Traveling-Salesman-related polytopes have attracted a lot of attention. Pedigree polytopes are extensions of the classical Symmetric Traveling Salesman Problem polytopes (Arthanari 2000) whose graphs contain the TSP polytope graphs as spanning subgraphs (Arthanari 2013). Unlike TSP polytopes, Pedigree polytopes are not “symmetric”, e.g., their graphs are not vertex transitive, not even regular.We show that in the graph of the pedigree polytope, the quotient minimum degree over number of vertices tends to 1 as the number of cities tends to infinity.

For a graph $$G=(V,E)$$, a set $$M\subseteq E$$ is called a matching in G if no two edges in M share a common vertex. A matching M in G is called an induced matching in G if G[M], the subgraph of G induced by M, is same as G[S], the subgraph of G induced by $$S=\{v \in V |$$ v is incident on an edge of M$$\}$$. The Maximum Induced Matching problem is to find an induced matching of maximum cardinality. Given a graph G and a positive integer k, the Induced Matching Decision problem is to decide whether G has an induced matching of cardinality at least k. The Induced Matching Decision problem is NP-complete on bipartite graphs, but polynomial time solvable for convex bipartite graphs. In this paper, we show that the Induced Matching Decision problem is NP-complete for star-convex bipartite graphs and perfect elimination bipartite graphs. On the positive side, we propose polynomial time algorithms to solve the Maximum Induced Matching problem in circular-convex bipartite graphs and triad-convex bipartite graphs by making polynomial reductions from the Maximum Induced Matching problem in these graph classes to the Maximum Induced Matching problem in convex bipartite graphs.

In this paper, we investigate the well-studied Hamiltonian cycle problem, and present an interesting dichotomy result on split graphs. T. Akiyama, T. Nishizeki, and N. Saito [23] have shown that the Hamiltonian cycle problem is NP-complete in planar bipartite graph with maximum degree 3. Using this reduction, we show that the Hamiltonian cycle problem is NP-complete in split graphs. In particular, we show that the problem is NP-complete in $$K_{1,5}$$K1,5-free split graphs. Further, we present polynomial-time algorithms for Hamiltonian cycle in $$K_{1,3}$$K1,3-free and $$K_{1,4}$$K1,4-free split graphs. We believe that the structural results presented in this paper can be used to show similar dichotomy result for Hamiltonian path and other variants of Hamiltonian cycle problem.

Line of Sight (LoS) networks provide a model of wireless communication which incorporates visibility constraints. Vertices of such networks can be embedded in finite d-dimensional grids of size n, and two vertices are adjacent if they share a line of sight and are at distance less than $$\omega $$ω. In this paper we study large independent sets in LoS networks. We prove that the computational problem of finding a largest independent set can be solved optimally in polynomial time for one dimensional LoS networks. However, for $$d\ge 2$$d≥2, the (decision version of) the problem becomes NP-hard for any fixed $$\omega \ge 3$$ω≥3 and even if $$\omega $$ω is chosen to be a function of n that is $$O(n^{1-\epsilon })$$O(n1-ϵ) for any fixed $$\epsilon > 0$$ϵ>0. In addition we show that the problem is also NP-hard when $$\omega = n$$ω=n for $$d \ge 3$$d≥3. This result extends earlier work which showed that the problem is solvable in polynomial time for gridline graphs when $$d=2$$d=2. Finally we describe simple algorithms that achieve constant factor approximations and present a polynomial time approximation scheme for the case where $$\omega $$ω is constant.

The cd-coloring is motivated by the super-peer architecture in peer-to-peer resource sharing technology. A vertex set partition of a graph G into k independent sets $$V_1, V_2, \ldots , V_k$$V1,V2,…,Vk is called a k-color domination partition (k-cd-coloring) of G if there exists a vertex $$u_i\in V(G)$$ui∈V(G) such that $$u_i$$ui dominates $$V_i$$Vi in G for $$1 \le i \le k$$1≤i≤k and the smallest integer k for which G admits a k-cd-coloring is called the cd-chromatic number of G, denoted by $$\chi _{cd}(G)$$χcd(G). A subclique is a set S of vertices of a graph G such that for any $$x,y\in S$$x,y∈S, $$d(x,y)\ne 2$$d(x,y)≠2 in G and the cardinality of a maximum subclique in G is denoted by $$\omega _{s}(G)$$ωs(G). Clearly, $$\omega _{s}(G) \le \chi _{cd}(G)$$ωs(G)≤χcd(G) for a graph G.In this paper, we explore the complexity status of Subclique: for a given graph G and a positive integer k, Subclique is to decide whether G has a subclique of size at least k. We prove that Subclique is NP-complete for (i) bipartite graphs, (ii) chordal graphs, and (iii) the class of H-free graphs when H is a fixed graph on 5-vertices. In addition, we prove that Subclique for the class of H-free graphs is polynomial time solvable only if H is an induced subgraph of $$P_4$$P4; otherwise the problem is NP-complete. Moreover, Subclique is polynomial time solvable for trees, split graphs, and co-bipartite graphs.

Let a, b and k be three integers with $$b>a\ge 2$$b>a≥2 and $$k\ge 0$$k≥0, and let G be a graph. If $$G-U$$G-U contains a Hamiltonian cycle for any $$U\subseteq V(G)$$U⊆V(G) with $$|U|=k$$|U|=k, then G is called a k-Hamiltonian graph. An [a, b]-factor F of a graph G is Hamiltonian if F admits a Hamiltonian cycle. If $$G-U$$G-U includes a Hamiltonian [a, b]-factor for every subset $$U\subseteq V(G)$$U⊆V(G) with $$|U|=k$$|U|=k, then we say that G has a k-Hamiltonian [a, b]-factor. In this paper, we prove that if G is a k-Hamiltonian graph with $$ 1\le \alpha (G)\le \frac{4(b-2)(\delta (G)-a-k+1)}{(a+k+1)^{2}}, $$1≤α(G)≤4(b-2)(δ(G)-a-k+1)(a+k+1)2,then G admits a k-Hamiltonian [a, b]-factor. Furthermore, it is shown that this result is sharp.

Let m, n, r and $$k_i$$ki$$(1\le i\le m)$$(1≤i≤m) be positive integers with $$n\le m$$n≤m and $$k_1\ge k_2\ge \cdots \ge k_m\ge 2r-1$$k1≥k2≥⋯≥km≥2r-1. Let G be a graph, and let $$H_1,H_2,\cdots ,H_r$$H1,H2,⋯,Hr be vertex-disjoint n-subgraphs of G. It is verified in this article that every $$[0,k_1+k_2+\cdots +k_m-n+1]$$[0,k1+k2+⋯+km-n+1]-graph G includes a subgraph R such that R has a $$[0,k_i]_1^{n}$$[0,ki]1n-factorization orthogonal to every $$H_i$$Hi, $$1\le i\le r$$1≤i≤r.