×

Induced matchings. (English) Zbl 0687.05033

An induced matching of a graph G is a vertex induced subgraph of G that is a matching. The author shows that the following decision problem is NP-complete: For a given bipartite graph G and positive integer k, is there an induced matching of size at least k?
So the problem of finding a largest induced matching for bipartite graphs is Np-hard. It is, however, shown that there is an efficient parallel algorithm for finding largest induced matchings in chordal graphs.
Reviewer: O.Oellermann

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C., Les problémes de colorations en théorie des graphs, (Publ. Inst. Statist., 9 (1960), University Paris), 123-160 · Zbl 0103.16201
[2] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[3] Buneman, P., A characterization of rigid circuit graphs, Discrete Math., 9, 205-212 (1974) · Zbl 0288.05128
[4] Dirac, G. A., On rigid circuit graphs, (Abh. Math. Sem., 25 (1961), University Hamburg), 71-76 · Zbl 0098.14703
[5] Farber, M., Applications of LP duality to problems involving independence and domination, (Ph.D. thesis (1981), Rutgers University)
[6] Farber, M., Characterizations of strongly chordal graphs, Discrete Math., 43, 173-189 (1983) · Zbl 0514.05048
[7] Frank, A., Some polynomial algorithms for certain graphs and hypergraphs, Proceeding 5th British Combin. Conf. (1976), Congressus Numerantium No. XV, Utilitas Math., Winnipeg · Zbl 0328.05141
[8] Fulkerson, D. R.; Gross, O. A., Incidence matrices and interval graphs, Pacific J. Math., 15, 835-855 (1965) · Zbl 0132.21001
[9] Garey, M. R.; Johnson, D. S., Computers and Intractibility: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA
[10] Gavril, F., lgorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Comput., 1, 180-187 (1972) · Zbl 0227.05116
[11] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory Ser. B, 16, 47-56 (1974) · Zbl 0266.05101
[12] Golumbie, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York
[13] Hajnal, A.; Surányi, J., Über die Auflösung von Graphen in vollständige Teilgraphen, (Sect. Math., 1 (1958), Ann. University Sci. Budapest. Eötvös), 113-121 · Zbl 0093.37801
[14] Hoffman, A. J.; Sakarovich, M.; Kolen, A., Totally balanced and greedy matrices, SIAM J. Algebraic and Discrete Methods, 6, 721-730 (1985) · Zbl 0573.05041
[15] Lekkerkerker, C. G.; Boland, J. Ch., Representations of a finite graph by a set of intervals on the real line, Fund. Math., 51, 45-64 (1962) · Zbl 0105.17501
[16] Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2, 253-267 (1972) · Zbl 0239.05111
[17] Lubiw, A., \(Г\)-free matrices, (Master’s thesis (1982), University of Waterloo)
[18] Naor, J.; Naor, M.; Schäffer, A. A., Fast parallel algorithms for chordal graphs, Proceedings 19th Annual ACM Symposium on Theory of Computing, 355-364 (1987)
[19] Walter, J. R., Representations of rigid cycle graphs, (Ph.D. thesis (1972), Wayne State University)
[20] Walter, J. R., Representations of chordal graphs as subtrees of a tree, J. Graph Theory, 2, 265-267 (1978) · Zbl 0441.05022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.