A Linear Time Algorithm for L(2,1)-Labeling of Trees

An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)?f(y)|≥2 if x and y are adjacent and |f(x)?f(y)|≥1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an L(2,1)-labeling f:V(G)→{0,…,k}, and the L(2,1)-labeling problem asks the minimum k, which we denote by λ(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Δ ^4.5 n) for more than a decade, and an O(min{n ^1.75,Δ ^1.5 n})-time algorithm has appeared recently, where Δ and n are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for L(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for L(p,1)-labeling with a constant p.     

Improved upper bounds on the L(2,1) -labeling of the skew and converse skew product graphs

An L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1 and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between x and y in G. The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):vV(G)}=k. Griggs and Yeh conjecture that λ(G)≤Δ² for any simple graph with maximum degree Δ≥2. This paper considers the graph formed by the skew product and the converse skew product of two graphs with a new approach on the analysis of adjacency matrices of the graphs as in [W.C. Shiu, Z. Shao, K.K. Poon, D. Zhang, A new approach to the L(2,1)-labeling of some products of graphs, IEEE Trans. Circuits Syst. II: Express Briefs (to appear)] and improves the previous upper bounds significantly.     

A General Approach to L（h,k）-Label Interconnection Networks

Given two non-negative integers h and k, an L（h, k）-labeling of a graph G = （V, E） is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h, and nodes at distance 2 take colors at distance at least k. The aim of the L（h, k）-labeling problem is to minimize the greatest used color. Since the decisional version of this problem is NP-complete, it is important to investigate particular classes of graphs for which the problem can be efficiently solved. It is well known that the most common interconnection topologies, such as Butterfly-like, Beneg, CCC, Trivalent Cayley networks, are all characterized by a similar structure： they have nodes organized as a matrix and connections are divided into layers. So we naturally introduce a new class of graphs, called （l × n）-multistage graphs, containing the most common interconnection topologies, on which we study the L（h, k）-labeling. A general algorithm for L（h, k）-labeling these graphs is presented, and from this method an efficient L（2, 1）-labeling for Butterfly and CCC networks is derived. Finally we describe a possible generalization of our approach.     

Applying Modular Decomposition to Parameterized Cluster Editing Problems

A graph G is said to be a bicluster graph if G is a disjoint union of bicliques (complete bipartite subgraphs), and a cluster graph if G is a disjoint union of cliques (complete subgraphs). In this work, we study the parameterized versions of the NP-hard Bicluster Graph Editing and Cluster Graph Editing problems. The former consists of obtaining a bicluster graph by making the minimum number of modifications in the edge set of an input bipartite graph. When at most k modifications are allowed (Bicluster(k) Graph Editing problem), this problem is FPT, and can be solved in O(4 ^k nm) time by a standard search tree algorithm. We develop an algorithm of time complexity O(4 ^k +n+m), which uses a strategy based on modular decomposition techniques; we slightly generalize the original problem as the input graph is not necessarily bipartite. The algorithm first builds a problem kernel with O(k ²) vertices in O(n+m) time, and then applies a bounded search tree. We also show how this strategy based on modular decomposition leads to a new way of obtaining a problem kernel with O(k ²) vertices for the Cluster(k) Graph Editing problem, in O(n+m) time. This problem consists of obtaining a cluster graph by modifying at most k edges in an input graph. A previous FPT algorithm of time O(1.92 ^k +n ³) for this problem was presented by Gramm et al. (Theory Comput. Syst. 38(4), 373–392, 2005, Algorithmica 39(4), 321–347, 2004). In their solution, a problem kernel with O(k ²) vertices is built in O(n ³) time.     

Group path covering and distance two labeling of graphs

