Abstract
The Induced Graph Matching problem asks to find \(k\) disjoint induced subgraphs isomorphic to a given graph \(H\) in a given graph \(G\) such that there are no edges between vertices of different subgraphs. This problem generalizes the classical Independent Set and Induced Matching problems, among several other problems. We show that Induced Graph Matching is fixed-parameter tractable in \(k\) on claw-free graphs when \(H\) is a fixed connected graph, and even admits a polynomial kernel when \(H\) is a complete graph. Both results rely on a new, strong, and generic algorithmic structure theorem for claw-free graphs. Complementing the above positive results, we prove \(\mathsf {W}[1]\)-hardness of Induced Graph Matching on graphs excluding \(K_{1,4}\) as an induced subgraph, for any fixed complete graph \(H\). In particular, we show that Independent Set is \(\mathsf {W}[1]\)-hard on \(K_{1,4}\)-free graphs. Finally, we consider the complexity of Induced Graph Matching on a large subclass of claw-free graphs, namely on proper circular-arc graphs. We show that the problem is either polynomial-time solvable or \(\mathsf {NP}\)-complete, depending on the connectivity of \(H\) and the structure of \(G\).


Similar content being viewed by others
Notes
Observe that the reduction given here does not work in the case that \(H\) is a triangle, because the pre-image of a triangle is not unique. The triangle is also the only line graph for which the pre-image is not unique [43], which is why the reduction works for all other cases. We give a proof of the \(\mathsf {NP}\)-hardness of Induced Graph Matching for \(H = K_3\) in the Appendix.
We can explicitly prove this using the language of Sect. 4. Note that any co-bipartite graph is a thickening of a single semi-edge, a single vertex, or two independent vertices. Moreover, the graph consisting of a single semi-edge, a single vertex, or two independent vertices is a circular interval trigraph. Hence, using Lemma 1, we can see that any co-bipartite graph is a fuzzy circular-arc graph.
We note that the definition of isomorphism can be easily extended to hypergraphs.
References
Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)
Cameron, K., Hell, P.: Independent packings in structured graphs. Math. Program. 105(2–3), 201–213 (2006)
Chudnovsky, M., Ovetsky, A.: Coloring quasi-line graphs. J. Graph Theory 54(1), 41–50 (2007)
Chudnovsky, M., Seymour, P.D.: The structure of claw-free graphs. Surveys in Comb. 327, 153–171 (2005)
Chudnovsky, M., Seymour, P.D.: Claw-free graph. I. Orientable prismatic graphs. J. Comb. Theory Ser. B 97(6), 1373–1410 (2007)
Chudnovsky, M., Seymour, P.D.: Claw-free graph. II. Non-orientable prismatic graphs. J. Comb. Theory Ser. B 98(2), 249–290 (2008)
Chudnovsky, M., Seymour, P.D.: Claw-free graph. III. Circular interval graphs. J. Comb. Theory Ser. B 98(4), 812–834 (2008)
Chudnovsky, M., Seymour, P.D.: Claw-free graph. IV. Decomposition theorem. J. Comb. Theory Ser. B 98(5), 839–938 (2008)
Chudnovsky, M., Seymour, P.D.: Claw-free graph. V. Global structure. J. Comb. Theory Ser. B 98(6), 1373–1410 (2008)
Chudnovsky, M., Seymour, P.D.: Claw-free graph. VI. Coloring. J. Comb. Theory Ser. B 100(6), 560–572 (2010)
Chudnovsky, M., Seymour, P.D.: Claw-free graph. VII. Quasi-line graphs. J. Comb. Theory Ser. B 102(6), 1267–1294 (2012)
Cygan, M., Philip, G., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Dominating set is fixed parameter tractable in claw-free graphs. Theor. Comput. Sci. 412(50), 6982–7000 (2011)
Damaschke, P.: Induced subgraph isomorphism for cographs is \({\sf NP}\)-complete. In: Graph-Theoretic Concepts in Computer Science (WG 1990), Lecture Notes in Computer Science, vol. 484, pp. 72–78 (1991)
Dell, H., Marx, D.: Kernelization of packing problems. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 68–81 (2012)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Faenza, Y., Oriolo, G., Stauffer, G.: An algorithmic decomposition of claw-free graphs leading to an \(O(n^3)\)-algorithm for the weighted stable set problem. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 630–646 (2011)
Faudree, R.J., Flandrin, E., Ryjácek, Z.: Claw-free graphs: a survey. Discret. Math. 164(1–3), 87–147 (1997)
Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53–61 (2009)
Fellows, M.R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F.A., Stege, U., Thilikos, D.M., Whitesides, S.: Faster fixed-parameter tractable algorithms for matching and packing problems. Algorithmica 52(2), 167–176 (2008)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of \({\sf NP}\)-Completeness. Freeman, San Francisco (1979)
Golovach, P., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in AT-free graphs. In: Algorithm Theory (SWAT 2012), Lecture Notes in Computer Science, vol. 7357, pp. 153–164 (2012)
Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in claw-free graphs. In: Algorithms (ESA 2012), Lecture Notes in Computer Science, vol. 7501, pp. 515–526 (2012)
Habib, M., McConnell, R., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234, 59–84 (2000)
Heggernes, P., van, ’t Hof, P., Meister, D., Villanger, Y.: The induced subgraph isomorphism problem on proper interval graphs and bipartite permutation graphs. Preprint (2012).
Heggernes, P., Meister, D., Villanger, Y.: Induced subgraph isomorphism on interval and proper interval graphs. In: Algorithms and Computation (ISAAC 2010), Lecture Notes in Computer Science, vol. 6507, pp. 399–409 (2010)
Hermelin, D., Mnich, M., van Leeuwen, E.J.: Parameterized complexity of induced \(H\)-matching in claw-free graphs. In: Algorithms (ESA 2012), Lecture Notes in Computer Science, vol. 7501, pp. 624–635 (2012)
Hermelin, D., Mnich, M., van Leeuwen, E.J., Woeginger, G.J.: Domination when the stars are out. In: Automata, Languages and Programming (ICALP 2011), Lecture Notes in Computer Science, vol. 6755, pp. 462–473 (2011)
Hermelin, D., Wu, X.: Weak compositions and their applications to polynomial lower bounds for kernelization. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 104–113 (2012)
King, A.D., Reed, B.A.: Bounding \(\chi \) in terms of \(\omega \) and \(\Delta \) for quasi-line graphs. J. Graph Theory 59(3), 215–228 (2008)
Kirkpatrick, D., Hell, P.: On the complexity of general graph factor problems. SIAM J. Comput. 12(3), 601–609 (1983)
Kneis, J., Mölle, D., Richter, S., Rossmanith, P.: Divide-and-color. In: Graph-Theoretic Concepts in Computer Science (WG 2006), Lecture Notes in Computer Science, vol. 4271, pp. 58–67 (2006).
Kobler, D., Rotics, U.: Finding maximum induced matchings in subclasses of claw-free and \(P_{5}\)-free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica 37(4), 327–346 (2003)
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L.: Normal Helly circular-arc graphs and its subclasses. Discret. Appl. Math. 161(7–8), 1037–1059 (2013)
Maier, D., Storer, J.A.: A note on the complexity of the superstring problem. Technical Report 233, Computer Science Laboratory, Princeton University (1977).
Marx, D.: Efficient approximation schemes for geometric problems? In: Algorithms (ESA 2005), Lecture Notes in Computer Science, vol. 3669, pp. 448–459 (2005)
McKee, T.A.: Restricted circular-arc graphs and clique cycles. Discret. Math. 263(1–3), 221–231 (2003)
Moser, H.: A problem kernelization for graph packing. In: Theory and Practice of Computer Science (SOFSEM 2009), Lecture Notes in Computer Science, vol. 5404, pp. 401–412 (2009)
Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. J. Discret. Algorithms 7(2), 181–190 (2009)
Oriolo, G., Pietropaoli, U., Stauffer, G.: On the recognition of fuzzy circular interval graphs. Discret. Math. 312(8), 1426–1435 (2012)
Prieto, E., Sloper, C.: Looking at the stars. Theor. Comput. Sci. 351(3), 437–445 (2006)
Roussopoulos, N.: A \(\max \{m, n\}\) algorithm for determining the graph \(H\) from its line graph \(G\). Inf. Process. Lett. 2(4), 108–112 (1973)
Spinrad, J.R.: Efficient graph representations, Field Institute Monographs, vol. 19, American Mathematical Society (2003)
Whitney, H.: Congruent graphs and the connectivity of graphs. American J. Math. 54, 150–168 (1932)
Acknowledgments
We thank the anonymous reviewers for helpful remarks improving the presentation of this manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
An extended abstract of the results in this paper have appeared in the Proceedings of 20th European Symposium on Algorithms (ESA 2012) [26]. Partially supported by ERC StG project PAAl No. 259515. The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007–2013) under REA grant agreement No. 631163.11.
Appendix: Induced Graph Matching for Triangles is \(\mathsf {NP}\)-hard on Line Graphs
Appendix: Induced Graph Matching for Triangles is \(\mathsf {NP}\)-hard on Line Graphs
Recall from the introduction that the immediate correspondence between an \(H\)-matching in a graph \(G\) and an induced \(L(H)\)-matching in \(L(G)\) does not apply in case \(L(H)\) is a triangle, i.e. in case that \(H\) is \(K_{3}\) or \(K_{1,3}\). Hence, to the best of our knowledge, the complexity of Induced Graph Matching for \(H = K_3\) (also known as Induced Triangle Matching or Induced Triangle Packing) on line graphs is open.
In this section, we prove that Induced Graph Matching for \(H = K_3\) on line graphs is \(\mathsf {NP}\)-hard.
Theorem 15
Induced Graph Matching for \(H = K_3\) is \(\mathsf {NP}\)-complete on line graphs of planar graphs.
Proof
It is clear that Induced Graph Matching for \(H = K_3\) on line graphs of planar graphs belongs to \(\mathsf {NP}\). To prove \(\mathsf {NP}\)-hardness, we reduce from Independent Set on planar graphs where each vertex has degree exactly three, which is known to be \(\mathsf {NP}\)-complete [34]. Let \((G,k)\) be an instance of this problem. We transform this to an instance of Induced Graph Matching with \(H = K_{3}\) as follows. First, we subdivide each edge of \(G\). That is, we (simultaneously) remove each edge \(e = \{u,v\}\) and add a new vertex \(x_{e}\) and new edges \(\{u,x_{e}\}\) and \(\{x_{e},v\}\). Denote the resulting graph by \(G'\). Then the instance of Induced Graph Matching is \((L(G'), K_{3}, k)\), where \(L(G')\) is the line graph of \(G'\). Note that \(G'\) is planar, and thus \(L(G')\) is the line graph of a planar graph.
Observe that any induced subgraph in \(L(G')\) that is isomorphic to \(K_{3}\) corresponds to three edges of \(G'\) that are incident on the same vertex. Armed with this observation, we show that \((L(G'), K_{3}, k')\) is a “yes”-instance of Induced Graph Matching if and only if \((G,k)\) is a “yes”-instance of Independent Set, thus completing the proof.
Suppose that \((G,k)\) is a “yes”-instance of Independent Set. Let \(I\) be an independent set of \(G\) of size \(k\). For each \(v \in I\), consider the three edges of \(G'\) that are incident on \(v\). These correspond to a triangle in \(L(G')\). Let \(M\) be the set of these triangles for all vertices in \(I\). Note that \(|M| = k\). By the above observation, no two triangles in \(L(G')\) have a vertex in common. Moreover, since \(I\) is independent, no two triangles in \(M\) are adjacent. Therefore, \((L(G'), K_{3}, k)\) is a “yes”-instance of Induced Graph Matching.
Suppose that \((L(G'), K_{3}, k)\) is a “yes”-instance of Induced Graph Matching. Let \(M\) be an induced \(K_{3}\)-matching in \(L(G')\) of size \(k\). By the above observation, no two triangles in \(L(G')\) have a vertex in common, and by construction each triangle corresponds to some vertex \(v\) that is both in \(G\) and \(G'\). Let \(I\) be the set of vertices that correspond to the triangles of \(M\). Since \(M\) cannot contain triangles that correspond to adjacent vertices in \(G\), \(I\) is an independent set. As \(|I|=|M|=k\), \((G,k)\) is a “yes”-instance of Independent Set. \(\square \)
Rights and permissions
About this article
Cite this article
Hermelin, D., Mnich, M. & van Leeuwen, E.J. Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs. Algorithmica 70, 513–560 (2014). https://doi.org/10.1007/s00453-014-9877-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-014-9877-5