Maximum Induced Matchings for Chordal Graphs in Linear Time

The Maximum Induced Matching (MIM) Problem asks for a largest set of pairwise vertex-disjoint edges in a graph which are pairwise of distance at least two. It is well-known that the MIM problem is NP-complete even on particular bipartite graphs and on line graphs. On the other hand, it is solvable in polynomial time for various classes of graphs (such as chordal, weakly chordal, interval, circular-arc graphs and others) since the MIM problem on graph G corresponds to the Maximum Independent Set problem on the square G ^*=L(G)² of the line graph L(G) of G, and in some cases, G ^* is in the same graph class; for example, for chordal graphs G, G ^* is chordal. The construction of G ^*, however, requires time, where m is the number of edges in G. Is has been an open problem whether there is a linear-time algorithm for the MIM problem on chordal graphs. We give such an algorithm which is based on perfect elimination order and LexBFS.     

Counting the Number of Perfect Matchings in K5-Free Graphs

Counting the number of perfect matchings in graphs is a computationally hard problem. However, in the case of planar graphs, and even for K_3,3-free graphs, the number of perfect matchings can be computed efficiently. The technique to achieve this is to compute a Pfaffian orientation of a graph. In the case of K₅-free graphs, this technique will not work because some K₅-free graphs do not have a Pfaffian orientation. We circumvent this problem and show that the number of perfect matchings in K₅-free graphs can be computed in polynomial time. We also parallelize the sequential algorithm and show that the problem is in TC². We remark that our results generalize to graphs without singly-crossing minor.     

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.     

Linear Time Algorithms for Generalized Edge Dominating Set Problems

We prove that a generalization of the edge dominating set problem, in which each edge e needs to be covered b _e times for all e∈E, admits a linear time 2-approximation for general unweighted graphs and that it can be solved optimally for weighted trees. We show how to solve it optimally in linear time for unweighted trees and for weighted trees in which b _e ∈{0,1} for all e∈E. Moreover, we show that it solves generalizations of weighted matching, vertex cover, and edge cover in trees.     

Finding Maximum Induced Matchings in Subclasses of Claw-Free and <Emphasis Type="Italic">P</Emphasis><Subscript>5</Subscript>-Free Graphs,and in Graphs with Matching and Induced Matching of Equal Maximum Size

In a graph G a matching is a set of edges in which no two edges have a common endpoint. An induced matching is a matching in which no two edges are linked by an edge of G. The maximum induced matching (abbreviated MIM) problem is to find the maximum size of an induced matching for a given graph G. This problem is known to be NP-hard even on bipartite graphs or on planar graphs. We present a polynomial time algorithm which given a graph G either finds a maximum induced matching in G, or claims that the size of a maximum induced matching in G is strictly less than the size of a maximum matching in G. We show that the MIM problem is NP-hard on line-graphs, claw-free graphs, chair-free graphs, Hamiltonian graphs and r-regular graphs for r \geq 5. On the other hand, we present polynomial time algorithms for the MIM problem on (P ₅,D _m )-free graphs, on (bull, chair)-free graphs and on line-graphs of Hamiltonian graphs.     

Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width

Hierarchical decompositions of graphs are interesting for algorithmic purposes. There are several types of hierarchical decompositions. Tree decompositions are the best known ones. On graphs of tree-width at most k , i.e., that have tree decompositions of width at most k , where k is fixed, every decision or optimization problem expressible in monadic second-order logic has a linear algorithm. We prove that this is also the case for graphs of clique-width at most k , where this complexity measure is associated with hierarchical decompositions of another type, and where logical formulas are no longer allowed to use edge set quantifications. We develop applications to several classes of graphs that include cographs and are, like cographs, defined by forbidding subgraphs with ``too many' induced paths with four vertices. Received April 13, 1998, and in revised form June 22, 1999, and in final form August 20, 1999.     

Evaluating Network Reliability and 2-Edge-Connected Reliability in Linear Time for Bounded Pathwidth Graphs