For a positive integer d, an L(d,1)-labeling f of a graph G is an assignment of integers to the vertices of G such that |f(u)−f(v)|?d if uv∈E(G), and |f(u)−f(v)|?1 if u and u are at distance two. The span of an L(d,1)-labeling f of a graph is the absolute difference between the maximum and minimum integers used by f. The L(d,1)-labeling number of G, denoted by λd,1(G), is the minimum span over all L(d,1)-labelings of G. An L^′(d,1)-labeling of a graph G is an L(d,1)-labeling of G which assigns different labels to different vertices. Denote by the L^′(d,1)-labeling number of G. Georges et al. [Discrete Math. 135 (1994) 103-111] established relationship between the L(2,1)-labeling number of a graph G and the path covering number of Gc, the complement of G. In this paper we first generalize the concept of the path covering of a graph to the t-group path covering. Then we establish the relationship between the L^′(d,1)-labeling number of a graph G and the (d−1)-group path covering number of Gc. Using this result, we prove that and for bipartite graphs G can be computed in polynomial time.     

On Cutwidth Parameterized by Vertex Cover

We study the Cutwidth problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for Cutwidth with running time O(2 ^k n ^O(1)). Here k is the size of a minimum vertex cover of the input graph G, and n is the number of vertices in G. Our algorithm gives an O(2 ^n/2 n ^O(1)) time algorithm for Cutwidth on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for Cutwidth on a graph class where the problem remains NP-complete. Additionally, we show that Cutwidth parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless NP?coNP/poly. Our kernelization lower bound contrasts with the recent results of Bodlaender et al. (ICALP, Springer, Berlin, 2011; SWAT, Springer, Berlin, 2012) that both Treewidth and Pathwidth parameterized by vertex cover do admit polynomial kernels.     

On the L(2, 1)-labelling of block graphs

The distance-two labelling problem of graphs was proposed by Griggs and Roberts in 1988, and it is a variation of the frequency assignment problem introduced by Hale in 1980. An L(2, 1)-labelling of a graph G is an assignment of non-negative integers to the vertices of G such that vertices at distance two receive different numbers and adjacent vertices receive different and non-consecutive integers. The L(2, 1)-labelling number of G, denoted by λ(G), is the smallest integer k such that G has a L(2, 1)-labelling in which no label is greater than k.

In this work, we study the L(2, 1)-labelling problem on block graphs. We find upper bounds for λ(G) in the general case and reduce those bounds for some particular cases of block graphs with maximum clique size equal to 3.     

An Approximation Algorithm for the Minimum Co-Path Set Problem

We present an approximation algorithm for the problem of finding a minimum set of edges in a given graph G whose removal from G leaves a graph in which each connected component is a path. It achieves a ratio of \frac 107\frac {10}{7} and runs in O(n ^1.5) time, where n is the number of vertices in the input graph. The previously best approximation algorithm for this problem achieves a ratio of 2 and runs in O(n ²) time.     

The k-neighbourhood-covering problem on interval graphs

Let G=(V, E) be a simple connected graph and k be a fixed positive integer. A vertex w is said to be a k-neighbourhood-cover (kNC) of an edge (u, v) if d(u, w)≤k and d(v, w)≤k. A set C ? V is called a kNC set if every edge in E is kNC by some vertices of C. The decision problem associated with this problem is NP-complete for general graphs and it remains NP-complete for chordal graphs. In this article, we design an O(n) time algorithm to solve minimum kNC problem on interval graphs by using a data structure called interval tree.     

Efficient Algorithms for <Emphasis Type="Italic">k</Emphasis>-Terminal Cuts on Planar Graphs

The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a min{O(n ² log n logm), O(m ² n ^1.5 log² n + k n)} time algorithm with a (2–2/k)-approximation ratio (clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(n k3 + (n log n)k ²) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation algorithm of Dahlhaus et al. (for general graphs) takes O(k n ² log n) time when applied to planar graphs. Our approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm) factor (m \le k).     

Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds

