Covering directed graphs by in-trees

Given a directed graph D=(V,A) with a set of d specified vertices S={s ₁,…,s _d }?V and a function f : S→? where ? denotes the set of positive integers, we consider the problem which asks whether there exist ∑ _i=1 ^d f(s _i ) in-trees denoted by \(T_{i,1},T_{i,2},\ldots,T_{i,f(s_{i})}\) for every i=1,…,d such that \(T_{i,1},\ldots,T_{i,f(s_{i})}\) are rooted at s _i , each T _i,j spans vertices from which s _i is reachable and the union of all arc sets of T _i,j for i=1,…,d and j=1,…,f(s _i ) covers A. In this paper, we prove that such set of in-trees covering A can be found by using an algorithm for the weighted matroid intersection problem in time bounded by a polynomial in ∑ _i=1 ^d f(s _i ) and the size of D. Furthermore, for the case where D is acyclic, we present another characterization of the existence of in-trees covering A, and then we prove that in-trees covering A can be computed more efficiently than the general case by finding maximum matchings in a series of bipartite graphs.     

Unavoidable regularities in long words with bounded number of symbol occurrences

Traditionally in combinatorics on words one studies unavoidable regularities that appear in sufficiently long strings over a fixed size alphabet. Inspired by permutation problems originating from information security, another viewpoint is taken in this paper. We focus on combinatorial properties of long words in which the number of occurrences of any symbol is restricted by a fixed given constant. More precisely, we show that for all positive integers m and q there exists the least positive integer N(m,q) which is smaller than $m^{2^{q-1}}$ and satisfies the following: If α is a word such that

1. |alph(α)|≥N(m,q) (i.e., the cardinality of the alphabet of α is at least N(m,q)); and
2. |α| _a ≤q for each a∈alph(α) (i.e., the number of occurrences of any symbol of alph(α) in α is at most q),

then there exist a set A?alph(α) of cardinality |A|=m, an integer p∈{1,2,…,q}, and permutations σ ₁,σ ₂,…,σ _p :{1,2,…,m}→{1,2,…,m} for which $$\pi_A(\alpha)\in a_{\sigma_1(1)}^+\cdots a_{\sigma_1(m)}^+a_{\sigma _2(1)}^+\cdots a_{\sigma_2(m)}^+\cdots a_{\sigma_p(1)}^+\cdots a_{\sigma_p(m)}^+ .$$ Here A={a ₁,a ₂,…,a _m } and π _A is the projection morphism from alph(α)^? into A ^?. The second part of the paper considers information security. We give an introduction to (generalized iterated) hash functions and their security properties; finally we demonstrate how our combinatorial results are connected to constructing multicollision attacks on these functions.     

The subdivision-constrained routing requests problem

We are given a digraph D=(V,A;w), a length (delay) function w:A→R ⁺, a positive integer d and a set $\mathcal{P}=\{(s_{i},t_{i};B_{i}) | i=1,2,\ldots,k\}$ of k requests, where s _i ∈V is called as the ith source node, t _i ∈V is called the ith sink node and B _i is called as the ith length constraint. For a given positive integer d, the subdivision-constrained routing requests problem (SCRR, for short) is to find a directed subgraph D′=(V′,A′) of D, satisfying the two constraints: (1) Each request (s _i ,t _i ;B _i ) has a path P _i from s _i to t _i in D′ with length $w(P_{i})=\sum_{e\in P_{i}} w(e)$ no more than B _i ; (2) Insert some nodes uniformly on each arc e∈A′ to ensure that each new arc has length no more than d. The objective is to minimize the total number of the nodes inserted on the arcs in A′. We obtain the following three main results: (1) The SCRR problem is at least as hard as the set cover problem even if each request has the same source s, i.e., s _i =s for each i=1,2,…,k; (2) For each request (s,t;B), we design a dynamic programming algorithm to find a path from s to t with length no more than B such that the number of the nodes inserted on such a path is minimized, and as a corollary, we present a k-approximation algorithm to solve the SCRR problem for any k requests; (3) We finally present an optimal algorithm for the case where $\mathcal{P}$ contains all possible requests (s _i ,t _i ) in V×V and B _i is equal to the length of the shortest path in D from s _i to t _i . To the best of our knowledge, this is the first time that the dynamic programming algorithm within polynomial time in (2) is designed for a weighted optimization problem while previous optimal algorithms run in pseudo-polynomial time.     

Multiple L(j,1)-labeling of the triangular lattice

