Linear time construction of 5-phylogenetic roots for tree chordal graphs

Inspired by phylogenetic tree construction in computational biology, Lin et al. (The 11th Annual International Symposium on Algorithms and Computation (ISAAC 2000), pp. 539–551, 2000) introduced the notion of a k -phylogenetic root. A k-phylogenetic root of a graph G is a tree T such that the leaves of T are the vertices of G, two vertices are adjacent in G precisely if they are within distance k in T, and all non-leaf vertices of T have degree at least three. The k-phylogenetic root problem is to decide whether such a tree T exists for a given graph G. In addition to introducing this problem, Lin et al. designed linear time constructive algorithms for k≤4, while left the problem open for k≥5. In this paper, we partially fill this hole by giving a linear time constructive algorithm to decide whether a given tree chordal graph has a 5-phylogenetic root; this is the largest class of graphs known to have such a construction.     

Popular matchings: structure and algorithms

An instance of the popular matching problem (POP-M) consists of a set of applicants and a set of posts. Each applicant has a preference list that strictly ranks a subset of the posts. A matching M of applicants to posts is popular if there is no other matching M′ such that more applicants prefer M′ to M than prefer M to M′. Abraham et al. (SIAM J. Comput. 37:1030–1045, 2007) described a linear time algorithm to determine whether a popular matching exists for a given instance of POP-M, and if so to find a largest such matching. A number of variants and extensions of POP-M have recently been studied. This paper provides a characterization of the set of popular matchings for an arbitrary POP-M instance in terms of a structure called the switching graph, a directed graph computable in linear time from the preference lists. We show that the switching graph can be exploited to yield efficient algorithms for a range of associated problems, including the counting and enumeration of the set of popular matchings, generation of a popular matching uniformly at random, finding all applicant-post pairs that can occur in a popular matching, and computing popular matchings that satisfy various additional optimality criteria. Our algorithms for computing such optimal popular matchings improve those described in a recent paper by Kavitha and Nasre (Proceedings of MATCH-UP: Matching Under Preferences—Algorithms and Complexity, 2008).     

The canadian traveller problem and its competitive analysis

From the online point of view, we study the Canadian Traveller Problem (CTP), in which the traveller knows in advance the structure of the graph and the costs of all edges. However, some edges may fail and the traveller only observes that upon reaching an adjacent vertex of the blocked edge. The goal is to find the least-cost route from the source O to the destination D, more precisely, to find an adaptive strategy minimizing the competitive ratio, which compares the performance of this strategy with that of a hypothetical offline algorithm that knows the entire topology in advance. In this paper, we present two adaptive strategies—a greedy or myopic strategy and a comparison strategy combining the greedy strategy and the reposition strategy in which the traveller backtracks to the source every time when he/she sees a failed edge. We prove tight competitive ratios of 2 ^k+1−1 and 2k+1 respectively for the two strategies, where k is the number of failed edges in the graph. Finally, we propose an explanation of why the greedy strategy and the comparison strategy are usually preferred by drivers in an urban traffic environment, based on an argument related to the length of the second-shortest path in a grid graph. We would like to acknowledge the support from NSF of China (No. 70525004, No. 70121001 and No. 60736027), and the support from K.C. Wong Education Foundation, Hong Kong.     

A quadratic lower bound for Rocchio’s similarity-based relevance feedback algorithm with a fixed query updating factor

Rocchio’s similarity-based relevance feedback algorithm, one of the most important query reformation methods in information retrieval, is essentially an adaptive supervised learning algorithm from examples. In practice, Rocchio’s algorithm often uses a fixed query updating factor. When this is the case, we strengthen the linear Ω(n) lower bound obtained by Chen and Zhu (Inf. Retr. 5:61–86, 2002) and prove that Rocchio’s algorithm makes Ω(k(n−k)) mistakes in searching for a collection of documents represented by a monotone disjunction of k relevant features over the n-dimensional binary vector space {0,1} ⁿ , when the inner product similarity measure is used. A quadratic lower bound is obtained when k is linearly proportional to n. We also prove an O(k(n−k)³) upper bound for Rocchio’s algorithm with the inner product similarity measure in searching for such a collection of documents with a constant query updating factor and a zero classification threshold.     

Strongly chordal and chordal bipartite graphs are sandwich monotone