Edge coloring, total coloring and L(2,1)-labeling are well-studied NP-hard graph problems. Even the versions asking whether a graph has a coloring with few colors or a labeling with few labels remain NP-hard on graphs of small maximum degree. This paper studies enumeration and counting problems on edge colorings, total colorings and L(2,1)-labelings of graphs. One part deals with the enumeration of all edge 3-colorings, all total 4-colorings and all L(2,1)-labelings of span 5 of a given connected cubic graph. Branching algorithms to solve these enumeration problems are established. They imply upper bounds on the maximum number of edge 3-colorings, total 4-colorings and L(2,1)-labelings of span 5 in any n-vertex connected cubic graphs. Corresponding combinatorial lower bounds are also provided. The other part of the paper studies dynamic programming algorithms solving counting problems. On one hand, algorithms to count the number of edge k-colorings and total k-colorings for graphs of bounded pathwidth are given. On the other hand, an algorithm to count the number of L(2,1)-labelings of span 4 for graphs of maximum degree three are given.     

A Cubic Kernel for Feedback Vertex Set and Loop Cutset

The Feedback Vertex Set problem on unweighted, undirected graphs is considered. Improving upon a result by Burrage et al. (Proceedings 2nd International Workshop on Parameterized and Exact Computation, pp. 192–202, 2006), we show that this problem has a kernel with O(k ³) vertices, i.e., there is a polynomial time algorithm, that given a graph G and an integer k, finds a graph G′ with O(k ³) vertices and integer k′≤k, such that G has a feedback vertex set of size at most k, if and only if G′ has a feedback vertex set of size at most k′. Moreover, the algorithm can be made constructive: if the reduced instance G′ has a feedback vertex set of size k′, then we can easily transform a minimum size feedback vertex set of G′ into a minimum size feedback vertex set of G. This kernelization algorithm can be used as the first step of an FPT algorithm for Feedback Vertex Set, but also as a preprocessing heuristic for Feedback Vertex Set.     

Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms

Motivated by the research in reconfigurable memory array structures, this paper studies the complexity and algorithms for the constrained minimum vertex cover problem on bipartite graphs (min-cvcb) defined as follows: given a bipartite graph G=(V,E) with vertex bipartition V=U∪L and two integers k_u and k_l, decide whether there is a minimum vertex cover in G with at most k_u vertices in U and at most k_l vertices in L. It is proved in this paper that the min-cvcb problem is NP-complete. This answers a question posed by Hasan and Liu. A parameterized algorithm is developed for the problem, in which classical results in matching theory and recently developed techniques in parameterized computation theory are nicely combined and extended. The algorithm runs in time O(1.26^k_u+k_l+(k_u+k_l)|G|) and significantly improves previous algorithms for the problem.     

Bandwidth Minimization: An approximation algorithm for caterpillars

The Bandwidth Minimization Problem (BMP) is the problem, given a graphG and an integerk, to map the vertices ofG to distinct positive integers, so that no edge ofG has its endpoints mapped to integers that differ by more thank. There is no known approximation algorithm for this problem, even for the case of trees. We present an approximation algorithm for the BMP for the case of special graphs, called caterpillars. The BMP arises from many different engineering applications which try to achieve efficient storage and processing and has been studied extensively, especially with relation to other graph layout problems. In particular, the BMP for caterpillars is related to multiprocessor scheduling. It has been shown to be NP-complete, even for degree-3 trees. Our algorithm, gives a logn times optimal algorithm, wheren is the number of nodes of the caterpillar. It is based on the idea of level algorithms.This work has been, in part, supported by the Computer Learning Research (CLEAR) Center at UTD.     

Algorithms for (0, 1, d)-graphs with d constrains

Let G be a graph with vertex set V(G). Let n, k, d be non-negative integers such that n+2k+d≤|V(G)|?2 and |V(G)|?n?d are even. A matching which saturates exactly |V(G)|?d vertices is called a defect-d matching of G. If when deleting any n vertices the remaining subgraph contains a matching of k edges and every k-matching can be extended to a defect-d matching, then G is said to be an (n, k, d)-graph. We present an algorithm to determine (0, 1, d)-graphs with d constraints. Moreover, we solve the problem of augmenting a bipartite graph G=(B, W) to be a (0, 1, d)-graph by adding fewest edges, where d=∥B|?|W∥. The latter problem is applicable to the job assignment problem, where the number of jobs does not equal the number of persons.     

