graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, an induced matching or strong matching is a subset of the edges of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

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 In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

). An induced matching can also be described as an independent set in the

square In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length a ...

of the

line graph In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...

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 In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blu ...

of the graph, the minimum number of matchings into which its edges can be partitioned. It equals the

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

of the square of the line graph.

Brooks' theorem In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with ...

, 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 In combinatorial mathematics and extremal graph theory, the Ruzsa–Szemerédi problem or (6,3)-problem asks for the maximum number of edges in a graph in which every edge belongs to a unique triangle. Equivalently it asks for the maximum number ...

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 graph In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be ...

s in which the neighborhood 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

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...

(and thus, finding an induced matching of maximum size is NP-hard). It can be solved in polynomial time in

chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...

s, because the squares of line graphs of chordal graphs are

perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfe ...

s. Moreover, it can be solved in linear time in

s . Unless an unexpected collapse in the

polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. ...

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 In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the soluti ...

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 In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...

. 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.

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 , 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 ''Algorithmica'' is a monthly peer-reviewed scientific journal focusing on research and the application of computer science algorithms. The journal was established in 1986 and is published by Springer Science+Business Media. The editor in chief is ...

, 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 , 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 , 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 = Discrete Applied Mathematics , 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