Efficient Enumeration of Induced Matchings in a Graph without Cycles with Length Four

Kazuhiro KURITA  Kunihiro WASA  Takeaki UNO  Hiroki ARIMURA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.9   pp.1383-1391
Publication Date: 2018/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.1383
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
enumeration algorithm,  induced subgraph,  induced matching,  constant amortized time enumeration,  

Full Text: PDF(1.3MB)
>>Buy this Article


Summary: 
In this study, we address a problem pertaining to the induced matching enumeration. An edge set M is an induced matching of a graph G=(V,E). The enumeration of matchings has been widely studied in literature; however, there few studies on induced matching. A straightforward algorithm takes O2) time for each solution that is coming from the time to generate a subproblem, where Δ is the maximum degree in an input graph. To generate a subproblem, an algorithm picks up an edge e and generates two graphs, the one is obtained by removing e from G, the other is obtained by removing e, adjacent edge to e, and edges adjacent to adjacent edge of e. Since this operation needs O2) time, a straightforward algorithm enumerates all induced matchings in O2) time per solution. We investigated local structures that enable us to generate subproblems within a short time and proved that the time complexity will be O(1) if the input graph is C4-free. A graph is C4-free if and only if none of its subgraphs have a cycle of length four.