Let n,j,k be nonnegative integers. An n-fold L(j,k)-labeling of a graph G is an assignment f of sets of nonnegative integers of order n to the vertices of G such that, for any two vertices u,v and any two integers a∈f(u), b∈f(v), |a?b|≥j if uv∈E(G), and |a?b|≥k if u and v are distance two apart. The span of f is the absolute difference between the maximum and minimum integers used by f. The n-fold L(j,k)-labeling number of G is the minimum span over all n-fold L(j,k)-labelings of G. Let n,j,k and m be nonnegative integers. An n-fold circular m-L(j,k)-labeling of a graph G is an assignment f of subsets of {0,1,…,m?1} of order n to the vertices of G such that, for any two vertices u,v and any two integers a∈f(u), b∈f(v), min{|a?b|,m?|a?b|}≥j if uv∈E(G), and min{|a?b|,m?|a?b|}≥k if u and v are distance two apart. The minimum m such that G has an n-fold circular m-L(j,k)-labeling is called the n-fold circular L(j,k)-labeling number of G. This paper provides upper and lower bounds for the n-fold L(j,1)-labeling number and the n-fold circular L(j,1)-labeling number of the triangular lattice and determines the n-fold L(2,1)-labeling number and n-fold circular L(2,1)-labeling number of the triangular lattice for n≥3.     

A branch-and-bound algorithm for the minimum cut linear arrangement problem

Given an edge-weighted graph G of order n, the minimum cut linear arrangement problem (MCLAP) asks to find a one-to-one map from the vertices of G to integers from 1 to n such that the largest of the cut values c ₁,…,c _n?1 is minimized, where c _i , i∈{1,…,n?1}, is the total weight of the edges connecting vertices mapped to integers 1 through i with vertices mapped to integers i+1 through n. In this paper, we present a branch-and-bound algorithm for solving this problem. A salient feature of the algorithm is that it employs a dominance test which allows reducing the redundancy in the enumeration process drastically. The test is based on the use of a tabu search procedure developed to solve the MCLAP. We report computational results for both the unweighted and weighted graphs. In particular, we focus on calculating the cutwidth of some well-known graphs from the literature.     

Roman domination on strongly chordal graphs

Given real numbers b≥a>0, an (a,b)-Roman dominating function of a graph G=(V,E) is a function f:V→{0,a,b} such that every vertex v with f(v)=0 has a neighbor u with f(u)=b. An independent/connected/total (a,b)-Roman dominating function is an (a,b)-Roman dominating function f such that {v∈V:f(v)≠0} induces a subgraph without edges/that is connected/without isolated vertices. For a weight function $w{:} V\to\Bbb{R}$ , the weight of f is w(f)=∑ _v∈V w(v)f(v). The weighted (a,b)-Roman domination number $\gamma^{(a,b)}_{R}(G,w)$ is the minimum weight of an (a,b)-Roman dominating function of G. Similarly, we can define the weighted independent (a,b)-Roman domination number $\gamma^{(a,b)}_{Ri}(G,w)$ . In this paper, we first prove that for any fixed (a,b) the (a,b)-Roman domination and the total/connected/independent (a,b)-Roman domination problems are NP-complete for bipartite graphs. We also show that for any fixed (a,b) the (a,b)-Roman domination and the total/connected/weighted independent (a,b)-Roman domination problems are NP-complete for chordal graphs. We then give linear-time algorithms for the weighted (a,b)-Roman domination problem with b≥a>0, and the weighted independent (a,b)-Roman domination problem with 2a≥b≥a>0 on strongly chordal graphs with a strong elimination ordering provided.     

Near optimal solutions for maximum quasi-bicliques

The maximum quasi-biclique problem has been proposed for finding interacting protein group pairs from large protein-protein interaction (PPI) networks. The problem is defined as follows: The Maximum Quasi-biclique Problem: Given a bipartite graph G=(X∪Y,E) and a number 0<δ≤0.5, find a subset X _opt of X and a subset Y _opt of Y such that any vertex x∈X _opt is incident to at least (1?δ)|Y _opt | vertices in Y _opt , any vertex y∈Y _opt is incident to at least (1?δ)|X _opt | vertices in X _opt and |X _opt |+|Y _opt | is maximized. The problem was proved to be NP-hard. We design a polynomial time approximation scheme to give a quasi-biclique X′?X and Y′?Y with |X′|+|Y′|≥(1?ε)(|X _opt |+|Y _opt |) such that any vertex x∈X′ is incident to at least (1?δ?ε)|Y′| vertices in Y′ and any vertex y∈Y′ is incident to at least (1?δ?ε)|X′| vertices in X′ for any ε>0, where X _opt and Y _opt form the optimal solution.     