A graph class is sandwich monotone if, for every pair of its graphs G ₁=(V,E ₁) and G ₂=(V,E ₂) with E ₁⊂E ₂, there is an ordering e ₁,…,e _k of the edges in E ₂∖E ₁ such that G=(V,E ₁∪{e ₁,…,e _i }) belongs to the class for every i between 1 and k. In this paper we show that strongly chordal graphs and chordal bipartite graphs are sandwich monotone, answering an open question by Bakonyi and Bono (Czechoslov. Math. J. 46:577–583, 1997). So far, very few classes have been proved to be sandwich monotone, and the most famous of these are chordal graphs. Sandwich monotonicity of a graph class implies that minimal completions of arbitrary graphs into that class can be recognized and computed in polynomial time. For minimal completions into strongly chordal or chordal bipartite graphs no polynomial-time algorithm has been known. With our results such algorithms follow for both classes. In addition, from our results it follows that all strongly chordal graphs and all chordal bipartite graphs with edge constraints can be listed efficiently.     

The broadcast median problem in heterogeneous postal model

We propose the problem of finding broadcast medians in heterogeneous networks. A heterogeneous network is represented by a graph G=(V,E), in which each edge has a weight that denotes the communication time between its two end vertices. The overall delay of a vertex v∈V(G), denoted as b(v,G), is the minimum sum of the communication time required to send a message from v to all vertices in G. The broadcast median problem consists of finding the set of vertices v∈V(G) with minimum overall delay b(v,G) and determining the value of b(v,G). In this paper, we consider the broadcast median problem following the heterogeneous postal model. Assuming that the underlying graph G is a general graph, we show that computing b(v,G) for an arbitrary vertex v∈V(G) is NP-hard. On the other hand, assuming that G is a tree, we propose a linear time algorithm for the broadcast median problem in heterogeneous postal model.     

Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

Given a simple, undirected graph G=(V,E) and a weight function w:E→ℤ⁺, we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. It has previously been shown that the unweighted version of the problem is solvable in polynomial time while the weighted version is (weakly) NP-hard. In this paper, we strengthen these results as follows: (1) We prove that the weighted version is strongly NP-hard even if all edge weights belong to the set {1,k}, where k is any fixed integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm for this problem whose approximation ratio is smaller than (1+1/k) unless P = NP; (2) we present a new polynomial-time algorithm that approximates the general version of the problem within a ratio of (2−1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1,k} within a ratio of 3/2 for k=2 (note that this matches the inapproximability bound above), and (2−2/(k+1)) for any k≥3, respectively, in polynomial time.     

Improving an upper bound on the size of k-regular induced subgraphs

This paper considers the NP-hard graph problem of determining a maximum cardinality subset of vertices inducing a k-regular subgraph. For any graph G, this maximum will be denoted by α _k (G). From a well known Motzkin-Straus result, a relationship is deduced between α _k (G) and the independence number α(G). Next, it is proved that the upper bounds υ _k (G) introduced in Cardoso et al. (J. Comb. Optim., 14, 455–463, 2007) can easily be computed from υ ₀(G), for any positive integer k. This relationship also allows one to present an alternative proof of the Hoffman bound extension introduced in the above paper. The paper continues with the introduction of a new upper bound on α _k (G) improving υ _k (G). Due to the difficulty of computing this improved bound, two methods are provided for approximating it. Finally, some computational experiments which were performed to compare all bounds studied are reported.     

A dynamic programming approach of finding an optimal broadcast schedule in minimizing total flow time

We study the problem of (off-line) broadcast scheduling in minimizing total flow time and propose a dynamic programming approach to compute an optimal broadcast schedule. Suppose the broadcast server has k pages and the last page request arrives at time n. The optimal schedule can be computed in O(k³(n+k)^k−1) time for the case that the server has a single broadcast channel. For m channels case, i.e., the server can broadcast m different pages at a time where m < k, the optimal schedule can be computed in O(n^k−m) time when k and m are constants. Note that this broadcast scheduling problem is NP-hard when k is a variable and will take O(n^k−m+1) time when k is fixed and m ≥ 1 with the straightforward implementation of the dynamic programming approach. The preliminary version of this paper appeared in Proceedings of the 11th Annual International Computing and Combinatorics Conference as “Off-line Algorithms for Minimizing the Total Flow Time in Broadcast Scheduling”.     

Labelling algorithms for paired-domination problems in block and interval graphs

