An improved exact algorithm for the domatic number problem

The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time n^2.695 (up to polynomial factors) and in polynomial space. This result improves the previous bound of n^2.8805, which is due to Björklund and Husfeldt. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Δ(G) by a randomized polynomial-space algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Δ(G)?5. Our new randomized algorithm employs Schöning's approach to constraint satisfaction problems.     

Acyclic edge colourings of graphs with the number of edges linearly bounded by the number of vertices

Let G be any finite graph. A mapping c:E(G)→{1,…,k} is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced in G by all the edges that have colour i or j is acyclic. The smallest number k of colours such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G and is denoted by .Determining the acyclic chromatic index of a graph is a hard problem, both from theoretical and algorithmical point of view. In 1991, Alon et al. proved that for any graph G of maximum degree Δ(G). This bound was later improved to 16Δ(G) by Molloy and Reed. In general, the problem of computing the acyclic chromatic index of a graph is NP-complete. Only a few algorithms for finding acyclic edge colourings have been known by now. Moreover, these algorithms work only for graphs from particular classes.In our paper, we prove that for every graph G which satisfies the condition that |E(G^′)|?t|V(G^′)|−1 for each subgraph G^′⊆G, where t?2 is a given integer, the constant p=2t³−3t+2. Based on that result, we obtain a polynomial algorithm which computes such a colouring. The class of graphs covered by our theorem is quite rich, for example, it contains all t-degenerate graphs.     

Faster algorithms for guided tree edit distance

The guided tree edit distance problem is to find a minimum cost series of edit operations that transforms two input forests F and G into isomorphic forests F^′ and G^′ such that a third input forest H is included in F^′ (and G^′). The edit operations are relabeling a vertex and deleting a vertex. We show efficient algorithms for this problem that are faster than the previous algorithm for this problem of Peng and Ting [Z. Peng, H. Ting, Guided forest edit distance: Better structure comparisons by using domain-knowledge, in: Proc. 18th Symposium on Combinatorial Pattern Matching (CPM), 2007, pp. 28-39].     

Analysis of a heuristic for acyclic edge colouring