This paper presents a decomposition method for computing the 2-edge-connected reliability of undirected networks. This reliability is defined as the probability that all the vertices of a given graph G are 2-edge-connected, when edges fail independently with known probabilities. The principle of this method was introduced by Rosenthal in 1977 [1]. For the all terminal reliability problem it consists in enumerating specific state classes of some subnetworks. These classes are represented by the partitions of the boundary sets. For the 2-edge-connected reliability problem these classes are represented by labeled forests whose nodes are the partition blocks and some ``unidentified' blocks. Our implementation uses a vertex linear ordering. The computational complexity depends on the number of classes, which depends on the vertex separation number of a given vertex linear ordering. Our computational results show the efficiency of this method when the vertex separation number is smaller than 7.     

A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs

Given a graph G=(V,E) and two vertices s,t ∈ V , s\neq t , the Menger problem is to find a maximum number of disjoint paths connecting s and t . Depending on whether the input graph is directed or not, and what kind of disjointness criterion is demanded, this general formulation is specialized to the directed or undirected vertex, and the edge or arc disjoint Menger problem, respectively. For planar graphs the edge disjoint Menger problem has been solved to optimality [W2], while the fastest algorithm for the arc disjoint version is Weihe's general maximum flow algorithm for planar networks [W1], which has running time \bf O (|V| log |V|) . Here we present a linear time, i.e., asymptotically optimal, algorithm for the arc disjoint version in planar directed graphs. Received August 1997; revised January 1999.     

任意图支配集精确算法回顾

该文综述了任意图支配集精确算法分析和设计的新进展.支配集问题是经典NP完全问题,很多问题都能与它相联系.我们针对最小支配集、最大独立集、最小独立支配集、最小连通支配集、最小加权支配集问题提供了详尽算法描述和实例说明,以使文章自包含方便阅读.文中还讨论了诸如分支简化策略、复杂度分析、测度分析、记忆等技术.自Claude Berge首次准确阐述现代图支配概念后,经过很长一段时期的沉寂,关于指数时间精确算法设计的研究热情在过去五年中显著增涨.除回顾这些最新成果之外,作者还盼望国内研究团体能更加重视这个快速发展的研究领域.     

An Exact Exponential Time Algorithm for Power Dominating Set

The Power Dominating Set problem is an extension of the well-known domination problem on graphs in a way that we enrich it by a second propagation rule: given a graph G(V,E), a set P?V is a power dominating set if every vertex is observed after the exhaustive application of the following two rules. First, a vertex is observed if v∈P or it has a neighbor in P. Secondly, if an observed vertex has exactly one unobserved neighbor u, then also u will be observed, as well. We show that Power Dominating Set remains $\mathcal{NP}$ -hard on cubic graphs. We design an algorithm solving this problem in time $\mathcal{O}^{*}(1.7548^{n})$ on general graphs, using polynomial space only. To achieve this, we introduce so-called reference search trees that can be seen as a compact representation of usual search trees, providing non-local pointers in order to indicate pruned subtrees.     

The Minimum Weight Dominating Set Problem for Permutation Graphs Is in NC

In this paper, we show that the problem of finding a minimum weight dominating set in a permutation graph, where a positive weight is assigned to each vertex, is in NC by presenting an O(log n) parallel algorithm with polynomially many processors on the CRCW model.     

Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces

Graphs are a flexible and general formalism providing rich models in various important domains, such as distributed computing, intelligent tutoring systems or social network analysis. In many cases, such models need to take changes in the graph structure into account, that is, changes in the number of nodes or in the graph connectivity. Predicting such changes within graphs can be expected to yield important insight with respect to the underlying dynamics, e.g. with respect to user behaviour. However, predictive techniques in the past have almost exclusively focused on single edges or nodes. In this contribution, we attempt to predict the future state of a graph as a whole. We propose to phrase time series prediction as a regression problem and apply dissimilarity- or kernel-based regression techniques, such as 1-nearest neighbor, kernel regression and Gaussian process regression, which can be applied to graphs via graph kernels. The output of the regression is a point embedded in a pseudo-Euclidean space, which can be analyzed using subsequent dissimilarity- or kernel-based processing methods. We discuss strategies to speed up Gaussian processes regression from cubic to linear time and evaluate our approach on two well-established theoretical models of graph evolution as well as two real data sets from the domain of intelligent tutoring systems. We find that simple regression methods, such as kernel regression, are sufficient to capture the dynamics in the theoretical models, but that Gaussian process regression significantly improves the prediction error for real-world data.     

3-Colouring AT-Free Graphs in Polynomial Time

Determining the complexity of the colouring problem on AT-free graphs is one of long-standing open problems in algorithmic graph theory. One of the reasons behind this is that AT-free graphs are not necessarily perfect unlike many popular subclasses of AT-free graphs such as interval graphs or co-comparability graphs. In this paper, we resolve the smallest open case of this problem, and present the first polynomial time algorithm for the 3-colouring problem on AT-free graphs.     

On the (Non-)Existence of Polynomial Kernels for P l -Free Edge Modification Problems

Given a graph G=(V,E) and a positive integer k, an edge modification problem for a graph property Π consists in deciding whether there exists a set F of pairs of V of size at most k such that the graph $H=(V,E\vartriangle F)$ satisfies the property Π. In the Π edge-completion problem, the set F is constrained to be disjoint from E; in the Π edge-deletion problem, F is a subset of E; no constraint is imposed on F in the Π edge-editing problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity (Cai in Inf. Process. Lett. 58:171–176, 1996; Fellows et al. in FCT, pp. 312–321, 2007; Heggernes et al. in STOC, pp. 374–381, 2007). When parameterized by the size k of the set F, it has been proved that if Π is a hereditary property characterized by a finite set of forbidden induced subgraphs, then the three Π edge-modification problems are FPT (Cai in Inf. Process. Lett. 58:171–176, 1996). It was then natural to ask (Bodlaender et al. in IWPEC, 2006) whether these problems also admit a polynomial kernel. in polynomial time to an equivalent instance (G′,k′) with size bounded by a polynomial in k). Using recent lower bound techniques, Kratsch and Wahlström answered this question negatively (Kratsch and Wahlström in IWPEC, pp. 264–275, 2009). However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. question to characterize for which type of graph properties, the parameterized edge-modification problems have polynomial kernels. Kratsch and Wahlström asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of P ₄-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that Parameterized cograph edge-modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the P _l -free edge-deletion and the C _l -free edge-deletion problems for l?7 and l≥4 respectively. Indeed, if they exist, then NP?coNP/poly.     

Linear Time Algorithms for Exact Distance Transform

In 2003, Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) published a paper describing an algorithm that computes the exact distance transform in linear time (with respect to image size) for the rectangular binary images in the k-dimensional space ℝ ^k and distance measured with respect to L _p -metric for 1≤p≤∞, which includes Euclidean distance L ₂. In this paper we discuss this algorithm from theoretical and practical points of view. On the practical side, we concentrate on its Euclidean distance version, discuss the possible ways of implementing it as signed distance transform, and experimentally compare implemented algorithms. We also describe the parallelization of these algorithms and discuss the computational time savings associated with them. All these implementations will be made available as a part of the CAVASS software system developed and maintained in our group (Grevera et al. in J. Digit. Imaging 20:101–118, 2007). On the theoretical side, we prove that our version of the signed distance transform algorithm, GBDT, returns the exact value of the distance from the geometrically defined object boundary. We provide a complete proof (which was not given of Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) that all these algorithms work correctly for L _p -metric with 1<p<∞. We also point out that the precise form of the algorithm from Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) is not well defined for L ₁ and L _∞ metrics. In addition, we show that the algorithm can be used to find, in linear time, the exact value of the diameter of an object, that is, the largest possible distance between any two of its elements.