Channel assignment via fast zeta transform

We show an O^?(n(?+1))-time algorithm for the channel assignment problem, where ? is the maximum edge weight. This improves on the previous O^?(n(?+2))-time algorithm by Král (2005) [1], as well as algorithms for important special cases, like L(2,1)-labeling. For the latter problem, our algorithm works in O^?(n³) time. The progress is achieved by applying the fast zeta transform in combination with the inclusion-exclusion principle.     

Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization

We show that the NP-complete Feedback Vertex Set problem, which asks for the smallest set of vertices to remove from a graph to destroy all cycles, is deterministically solvable in O(ck⋅m) time. Here, m denotes the number of graph edges, k denotes the size of the feedback vertex set searched for, and c is a constant. We extend this to an algorithm enumerating all solutions in O(dk⋅m) time for a (larger) constant d. As a further result, we present a fixed-parameter algorithm with runtime O(k²⋅m²) for the NP-complete Edge Bipartization problem, which asks for at most k edges to remove from a graph to make it bipartite.     

Shortest noncrossing paths in plane graphs

Let G be an undirected plane graph with nonnegative edge length, and letk terminal pairs lie on two specified face boundaries. This paper presents an algorithm for findingk noncrossing paths inG, each connecting a terminal pair, and whose total length is minimum. Noncrossing paths may share common vertices or edges but do not cross each other in the plane. The algorithm runs in timeO(n logn) wheren is the number of vertices inG andk is an arbitrary integer.     

Efficient parallel algorithms for breadth first spanning forests of general graphs

Ghosh and Bhattacharjee propose [2] (Intern. J. Computer Math., 1984, Vol. 15, pp. 255-268) an algorithm of determining breadth first spanning trees for graphs, which requires that the input graphs contain some vertices, from which every other vertex in the input graph can be reached. These vertices are called starting vertices. The complexity of the GB algorithm is O(log² n) using O{n ³) processors. In this paper an algorithm, named BREADTH, also computing breadth first spanning trees, is proposed. The complexity is O(log² n) using O{n ³/logn) processors. Then an efficient parallel algorithm, named- BREADTHFOREST, is proposed, which generalizes algorithm BREADTH. The output of applying BREADTHFOREST to a general graph, which may not contain any starting vertices, is a breadth first spanning forest of the input graph. The complexity of BREADTHFOREST is the same as BREADTH.     

Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs

There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a k ^O(dk) n time algorithm for finding a dominating set of size at most k in a d-degenerated graph with n vertices. This proves that the dominating set problem is fixed-parameter tractable for degenerated graphs. For graphs that do not contain K _h as a topological minor, we give an improved algorithm for the problem with running time (O(h)) ^hk n. For graphs which are K _h -minor-free, the running time is further reduced to (O(log h)) ^hk/2 n. Fixed-parameter tractable algorithms that are linear in the number of vertices of the graph were previously known only for planar graphs. For the families of graphs discussed above, the problem of finding an induced cycle of a given length is also addressed. For every fixed H and k, we show that if an H-minor-free graph G with n vertices contains an induced cycle of size k, then such a cycle can be found in O(n) expected time as well as in O(nlog n) worst-case time. Some results are stated concerning the (im)possibility of establishing linear time algorithms for the more general family of degenerated graphs. A preliminary version of this paper appeared in the Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON), Banff, Alberta, Canada (2007), pp. 394–405. N. Alon research supported in part by a grant from the Israel Science Foundation, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. This paper forms part of a Ph.D. thesis written by S. Gutner under the supervision of Prof. N. Alon and Prof. Y. Azar in Tel Aviv University.