On the vertex cover $$P_3$$ problem parameterized by treewidth

Consider a graph G. A subset of vertices, F, is called a vertex cover \(P_t\) (\(VCP_t\)) set if every path of order t contains at least one vertex in F. Finding a minimum \(VCP_t\) set in a graph is is NP-hard for any integer \(t\ge 2\) and is called the \(MVCP_3\) problem. In this paper, we study the parameterized algorithms for the \(MVCP_3\) problem when the underlying graph G is parameterized by the treewidth. Given an n-vertex graph together with its tree decomposition of width at most p, we present an algorithm running in time \(4^{p}\cdot n^{O(1)}\) for the \(MVCP_3\) problem. Moreover, we show that for the \(MVCP_3\) problem on planar graphs, there is a subexponential parameterized algorithm running in time \(2^{O(\sqrt{k})}\cdot n^{O(1)}\) where k is the size of the optimal solution.     

Online covering salesman problem

Given a graph \(G=(V,E,D,W)\), the generalized covering salesman problem (CSP) is to find a shortest tour in G such that each vertex \(i\in D\) is either on the tour or within a predetermined distance L to an arbitrary vertex \(j\in W\) on the tour, where \(D\subset V\),\(W\subset V\). In this paper, we propose the online CSP, where the salesman will encounter at most k blocked edges during the traversal. The edge blockages are real-time, meaning that the salesman knows about a blocked edge when it occurs. We present a lower bound \(\frac{1}{1 + (k + 2)L}k+1\) and a CoverTreeTraversal algorithm for online CSP which is proved to be \(k+\alpha \)-competitive, where \(\alpha =0.5+\frac{(4k+2)L}{OPT}+2\gamma \rho \), \(\gamma \) is the approximation ratio for Steiner tree problem and \(\rho \) is the maximal number of locations that a customer can be served. When \(\frac{L}{\texttt {OPT}}\rightarrow 0\), our algorithm is near optimal. The problem is also extended to the version with service cost, and similar results are derived.     

On minimally 2-connected graphs with generalized connectivity $$\kappa _{3}=2$$

For \(S\subseteq G\), let \(\kappa (S)\) denote the maximum number r of edge-disjoint trees \(T_1, T_2, \ldots , T_r\) in G such that \(V(T_i)\cap V(T_j)=S\) for any \(i,j\in \{1,2,\ldots ,r\}\) and \(i\ne j\). For every \(2\le k\le n\), the k-connectivity of G, denoted by \(\kappa _k(G)\), is defined as \(\kappa _k(G)=\hbox {min}\{\kappa (S)| S\subseteq V(G)\ and\ |S|=k\}\). Clearly, \(\kappa _2(G)\) corresponds to the traditional connectivity of G. In this paper, we focus on the structure of minimally 2-connected graphs with \(\kappa _{3}=2\). Denote by \(\mathcal {H}\) the set of minimally 2-connected graphs with \(\kappa _{3}=2\). Let \(\mathcal {B}\subseteq \mathcal {H}\) and every graph in \(\mathcal {B}\) is either \(K_{2,3}\) or the graph obtained by subdividing each edge of a triangle-free 3-connected graph. We obtain that \(H\in \mathcal {H}\) if and only if \(H\in \mathcal {B}\) or H can be constructed from one or some graphs \(H_{1},\ldots ,H_{k}\) in \(\mathcal {B}\) (\(k\ge 1\)) by applying some operations recursively.     

On the complete width and edge clique cover problems