Selective support vector machines

In this study we introduce a generalized support vector classification problem: Let X _i , i=1,…,n be mutually exclusive sets of pattern vectors such that all pattern vectors x _i,k , k=1,…,|X _i | have the same class label y _i . Select only one pattern vector $x_{i,k^{*}}In this study we introduce a generalized support vector classification problem: Let X _i , i=1,…,n be mutually exclusive sets of pattern vectors such that all pattern vectors x _i,k , k=1,…,|X _i | have the same class label y _i . Select only one pattern vector from each set X _i such that the margin between the set of selected positive and negative pattern vectors are maximized. This problem is formulated as a quadratic mixed 0-1 programming problem, which is a generalization of the standard support vector classifiers. The quadratic mixed 0-1 formulation is shown to be -hard. An alternative approach is proposed with the free slack concept. Primal and dual formulations are introduced for linear and nonlinear classification. These formulations provide flexibility to the separating hyperplane to identify the pattern vectors with large margin. Iterative elimination and direct selection methods are developed to select such pattern vectors using the alternative formulations. These methods are compared with a na?ve method on simulated data. The iterative elimination method is also applied to neural data from a visuomotor categorical discrimination task to classify highly cognitive brain activities.     

Note on the hardness of generalized connectivity

Let G be a nontrivial connected graph of order n and let k be an integer with 2??k??n. For a set S of k vertices of G, let ??(S) denote the maximum number ? of edge-disjoint trees T ₁,T ₂,??,T _? in G such that V(T _i )??V(T _j )=S for every pair i,j of distinct integers with 1??i,j???. Chartrand et al. generalized the concept of connectivity as follows: The k-connectivity, denoted by ?? _k (G), of G is defined by ?? _k (G)=min{??(S)}, where the minimum is taken over all k-subsets S of V(G). Thus ?? ₂(G)=??(G), where ??(G) is the connectivity of G, for which there are polynomial-time algorithms to solve it. This paper mainly focus on the complexity of determining the generalized connectivity of a graph. At first, we obtain that for two fixed positive integers k ₁ and k ₂, given a graph G and a k ₁-subset S of V(G), the problem of deciding whether G contains k ₂ internally disjoint trees connecting S can be solved by a polynomial-time algorithm. Then, we show that when k ₁ is a fixed integer of at least 4, but k ₂ is not a fixed integer, the problem turns out to be NP-complete. On the other hand, when k ₂ is a fixed integer of at least 2, but k ₁ is not a fixed integer, we show that the problem also becomes NP-complete.     

L(d,1)-labelings of the edge-path-replacement of a graph

