In graph theory, an induced matching or strong matching is a subset of the edges of an undirected graph that do not share any vertices (it is a matching) and includes every edge connecting any two vertices in the subset (it is an induced subgraph). An induced matching can also be described as an independent set in the square of the line graph of the given graph.

Strong coloring and neighborhoods

The minimum number of induced matchings into which the edges of a graph can be partitioned is called its ''strong chromatic index'', by analogy with the chromatic index of the graph, the minimum number of matchings into which its edges can be partitioned. It equals the chromatic number of the square of the line graph. Brooks' theorem, applied to the square of the line graph, shows that the strong chromatic index is at most quadratic in the maximum degree of the given graph, but better constant factors in the quadratic bound can be obtained by other methods. The Ruzsa–Szemerédi problem concerns the edge density of balanced bipartite graphs with linear strong chromatic index. Equivalently, it concerns the density of a different class of graphs, the locally linear graphs in which the

neighborhood A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural area, ...

of every vertex is an induced matching. Neither of these types of graph can have a quadratic number of edges, but constructions are known for graphs of this type with nearly-quadratic numbers of edges.

Computational complexity

Finding an induced matching of size at least

k

is NP-complete (and thus, finding an induced matching of maximum size is

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

). It can be solved in polynomial time in chordal graphs, because the squares of line graphs of chordal graphs are perfect graphs. Moreover, it can be solved in linear time in chordal graphs . Unless an unexpected collapse in the polynomial hierarchy occurs, the largest induced matching cannot be approximated to within any

n^

approximation ratio An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...

in polynomial time. The problem is also W hard, meaning that even finding a small induced matching of a given size

k

is unlikely to have an algorithm significantly faster than the brute force search approach of trying all

k

-tuples of edges. However, the problem of finding

k

vertices whose removal leaves an induced matching is fixed-parameter tractable. The problem can also be solved exactly on

n

-vertex graphs in time

O(1.3752^n)

with exponential space, or in time

O(1.4231^n)

with

polynomial space In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...

References

{{reflist, refs= {{citation , last1 = Brandstaedt , first = Andreas , last2 = Hoang , first2 = Chinh , doi = 10.1007/s00453-007-9045-2 , issue = 1–3 , journal =

Discrete Applied Mathematics ''Discrete Applied Mathematics'' is a peer-reviewed scientific journal covering algorithmic and applied areas of discrete mathematics. It is published by Elsevier and the editor-in-chief is Endre Boros (Rutgers University). The journal was split ...

, mr = , pages = 97–102 , title = Induced matchings , volume = 24 , year = 1989 {{citation , last = Cameron , first = Kathie , department = Special issue for First Montreal Conference on Combinatorics and Computer Science, 1987 , doi = 10.1016/0166-218X(92)90275-F , journal = Algorithmica , mr = 1011265 , pages = 440–447 , title = Maximum Induced Matchings for Chordal Graphs in Linear Time , volume = 52 , year = 2008, doi-access = free {{citation , last = Cameron , first = Kathie , doi = 10.1016/j.disc.2003.05.001 , issue = 1–3 , journal =

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

, mr = 2035386 , pages = 1–9 , title = Induced matchings in intersection graphs , volume = 278 , year = 2004, doi-access = free {{citation , last1 = Chalermsook , first1 = Parinya , last2 = Laekhanukit , first2 = Bundit , last3 = Nanongkai , first3 = Danupon , contribution = Graph products revisited: tight approximation hardness of induced matching, poset dimension and more , mr = 3202998 , pages = 1557–1576 , publisher = SIAM , location = Philadelphia, Pennsylvania , title = Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms , year = 2012 {{citation , last = Fronček , first = Dalibor , issue = 1 , journal = Mathematica Slovaca , mr = 1016323 , pages = 3–6 , title = Locally linear graphs , volume = 39 , year = 1989, hdl = 10338.dmlcz/136481 {{citation , last1 = Fouquet , first1 = J.-L. , last2 = Jolivet , first2 = J.-L. , issue = A , journal = Ars Combinatoria , mr = 737086 , pages = 141–150 , title = Strong edge-colorings of graphs and applications to multi-{{mvar, k-gons , volume = 16 , year = 1983 {{citation , last1 = Molloy , first1 = Michael , last2 = Reed , first2 = Bruce , author2-link = Bruce Reed (mathematician) , doi = 10.1006/jctb.1997.1724 , issue = 2 , journal =

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, mr = 1438613 , pages = 103–109 , series = Series B , title = A bound on the strong chromatic index of a graph , volume = 69 , year = 1997, hdl = 1807/9474 , hdl-access = free {{citation , last1 = Moser , first1 = Hannes , last2 = Sikdar , first2 = Somnath , doi = 10.1016/j.dam.2008.07.011 , issue = 4 , journal =

, mr = 2499485 , pages = 715–727 , title = The parameterized complexity of the induced matching problem , volume = 157 , year = 2009, doi-access = free {{citation , last1 = Ruzsa , first1 = I. Z. , author1-link = Imre Z. Ruzsa , last2 = Szemerédi , first2 = E. , author2-link = Endre Szemerédi , contribution = Triple systems with no six points carrying three triangles , mr = 519318 , pages = 939–945 , publisher = North-Holland , location = Amsterdam and New York , series = Colloq. Math. Soc. János Bolyai , title = Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II , volume = 18 , year = 1978 {{citation , last1 = Xiao , first1 = Mingyu , last2 = Kou , first2 = Shaowei , editor-last = Heggernes , editor-first = Pinar , editor-link = Pinar Heggernes , contribution = Almost induced matching: linear kernels and parameterized algorithms , doi = 10.1007/978-3-662-53536-3_19 , location = Berlin , mr = 3593958 , pages = 220–232 , publisher = Springer , series = Lecture Notes in Computer Science , title = Graph-Theoretic Concepts in Computer Science: 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22–24, 2016, Revised Selected Papers , volume = 9941 , year = 2016 {{citation , last1 = Xiao , first1 = Mingyu , last2 = Tan , first2 = Huan , doi = 10.1016/j.ic.2017.07.006 , journal = Information and Computation , mr = 3705425 , pages = 196–211 , title = Exact algorithms for maximum induced matching , volume = 256 , year = 2017, doi-access = free Graph theory objects Matching (graph theory)

Strong coloring and neighborhoods

Computational complexity

See also

References