Search

Let n, k, t be positive integers. What is the maximum number of arcs in a digraph on n vertices in which there are at most t distinct walks of length k with the same endpoints? Determine the extremal digraphs attaining the maximum number. When $$t=1$$ , the problem has been studied by Wu, by Huang and Zhan, by Huang, Lyu and Qiao, by Lyu in four papers, and they solved all the cases but $$k=3$$ . For $$t\ge 2$$ , Huang and Lyu proved that the maximum number is equal to $$n(n-1)/2$$ and the extremal digraph is the transitive tournament when $$n\ge 6t+2$$ and $$k\ge n-1$$ . They also discussed the maximum number for the case $$n=k+2,k+3,k+4$$ . In this paper, we solve the problem for the case $$k\ge 6t+1$$ and $$n\ge k+5$$ , and we also characterize the structures of the extremal digraphs for $$n=k+2,k+3,k+4$$ .

In this paper, we study a dynamic coloring of the vertices of a graph G that starts with an initial subset S of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set S is a zero forcing set of G if, by iteratively5 applying the forcing process, every vertex in G becomes colored. The zero forcing number of G is the minimum cardinality of a zero forcing set of G. In this paper, we prove that if $$G \ne K_4$$ is a connected cubic graph, then the zero forcing number of G is bounded above by twice its domination number, where the domination number of G is the minimum cardinality of a set of vertices of G such that every vertex not in S is adjacent to some vertex in S.

In a graph $$G=(V,E)$$ , each vertex $$v\in V$$ is assigned 0, 1 or 2 such that each vertex assigned 0 is adjacent to at least one vertex assigned 2 or two vertices assigned 1. Such an assignment is called an Italian dominating function (IDF) of G. The weight of an IDF f is $$w(f)=\sum _{v\in V}f(v)$$ . The Italian domination number of G is $$\gamma _{I}(G)=\min _{f} w(f)$$ . In this paper, we investigate the Italian domination number of the Cartesian product of paths, $$P_n\Box P_m$$ . We obtain the exact values of $$\gamma _{I}(P_n\Box P_2)$$ and $$\gamma _{I}(P_n\Box P_3)$$ . Also, we present a bound of $$\gamma _{I}(P_n\Box P_m)$$ for $$m\ge 4$$ , that is $$\frac{mn}{3}+\frac{m+n-4}{9}\le \gamma _{I}(P_{n}\Box P_{m})\le \frac{mn+2m+2n-8}{3}$$ where the lower bound is improved since the general lower bound is $$\frac{mn}{3}$$ presented by Chellali et al. (Discrete Appl Math 204:22–28, 2016). By the results of this paper, together with existing results, we give $$P_n\Box P_2$$ and $$P_n\Box P_3$$ are examples for which $$\gamma _{I}=\gamma _{r2}$$ where $$\gamma _{r2}$$ is the 2-rainbow domination number. This can partially solve the open problem presented by Bresar et al. (Discrete Appl Math 155:2394–2400, 2007). Finally, Vizing’s conjecture on Italian domination in $$P_n\Box P_m$$ is checked.

For a given simple graph $$G=(V,E)$$ , a latency bound t and a threshold function $$\theta (v)=\lceil \rho d(v)\rceil $$ , where $$\rho \in (0,1)$$ and d(v) denotes the degree of the vertex $$v(\in V)$$ , a subset $$S\subseteq V$$ is called a strong target set if for each vertex $$v\in S$$ , the number of its neighborhood in S not including itself is at least $$\theta (v)$$ , and all vertices in V can be activated by S through a process with t rounds. Initially, all vertices in S become activated. At the ith round of the process, each vertex is activated if the number of active vertices in its neighbor after $$i-1$$ rounds exceeds its threshold. The $$t$$ -Latency Bounded Strong Target Set Selection (t-LBSTSS) problem is to find such a strong target set S with the minimum cardinality in G. In general graphs, the t-LBSTSS problem is not only NP-hard, but also hard to be approximated. The aim of this paper is to find an optimal t-latency bounded strong target set for some special family of graphs. For a given simple graph G, a simple, tight but nontrivial inequality in terms of the number of edges in G is proposed to obtain the lower bound of the sum of degrees in a strong target set S to the t-LBSTSS problem. Moreover, a necessary and sufficient condition is presented for equality to hold. Finally, we give the exact formulas for the optimal solutions to the t-LBSTSS problem in two kinds of natural family of graphs, while it seems difficult to tell without the inequality given in this paper.

This paper addresses a partial inverse combinatorial optimization problem, called the partial inverse min–max spanning tree problem. For a given weighted graph G and a forest F of the graph, the problem is to modify weights at minimum cost so that a bottleneck (min–max) spanning tree of G contains the forest. In this paper, the modifications are measured by the weighted Manhattan distance. The main contribution is to present two algorithms to solve the problem in polynomial time. This result is considerable because the partial inverse minimum spanning tree problem, which is closely related to this problem, is proved to be NP-hard in the literature. Since both the algorithms have the same worse-case complexity, some computational experiments are reported to compare their running time.

