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

Abstract

We address the induced matching enumeration problem. An edge set $M$ is an induced matching of a graph $G=(V,E)$. The enumeration of matchings are widely studied in literature, but the induced matching has not been paid much attention. A straightforward algorithm takes $O(|V|)$ time for each solution, that is coming from the time to generate a subproblem. We investigated local structures that enables us to generate subproblems in short time, and proved that the time complexity will be $O(1)$ if the input graph is $C_4$-free. A $C_4$-free graph is a graph any whose subgraph is not a cycle of length four. Finally, we show the fixed parameter tractability of counting induced matchings for graphs with bounded tree-width and planar graphs.

References in corpus (2)

• Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts
• A Graph-Theoretic Approach to Multitasking

Cited by in corpus (2)

• Constant Amortized Time Enumeration of Independent Sets for Graphs with Bounded Clique Number
• Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size