Computational problems in graph theory | NP-complete problems

Maximum common induced subgraph

In graph theory and theoretical computer science, a maximum common induced subgraph of two graphs G and H is a graph that is an induced subgraph of both G and H,and that has as many vertices as possible. Finding this graph is NP-hard.In the associated decision problem, the input is two graphs G and H and a number k. The problem is to decide whether G and H have a common induced subgraph with at least k vertices. This problem is NP-complete. It is a generalization of the induced subgraph isomorphism problem, which arises when k equals the number of vertices in the smaller of G and H, so that this entire graph must appear as an induced subgraph of the other graph. Based on hardness of approximation results for the maximum independent set problem, the maximum common induced subgraph problem is also hard to approximate. This implies that, unless P = NP, there is no approximation algorithm that, in polynomial time on -vertex graphs, always finds a solution within a factor of of optimal, for any . One possible solution for this problem is to build a modular product graph of G and H.In this graph, the largest clique corresponds to a maximum common induced subgraph of G and H. Therefore, algorithms for finding maximum cliques can be used to find the maximum common induced subgraph. Moreover, a modified maximum-clique algorithm can be used to find a maximum common connected subgraph. The McSplit algorithm (along with its McSplit↓ variant) is a forward checking algorithm that does not use the clique encoding, but uses a compact data structure to keep track of the vertices in graph H to which each vertex in graph G may be mapped. Both versions of the McSplit algorithm outperform the clique encoding for many graph classes. Maximum common induced subgraph algorithms have a long tradition in cheminformatics and pharmacophore mapping. (Wikipedia).

Video thumbnail

The Greatest Common Factor

This video explains how to determine the GCF of integers and expressions. http://mathispower4u.wordpress.com/

From playlist Integers

Video thumbnail

Highest Common Factor & Lowest Common Multiple - GCSE Mathematics

How to find the highest common factor and lowest common multiple (hcf and lcm) of any two numbers using prime factors. ❤️ ❤️ ❤️ Support the channel ❤️ ❤️ ❤️ https://www.youtube.com/channel/UCf89Gd0FuNUdWv8FlSS7lqQ/join

From playlist Number

Video thumbnail

Using the TI84 to Help Factor Out the GCF of an Expression

This video explains how to use the TI84 to determine the GCF of 2 or 3 integers.

From playlist Determining the Greatest Common Factor and Factoring by Grouping

Video thumbnail

Ex 1: Identify GCF and Factor a Binomial

This video explains how to find the greatest common factor of a binomial and then how to factor the greatest common factor out of a binomial. Complete Video Listing: http://www.mathispower4u.com Search by Topic: http://www.mathispower4u.wordpress.com

From playlist Determining the Greatest Common Factor and Factoring by Grouping

Video thumbnail

Factor Trinomial with a GCF of the Leading Coefficient: 5x^3-85x^2+360x, 6x^4+78x^3+216x^2

This video explains how to factor a trinomial in the form ax^2+bx+c when a is a GCF. http://mathispower4u.com

From playlist Factoring Trinomials with a Leading Coefficient Not 1

Video thumbnail

Greatest Common Factors WITHOUT Listing Every Factor // Math Minute [#32] [ALGEBRA]

This video does exactly what it says on the tin. You can identify the GCF between any number of expressions *without* having to individually list off every factor of the expressions and then find the common factor that is, in some sense, the "greatest". Instead, prime factorize each expres

From playlist Math Minutes

Video thumbnail

Lecture 2: A structure theorem for rooted binary phylogenetic networks and its various applications

This video is one of the two introductory lectures (Introduction to Discrete Mathematical Biology) given by Momoko Hayamizu as part of an omnibus lecture series "Advanced Modern Mathematical Sciences 2" for undergraduate mathematics majors at Waseda University. In this lecture, she gives a

From playlist 2020 Advanced Topic in Modern Mathematical Sciences 2

Video thumbnail

Matchings, Perfect Matchings, Maximum Matchings, and More! | Independent Edge Sets, Graph Theory

What are matchings, perfect matchings, complete matchings, maximal matchings, maximum matchings, and independent edge sets in graph theory? We'll be answering that great number of questions in today's graph theory video lesson! A matching in a graph is a set of edges with no common end-ve

From playlist Graph Theory

Video thumbnail

Kent Quanrud: On Iterative Peeling and Supermodularity for Densest Subgraph

The densest subgraph problem in a graph (DSG), in the simplest form, is the following. Given an undirected graph G = (V,E) find a subset S ⊆ V of vertices that maximizes the ratio |E(S)|/|S| where E(S) is the set of edges with both endpoints in S. DSG and several of its variants are well-s