For a connected graph $$G = (V, E)$$ , a subset F of E is an edge dominating set (resp. a total edge dominating set) if every edge in $$E-F$$ (resp. in E) is adjacent to at least one edge in F, the minimum cardinality of an edge dominating set (resp. a total edge dominating set) of G is the edge domination number (resp. total edge domination number) of G, denoted by $$\gamma '(G)$$ (resp. $$\gamma '_t(G)$$ ). In the present paper, we study a parameter, called the semitotal edge domination number, which is squeezed between $$\gamma '(G)$$ and $$\gamma '_t(G)$$ . A semitotal edge dominating set is an edge dominating set S such that, for every edge e in S, there exists such an edge $$e'$$ in S that e either is adjacent to $$e'$$ or shares a common neighbor edge with $$e'$$ . The semitotal edge domination number, denoted by $$\gamma ^{'}_{st}(G)$$ , is the minimum cardinality of a semitotal edge dominating set of G. In this paper, we prove that the problem of deciding whether $$\gamma ^{'}(G)=\gamma ^{'}_{st}(G)$$ or $$\gamma _t^{'}(G)=\gamma ^{'}(G)$$ is NP-hard even when restricted to planar graphs with maximum degree 4. We also characterize trees with equal edge domination and semitotal edge domination numbers (Pan et al. in The complexity of total edge domination and some related results on trees, J Comb Optim, 2020, https://doi.org/10.1007/s10878-020-00596-y , we characterized trees with equal edge domination and total edge domination numbers).

A fractional matching of a graph G is a function f that assigns to each edge a number in [0, 1] such that for each vertex v, $$\sum \nolimits _{e\in \Gamma (v)}f(e) \le 1$$, where $$\Gamma (v)$$ is the set of all edges incident with v. The fractional matching number $$\mu _{f}(G)$$ of G is the supremum of $$\sum \nolimits _{e\in E(G)}f(e)$$ over all fractional matchings f of G. Let $$D_f(G)$$ be the set of vertices which are unsaturated by some maximum fractional matching of G, $$A_f(G)$$ the set of vertices in $$V(G)-D_f(G)$$ adjacent to a vertex in $$D_f(G)$$ and $$C_f(G)=V(G)-A_f(G)-D_f(G)$$. In this paper, the partition $$(C_f(G), A_f(G), D_f(G))$$, named fractional Gallai–Edmonds decomposition, is obtained by an algorithm in polynomial time via the Gallai–Edmonds decomposition. A graph G is maximal on $$\mu _{f}(G)$$ if any addition of edge increases the fractional matching number $$\mu _{f}(G)$$. The Turan number is the maximum of edge numbers of maximal graphs and the saturation number is the minimum of edge numbers of maximal graphs. In this paper, the maximal graphs are characterized by using the fractional Gallai–Edmonds decomposition. Thus the Turan number, saturation number and extremal graphs are obtained.

Given a simple graph G, let $$Z(G),\, p(G),\, \Phi (G), ex(G)$$ and M(G), respectively, be the zero forcing number, the number of pendant vertices, the cyclomatic number, the number of exterior major vertices and the maximum nullity of G. Wang et al. (Linear Multilinear Algebra, 2018. https://doi.org/10.1080/03081087.2018.1545829) established upper and lower bounds on Z(G) with respect to $$p(G),\, ex(G)$$ and $$\Phi (G)$$: $$p(G)-ex(G)-1\leqslant Z(G)\leqslant p(G)+2\Phi (G)+1$$. Hence, it is interesting to study the distribution of the zero forcing number Z(G) in the interval $$[p(G)-ex(G)-1,\, p(G)+2\Phi (G)+1]$$. Wang et al. (2018) determined all the connected graphs G with $$Z(G)=p(G)-ex(G)$$ and $$Z(G)=p(G)+2\Phi (G)-1.$$ In this paper we identify all the connected graphs G with $$Z(G)=p(G)-ex(G)+1$$ and $$Z(G)=p(G)+2\Phi (G)-2.$$ On the other hand, ‘AIM Minimum Rank-Special Graphs Work Group’ (Linear Algebra Appl 428(7):1628–1648, 2008) established the inequality $$Z(G)\geqslant M(G)$$. The authors posted an attractive question: What is the class of graphs G for which $$Z(G)=M(G)$$? In this paper, we show that the equality holds for threshold graphs.

The first and the second Zagreb indices of a graph G are defined as $$M_1(G)= \sum _{v\in V_G}d_v^2 $$ and $$ M_2(G)= \sum _{uv\in E_G}d_ud_v$$ , where $$d_v,\, d_u$$ are the degrees of vertices $$v,\, u$$ in G. The difference of Zagreb indices of G is defined as $$\Delta M(G)=M_2(G)-M_1(G)$$ . A cactus is a connected graph in which every block is either an edge or a cycle. Let $$\mathscr {C}_{n,k}$$ be the set of all n-vertex cacti with k pendant vertices and let $$\mathscr {C}_n^r$$ be the set of all n-vertex cacti with r cycles. In this paper, the sharp upper bound on $$\Delta M(G)$$ of graph G among $$\mathscr {C}_{n,k}$$ (resp. $$\mathscr {C}_n^r$$ ) is established. Combining the results in Furtula et al. (Discrete Appl Math 178:83–88, 2014) and our results obtained in the current paper, sharp upper bounds on $$\Delta M(G)$$ of n-vertex cacti and n-vertex unicyclic graphs are determined, respectively. All the extremal graphs are characterized.

The k-means problem has been paid lots of attention in many fields, and each cluster of the k-means problem always satisfies locality property. In this paper, we study the constrained k-means problem, where the clusters do not satisfy locality property and can be an arbitrary partition of the set of points. Ding and Xu presented a unified framework with running time $$O(2^{poly (k/\epsilon )} (\log n)^{k+1} nd)$$ by applying uniform sampling and simplex lemma techniques such that a collection of size $$O(2^{poly (k/\epsilon )} (\log n)^{k+1})$$ of candidate sets containing approximate centers is obtained. Then, the collection is enumerated to get the one that can induce a $$(1+\epsilon )$$ -approximation solution for the constrained k-means problem. By applying $$D^2$$ -sampling technique, Bhattacharya, Jaiswal, and Kumar presented an algorithm with running time $$O(2^{{\tilde{O}}(k/\epsilon )}nd)$$ , which is bounded by $$O(2^k( \frac{2123ek}{\epsilon ^3})^{64k/\epsilon }knd)$$ . The algorithm outputs a collection of size $$O(2^k( \frac{2123ek}{\epsilon ^3})^{64k/\epsilon })$$ of candidate sets containing approximate centers. In this paper, we present an algorithm with running time $$O((\frac{1891ek}{\epsilon ^2})^{8k/\epsilon }nd)$$ such that a collection of size $$O((\frac{1891ek}{\epsilon ^2})^{8k/\epsilon }n)$$ of candidate sets containing approximate centers can be obtained.

In this paper we study the m-clique free interval subgraphs. We investigate the facial structure of the polytope defined as the convex hull of the incidence vectors associated with these subgraphs. We also present some facet-defining inequalities to strengthen the associated linear relaxation. As an application, the generalized open-shop problem with disjunctive constraints (GOSDC) is considered. Indeed, by a projection on a set of variables, the m-clique free interval subgraphs represent the solution of an integer linear program solving the GOSDC presented in this paper. Moreover, we propose exact and heuristic separation algorithms, which are exploited into a Branch-and-cut algorithm for solving the GOSDC. Finally, we present and discuss some computational results.

This paper considers the channel assignment problem in mobile communications systems. Suppose there are many base stations in an area, each of which demands a number of channels to transmit signals. The channels assigned to the same base station must be separated in some extension, and two channels assigned to two different stations that are within a distance must be separated in some other extension according to the distance between the two stations. The aim is to assign channels to stations so that the interference is controlled within an acceptable level and the spectrum of channels used is minimized. This channel assignment problem can be modeled as the multiple t-separated $$L(j_1,j_2,\ldots ,j_m)$$ -labeling of the interference graph. In this paper, we consider the case when all base stations demand the same number of channels. This case is referred as n-fold t-separated $$L(j_1,j_2,\ldots ,j_m)$$ -labeling of a graph. This paper first investigates the basic properties of n-fold t-separated $$L(j_1,j_2,\ldots ,j_m)$$ -labelings of graphs. And then it focuses on the special case when $$m=1$$ . The optimal n-fold t-separated L(j)-labelings of all complete graphs and almost all cycles are constructed. As a consequence, the optimal n-fold t-separated $$L(j_1,j_2,\ldots ,j_m)$$ -labelings of the triangular lattice and the square lattice are obtained for the case $$j_1=j_2=\cdots =j_m$$ . This provides an optimal solution to the corresponding channel assignment problems with interference graphs being the triangular lattice and the square lattice, in which each base station demands a set of n channels that are t-separated and channels from two different stations at distance at most m must be $$j_1$$ -separated. We also study a variation of n-fold t-separated $$L(j_1,j_2,\ldots ,j_m)$$ -labeling, namely, n-fold t-separated consecutive $$L(j_1,j_2,\ldots ,j_m)$$ -labeling. And present the optimal n-fold t-separated consecutive L(j)-labelings of all complete graphs and cycles.

An r-acyclic edge coloring of a graph G is a proper edge coloring such that any cycle C has at least $$\min \{|C|,r\}$$ colors. The least number of colors needed for an r-acyclic edge coloring of G is called the r-acyclic edge chromatic number or the r-acyclic chromatic index of G, denoted by $$A'_{r}\left( G\right) $$ . In this paper, we study the r-acyclic edge chromatic number with $$r\ge 4$$ and prove that $$A'_{r}\left( G\right) \le 2\Delta ^{\lfloor \tfrac{r}{2}\rfloor }+O\left( \Delta ^{\tfrac{r+1}{3}}\right) $$ . We also prove that when r is even, $$A'_{r}\left( G\right) \le \Delta ^{\tfrac{r}{2}}+O\left( \Delta ^{\tfrac{r+1}{3}}\right) $$ , which is asymptotically optimal. In addition, we investigate how the r-acyclic edge chromatic number performs as the girth increases. It is proved in this paper that for every graph G with girth at least $$2r-1$$ , $$A'_r\left( G\right) \le \left( 9r-7\right) \Delta +10r-12$$ holds. Our approach is based on the entropy compression method.

In this paper, three-sided stable matching problem is discussed, in which two sets, $$V_1$$V1 and $$V_2$$V2 are cooperative partners, and the agent of the other set U has a strict preference to the agents of set $$V_1$$V1 and set $$V_2$$V2 respectively. On the other side, the agents of set $$V_1$$V1 and set $$V_2$$V2 have a strict preference to the agent of set U . About this three-sided matching problem, this paper gives the definition of stable matching, proves that the problem must have a stable matching, and gives an algorithm that can obtain a stable matching.

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let $$T = (V, E, c, d, \ell , \mu )$$ be an undirected rooted tree, where each node $$v \in V$$ has a weight $$d(v) \ge 0$$ denoting the demand amount of v as well as a weight $$\ell (v) \ge 0$$ denoting the cost of opening a facility at v, and each edge $$e \in E$$ has a weight $$c(e) \ge 0$$ denoting the cost on e and is associated with a function $$\mu (e,t) \ge 0$$ denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset $$\mathcal {D} \subseteq V$$ of clients, and a subset $$\mathcal {F} \subseteq \mathcal {P}(T)$$ of continuum points admitting facilities where $$\mathcal {P}(T)$$ is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points $$x_1$$ and $$x_2$$ in $$\mathcal {F}$$ , the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at $$x_1$$ and $$x_2$$ , K times the cost of connecting $$x_1$$ and $$x_2$$ , and the cost of all the clients in $$\mathcal {D}$$ connecting to some facility. The objective is to open two facilities at a pair of continuum points in $$\mathcal {F}$$ to minimize the total cost, for a given input parameter $$K \ge 1$$ . This paper focuses on the case of $$\mathcal {D} = V$$ and $$\mathcal {F} = \mathcal {P}(T)$$ . We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of $$\mathcal {D} \subseteq V$$ and $$\mathcal {F} \subseteq \mathcal {P}(T)$$ .

This paper is concerned with the design and analysis of a certifying algorithm for checking the lattice point feasibility of a class of constraints called unit two variable per inequality (UTVPI) constraints. A UTVPI constraint has at most two non-zero variables and the coefficients of the non-zero variables belong to the set $$\{+\,1,\ -\,1\}$${+1,-1}. These constraints occur in a number of application domains, including but not limited to program verification, abstract interpretation, and operations research. As per the literature, the fastest known model generating algorithm for checking lattice point feasibility in UTVPI constraint systems runs in $$O(m \cdot n+n^{2} \cdot \log n)$$O(m·n+n2·logn) time and $$O(n^{2})$$O(n2) space, where m represents the number of constraints and n represents the number of variables in the constraint system (Lahiri and Musuvathi, in: Proceedings of the 5th international workshop on the frontiers of combining systems (FroCos), lecture notes in computer science, vol 3717, pp 168---183, 2005). In this paper, we design and analyze a new algorithm for checking the lattice point feasibility of UTVPI constraints. The presented algorithm runs in $$O(m \cdot n)$$O(m·n) time and $$O(m+n)$$O(m+n) space. Additionally it is certifying in that it produces a satisfying assignment in the event that it is presented with feasible instances and refutations in the event that it is presented with infeasible instances. The importance of providing certificates cannot be overemphasized, especially in mission-critical applications. Our approaches for the lattice point feasibility problem in UTVPI constraint systems is fundamentally different from existing approaches for this problem; indeed, it is based on new insights into combining well-known inference rules for these systems.

A $k$-submodular function is a generalization of submodular and bisubmodular functions. This paper establishes a compact representation for minimizers of a $k$-submodular function by a poset with inconsistent pairs (PIP). This is a generalization of Ando-Fujishige's signed poset representation for minimizers of a bisubmodular function. We completely characterize the class of PIPs (elementary PIPs) arising from $k$-submodular functions. We give algorithms to construct the elementary PIP of minimizers of a $k$-submodular function $f$ for three cases: (i) a minimizing oracle of $f$ is available, (ii) $f$ is network-representable, and (iii) $f$ arises from a Potts energy function. Furthermore, we provide an efficient enumeration algorithm for all maximal minimizers of a Potts $k$-submodular function. Our results are applicable to obtain all maximal persistent labelings in actual computer vision problems. We present experimental results for real vision instances., An earlier version of this paper was presented at the 4th International Symposium on Combinatorial Optimization (ISCO 2016), Vietri sul Mare, Italy, May 16--18, 2016

In this paper, we study the minimum partial set multi-cover problem (PSMC). Given an element set E, a collection of subsets \({\mathcal {S}}\subseteq 2^E\), a cost \(c_S\) on each set \(S\in {\mathcal {S}}\), a covering requirement \(r_e\) for each element \(e\in E\), and an integer k, the PSMC problem is to find a sub-collection \({\mathcal {F}}\subseteq {\mathcal {S}}\) to fully cover at least k elements such that the cost of \({\mathcal {F}}\) is as small as possible, where element e is fully covered by \({\mathcal {F}}\) if it belongs to at least \(r_e\) sets of \({\mathcal {F}}\). This paper presents an approximation algorithm using local ratio method achieving performance ratio \(\max \left\{ \frac{\Delta }{k}\left( \frac{1}{f-r_{\min }}+\frac{r_{\max }}{r_{\min }}\right) ,\frac{1}{\rho }+\frac{f}{r_{\min }}+\frac{1}{r_{\max }}-\frac{1}{\rho r_{\max }}-1,\frac{1}{\rho }\right\} \), where \(\Delta \) is the size of a maximum set, f is the maximum number of sets containing a common element, \(\rho \) is the minimum percentage of elements required to be fully covered during iterations of the algorithm, and \(r_{\max }\) and \(r_{\min }\) are the maximum and the minimum covering requirement, respectively. In particular, when \(r_{\max }\) is a constant, the first term can be omitted. Notice that our ratio coincides with the classic ratio f for both the set multi-cover problem (in which case \(k=|E|\)) and the partial set single-cover problem (in which case \(r_{\max }=1\)). However, when \(k 1\), the ratio might be as large as \(\Theta (n)\). This result shows an interesting “shock wave like” feature of approximating PSMC. The purpose of this paper is trying to arouse some interest in such a feature and attract more work on this challenging problem.

In this paper, we introduce a new relaxation of strong edge-coloring. Let G be a graph. For two nonnegative integers s and t, an (s, t)-relaxed strong k-edge-coloring is an assignment of k colors to the edges of G, such that for any edge e, there are at most s edges adjacent to e and t edges which are distance two apart from e assigned the same color as e. The (s, t)-relaxed strong chromatic index, denoted by $${\chi '}_{(s,t)}(G)$$źź(s,t)(G), is the minimum number k of an (s, t)-relaxed strong k-edge-coloring admitted by G. This paper studies the (s, t)-relaxed strong edge-coloring of graphs, especially trees. For a tree T, the tight upper bounds for $${\chi '}_{(s,0)}(T)$$źź(s,0)(T) and $${\chi '}_{(0,t)}(T)$$źź(0,t)(T) are given. And the (1, 1)-relaxed strong chromatic index of an infinite regular tree is determined. Further results on $${\chi '}_{(1,0)}(T)$$źź(1,0)(T) are also presented.

The popular matching problem introduced by Abraham, Irving, Kavitha, and Mehlhorn is a matching problem in which there exist applicants and posts, and applicants have preference lists over posts. A matching M is said to be popular, if there exists no other matching N such that the number of applicants that prefer N to M is larger than the number of applicants that prefer M to N. The goal of this problem is to decide whether there exists a popular matching, and find a popular matching if one exists. In this paper, we first consider a matroid generalization of the popular matching problem with strict preference lists, and give a polynomial-time algorithm for this problem. In the second half of this paper, we consider the problem of transforming a given instance of a matroid generalization of the popular matching problem with strict preference lists by deleting a minimum number of applicants so that it has a popular matching. This problem is a matroid generalization of the popular condensation problem with strict preference lists introduced by Wu, Lin, Wang, and Chao. By using the results in the first half, we give a polynomial-time algorithm for this problem.

Co-path Set problem is of important applications in mapping unique DNA sequences onto chromosomes and whole genomes. Given a graph G, the parameterized version of Co-path Set problem is to find a subset F of edges with size at most k such that each connected component in $$G[E\backslash F]$$G[E\F] is a path. In this paper, we give a kernel of size 6k and a randomized algorithm of running time $$O^*(2.17^k)$$Oź(2.17k) for the Parameterized Co-path Set problem. The randomized methods developed in the paper are of great promising to be applied to other branch-based algorithms.

In this paper, we study the following Chromatic kernel (CK) problem: given an $$n$$n-partite graph (called a chromatic correlation graph) $$G=(V,E)$$G=(V,E) with $$V=V_{1}\bigcup \cdots \bigcup V_{n}$$V=V1???Vn and each partite set $$V_{i}$$Vi containing a constant number $$\lambda $$? of vertices, compute a subgraph $$G[V_{CK}]$$G[VCK] of $$G$$G with exactly one vertex from each partite set and the maximum number of edges or the maximum total edge weight, if $$G$$G is edge-weighted (among all such subgraphs). CK is a new problem motivated by several applications and no existing algorithm directly solves it. In this paper, we first show that CK is NP-hard even if $$\lambda =2$$?=2, and cannot be approximated within a factor of $$16/17$$16/17 unless P = NP. Then, we present a random-sampling-based PTAS for dense CK. As its application, we show that CK can be used to determine the pattern of chromosome associations in the nucleus for a population of cells. We test our approach by using random and real biological data; experimental results suggest that our approach yields near optimal solutions, and significantly outperforms existing approaches.

In this paper, we use the connection between dynamic monopolies and feedback vertex sets to establish explicit formulas and new bounds for decycling number $$\nabla (G)$$?(G) when $$G$$G is one of the following classes of graphs: cycle permutation graphs, generalized Petersen graphs, and torus cordalis. In the first part of this paper, we show that if $$G$$G is a cycle permutation graph or a generalized Petersen graph on $$2n$$2n vertices, then $$\nabla (G)=\lceil (n+1)/2\rceil $$?(G)=?(n+1)/2?. These results extend a recent result by Zaker (Discret Math 312:1136---1143, 2012) and partially answer a question of Bau and Beineke (Australas J Comb 25:285---298, 2002). Note that our definition of a generalized Petersen graph is more general than the one used in Zaker (Discret Math 312:1136---1143, 2012). The second and major part of this paper is devoted to proving new upper bounds and exact values on the size of the minimum feedback vertex set and minimum dynamic monopoly for torus cordalis. Our results improve the previous results by Flocchini in 2004.

An edge-colored graph G is a graph with an edge coloring. We say G is properly colored if any two adjacent edges of G have distinct colors, and G is rainbow if any two edges of G have distinct colors. For a vertex $$v \in V(G)$$ , the color degree $$d_G^{col}(v)$$ of v is the number of distinct colors appearing on edges incident with v. The minimum color degree $$\delta ^{col}(G)$$ of G is the minimum $$d_G^{col}(v)$$ over all vertices $$v \in V(G)$$ . In this paper, we study the relation between the order of maximum properly colored tree in G and the minimum color degree $$\delta ^{col}(G)$$ of G. We obtain that for an edge-colored connected graph G, the order of maximum properly colored tree is at least $$\min \{|G|, 2\delta ^{col}(G)\}$$ , which generalizes the result of Cheng et al. [Properly colored spanning trees in edge-colored graphs, Discrete Math., 343 (1), 2020]. Moreover, the lower bound $$2\delta ^{col}(G)$$ in our result is sharp and we characterize all extremal graphs G with the maximum properly colored tree of order $$2\delta ^{col}(G) \ne |G|$$ .

For an edge-colored graph G, we call an edge-cut M of G monochromatic if the edges of M are colored with a same color. The graph G is called monochromatically disconnected if any two distinct vertices of G are separated by a monochromatic edge-cut. The monochromatic disconnection number, denoted by md(G), of a connected graph G is the maximum number of colors that are allowed to make G monochromatically disconnected. In this paper, we solve the Erdős-Gallai-type problems for the monochromatic disconnection, and give the monochromatic disconnection numbers for four graph products, i.e., Cartesian, strong, lexicographic, and tensor products.

In this paper, motivated by many practical applications, we address the 1-line minimum rectilinear Steiner tree (1L-MRStT) problem, which is a variation of the Euclidean minimum rectilinear Steiner tree problem. More specifically, given n points in the Euclidean plane $${\mathbb {R}}^2$$ , it is asked to find the location of a line l and a Steiner tree T(l), consisting only of vertical and horizontal line segments plus several successive segments located on this line l, to interconnect these n points and at least one point located on the line l, the objective is to minimize total weight of this Steiner tree T(l), i.e., $$\min \{\sum _{uv\in T(l)} w(u,v)$$ | T(l) is a Steiner tree mentioned-above $$\}$$ , where we define a weight $$w(u,v)=0$$ if the two endpoints u and v of that edge $$uv \in T(l)$$ is located on the line l and otherwise we define a weight w(u, v) as the rectilinear distance between the two endpoints u and v of that edge $$uv \in T(l)$$ . Given a line l as an input in $${\mathbb {R}}^2$$ , we denote this problem as the 1-line-fixed minimum rectilinear Steiner tree (1LF-MRStT) problem; Furthermore, when the Steiner points of T(l) are all located on the fixed line l, we recall this problem as the 1-line-fixed-constrained minimum rectilinear Steiner tree (1LFC-MRStT) problem. We provide three following main contributions. (1) We design an algorithm $${{\mathcal {A}}}_{C}$$ to optimally solve the 1LFC-MRStT problem, where the algorithm $${{\mathcal {A}}}_{C}$$ runs in time $$O(n\log n)$$ ; (2) We prove that this algorithm $${{\mathcal {A}}}_{C}$$ is a 1.5-approximation algorithm to solve the 1LF-MRStT problem; (3) Combining the algorithm $${{\mathcal {A}}}_{C}$$ for many times and a key lemma proved by some techniques of computational geometry, we present a 1.5-approximation algorithm to solve the 1L-MRStT problem, where this algorithm runs in time $$O(n^3\log n)$$ , and we finally provide another approximation algorithm to solve a special version of the 1L-MRStT problem, where that new algorithm runs in lower time $$O(n^2\log n)$$ .

G has a list k-L(2, 1)-labeling if for any k-list assignment L, there exists a coloring $$c:V(G)\rightarrow \bigcup \limits _{v\in V} L(v)$$ of G such that $$c(v)\in L(v)$$ for $$\forall v\in V(G)$$ and for $$\forall u,v\in V(G)$$ , $$|c(u)-c(v)|\ge 2$$ if $$d(u,v)=1$$ , $$|c(u)-c(v)|\ge 1$$ if $$d(u,v)=2$$ . $$\lambda _{2,1}^{l}(G)=\min \{k|G$$ has a list k-L(2, 1)-labeling $$\}$$ is called the list L(2, 1)-labeling number of G. In this paper, we prove that for planar graph with maximum degree $$\Delta \ge 5$$ , girth $$g\ge 13$$ and without adjacent 13-cycles, $$\lambda _{2,1}^{l}(G)\le \Delta +3$$ holds. Moreover, the upper bound $$\Delta +3$$ is tight.

The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line $$P_n$$ with $$n=|V(G)|$$ vertices, in such a way that the maximum number of overlapping edges (i.e., the congestion) is minimized. A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has cutwidth less than k and G is homeomorphically minimal. In this paper, we mainly investigated a class of decomposable k-cutwidth critical graphs for $$k\ge 2$$ , which can be decomposed into three $$(k-1)$$ -cutwidth critical subgraphs.

A domination coloring of a graph G is a proper vertex coloring with an additional condition that each vertex dominates a color class and each color class is dominated by a vertex. The minimum number of colors used in a domination coloring of G is denoted as $$\chi _{dd}(G)$$ and it is called domination chromatic number of G. In this paper, we give a polynomial-time characterization of graphs with domination chromatic number at most 3 and consider the approximability of a node deletion problem called minimum q-domination partization. Given a graph G, in the Minimum q-Domination Partization problem (in short Min-q-Domination-Partization), the objective is to find a vertex set S of minimum size such that $$\chi _{dd}(G[V{\setminus } S]) \le q$$ . For $$q=2$$ , we prove that it is $${\mathsf {APX}}$$ -complete and is best approximable within a factor of 2. For $$q=3$$ , it is approximable within a factor of $$O(\sqrt{\log n})$$ and it is equivalent to minimum odd cycle transversal problem.

Due to their ubiquity and extensive applications, graph routing problems have been widely studied in the fields of operations research, computer science and engineering. An important example of a routing problem is the traveling salesman problem. In this paper, we consider two variants of the general cluster routing problem. In these variants, we are given a complete undirected graph $$G=(V,E)$$ with a metric cost function c and a partition $$V=C_{1}\cup C_{2}\cdots \cup C_{k}$$ of the vertex set. For a given subset $$V^{'}$$ of V and subset $$E^{'}$$ of E, the task is to find a walk T with minimum cost such that it visits each vertex in $$V^{\prime }$$ exactly once and covers each edge in $$E^{\prime }$$ at least once. Besides, for every $$i\in [k]$$ , all the vertices in $$T\cap C_i$$ are required to be visited consecutively in T. We design two combinatorial approximation algorithms with ratios 21/11 and 2.75 for the two variants, respectively; both ratios match the approximation ratios for the corresponding variants of the cluster traveling salesman problem, a special case of general cluster routing problem.

A fractional matching of a graph G is a function f giving each edge a number in [0, 1] so that $$\sum _{e\in \Gamma _G (v)} f(e)\le 1 $$ for each $$v \in V(G)$$ , where $$\Gamma _G (v)$$ is the set of edges incident to v in G. The fractional matching number of G, denoted by $$\mu _f(G)$$ , is the maximum of $$\sum _{e\in E(G)} f(e)$$ over all fractional matchings f. A fractional matching f of G is called a maximum fractional matching if $$\sum _{e\in E(G)} f(e)=\mu _f(G)$$ . In this paper, as a supplement of known results in Liu et al. (J Comb Optim 40:59–68, 2020), we further study the maximum fractional matching, and give some sufficient and necessary conditions to characterize the maximum fractional matching. Furthermore, as applications, the sharp lower bounds of the fractional matching number for Cartesian product, strong product, lexicographic product and direct product are obtained.

Let $$G=(V,E)$$ be a graph. A complete subgraph of G is a subgraph of pairwise adjacent vertices of V of size at least 2. Let $$\Phi _C(G)$$ be the set of all complete subgraphs of G and $$\Phi \subseteq {\Phi }_C(G)$$ . In this paper, we consider the Complete-Subgraph-Transversal-Set on $$\Phi $$ problem and the L-Max Complete-Subgraph-Transversal-Set on $$\Phi $$ problem. We give polynomial time algorithms to these two problems on graphs of bounded treewidth. At last, we show the connections between these two problems with some other NP-complete problems, for example Clique-Transversal-Set problem on graphs and Vertex-Cover problem on hypergraphs.

A graph G on n vertices is called non-universal if its maximum degree is at most $$n-2$$ . In this paper, we give a structural characterization for non-universal maximal planar graphs with diameter two. In precise, we find 10 basic graphs, and then generate all 25 non-universal maximal planar graphs with diameter two by adding repeatedly and appropriately 3-vertices to some of these 10 basic graphs. As an application, we show that maximal planar graphs with diameter two are pancyclic except five special graphs.

In this paper, we study Roman {k}-dominating functions on a graph G with vertex set V for a positive integer k: a variant of {k}-dominating functions, generations of Roman $$\{2\}$$ -dominating functions and the characteristic functions of dominating sets, respectively, which unify classic domination parameters with certain Roman domination parameters on G. Let $$k\ge 1$$ be an integer, and a function $$f:V \rightarrow \{0,1,\dots ,k\}$$ defined on V called a Roman $$\{k\}$$ -dominating function if for every vertex $$v\in V$$ with $$f(v)=0$$ , $$\sum _{u\in N(v)}f(u)\ge k$$ , where N(v) is the open neighborhood of v in G. The minimum value $$\sum _{u\in V}f(u)$$ for a Roman $$\{k\}$$ -dominating function f on G is called the Roman $$\{k\}$$ -domination number of G, denoted by $$\gamma _{\{Rk\}}(G)$$ . We first present bounds on $$\gamma _{\{Rk\}}(G)$$ in terms of other domination parameters, including $$\gamma _{\{Rk\}}(G)\le k\gamma (G)$$ . Secondly, we show one of our main results: characterizing the trees achieving equality in the bound mentioned above, which generalizes M.A. Henning and W.F. klostermeyer’s results on the Roman {2}-domination number (Henning and Klostermeyer in Discrete Appl Math 217:557–564, 2017). Finally, we show that for every fixed $$k\in \mathbb {Z_{+}}$$ , associated decision problem for the Roman $$\{k\}$$ -domination is NP-complete, even for bipartite planar graphs, chordal bipartite graphs and undirected path graphs.

The spherical k-means problem (SKMP) is an important variant of the k-means clustering problem (KMP). In this paper, we consider the SKMP, which aims to divide the n points in a given data point set $${\mathcal {S}}$$ into k clusters so as to minimize the total sum of the cosine dissimilarity measure from each data point to their respective closest cluster center. Our main contribution is to design an expected constant approximation algorithm for the SKMP by integrating the seeding algorithm for the KMP and the local search technique. By utilizing the structure of the clusters, we further obtain an improved LocalSearch++ algorithm involving $$\varepsilon k$$ local search steps.

Let G(V, E) be a simple, connected and undirected graph. A dominating set $$S \subseteq V$$ is called a 2-secure dominating set (2-SDS) in G, if for each pair of distinct vertices $$v_1,v_2 \in V$$ there exists a pair of distinct vertices $$u_1,u_2 \in S$$ such that $$u_1 \in N[v_1]$$ , $$u_2 \in N[v_2]$$ and $$(S {\setminus } \{u_1,u_2\}) \cup \{v_1,v_2 \}$$ is a dominating set in G. The size of a minimum 2-SDS in G is said to be 2-secure domination number denoted by $$\gamma _{2s}(G)$$ . The 2-SDM problem is to check if an input graph G has a 2-SDS S, with $$ \vert S \vert \le k$$ , where $$ k \in \mathbb {Z}^+ $$ . It is proved that for bipartite graphs 2-SDM is NP-complete. In this paper, we prove that the 2-SDM problem is NP-complete for planar graphs and doubly chordal graphs, a subclass of chordal graphs. We reinforce the existing NP-complete result for bipartite graphs, by proving 2-SDM is NP-complete for some subclasses of bipartite graphs specifically, comb convex bipartite and star convex bipartite graphs. We prove that this problem is linear time solvable for bounded tree-width graphs. We also show that the 2-SDM is W[2]-hard even for split graphs. The M2SDS problem is to find a 2-SDS of minimum size in the given graph. We give a $$ \varDelta +1 $$ -approximation algorithm for M2SDS, where $$ \varDelta $$ is the maximum degree of the given graph and prove that M2SDS cannot be approximated within $$ (1 - \epsilon ) \ln (\vert V \vert ) $$ for any $$ \epsilon > 0 $$ unless $$ NP \subseteq DTIME(\vert V \vert ^{ O(\log \log \vert V \vert )}) $$ . Finally, we prove that the M2SDS is APX-complete for graphs with $$\varDelta =4.$$

Sets of straight line segments with special structures and properties appear in various applications of geometric modeling, such as scientific visualization, computer-aided design, and medical image processing. In this paper, we derive sharp upper and lower bounds on the number of intersection points and closed regions that can occur in sets of line segments with certain structure, in terms of the number of segments. In particular, we consider sets of segments whose underlying planar graphs are Halin graphs, cactus graphs, maximal planar graphs, and triangle-free planar graphs, as well as randomly produced segment sets.

The H-rank of a mixed graph $$G^{\alpha }$$ is defined to be the rank of its Hermitian adjacency matrix $$H(G^{\alpha })$$ . If $$ G^{\alpha } $$ is switching equivalent to a mixed graph $$(G^{\alpha })' $$ , and two vertices u, v of $$G^{\alpha }$$ have exactly the same neighborhood in $$(G^{\alpha })'$$ , then u and v are said to be twins. The twin reduction graph $$T_{G^{\alpha }}$$ of $$G^{\alpha }$$ is a mixed graph whose vertices are the equivalence classes, and $$[u][v]\in E(T_{G^{\alpha }})$$ if $$uv\in E((G^{\alpha })')$$ , where [u] denotes the equivalence class containing the vertex u. In this paper, we give the upper (resp., lower) bound of the number of vertices of the twin reduction graphs of connected mixed bipartite graphs, and characterize all twin reduction graphs of the connected mixed bipartite graphs with H-rank 4 (resp., 6 or 8). Then, we characterize all connected mixed graphs with H-rank 4 (resp., 6 or 8) among all mixed graphs containing induced mixed odd cycles whose lengths are no less than 5 (resp., 7 or 9).

This paper considers two graph covering problems, the Minimum Constellation Cover (CC) and the Minimum k-Split Constellation Cover (k-SCC). The input of these problems consists on a graph $$G=\left( V,E\right) $$ and a set $${\mathcal {C}}$$ of stars of G, and the output is a minimum cardinality set of stars C, such that any two different stars of C are edge-disjoint and the union of the stars of C covers all edges of G. For CC, the set C must be compound by edges of G or stars of $${\mathcal {C}}$$ while, for k-SCC, an integer k is given and the elements of C must be k-stars obtained by splitting stars of $${\mathcal {C}}$$ . This work proves that unless $$P=NP$$ , CC does not admit polynomial time $$\left| {\mathcal {C}}\right| ^{{\mathcal {O}}\left( 1\right) }$$ -approximation algorithms and k-SCC cannot be $$\left( \left( 1-\epsilon \right) \ln \left| E\right| \right) $$ -approximated in polynomial time, for any $$\epsilon >0$$ . Additionally, approximation ratios are given for the worst feasible solutions of the problems and, for k-SCC, polynomial time approximation algorithms are proposed, achieving a $$\left( \ln \left| E\right| -\ln \ln \left| E\right| +\varTheta \left( 1\right) \right) $$ approximation ratio. Also, polynomial time algorithms are presented for special classes of graphs that include bounded degree trees and cacti.

The exponential of the second Zagreb index of a graph G with n vertices is defined as $$\begin{aligned} e^{{\mathcal {M}}_{2}}\left( G\right) =\sum _{1\le i\le j\le n-1}m_{i,j}\left( G\right) e^{ij}, \end{aligned}$$ where $$m_{i,j}$$ is the number of edges joining vertices of degree i and j. It is well known that among all trees with n vertices, the path has minimum value of $$e^{M_{2}}$$ . In this paper we show that the balanced double star tree has maximum value of $$e^{{\mathcal {M}}_{2}}$$ .

Let $$G=(V,E)$$ be a graph. A function $$f : V \rightarrow \{0, 1, 2\}$$ is an outer independent Roman dominating function (OIRDF) on a graph G if for every vertex $$v \in V$$ with $$f (v) = 0$$ there is a vertex u adjacent to v with $$f (u) = 2$$ and $$\{x\in V:f(x)=0\}$$ is an independent set. The weight of f is the value $$ f(V)=\sum _{v\in V}f(v)$$ . An outer independent total Roman dominating function (OITRDF) f on G is an OIRDF on G such that for every $$v\in V$$ with $$f(v)>0$$ there is a vertex u adjacent to v with $$f (u)>0$$ . The minimum weight of an OIRDF on G is called the outer independent Roman domination number of G, denoted by $$\gamma _{oiR}(G)$$ . Similarly, the outer independent total Roman domination number of G is defined, denoted by $$\gamma _{oitR}(G)$$ . In this paper, we first show that computing $$\gamma _{oiR}(G)$$ (respectively, $$\gamma _{oitR}(G)$$ ) is a NP-hard problem, even when G is a chordal graph. Then, for a given proper interval graph $$G=(V,E)$$ we propose an algorithm to compute $$\gamma _{oiR}(G)$$ (respectively, $$\gamma _{oitR}(G)$$ ) in $${\mathcal {O}}(|V| )$$ time.

For a graph $$G=(V,E)$$ , a vertex set $$C\subseteq V$$ is an m-fold outer-connected dominating set (m-fold OCDS) of G if every vertex in $$V\backslash C$$ has at least m neighbors in C and the subgraph of G induced by $$V\backslash C$$ is connected. In this paper, we present a greedy algorithm to compute an m-fold OCDS in general graphs, which returns a solution of size at most $$\alpha +1+\ln (\Delta +m+1)$$ times that of a minimum m-fold OCDS, where $$\Delta $$ is the maximum degree of the graph and $$\alpha $$ is a positive number at most $$\Delta $$ +m+1.

In Classical group testing, one is given a population of n items N which contains some defective d items inside. A group test (pool) is a test on a subset of N. Under the circumstance of no errors, a test is negative if the testing pool contains no defective items and the test is positive if the testing pool contains at least one defective item but we don’t know which one. The goal is to find all defectives by using as less tests as possible, mainly to minimize the number of tests (in the worst case situation). Let M(d, n) denote the minimum number of tests in the worst case situation where $$|N|=n$$ and d is the number of defectives. In this paper, we focus on estimating M(d, n) and obtain a better result than known ones in various cases of d and n.

An Italian dominating function (IDF) on a graph G is a function $$f:V(G)\rightarrow \{0,1,2\}$$ f : V ( G ) → { 0 , 1 , 2 } such that for every vertex v with $$f(v)=0$$ f ( v ) = 0 , the total weight of f assigned to the neighbours of v is at least two, i.e., $$\sum _{u\in N_G(v)}f(u)\ge 2$$ ∑ u ∈ N G ( v ) f ( u ) ≥ 2 . For any function $$f:V(G)\rightarrow \{0,1,2\}$$ f : V ( G ) → { 0 , 1 , 2 } and any pair of adjacent vertices with $$f(v) = 0$$ f ( v ) = 0 and u with $$f(u) > 0$$ f ( u ) > 0 , the function $$f_{u\rightarrow v}$$ f u → v is defined by $$f_{u\rightarrow v}(v)=1$$ f u → v ( v ) = 1 , $$f_{u\rightarrow v}(u)=f(u)-1$$ f u → v ( u ) = f ( u ) - 1 and $$f_{u\rightarrow v}(x)=f(x)$$ f u → v ( x ) = f ( x ) whenever $$x\in V(G){\setminus }\{u,v\}$$ x ∈ V ( G ) \ { u , v } . A secure Italian dominating function on a graph G is defined as an IDF f which satisfies that for every vertex v with $$f(v)=0$$ f ( v ) = 0 , there exists a neighbour u with $$f(u)>0$$ f ( u ) > 0 such that $$f_{u\rightarrow v}$$ f u → v is an IDF. The weight of f is $$\omega (f)=\sum _{v\in V(G) }f(v)$$ ω ( f ) = ∑ v ∈ V ( G ) f ( v ) . The minimum weight among all secure Italian dominating functions on G is the secure Italian domination number of G. This paper is devoted to initiating the study of the secure Italian domination number of a graph. In particular, we prove that the problem of finding this parameter is NP-hard and we obtain general bounds on it. Moreover, for certain classes of graphs, we obtain closed formulas for this novel parameter.

Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem (MWTP for short) asks for a collection of n vertex-disjoint triangles in G such that the total weight of edges in these n triangles is maximized. Although MWTP has been extensively studied in the literature, it is surprising that prior to this work, no nontrivial approximation algorithm had been designed and analyzed for its metric case (denoted by MMWTP), where the edge weights in the input graph satisfy the triangle inequality. In this paper, we design the first nontrivial polynomial-time approximation algorithm for MMWTP. Our algorithm is randomized and achieves an expected approximation ratio of \(0.66745 - \epsilon \) for any constant \(\epsilon > 0\).

Given a graph $$G=(V, E)$$ , a connected cut $$\delta (U)$$ is the set of edges of E linking all vertices of U to all vertices of $$V\backslash U$$ such that the induced subgraphs G[U] and $$G[V\backslash U]$$ are connected. Given a positive weight function w defined on E, the connected maximum cut problem (CMAX CUT) is to find a connected cut $$\varOmega $$ such that $$w(\varOmega )$$ is maximum among all connected cuts. CMAX CUT is NP-hard even for planar graphs, and thus for graph without the excluded minor $$K_5$$ . In this paper, we prove that CMAX CUT is polynomial for the class of graphs without the excluded minor $$K_5\backslash e$$ , denoted by $${\mathcal {G}}(K_5\backslash e)$$ . We deduce two quadratic time algorithms: one for the minimum cut problem in $${\mathcal {G}}(K_5\backslash e)$$ without computing the maximum flow, and another one for Hamilton cycle problem in the class of graphs without the two excluded minors the prism $$P_6$$ and $$K_{3, 3}$$ . This latter problem is NP-complete for maximal planar graphs.

This paper studies the online machine minimization problem, where the jobs have real release times, uniform processing times and a common deadline. We investigate how the lookahead ability improves the performance of online algorithms. Two lookahead models are studied, that is, the additive lookahead and the multiplicative lookahead. At any time t, the online algorithm knows all the jobs to be released before time $$t+L$$ (or $$\beta \cdot t$$ ) in the additive (or multiplicative) lookahead model. We propose a $$\frac{e}{\alpha (e-1)+1}$$ -competitive online algorithm with the additive lookahead, where $$\alpha = \frac{L}{T} \le 1$$ and T is the common deadline of the jobs. For the multiplicative lookahead, we provide an online algorithm with a competitive ratio of $$\frac{\beta e}{(\beta -1) e +1}$$ , where $$\beta \ge 1$$ . Lower bounds are also provided for both of the two models, which show that our algorithms are optimal for two extreme cases, that is, $$\alpha = 0$$ (or $$\beta = 1$$ ) and $$\alpha = 1$$ (or $$\beta \rightarrow \infty $$ ), and remain a small gap for the cases in between. Particularly, for $$\alpha = 0$$ (or $$\beta = 1$$ ), the competitive ratio is e, which corresponds to the problem without lookahead. For $$\alpha = 1$$ (or $$\beta \rightarrow \infty $$ ), the competitive ratio is 1, which corresponds to the offline version (with full information).

In this paper, we consider the $$\tau $$ -relaxed soft capacitated facility location problem ( $$\tau $$ -relaxed SCFLP), which extends several well-known facility location problems like the squared metric soft capacitated facility location problem (SMSCFLP), soft capacitated facility location problem (SCFLP), squared metric facility location problem and uncapacitated facility location problem. In the $$\tau $$ -relaxed SCFLP, we are given a facility set $$\mathcal {F}$$ , a client set and a parameter $$\tau \ge 1$$ . Every facility $$i \in \mathcal {F}$$ has a capacity $$u_i$$ and an opening cost $$f_i$$ , and can be opened multiple times. If facility i is opened l times, this facility can be connected by at most $$l u_i$$ clients and incurs an opening cost of $$l f_i$$ . Every facility-client pair has a connection cost. Under the assumption that the connection costs are non-negative, symmetric and satisfy the $$\tau $$ -relaxed triangle inequality, we wish to open some facilities (once or multiple times) and connect every client to an opened facility without violating the capacity constraint so as to minimize the total opening costs as well as connection costs. As our main contribution, we propose a primal-dual based $$(3 \tau + 1)$$ -approximation algorithm for the $$\tau $$ -relaxed SCFLP. Furthermore, our algorithm not only extends the applicability of the primal-dual technique but also improves the previous approximation guarantee for the SMSCFLP from $$11.18+ \varepsilon $$ to 10.

In a social network, the propagation of information has sparked intense research. Influence Maximization (IM) is a well-studied problem that asks for k nodes to influence the largest users in the social network. However IM is submodular at the most time. In recent years, many non-submodular problems have been proposed and researchers give a lot of algorithms to solve them. In this paper, we propose Activity Probability Maximization Problem without submodular property. For a given social network G, a candidate edge set $${\overline{E}}$$ and a constant k, the Activity Probability Maximization Problem asks for k edges in the candidate edge set that make the all nodes of G with highest probability of being activated under a pre-determined seed set S. Using the marginal increment, we give a general way to construct submodular lower bound and submodular upper bound functions of the non-submodular objective function at the same time. Interestingly, the optimal solution of upper bound is the same as that of lower bound. Therefore, we develop the Sandwich framework called Semi-Sandwich framework. Based on the same optimal solution of lower and upper bounds, we propose a Difference Minimizing Greedy (DMG) algorithm to get an approximation solution of the original problem. Through massive experiments, we show that the method and algorithm are effective.