An acyclic edge colouring of a graph is a proper edge colouring in which the union of any two colour classes does not contain a cycle, that is, forms a forest. It is known that there exists such a colouring using at most 16Δ(G) colours where Δ(G) denotes the maximum degree of a graph G. However, no non-trivial constructive bound (which works for all graphs) is known except for the straightforward distance 2 colouring which requires Δ² colours. We analyse a simple O(mnΔ²²(logΔ)) time greedy heuristic and show that it uses at most 5Δ(logΔ+2) colours on any graph.     

Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O^∗(²n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O^∗(²n/2). Another implication is an algorithm for general graphs whose running time is O(n^1.7088).     

An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem

We consider the minimum maximal matching problem, which is NP-hard (Yannakakis and Gavril (1980) [18]). Given an unweighted simple graph G=(V,E), the problem seeks to find a maximal matching of minimum cardinality. It was unknown whether there exists a non-trivial approximation algorithm whose approximation ratio is less than 2 for any simple graph. Recently, Z. Gotthilf et al. (2008) [5] presented a -approximation algorithm, where c is an arbitrary constant.In this paper, we present a -approximation algorithm based on an LP relaxation, where χ^′(G) is the edge-coloring number of G. Our algorithm is the first non-trivial approximation algorithm whose approximation ratio is independent of |V|. Moreover, it is known that the minimum maximal matching problem is equivalent to the edge dominating set problem. Therefore, the edge dominating set problem is also -approximable. From edge-coloring theory, the approximation ratio of our algorithm is , where Δ(G) represents the maximum degree of G. In our algorithm, an LP formulation for the edge dominating set problem is used. Fujito and Nagamochi (2002) [4] showed the integrality gap of the LP formulation for bipartite graphs is at least . Moreover, χ^′(G) is Δ(G) for bipartite graphs. Thus, as far as an approximation algorithm for the minimum maximal matching problem uses the LP formulation, we believe our result is the best possible.     

Exact exponential-time algorithms for finding bicliques

Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G=(V,E) on n vertices, a pair (X,Y), with X,Y⊆V, X∩Y=∅, is a non-induced biclique if {x,y}∈E for any x∈X and y∈Y. The NP-complete problem of finding a non-induced (k₁,k₂)-biclique asks to decide whether G contains a non-induced biclique (X,Y) such that |X|=k₁ and |Y|=k₂. In this paper, we design a polynomial-space O(n^1.6914)-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(n^1.30052). In deriving this algorithm, we also exhibit a relation to the spare allocation problem known from memory chip fabrication. As a byproduct, we show that the constraint bipartite vertex cover problem can be solved in time O(n^1.30052).     

Minimum cycle bases of weighted outerplanar graphs

We give the first optimal algorithm that computes a minimum cycle basis for any weighted outerplanar graph. Specifically, for any n-node edge-weighted outerplanar graph G, we give an O(n)-time algorithm to obtain an O(n)-space compact representation Z(C) for a minimum cycle basis C of G. Each cycle in C can be computed from Z(C) in O(1) time per edge. Our result works for directed and undirected outerplanar graphs G.     

Minimal proper interval completions

Given an arbitrary graph G=(V,E) and a proper interval graph H=(V,F) with E⊆F we say that H is a proper interval completion of G. The graph H is called a minimal proper interval completion of G if, for any sandwich graph H^′=(V,F^′) with E⊆F^′⊂F, H^′ is not a proper interval graph. In this paper we give a O(n+m) time algorithm computing a minimal proper interval completion of an arbitrary graph. The output is a proper interval model of the completion.     

Speedup for a periodic subgraph miner

Given a series G={G₀,G₁,…,GT} of graphs encompassing V vertices and E edges, a periodic graph is a spatially as well as temporally maximal subgraph of a subsequence of G in the form , where n is not smaller than some predetermined threshold value σ. An algorithm for finding all such subgraphs is proposed taking time O((E+V)T²ln(T/σ)), which is faster by a factor of T than the method previously available.     

Dominating set based exact algorithms for 3-coloring

We show that the 3-colorability problem can be solved in O(n^1.296) time on any n-vertex graph with minimum degree at least 15. This algorithm is obtained by constructing a dominating set of the graph greedily, enumerating all possible 3-colorings of the dominating set, and then solving the resulting 2-list coloring instances in polynomial time. We also show that a 3-coloring can be obtained in ²o(n) time for graphs having minimum degree at least ω(n) where ω(n) is any function which goes to ∞. We also show that if the lower bound on minimum degree is replaced by a constant (however large it may be), then neither a ²o(n) time nor a ²o(m) time algorithm is possible (m denotes the number of edges) for 3-colorability unless Exponential Time Hypothesis (ETH) fails. We also describe an algorithm which obtains a 4-coloring of a 3-colorable graph in O(n^1.2535) time.     

Acyclic coloring of graphs of maximum degree five: Nine colors are enough

An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic number of G is the least number of colors necessary to acyclically color G. In this paper, we show that any graph of maximum degree 5 has acyclic chromatic number at most 9, and we give a linear time algorithm that achieves this bound.     

Parameterized approximation of dominating set problems

A problem open for many years is whether there is an FPT algorithm that given a graph G and parameter k, either: (1) determines that G has no k-Dominating Set, or (2) produces a dominating set of size at most g(k), where g(k) is some fixed function of k. Such an outcome is termed an FPT approximation algorithm. We describe some results that begin to provide some answers. We show that there is no such FPT algorithm for g(k) of the form k+c (where c is a fixed constant, termed an additive FPT approximation), unless FPT=W[2]. We answer the analogous problem completely for the related Independent Dominating Set (IDS) problem, showing that IDS does not admit an FPT approximation algorithm, for any g(k), unless FPT=W[2].     

2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs

An important optimization problem in the design of cellular networks is to assign sets of frequencies to transmitters to avoid unacceptable interference. A cellular network is generally modeled as a subgraph of the infinite triangular lattice. The distributed frequency assignment problem can be abstracted as a multicoloring problem on a weighted hexagonal graph, where the weight vector represents the number of calls to be assigned at vertices. In this paper we present a 2-local distributed algorithm for multicoloring triangle-free hexagonal graphs using only the local clique numbers ω₁(v) and ω₂(v) at each vertex v of the given hexagonal graph, which can be computed from local information available at the vertex. We prove that the algorithm uses no more than colors for any triangle-free hexagonal graph G, without explicitly computing the global clique number ω(G). Hence the competitive ratio of the algorithm is 5/4.     

Enhanced algorithms for Local Search

Let G=(V,E) be a finite graph, and be any function. The Local Search problem consists in finding a local minimum of the function f on G, that is a vertex v such that f(v) is not larger than the value of f on the neighbors of v in G. In this note, we first prove a separation theorem slightly stronger than the one of Gilbert, Hutchinson and Tarjan for graphs of constant genus. This result allows us to enhance a previously known deterministic algorithm for Local Search with query complexity , so that we obtain a deterministic query complexity of , where n is the size of G, d is its maximum degree, and g is its genus. We also give a quantum version of our algorithm, whose query complexity is of . Our deterministic and quantum algorithms have query complexities respectively smaller than the algorithm Randomized Steepest Descent of Aldous and Quantum Steepest Descent of Aaronson for large classes of graphs, including graphs of bounded genus and planar graphs.     

A note on finding all homogeneous set sandwiches

A module is a set of vertices H of a graph G=(V,E) such that each vertex of V?H is either adjacent to all vertices of H or to none of them. A homogeneous set is a nontrivial module. A graph G_s=(V,E_s) is a sandwich for a pair of graphs G_t=(V,E_t) and G=(V,E) if E_t⊆E_s⊆E. In a recent paper, Tang et al. [Inform. Process. Lett. 77 (2001) 17-22] described an O(Δn²) algorithm for testing the existence of a homogeneous set in sandwich graphs of G_t=(V,E_t) and G=(V,E) and then extended it to an enumerative algorithm computing all these possible homogeneous sets. In this paper, we invalidate this latter algorithm by proving there are possibly exponentially many such sets, even if we restrict our attention to strong modules. We then give a correct characterization of a homogeneous set of a sandwich graph.     

A linear-time algorithm to compute a MAD tree of an interval graph

The average distance of a connected graph G is the average of the distances between all pairs of vertices of G. We present a linear time algorithm that determines, for a given interval graph G, a spanning tree of G with minimum average distance (MAD tree). Such a tree is sometimes referred to as a minimum routing cost spanning tree.     

Uniform metrical task systems with a limited number of states

We give a randomized algorithm (the “Wedge Algorithm”) of competitiveness for any metrical task system on a uniform space of k points, for any k?2, where , the kth harmonic number. This algorithm has better competitiveness than the Irani-Seiden algorithm if k is smaller than 10⁸. The algorithm is better by a factor of 2 if k<47.     

The hub number of a graph

A hub set in a graph G is a set U⊆V(G) such that any two vertices outside U are connected by a path whose internal vertices lie in U. We prove that h(G)?hc(G)?γc(G)?h(G)+1, where h(G), hc(G), and γc(G), respectively, are the minimum sizes of a hub set in G, a hub set inducing a connected subgraph, and a connected dominating set. Furthermore, all graphs with γc(G)>hc(G)?4 are obtained by substituting graphs into three consecutive vertices of a cycle; this yields a polynomial-time algorithm to check whether hc(G)=γc(G).     

The on-line first-fit algorithm for radio frequency assignment problems

The radio frequency assignment problem is to minimize the number of frequencies used by transmitters with no interference in radio communication networks; it can be modeled as the minimum vertex coloring problem on unit disk graphs. In this paper, we consider the on-line first-fit algorithm for the problem and show that the competitive ratio of the algorithm for the unit disk graph G with χ(G)=2 is 3, where χ(G) is the chromatic number of G. Moreover, the competitive ratio of the algorithm for the unit disk graph G with χ(G)>2 is at least 4−3/χ(G). The average performance for the algorithm is also discussed in this paper.