Let G=(V,E) be a graph without isolated vertices. A set S⊆V is a paired-dominating set if every vertex in V−S is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination problem is to determine the paired-domination number, which is the minimum cardinality of a paired-dominating set. Motivated by a mistaken algorithm given by Chen, Kang and Ng (Discrete Appl. Math. 155:2077–2086, 2007), we present two linear time algorithms to find a minimum cardinality paired-dominating set in block and interval graphs. In addition, we prove that paired-domination problem is NP-complete for bipartite graphs, chordal graphs, even for split graphs.     

Multiple hypernode hitting sets and smallest two-cores with targets

The multiple weighted hitting set problem is to find a subset of nodes in a hypergraph that hits every hyperedge in at least m nodes. We extend the problem to a notion of hypergraphs with so-called hypernodes and show that, for m=2, it remains fixed-parameter tractable (FPT), parameterized by the number of hyperedges. This is accomplished by a nontrivial extension of the dynamic programming algorithm for hypergraphs. The algorithm might be interesting for certain assignment problems, but here we need it as a tool to solve another problem motivated by network analysis: A d-core of a graph is a subgraph in which every vertex has at least d neighbors. We give an FPT algorithm that computes a smallest 2-core including a given set of target vertices, where the number of targets is the parameter. This FPT result is best possible in the sense that no FPT algorithm for 3-cores can be expected.     

Combinatorial algorithms for the maximum k-plex problem

The maximum clique problem provides a classic framework for detecting cohesive subgraphs. However, this approach can fail to detect much of the cohesive structure in a graph. To address this issue, Seidman and Foster introduced k-plexes as a degree-based clique relaxation. More recently, Balasundaram et al. formulated the maximum k-plex problem as an integer program and designed a branch-and-cut algorithm. This paper derives a new upper bound on the cardinality of k-plexes and adapts combinatorial clique algorithms to find maximum k-plexes.     

On the total {k}-domination number of Cartesian products of graphs

Let γ _t ^{k}(G) denote the total {k}-domination number of graph G, and let denote the Cartesian product of graphs G and H. In this paper, we show that for any graphs G and H without isolated vertices, . As a corollary of this result, we have for all graphs G and H without isolated vertices, which is given by Pak Tung Ho (Util. Math., 2008, to appear) and first appeared as a conjecture proposed by Henning and Rall (Graph. Comb. 21:63–69, 2005). The work was supported by NNSF of China (No. 10701068 and No. 10671191).     

Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts

For an edge weighted undirected graph G and an integer k > 2, a k-way cut is a set of edges whose removal leaves G with at least k components. We propose a simple approximation algorithm to the minimum k-way cut problem. It computes a nearly optimal k-way cut by using a set of minimum 3-way cuts. We show that the performance ratio of our algorithm is 2 – 3/k for an odd k and 2 – (3k – 4)/(k ² – k) for an even k. The running time is O(kmn ³ log(n ²/m)) where n and m are the numbers of vertices and edges respectively.     

On lazy bureaucrat scheduling with common deadlines

Lazy bureaucrat scheduling is a new class of scheduling problems introduced by Arkin et al. (Inf. Comput. 184:129–146, 2003). In this paper we focus on the case where all the jobs share a common deadline. Such a problem is denoted as CD-LBSP, which has been considered by Esfahbod et al. (Algorithms and data structures. Lecture notes in computer science, vol. 2748, pp. 59–66, 2003). We first show that the worst-case ratio of the algorithm SJF (Shortest Job First) is two under the objective function [min-time-spent], and thus answer an open question posed in (Esfahbod, et al. in Algorithms and data structures. Lecture notes in computer science, vol. 2748, pp. 59–66, 2003). We further present two approximation schemes A _k and B _k both having worst-case ratio of , for any given integer k>0, under the objective functions [min-makespan] and [min-time-spent], respectively. Finally, we prove that the problem CD-LBSP remains NP-hard under several objective functions, even if all jobs share the same release time. A preliminary version of the paper appeared in Proceedings of the 7th Latin American Symposium on Theoretical Informatics, pp 515–523, 2006. Research of G. Zhang supported in part by NSFC (60573020).     

Broadcast Routing with Minimum Wavelength Conversion in WDM Optical Networks

