An O (n √ n log log n) average case algorithm for the maximum induced matching problem in permutation graphs

摘要

Let G = (V, E) be an undirected graph, where V is the vertex set and E is the edge set. A subset M of E is an induced matching of G if M is a matching of G and no two edges in M are joined by an edge. Finding a maximum induced matching is a NP-Hard problem on general graphs, even on bipartite graphs. However, this problem can be solved in polynomial time in some special graph classes such as weakly chordal, chordal, interval and circular-arc graphs. In this paper, we introduce a maximum induced matching algorithm in permutation graphs with O(|V |k(G) log log(|V|)) time in worst V case complexity and O(|V|√|V| log log(|V |)) time in average case complexity, where k(G) is the cardinality of the minimum clique cover set. The approach is to reduce the size of vertex set of L(G)^{2 without changing the cardinality of its maximum independent set. Our algorithm has better time complexity than the best known algorithm in both worst case and average case.}