From playlist Workshop: Continuous approaches to discrete optimization

Video thumbnail

Ex 2: Identify GCF and Factor a Trinomial

This video explains how to find the greatest common factor of a trinomial and then how to factor the greatest common factor out of a trinomial. Complete Video Listing: http://www.mathispower4u.com Search by Topic: http://www.mathispower4u.wordpress.com

From playlist Determining the Greatest Common Factor and Factoring by Grouping

Video thumbnail

Graph Theory: 47. Subgraphs of Regular Graphs

Here I describe a construction technique used by Konig to prove that for every graph G of maximum degree r there exists an r-regular graph which contains G as an induced subgraph. I show how to use the construction with an example and discuss a related question. -- Bits of Graph Theory by

From playlist Graph Theory part-8

Video thumbnail

Dieter Rautenbach: Restricted types of matchings

Abstract: We present new results concerning restricted types of matchings such as uniquely restricted matchings and acyclic matchings, and we also consider the corresponding edge coloring notions. Our focus lies on bounds, exact and approximative algorithms. Furthermore, we discuss some ma

From playlist Combinatorics

Video thumbnail

Topics in Combinatorics lecture 15.0 --- Huang's solution to the sensitivity conjecture

The sensitivity conjecture was an important and long-standing conjecture in theoretical computer science that had been reduced to the following combinatorial question: let X be a set of 2^{n-1}+1 vertices in the n-dimensional Hamming cube {0,1}^n (where two sequences are joined by an edge

From playlist Topics in Combinatorics (Cambridge Part III course)

Video thumbnail

Factor by Grouping with GCF

This video provides two examples of how to factor by grouping when the original expression has a common factor. http://mathispower4u.com

From playlist Determining the Greatest Common Factor and Factoring by Grouping

Video thumbnail

Ex: Determine Factors and Greatest Common Factor Using a Fraction Wall or Rods

This video explains how to determine the factors and greatest common factor of two whole numbers using a fraction wall or rods. Site: http://mathispower4u.com

From playlist Factors, LCM, and GCF of Whole Numbers

Video thumbnail

Kernels, marriages, and the Dinitz problem #SoME2

The Dinitz problem is a graph theory problem proposed by Jeff Dinitz in 1979, and solved by Fred Galvin in 1994, 15 years later! In the video, I share the solution, along with some motivation that could have resulted in the solution. I hope you enjoy! I first heard of the problem in Diest

From playlist Summer of Math Exposition 2 videos

Video thumbnail

2. Forbidding a subgraph I: Mantel's theorem and Turán's theorem

MIT 18.217 Graph Theory and Additive Combinatorics, Fall 2019 Instructor: Yufei Zhao View the complete course: https://ocw.mit.edu/18-217F19 YouTube Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP62qauV_CpT1zKaGG_Vj5igX Which triangle-free graph has the maximum number of edges

From playlist MIT 18.217 Graph Theory and Additive Combinatorics, Fall 2019

Video thumbnail

What are Signed Graphs?

This video introduces signed graphs and signed graph theory. Signed graphs are graphs where the edges are given a positive or negative sign. They see applications in scheduling (signed graph coloring specifically), data science, social psychology, and more. In future videos we'll look at c

From playlist Summer of Math Exposition Youtube Videos

Video thumbnail

Factor the GCF out a Binomial (Common Core Math 7/8 Ex 3)

This video explains how to factor out the greatest common factor from a basic binomial. http://mathispower4u.com

From playlist Common Core Grade 7/8 Practice Standardized Test Math Problems

Video thumbnail

根付き二分系統ネットワークの構造定理と全域系統樹に関する色々な問題への応用

早稲田大学 基幹理工学部 応用数理学科2年生を対象とするオムニバス講義「応用数理概論」における早水の担当回(第25回・第26回)の授業動画です.履修者の方はWaseda Moodleを見たうえで,下記の再生リストにあるガイダンス動画と共にご視聴ください. ▷ 2020年度応用数理概論(第25回・第26回)の再生リスト https://youtube.com/playlist?list=PLCo60G1m_iboyOgcogs2JyXrhuQh1SZ43 ☆ 参考文献 ☆ ▷ この動画で解説した内容について連載記事を書かせていただいた雑誌 ‐『数学セミナー』2020年1月号

From playlist 2020 Advanced Topic in Modern Mathematical Sciences 2

Related pages

Approximation algorithm | Clique (graph theory) | Graph theory | Hardness of approximation | Induced subgraph | Look-ahead (backtracking) | Maximum common edge subgraph | Subgraph isomorphism problem | Theoretical computer science | Decision problem | Cheminformatics | Modular product of graphs | Molecule mining | Clique problem