A complete graph is the graph in which every two vertices are adjacent. For a graph \(G=(V,E)\), the complete width of G is the minimum k such that there exist k independent sets \(\mathtt {N}_i\subseteq V\), \(1\le i\le k\), such that the graph \(G'\) obtained from G by adding some new edges between certain vertices inside the sets \(\mathtt {N}_i\), \(1\le i\le k\), is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most k or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on \(3K_2\)-free bipartite graphs and polynomially solvable on \(2K_2\)-free bipartite graphs and on \((2K_2,C_4)\)-free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on \(\overline{3K_2}\)-free co-bipartite graphs and polynomially solvable on \(C_4\)-free co-bipartite graphs and on \((2K_2, C_4)\)-free graphs. We also give a characterization for k-probe complete graphs which implies that the complete width problem admits a kernel of at most \(2^k\) vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most \(2^k\) vertices. Finally we determine all graphs of small complete width \(k\le 3\).     

Maximum coverage problem with group budget constraints

We study the maximum coverage problem with group budget constraints (MCG). The input consists of a ground set X, a collection \(\psi \) of subsets of X each of which is associated with a combinatorial structure such that for every set \(S_j\in \psi \), a cost \(c(S_j)\) can be calculated based on the combinatorial structure associated with \(S_j\), a partition \(G_1,G_2,\ldots ,G_l\) of \(\psi \), and budgets \(B_1,B_2,\ldots ,B_l\), and B. A solution to the problem consists of a subset H of \(\psi \) such that \(\sum _{S_j\in H} c(S_j) \le B\) and for each \(i \in {1,2,\ldots ,l}\), \(\sum _{S_j \in H\cap G_i}c(S_j)\le B_i\). The objective is to maximize \(|\bigcup _{S_j\in H}S_j|\). In our work we use a new and improved analysis of the greedy algorithm to prove that it is a \((\frac{\alpha }{3+2\alpha })\)-approximation algorithm, where \(\alpha \) is the approximation ratio of a given oracle which takes as an input a subset \(X^{new}\subseteq X\) and a group \(G_i\) and returns a set \(S_j\in G_i\) which approximates the optimal solution for \(\max _{D\in G_i}\frac{|D\cap X^{new}|}{c(D)}\). This analysis that is shown here to be tight for the greedy algorithm, improves by a factor larger than 2 the analysis of the best known approximation algorithm for MCG.     

The longest commonly positioned increasing subsequences problem

Based on the well-known longest increasing subsequence problem and longest common increasing subsequence (LCIS) problem, we propose the longest commonly positioned increasing subsequences (LCPIS) problem. Let \(A=\langle a_1,a_2,\ldots ,a_n\rangle \) and \(B{=}\left\langle b_1,b_2,\ldots ,b_n\right\rangle \) be two input sequences. Let \({ Asub}=\left\langle a_{i_1},a_{i_2},\ldots ,a_{i_l}\right\rangle \) be a subsequence of A and \({ Bsub}=\left\langle b_{j_1},b_{j_2},\ldots ,b_{j_l}\right\rangle \) be a subsequence of B such that \(a_{i_k}\le a_{i_{k+1}}, b_{j_k}\le b_{j_{k+1}}(1\le k<l)\), and \(a_{i_k}\) and \(b_{j_k}\) (\(1\le k\le l\)) are commonly positioned (have the same index \(i_k=j_k\)) in A and B respectively but these two elements do not need to be equal. The LCPIS problem aims at finding a pair of subsequences Asub and \({ Bsub}\) as long as possible. When all the elements of the two input sequences are positive integers, this paper presents an algorithm with \(O(n\log n \log \log M)\) time to compute the LCPIS, where \(M={ min}\{{ max}_{1\le i\le n}a_i,{ max}_{1\le j\le n}b_j\}\). And we also show a dual relationship between the LCPIS problem and the LCIS problem.     

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

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)\).     

An algorithm for finding a representation of a subtree distance

Generalizing the concept of tree metric, Hirai (Ann Combinatorics 10:111–128, 2006) introduced the concept of subtree distance. A nonnegative-valued mapping \(d:X\times X \rightarrow \mathbb {R}_+\) is called a subtree distance if there exist a weighted tree T and a family \(\{T_x\mid x \in X\}\) of subtrees of T indexed by the elements in X such that \(d(x,y)=d_T(T_x,T_y)\), where \(d_T(T_x,T_y)\ge 0\) is the distance between \(T_x\) and \(T_y\) in T. Hirai (2006) provided a characterization of subtree distances that corresponds to Buneman’s (J Comb Theory, Series B 17:48–50, 1974) four-point condition for tree metrics. Using this characterization, we can decide whether or not a given mapping is a subtree distance in O\((n^4)\) time. In this paper, we show an O\((n^3)\) time algorithm that finds a representation of a given subtree distance. This results in an O\((n^3)\) time algorithm for deciding whether a given mapping is a subtree distance.     

The $$(k,\ell )$$-proper index of graphs