We consider dynamic routing of broadcast connections in WDM optical networks. Given the current network state, we want to find a minimum set of network nodes S such that a broadcast routing using only the nodes in S as wavelength conversion nodes can be found. This ensures that the average conversion delay from the source to all destinations is minimized. We refer to the problem as Broadcast Conversion Node Selection (BCNS) problem. We prove that BCNS has no polynomial-time approximation with performance ratio ln n for < 1 unless NPDTIME(n^{O(log log n)}) where n is the number of vertices in the input graph. We present a greedy approximation algorithm for BCNS that achieves approximation ratio 2+ln n. Simulation results show that the algorithm performs very well in practice, obtaining optimal solutions in most of the cases.     

Enumerating the edge-colourings and total colourings of a regular graph

In this paper, we are interested in computing the number of edge colourings and total colourings of a connected graph. We prove that the maximum number of k-edge-colourings of a connected k-regular graph on n vertices is k?((k?1)!) ^n/2. Our proof is constructive and leads to a branching algorithm enumerating all the k-edge-colourings of a connected k-regular graph in time O ^?(((k?1)!) ^n/2) and polynomial space. In particular, we obtain a algorithm to enumerate all the 3-edge-colourings of a connected cubic graph in time O ^?(2 ^n/2)=O ^?(1.4143 ⁿ ) and polynomial space. This improves the running time of O ^?(1.5423 ⁿ ) of the algorithm due to Golovach et al. (Proceedings of WG 2010, pp. 39–50, 2010). We also show that the number of 4-total-colourings of a connected cubic graph is at most 3?2^3n/2. Again, our proof yields a branching algorithm to enumerate all the 4-total-colourings of a connected cubic graph.     

Necessary Edges in k-Chordalisations of Graphs

A k-chordalisation of a graph G = (V,E) is a graph H = (V,F) obtained by adding edges to G, such that H is a chordal graph with maximum clique size at most k. This note considers the problem: given a graph G = (V,E) which pairs of vertices, non-adjacent in G, will be an edge in every k-chordalisation of G. Such a pair is called necessary for treewidth k. An equivalent formulation is: which edges can one add to a graph G such that every tree decomposition of G of width at most k is also a tree decomposition of the resulting graph G. Some sufficient, and some necessary and sufficient conditions are given for pairs of vertices to be necessary for treewidth k. For a fixed k, one can find in linear time for a given graph G the set of all necessary pairs for treewidth k. If k is given as part of the input, then this problem is coNP-hard. A few similar results are given when interval graphs (and hence pathwidth) are used instead of chordal graphs and treewidth.     

Optimal all-to-all personalized exchange in d-nary banyan multistage interconnection networks

All-to-all personalized exchange occurs in many important applications in parallel processing. In the past two decades, algorithms for all-to-all personalized exchange were mainly proposed for hypercubes, meshes, and tori. Recently, Yang and Wang (IEEE Trans Parallel Distrib Syst 11:261–274, 2000) proposed an optimal all-to-all personalized exchange algorithm for binary (each switch is of size 2×2) banyan multistage interconnection networks. It was pointed out in Massini (Discret Appl Math 128:435–446, 2003) that the algorithm in Yang, Wang (IEEE Trans Parallel Distrib Syst 11:261–274, 2000) depends on the network topologies and requires pre-computation and memory allocation for a Latin square. Thus in (Discret Appl Math 128:435–446, 2003), Massini proposed a new optimal algorithm, which is independent of the network topologies and does not require pre-computation or memory allocation for a Latin square. Unfortunately, Massini’s algorithm has a flaw and does not realize all-to-all personalized exchange. In this paper, we will correct the flaw and generalize Massini’s algorithm to be applicable to d-nary (each switch is of size d×d) banyan multistage interconnection networks. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This research was partially supported by the National Science Council of the Republic of China under the grant NSC94-2115-M-009-006.     

Finding paths with minimum shared edges

Motivated by a security problem in geographic information systems, we study the following graph theoretical problem: given a graph G, two special nodes s and t in G, and a number k, find k paths from s to t in G so as to minimize the number of edges shared among the paths. This is a generalization of the well-known disjoint paths problem. While disjoint paths can be computed efficiently, we show that finding paths with minimum shared edges is NP-hard. Moreover, we show that it is even hard to approximate the minimum number of shared edges within a factor of $2^{\log^{1-\varepsilon}n}$ , for any constant ε>0. On the positive side, we show that there exists a (k?1)-approximation algorithm for the problem, using an adaption of a network flow algorithm. We design some heuristics to improve the quality of the output, and provide empirical results.