Induced matching

Last updated

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 these are the only edges connecting any two vertices which are endpoints of the matching edges (it is an induced subgraph).

Contents

An induced matching can also be described as an independent set in the square of the line graph of the given graph. [1]

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. [2] 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. [3]

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 of every vertex is an induced matching. [4] 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. [5]

Computational complexity

Finding an induced matching of size at least is NP-complete (and thus, finding an induced matching of maximum size is NP-hard). It can be solved in polynomial time in chordal graphs, because the squares of line graphs of chordal graphs are perfect graphs. [6] Moreover, it can be solved in linear time in chordal graphs [7] . Unless an unexpected collapse in the polynomial hierarchy occurs, the largest induced matching cannot be approximated to within any approximation ratio in polynomial time. [8]

The problem is also W[1]-hard, meaning that even finding a small induced matching of a given size is unlikely to have an algorithm significantly faster than the brute force search approach of trying all -tuples of edges. [9] However, the problem of finding vertices whose removal leaves an induced matching is fixed-parameter tractable. [10] The problem can also be solved exactly on -vertex graphs in time with exponential space, or in time with polynomial space. [11]

See also

Related Research Articles

<span class="mw-page-title-main">Component (graph theory)</span> Maximal subgraph whose vertices can reach each other

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components.

<span class="mw-page-title-main">Graph coloring</span> Methodic assignment of colors to elements of a graph

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 a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper 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, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

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 cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs: a chordal completion of a graph is typically called a triangulation of that graph.

<span class="mw-page-title-main">Circle graph</span> Intersection graph of a chord diagram

In graph theory, a circle graph is the intersection graph of a chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.

<span class="mw-page-title-main">Graph property</span> Property of graphs that depends only on abstract structure

In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.

<span class="mw-page-title-main">Grundy number</span> Maximum number of colors obtainable by a greedy graph coloring algorithm

In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by Christen & Selkow (1979).

<span class="mw-page-title-main">Unit distance graph</span> Geometric graph with unit edge lengths

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

<span class="mw-page-title-main">Neighbourhood (graph theory)</span> Subgraph made of all nodes linked to a given node of a graph

In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The neighbourhood of a vertex v in a graph G is the subgraph of G induced by all vertices adjacent to v, i.e., the graph composed of the vertices adjacent to v and all edges connecting vertices adjacent to v.

<span class="mw-page-title-main">Triangle-free graph</span> Graph without triples of adjacent vertices

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

<span class="mw-page-title-main">Claw-free graph</span> Graph without four-vertex star subgraphs

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

<span class="mw-page-title-main">Greedy coloring</span> One-by-one assignment of colors to graph vertices

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

<span class="mw-page-title-main">Clebsch graph</span> One of two different regular graphs with 16 vertices

In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is the dimension-5 halved cube graph; it was called the Clebsch graph name by Seidel (1968) because of its relation to the configuration of 16 lines on the quartic surface discovered in 1868 by the German mathematician Alfred Clebsch. The 40-edge variant is the dimension-5 folded cube graph; it is also known as the Greenwood–Gleason graph after the work of Robert E. Greenwood and Andrew M. Gleason, who used it to evaluate the Ramsey number R(3,3,3) = 17.

<span class="mw-page-title-main">Degeneracy (graph theory)</span> Measurement of graph sparsity

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

In graph theory, the graph removal lemma states that when a graph contains few copies of a given subgraph, then all of the copies can be eliminated by removing a small number of edges. The special case in which the subgraph is a triangle is known as the triangle removal lemma.

<span class="mw-page-title-main">Ruzsa–Szemerédi problem</span>

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 of edges in a balanced bipartite graph whose edges can be partitioned into a linear number of induced matchings, or the maximum number of triples one can choose from points so that every six points contain at most two triples. The problem is named after Imre Z. Ruzsa and Endre Szemerédi, who first proved that its answer is smaller than by a slowly-growing factor.

<span class="mw-page-title-main">Locally linear graph</span> Graph where every edge is in one triangle

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 paired up into an induced matching. Locally linear graphs have also been called locally matched graphs. Their triangles form the hyperedges of triangle-free 3-uniform linear hypergraphs and the blocks of certain partial Steiner triple systems, and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems.

References

  1. Cameron, Kathie (2004), "Induced matchings in intersection graphs", Discrete Mathematics , 278 (1–3): 1–9, doi: 10.1016/j.disc.2003.05.001 , MR   2035386
  2. Fouquet, J.-L.; Jolivet, J.-L. (1983), "Strong edge-colorings of graphs and applications to multi-k-gons", Ars Combinatoria, 16 (A): 141–150, MR   0737086
  3. Molloy, Michael; Reed, Bruce (1997), "A bound on the strong chromatic index of a graph", Journal of Combinatorial Theory , Series B, 69 (2): 103–109, doi:10.1006/jctb.1997.1724, hdl: 1807/9474 , MR   1438613
  4. Fronček, Dalibor (1989), "Locally linear graphs", Mathematica Slovaca, 39 (1): 3–6, hdl:10338.dmlcz/136481, MR   1016323
  5. Ruzsa, I. Z.; Szemerédi, E. (1978), "Triple systems with no six points carrying three triangles", Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai, vol. 18, Amsterdam and New York: North-Holland, pp. 939–945, MR   0519318
  6. Cameron, Kathie (2008), "Maximum Induced Matchings for Chordal Graphs in Linear Time", Special issue for First Montreal Conference on Combinatorics and Computer Science, 1987, Algorithmica , 52: 440–447, doi: 10.1016/0166-218X(92)90275-F , MR   1011265
  7. Brandstaedt, Andreas; Hoang, Chinh (1989), "Induced matchings", Discrete Applied Mathematics , 24 (1–3): 97–102, doi:10.1007/s00453-007-9045-2
  8. Chalermsook, Parinya; Laekhanukit, Bundit; Nanongkai, Danupon (2012), "Graph products revisited: tight approximation hardness of induced matching, poset dimension and more", Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, Pennsylvania: SIAM, pp. 1557–1576, MR   3202998
  9. Moser, Hannes; Sikdar, Somnath (2009), "The parameterized complexity of the induced matching problem", Discrete Applied Mathematics , 157 (4): 715–727, doi: 10.1016/j.dam.2008.07.011 , MR   2499485
  10. Xiao, Mingyu; Kou, Shaowei (2016), "Almost induced matching: linear kernels and parameterized algorithms", in Heggernes, Pinar (ed.), Graph-Theoretic Concepts in Computer Science: 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22–24, 2016, Revised Selected Papers, Lecture Notes in Computer Science, vol. 9941, Berlin: Springer, pp. 220–232, doi:10.1007/978-3-662-53536-3_19, ISBN   978-3-662-53535-6, MR   3593958
  11. Xiao, Mingyu; Tan, Huan (2017), "Exact algorithms for maximum induced matching", Information and Computation, 256: 196–211, doi: 10.1016/j.ic.2017.07.006 , MR   3705425