A tree T in an edge-colored graph is called a proper tree if no two adjacent edges of T receive the same color. Let G be a connected graph of order n and k be an integer with \(2\le k \le n\). For \(S\subseteq V(G)\) and \(|S| \ge 2\), an S-tree is a tree containing the vertices of S in G. A set \(\{T_1,T_2,\ldots ,T_\ell \}\) of S-trees is called internally disjoint if \(E(T_i)\cap E(T_j)=\emptyset \) and \(V(T_i)\cap V(T_j)=S\) for \(1\le i\ne j\le \ell \). For a set S of k vertices of G, the maximum number of internally disjoint S-trees in G is denoted by \(\kappa (S)\). The k-connectivity \(\kappa _k(G)\) of G is defined by \(\kappa _k(G)=\min \{\kappa (S)\mid S\) is a k-subset of \(V(G)\}\). For a connected graph G of order n and for two integers k and \(\ell \) with \(2\le k\le n\) and \(1\le \ell \le \kappa _k(G)\), the \((k,\ell )\)-proper index \(px_{k,\ell }(G)\) of G is the minimum number of colors that are required in an edge-coloring of G such that for every k-subset S of V(G), there exist \(\ell \) internally disjoint proper S-trees connecting them. In this paper, we show that for every pair of positive integers k and \(\ell \) with \(k \ge 3\) and \(\ell \le \kappa _k(K_{n,n})\), there exists a positive integer \(N_1=N_1(k,\ell )\) such that \(px_{k,\ell }(K_n) = 2\) for every integer \(n \ge N_1\), and there exists also a positive integer \(N_2=N_2(k,\ell )\) such that \(px_{k,\ell }(K_{m,n}) = 2\) for every integer \(n \ge N_2\) and \(m=O(n^r) (r \ge 1)\). In addition, we show that for every \(p \ge c\root k \of {\frac{\log _a n}{n}}\) (\(c \ge 5\)), \(px_{k,\ell }(G_{n,p})\le 2\) holds almost surely, where \(G_{n,p}\) is the Erd?s–Rényi random graph model.     

Weak {2}-domination number of Cartesian products of cycles

For a graph \(G=(V, E)\), a weak \(\{2\}\)-dominating function \(f:V\rightarrow \{0,1,2\}\) has the property that \(\sum _{u\in N(v)}f(u)\ge 2\) for every vertex \(v\in V\) with \(f(v)= 0\), where N(v) is the set of neighbors of v in G. The weight of a weak \(\{2\}\)-dominating function f is the sum \(\sum _{v\in V}f(v)\) and the minimum weight of a weak \(\{2\}\)-dominating function is the weak \(\{2\}\)-domination number. In this paper, we introduce a discharging approach and provide a short proof for the lower bound of the weak \(\{2\}\)-domination number of \(C_n \Box C_5\), which was obtained by St?pień, et al. (Discrete Appl Math 170:113–116, 2014). Moreover, we obtain the weak \(\{2\}\)-domination numbers of \(C_n \Box C_3\) and \(C_n \Box C_4\).     

Total coloring of planar graphs without adjacent short cycles

In the study of computer science, optimization, computation of Hessians matrix, graph coloring is an important tool. In this paper, we consider a classical coloring, total coloring. Let \(G=(V,E)\) be a graph. Total coloring is a coloring of \(V\cup {E}\) such that no two adjacent or incident elements (vertex/edge) receive the same color. Let G be a planar graph with \(\varDelta \ge 8\). We proved that if for every vertex \(v\in V\), there exists two integers \(i_v,j_v\in \{3,4,5,6,7\}\) such that v is not incident with adjacent \(i_v\)-cycles and \(j_v\)-cycles, then the total chromatic number of graph G is \(\varDelta +1\).     

Total and forcing total edge-to-vertex monophonic number of a graph

For a connected graph \(G = \left( V,E\right) \), a set \(S\subseteq E(G)\) is called a total edge-to-vertex monophonic set of a connected graph G if the subgraph induced by S has no isolated edges. The total edge-to-vertex monophonic number \(m_{tev}(G)\) of G is the minimum cardinality of its total edge-to-vertex monophonic set of G. The total edge-to-vertex monophonic number of certain classes of graphs is determined and some of its general properties are studied. Connected graphs of size \(q \ge 3 \) with total edge-to-vertex monophonic number q is characterized. It is shown that for positive integers \(r_{m},d_{m}\) and \(l\ge 4\) with \(r_{m}< d_{m} \le 2 r_{m}\), there exists a connected graph G with \(\textit{rad}_ {m} G = r_{m}\), \(\textit{diam}_ {m} G = d_{m}\) and \(m_{tev}(G) = l\) and also shown that for every integers a and b with \(2 \le a \le b\), there exists a connected graph G such that \( m_{ev}\left( G\right) = b\) and \(m_{tev}(G) = a + b\). A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing total edge-to-vertex monophonic number of S, denoted by \(f_{tev}(S)\) is the cardinality of a minimum forcing subset of S. The forcing total edge-to-vertex monophonic number of G, denoted by \(f_{tev}(G) = \textit{min}\{f_{tev}(S)\}\), where the minimum is taken over all total edge-to-vertex monophonic set S in G. The forcing total edge-to-vertex monophonic number of certain classes of graphs are determined and some of its general properties are studied. It is shown that for every integers a and b with \(0 \le a \le b\) and \(b \ge 2\), there exists a connected graph G such that \(f_{tev}(G) = a\) and \( m _{tev}(G) = b\), where \( f _{tev}(G)\) is the forcing total edge-to-vertex monophonic number of G.     