For two positive integers j and k with j≥k, an L(j,k)-labeling of a graph G is an assignment of nonnegative integers to V(G) such that the difference between labels of adjacent vertices is at least j, and the difference between labels of vertices that are distance two apart is at least k. The span of an L(j,k)-labeling of a graph G is the difference between the maximum and minimum integers used by it. The L(j,k)-labelings-number of G is the minimum span over all L(j,k)-labelings of G. This paper focuses on L(d,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G. Note that G(P ₃) is the incidence graph of G. L(d,1)-labelings of the edge-path-replacement G(P _k ) of a graph, called (d,1)-total labeling of G, was introduced in 2002 by Havet and Yu (Workshop graphs and algorithms, 2003; Discrete Math 308:493–513, 2008). Havet and Yu (Discrete Math 308:498–513, 2008) obtained the bound $\Delta+ d-1\leq\lambda^{T}_{d}(G)\leq2\Delta+ d-1$ and conjectured $\lambda^{T}_{d}(G)\leq\Delta+2d-1$ . In (Lü in J Comb Optim, to appear; Zhejiang University, submitted), we worked on L(2,1)-labelings-number and L(1,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G, and obtained that λ(G(P _k ))≤Δ+2 for k≥5, and conjecture λ(G(P ₄))≤Δ+2 for any graph G with maximum degree Δ. In this paper, we will study L(d,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G for d≥3 and k≥4.     

Estimating hybrid frequency moments of data streams

We consider the problem of estimating hybrid frequency moments of two dimensional data streams. In this model, data is viewed to be organized in a matrix form (A _i,j )_1≤i,j,≤n . The entries A _i,j are updated coordinate-wise, in arbitrary order and possibly multiple times. The updates include both increments and decrements to the current value of A _i,j . The hybrid frequency moment F _p,q (A) is defined as \(\sum_{j=1}^{n}(\sum_{i=1}^{n}{A_{i,j}}^{p})^{q}\) and is a generalization of the frequency moment of one-dimensional data streams.We present the first \(\tilde{O}(1)\) space algorithm for the problem of estimating F _p,q for p∈[0,2] and q∈[0,1] to within an approximation factor of 1±ε. The \(\tilde{O}\) notation hides poly-logarithmic factors in the size of the stream m, the matrix size n and polynomial factors of ε ^?1. We also present the first \(\tilde{O}(n^{1-1/q})\) space algorithm for estimating F _p,q for p∈[0,2] and q∈(1,2].     

Circular L(j,k)-labeling number of direct product of path and cycle

Let j, k and m be positive numbers, a circular m-L(j,k)-labeling of a graph G is a function f:V(G)→[0,m) such that |f(u)?f(v)| _m ≥j if u and v are adjacent, and |f(u)?f(v)| _m ≥k if u and v are at distance two, where |a?b| _m =min{|a?b|,m?|a?b|}. The minimum m such that there exist a circular m-L(j,k)-labeling of G is called the circular L(j,k)-labeling number of G and is denoted by σ _j,k (G). In this paper, for any two positive numbers j and k with j≤k, we give some results about the circular L(j,k)-labeling number of direct product of path and cycle.     

A 6.55 factor primal-dual approximation algorithm for the connected facility location problem

In the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c _e on the edges, a set of facilities ??V, a set of demands (i.e., clients) $\mathcal{D}\subseteq VIn the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c _e on the edges, a set of facilities ℱ⊆V, a set of demands (i.e., clients) D í V\mathcal{D}\subseteq V , and a parameter M≥1. Each facility i has a nonnegative opening cost f _i and each client j has d _j units of demand. Our objective is to open some facilities, say F⊆ℱ, assign each demand j to some open facility i(j)∈F and connect all open facilities using a Steiner tree T such that the total cost, which is ?_{i ? F}f_i+?_{j ? D}d_jc_i(j)j+M?_{e ? T}c_e\sum_{i\in F}f_{i}+\sum_{j\in \mathcal{D}}d_{j}c_{i(j)j}+M\sum_{e\in T}c_{e} , is minimized. We present a primal-dual 6.55-approximation algorithm for the ConFL problem which improves the previous primal-dual 8.55-approximation algorithm given by Swamy and Kumar (Algorithmica 40:245–269, 2004).     

The paths embedding of the arrangement graphs with prescribed vertices in given position

Let n and k be positive integers with n?k≥2. The arrangement graph A _n,k is recognized as an attractive interconnection networks. Let x, y, and z be three different vertices of A _n,k . Let l be any integer with $d_{A_{n,k}}(\mathbf{x},\mathbf{y}) \le l \le \frac{n!}{(n-k)!}-1-d_{A_{n,k}}(\mathbf{y},\mathbf{z})$ . We shall prove the following existance properties of Hamiltonian path: (1)?for n?k≥3 or (n,k)=(3,1), there exists a Hamiltonian path R(x,y,z;l) from x to z such that d _R(x,y,z;l)(x,y)=l; (2) for n?k=2 and n≥5, there exists a Hamiltonian path R(x,y,z;l) except for the case that x, y, and z are adjacent to each other.     

Minimizing the maximum bump cost in linear extensions of a poset

A linear extension of a poset P=(X,?) is a permutation x ₁,x ₂,…,x _|X| of X such that i<j whenever x _i ?x _j . For a given poset P=(X,?) and a cost function c(x,y) defined on X×X, we want to find a linear extension of P such that maximum cost is as small as possible. For the general case, it is NP-complete. In this paper we consider the linear extension problem with the assumption that c(x,y)=0 whenever x and y are incomparable. First, we prove the discussed problem is polynomially solvable for a special poset. And then, we present a polynomial algorithm to obtain an approximate solution.     

Path packing and a related optimization problem

Let G be a supply graph, with the node set N and edge set E, and (T,S) be a demand graph, with T?N, S∩E=?. Observe paths whose end-vertices form pairs in S (called S-paths). The following path packing problem for graphs is fundamental: what is the maximal number of S-paths in G? In this paper this problem is studied under two assumptions: (a) the node degrees in N?T are even, and (b) any three distinct pairwise intersecting maximal stable sets A,B,C of (T,S) satisfy A∩B=B∩C=A∩C (this condition was defined by A. Karzanov in Linear Algebra Appl. 114–115:293–328, 1989). For any demand graph violating (b) the problem is known to be NP-hard even under (a), and only a few cases satisfying (a) and (b) have been solved. In each of the solved cases, a solution and an optimal dual object were defined by a certain auxiliary “weak” multiflow optimization problem whose solutions supply constructive elements for S-paths and concatenate them into an S-path packing by a kind of matching. In this paper the above approach is extended to all demand graphs satisfying (a) and (b), by proving existence of a common solution of the S-path packing and its weak counterpart. The weak problem is very interesting for its own sake, and has connections with such topics as Mader’s edge-disjoint path packing theorem and b-factors in graphs.     

On the union of intermediate nodes of shortest paths

Consider a connected graph G=(V,E). For a pair of nodes u and v, denote by M _uv the set of intermediate nodes of a shortest path between u and v. We are intertested in minimization of the union ? _u,v∈V M _uv . We will show that this problem is NP-hard and cannot have polynomial-time ρlnδ-approximation for 0<ρ<1 unless NP?DTIME(n ^O(loglogn)) where δ is the maximum node degree of input graph. We will also construct a polynomial-time $H(\frac{\delta (\delta -1)}{2})$ -approximation for the problem where H(?) is the harmonic function.     

An adaptive multistart tabu search approach to solve the maximum clique problem

Given an undirected graph G=(V,E) with vertex set V={1,…,n} and edge set E?V×V. The maximum clique problem is to determine in G a clique (i.e., a complete subgraph) of maximum cardinality. This paper presents an effective algorithm for the maximum clique problem. The proposed multistart tabu search algorithm integrates a constrained neighborhood, a dynamic tabu tenure mechanism and a long term memory based restart strategy. Our proposed algorithm is evaluated on the whole set of 80 DIMACS challenge benchmarks and compared with five state-of-the-art algorithms. Computational results show that our proposed algorithm attains the largest known clique for 79 benchmarks.     

On cyclic vertex-connectivity of Cartesian product digraphs

For a strongly connected digraph D=(V(D),A(D)), a?vertex-cut S?V(D) is a cyclic vertex-cut of D if D?S has at least two strong components containing directed cycles. The cyclic vertex-connectivity ?? _c (D) is the minimum cardinality of all cyclic vertex-cuts of D. In this paper, we study ?? _c (D) for Cartesian product digraph D=D ₁×D ₂, where D ₁,D ₂ are two strongly connected digraphs. We give an upper bound and a lower bound for ?? _c (D). Furthermore, the exact value of $\kappa_{c}(C_{n_{1}}\times C_{n_{2}}\times\cdots\times C_{n_{k}})$ is determined, where $C_{n_{i}}$ is the directed cycle of length n _i for i=1,2,??,k.     

Distance two edge labelings of lattices

Suppose G is a graph. Two edges e and e′ in G are said to be adjacent if they share a common end vertex, and distance two apart if they are nonadjacent but both are adjacent to a common edge. Let j and k be two positive integers. An L(j,k)-edge-labeling of a graph G is an assignment of nonnegative integers, called labels, to the edges of G such that the difference between labels of any two adjacent edges is at least j, and the difference between labels of any two edges that are distance two apart is at least k. The minimum range of labels over all L(j,k)-edge-labelings of a graph G is called the L(j,k)-edge-labeling number of G, denoted by $\lambda_{j,k}'(G)$ . Let m, j and k be positive integers. An m-circular-L(j,k)-edge-labeling of a graph G is an assignment f from {0,1,…,m?1} to the edges of G such that, for any two edges e and e′, |f(e)?f(e′)| _m ≥j if e and e′ are adjacent, and |f(e)?f(e′)| _m ≥k if e and e′ are distance two apart, where |a| _m =min{a,m?a}. The minimum m such that G has an m-circular-L(j,k)-edge-labeling is called the circular-L(j,k)-edge-labeling number of G, denoted by $\sigma_{j,k}'(G)$ . This paper investigates the L(1,1)-edge-labeling numbers, the L(2,1)-edge-labeling numbers and the circular-L(2,1)-edge-labeling numbers of the hexagonal lattice, the square lattice, the triangular lattice and the strong product of two infinite paths.