Algorithms for connected <Emphasis Type="Italic">p</Emphasis>-centdian problem on block graphs

We consider the facility location problem of locating a set \(X_p\) of p facilities (resources) on a network (or a graph) such that the subnetwork (or subgraph) induced by the selected set \(X_p\) is connected. Two problems on a block graph G are proposed: one problem is to minimizes the sum of its weighted distances from all vertices of G to \(X_p\), another problem is to minimize the maximum distance from each vertex that is not in \(X_p\) to \(X_p\) and, at the same time, to minimize the sum of its distances from all vertices of G to \(X_p\). We prove that the first problem is linearly solvable on block graphs with unit edge length. For the second problem, it is shown that the set of Pareto-optimal solutions of the two criteria has cardinality not greater than n, and can be obtained in \(O(n^2)\) time, where n is the number of vertices of the block graph G.     

An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs

Given a vertex-weighted undirected connected graph \(G = (V, E, \ell , \rho )\), where each edge \(e \in E\) has a length \(\ell (e) > 0\) and each vertex \(v \in V\) has a weight \(\rho (v) > 0\), a subset \(T \subseteq V\) of vertices and a set S containing all the points on edges in a subset \(E' \subseteq E\) of edges, the generalized absolute 1-center problem (GA1CP), an extension of the classic vertex-weighted absolute 1-center problem (A1CP), asks to find a point from S such that the longest weighted shortest path distance in G from it to T is minimized. This paper presents a simple FPTAS for GA1CP by traversing the edges in \(E'\) using a positive real number as step size. The FPTAS takes \(O( |E| |V| + |V|^2 \log \log |V| + \frac{1}{\epsilon } |E'| |T| {\mathcal {R}})\) time, where \({\mathcal {R}}\) is an input parameter size of the problem instance, for any given \(\epsilon > 0\). For instances with a small input parameter size \({\mathcal {R}}\), applying the FPTAS with \(\epsilon = \Theta (1)\) to the classic vertex-weighted A1CP can produce a \((1 + \Theta (1))\)-approximation in at most O(|E| |V|) time when the distance matrix is known and \(O(|E| |V| + |V|^2 \log \log |V|)\) time when the distance matrix is unknown, which are smaller than Kariv and Hakimi’s \(O(|E| |V| \log |V|)\)-time algorithm and \(O(|E| |V| \log |V| + |V|^3)\)-time algorithm, respectively.     

Majorization and the spectral radius of starlike trees

A starlike tree is a tree with exactly one vertex of degree greater than two. The spectral radius of a graph G, that is denoted by \(\lambda (G)\), is the largest eigenvalue of G. Let k and \(n_1,\ldots ,n_k\) be some positive integers. Let \(T(n_1,\ldots ,n_k)\) be the tree T (T is a path or a starlike tree) such that T has a vertex v so that \(T{\setminus } v\) is the disjoint union of the paths \(P_{n_1-1},\ldots ,P_{n_k-1}\) where every neighbor of v in T has degree one or two. Let \(P=(p_1,\ldots ,p_k)\) and \(Q=(q_1,\ldots ,q_k)\), where \(p_1\ge \cdots \ge p_k\ge 1\) and \(q_1\ge \cdots \ge q_k\ge 1\) are integer. We say P majorizes Q and let \(P\succeq _M Q\), if for every j, \(1\le j\le k\), \(\sum _{i=1}^{j}p_i\ge \sum _{i=1}^{j}q_i\), with equality if \(j=k\). In this paper we show that if P majorizes Q, that is \((p_1,\ldots ,p_k)\succeq _M(q_1,\ldots ,q_k)\), then \(\lambda (T(q_1,\ldots ,q_k))\ge \lambda (T(p_1,\ldots ,p_k))\).     

Upper bounds of proper connection number of graphs

A total weighting of a graph G is a mapping \(\phi \) that assigns a weight to each vertex and each edge of G. The vertex-sum of \(v \in V(G)\) with respect to \(\phi \) is \(S_{\phi }(v)=\sum _{e\in E(v)}\phi (e)+\phi (v)\). A total weighting is proper if adjacent vertices have distinct vertex-sums. A graph \(G=(V,E)\) is called \((k,k')\)-choosable if the following is true: If each vertex x is assigned a set L(x) of k real numbers, and each edge e is assigned a set L(e) of \(k'\) real numbers, then there is a proper total weighting \(\phi \) with \(\phi (y)\in L(y)\) for any \(y \in V \cup E\). In this paper, we prove that for any graph \(G\ne K_1\), the Mycielski graph of G is (1,4)-choosable. Moreover, we give some sufficient conditions for the Mycielski graph of G to be (1,3)-choosable. In particular, our result implies that if G is a complete bipartite graph, a complete graph, a tree, a subcubic graph, a fan, a wheel, a Halin graph, or a grid, then the Mycielski graph of G is (1,3)-choosable.     

The solution of a generalized secretary problem via analytic expressions

Given integers \(1\le k<n\), the Gusein-Zade version of a generalized secretary problem is to choose one of the k best of n candidates for a secretary, which are interviewing in random order. The stopping rule in the selection is based only on the relative ranks of the successive arrivals. It is known that the best policy can be described by a non-decreasing sequence \((s_1, \ldots , s_k)\) of integers with \(l\le s_l<n\) for every \(1\le l\le k\), and conversely, any such a sequence determines the general structure of the best policy. We found a finite analytic expression for the probability of success when using the optimal policy with a sequence \((s_1, \ldots , s_k)\). We also study the problem of the construction of the optimal sequence, i.e. a sequence which maximizes the corresponding probability of success. We discovered finite analytic expressions which enable to calculate the elements \(s_l\) of an optimal sequence one by one, from \(l=k\) to \(l=1\). Until now, such expressions were derived separately, and only for the values \(k\le 3\).     

Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree

Gyárfás conjectured that for a given forest F, there exists an integer function f(F, x) such that \(\chi (G)\le f(F,\omega (G))\) for each F-free graph G, where \(\omega (G)\) is the clique number of G. The broom B(m, n) is the tree of order \(m+n\) obtained from identifying a vertex of degree 1 of the path \(P_m\) with the center of the star \(K_{1,n}\). In this note, we prove that every connected, triangle-free and B(m, n)-free graph is \((m+n-2)\)-colorable as an extension of a result of Randerath and Schiermeyer and a result of Gyárfás, Szemeredi and Tuza. In addition, it is also shown that every connected, triangle-free, \(C_4\)-free and T-free graph is \((p-2)\)-colorable, where T is a tree of order \(p\ge 4\) and \(T\not \cong K_{1,3}\).     

Convex median and anti-median at prescribed distance

The status of a vertex v in a connected graph G is the sum of the distances between v and all the other vertices of G. The subgraph induced by the vertices of minimum (maximum) status in G is called median (anti-median) of G. Let \(H=(G_1,G_2,r)\) denote a graph with \(G_1\) as the median and \(G_2\) as the anti-median of H, \(d(G_1,G_2)=r\) and both \(G_1\) and \(G_2\) are convex subgraphs of H. It is known that \((G_1,G_2,r)\) exists for every \(G_1\), \(G_2\) with \(r \ge \left\lfloor diam(G_1)/2\right\rfloor +\left\lfloor diam(G_2)/2\right\rfloor +2\). In this paper we show the existence of \((G_1,G_2,r)\) for every \(G_1\), \(G_2\) and \(r \ge 1\). We also obtain a sharp upper bound for the maximum status difference in a graph G.     

Bounds on the domination number of a digraph

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S is adjacent from at least one vertex in S. The domination number of D, denoted by \(\gamma (D)\), is the minimum cardinality of a dominating set of D. The Slater number \(s\ell (D)\) is the smallest integer t such that t added to the sum of the first t terms of the non-increasing out-degree sequence of D is at least as large as the order of D. For any digraph D of order n with maximum out-degree \(\Delta ^+\), it is known that \(\gamma (D)\ge \lceil n/(\Delta ^++1)\rceil \). We show that \(\gamma (D)\ge s\ell (D)\ge \lceil n/(\Delta ^++1)\rceil \) and the difference between \(s\ell (D)\) and \(\lceil n/(\Delta ^++1)\rceil \) can be arbitrarily large. In particular, for an oriented tree T of order n with \(n_0\) vertices of out-degree 0, we show that \((n-n_0+1)/2\le s\ell (T)\le \gamma (T)\le 2s\ell (T)-1\) and moreover, each value between the lower bound \(s\ell (T)\) and the upper bound \(2s\ell (T)-1\) is attainable by \(\gamma (T)\) for some oriented trees. Further, we characterize the oriented trees T for which \(s\ell (T)=(n-n_0+1)/2\) hold and show that the difference between \(s\ell (T)\) and \((n-n_0+1)/2\) can be arbitrarily large. Some other elementary properties involving the Slater number are also presented.