Color-coding - Revision history

David Eppstein: Undid revision 1257998436 by Pateldarshak10 (talk) a summary of the main idea is not an application

2024-11-17T17:58:32Z

Undid revision 1257998436 by Pateldarshak10 (talk) a summary of the main idea is not an application

← Previous revision		Revision as of 17:58, 17 November 2024
Line 49:		Line 49:
	Due to the huge amount of gene data that can be collected, searching for pathways or motifs can be highly time consuming. However, by exploiting the color-coding method, the motifs or signaling pathways with <math>k=O(\log n)</math> vertices in a network {{mvar\|G}} with {{mvar\|n}} vertices can be found very efficiently in polynomial time. Thus, this enables us to explore more complex or larger structures in PPI networks.		Due to the huge amount of gene data that can be collected, searching for pathways or motifs can be highly time consuming. However, by exploiting the color-coding method, the motifs or signaling pathways with <math>k=O(\log n)</math> vertices in a network {{mvar\|G}} with {{mvar\|n}} vertices can be found very efficiently in polynomial time. Thus, this enables us to explore more complex or larger structures in PPI networks.

	Color coding provides an efficient randomized approximation approach for solving subgraph isomorphism problems, where the goal is to determine if a smaller graph is present as a subgraph in a larger graph. The random coloring is also applied in finding cycles in minor-closed families of graphs. <ref name="orig">Alon, N., Yuster, R., and Zwick, U. 1995. Color-coding. J. ACM 42, 4 (Jul. 1995), 844–856. DOI= http://doi.acm.org/10.1145/210332.210337</ref>
	==Further reading==		==Further reading==

Pateldarshak10: I have added citation for my edits on application of Random Coloring.

2024-11-17T16:34:02Z

I have added citation for my edits on application of Random Coloring.

← Previous revision		Revision as of 16:34, 17 November 2024
Line 49:		Line 49:
	Due to the huge amount of gene data that can be collected, searching for pathways or motifs can be highly time consuming. However, by exploiting the color-coding method, the motifs or signaling pathways with <math>k=O(\log n)</math> vertices in a network {{mvar\|G}} with {{mvar\|n}} vertices can be found very efficiently in polynomial time. Thus, this enables us to explore more complex or larger structures in PPI networks.		Due to the huge amount of gene data that can be collected, searching for pathways or motifs can be highly time consuming. However, by exploiting the color-coding method, the motifs or signaling pathways with <math>k=O(\log n)</math> vertices in a network {{mvar\|G}} with {{mvar\|n}} vertices can be found very efficiently in polynomial time. Thus, this enables us to explore more complex or larger structures in PPI networks.

			Color coding provides an efficient randomized approximation approach for solving subgraph isomorphism problems, where the goal is to determine if a smaller graph is present as a subgraph in a larger graph. The random coloring is also applied in finding cycles in minor-closed families of graphs. <ref name="orig">Alon, N., Yuster, R., and Zwick, U. 1995. Color-coding. J. ACM 42, 4 (Jul. 1995), 844–856. DOI= http://doi.acm.org/10.1145/210332.210337</ref>
	==Further reading==		==Further reading==

Notcharizard: Restored revision 1250833346 by JJMC89 bot III (talk): No citation

2024-11-17T16:12:47Z

Restored revision 1250833346 by JJMC89 bot III (talk): No citation

← Previous revision		Revision as of 16:12, 17 November 2024
Line 48:		Line 48:

	Due to the huge amount of gene data that can be collected, searching for pathways or motifs can be highly time consuming. However, by exploiting the color-coding method, the motifs or signaling pathways with <math>k=O(\log n)</math> vertices in a network {{mvar\|G}} with {{mvar\|n}} vertices can be found very efficiently in polynomial time. Thus, this enables us to explore more complex or larger structures in PPI networks.		Due to the huge amount of gene data that can be collected, searching for pathways or motifs can be highly time consuming. However, by exploiting the color-coding method, the motifs or signaling pathways with <math>k=O(\log n)</math> vertices in a network {{mvar\|G}} with {{mvar\|n}} vertices can be found very efficiently in polynomial time. Thus, this enables us to explore more complex or larger structures in PPI networks.

	Color coding provides an efficient randomized approximation approach for solving subgraph isomorphism problems, where the goal is to determine if a smaller graph is present as a subgraph in a larger graph. The random coloring is also applied in finding cycles in minor-closed families of graphs.

	==Further reading==		==Further reading==

Pateldarshak10: I have added application based on Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844–856, 1995

2024-11-17T16:11:03Z

I have added application based on Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844–856, 1995

← Previous revision		Revision as of 16:11, 17 November 2024
Line 48:		Line 48:

	Due to the huge amount of gene data that can be collected, searching for pathways or motifs can be highly time consuming. However, by exploiting the color-coding method, the motifs or signaling pathways with <math>k=O(\log n)</math> vertices in a network {{mvar\|G}} with {{mvar\|n}} vertices can be found very efficiently in polynomial time. Thus, this enables us to explore more complex or larger structures in PPI networks.		Due to the huge amount of gene data that can be collected, searching for pathways or motifs can be highly time consuming. However, by exploiting the color-coding method, the motifs or signaling pathways with <math>k=O(\log n)</math> vertices in a network {{mvar\|G}} with {{mvar\|n}} vertices can be found very efficiently in polynomial time. Thus, this enables us to explore more complex or larger structures in PPI networks.

			Color coding provides an efficient randomized approximation approach for solving subgraph isomorphism problems, where the goal is to determine if a smaller graph is present as a subgraph in a larger graph. The random coloring is also applied in finding cycles in minor-closed families of graphs.

	==Further reading==		==Further reading==

JJMC89 bot III: Moving :Category:Algorithms in graph theory to :Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

2024-10-12T19:54:51Z

Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

← Previous revision		Revision as of 19:54, 12 October 2024
Line 58:		Line 58:

	{{DEFAULTSORT:Color-Coding}}		{{DEFAULTSORT:Color-Coding}}
	[[Category:~~Algorithms~~ ~~in graph theory~~]]		[[Category:Graph algorithms]]

JJMC89 bot III: Moving :Category:Graph algorithms to :Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

2024-10-12T02:22:05Z

Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

← Previous revision		Revision as of 02:22, 12 October 2024
Line 58:		Line 58:

	{{DEFAULTSORT:Color-Coding}}		{{DEFAULTSORT:Color-Coding}}
	[[Category:~~Graph~~ ~~algorithms~~]]		[[Category:Algorithms in graph theory]]

CHHC(dec): correct the format

2023-12-01T16:31:57Z

correct the format

← Previous revision		Revision as of 16:31, 1 December 2023
Line 29:		Line 29:
	By applying random coloring method, each simple cycle has a probability of <math>k!/k^k > e^{-k}</math> to become colorful, since there are <math>k^k</math> ways of coloring the {{mvar\|k}} vertices on the cycle, among which there are <math>k!</math> colorful occurrences. Then an algorithm (described next) can be used to find colorful cycles in the randomly colored graph {{mvar\|G}} in time <math>O(V^\omega)</math>, where <math>\omega</math> is the matrix multiplication constant. Therefore, it takes <math>e^k\cdot O(V^\omega)</math> overall time to find a simple cycle of length {{mvar\|k}} in {{mvar\|G}}.		By applying random coloring method, each simple cycle has a probability of <math>k!/k^k > e^{-k}</math> to become colorful, since there are <math>k^k</math> ways of coloring the {{mvar\|k}} vertices on the cycle, among which there are <math>k!</math> colorful occurrences. Then an algorithm (described next) can be used to find colorful cycles in the randomly colored graph {{mvar\|G}} in time <math>O(V^\omega)</math>, where <math>\omega</math> is the matrix multiplication constant. Therefore, it takes <math>e^k\cdot O(V^\omega)</math> overall time to find a simple cycle of length {{mvar\|k}} in {{mvar\|G}}.

	The colorful cycle-finding algorithm works by first finding all pairs of vertices in {{mvar\|V}} that are connected by a simple path of length {{math\|''k'' − 1}}, and then checking whether the two vertices in each pair are connected. Given a coloring function {{math\|''c'' : ''V'' → {1, ..., ''k''} }} to color graph {{mvar\|G}}, enumerate all partitions of the color set {{math\|{1, ..., ''k''} }} into two subsets {{math\|''C''<sub>1</sub>, ''C''<sub>2</sub>}} of size <math>k/2</math> each. Note that {{mvar\|V}} can be divided into {{math\|''V''<sub>1</sub>}} and {{math\|''V''<sub>2</sub>}} accordingly, and let {{math\|''G''<sub>1</sub>}} and {{math\|''G''<sub>2</sub>}} denote the subgraphs induced by {{math\|''V''<sub>1</sub>}} and {{math\|''V''<sub>2</sub>}} respectively. Then, recursively find colorful paths of length <math>k/2 - 1</math> in each of {{math\|''G''<sub>1</sub>}} and {{math\|''G''<sub>2</sub>}}. Suppose the boolean matrix {{math\|''A''<sub>1</sub>}} and {{math\|''A''<sub>2</sub>}} represent the connectivity of each pair of vertices in {{math\|''G''<sub>1</sub>}} and {{math\|''G''<sub>2</sub>}} by a colorful path, respectively, and let {{mvar\|B}} be the matrix describing the adjacency relations between vertices of {{math\|''V''<sub>1</sub>}} and those of {{math\|''V''<sub>2</sub>}}, the boolean product <math>A_1BA_2</math> gives all pairs of vertices in {{mvar\|V}} that are connected by a colorful path of length {{math\|''k'' − 1}}. Thus, the recursive relation of matrix multiplications is <math>t(k) \le 2^k\cdot t(k/2)</math>, which yields a runtime of <math>2^{O(k)}\cdot V^\omega. Although this algorithm finds only the end points of the colorful path, another algorithm by Alon and Naor<ref>Alon, N. and Naor, M. 1994 Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions. Technical Report. UMI Order Number: CS94-11., Weizmann Science Press of Israel.</ref> that finds colorful paths themselves can be incorporated into it.		The colorful cycle-finding algorithm works by first finding all pairs of vertices in {{mvar\|V}} that are connected by a simple path of length {{math\|''k'' − 1}}, and then checking whether the two vertices in each pair are connected. Given a coloring function {{math\|''c'' : ''V'' → {1, ..., ''k''} }} to color graph {{mvar\|G}}, enumerate all partitions of the color set {{math\|{1, ..., ''k''} }} into two subsets {{math\|''C''<sub>1</sub>, ''C''<sub>2</sub>}} of size <math>k/2</math> each. Note that {{mvar\|V}} can be divided into {{math\|''V''<sub>1</sub>}} and {{math\|''V''<sub>2</sub>}} accordingly, and let {{math\|''G''<sub>1</sub>}} and {{math\|''G''<sub>2</sub>}} denote the subgraphs induced by {{math\|''V''<sub>1</sub>}} and {{math\|''V''<sub>2</sub>}} respectively. Then, recursively find colorful paths of length <math>k/2 - 1</math> in each of {{math\|''G''<sub>1</sub>}} and {{math\|''G''<sub>2</sub>}}. Suppose the boolean matrix {{math\|''A''<sub>1</sub>}} and {{math\|''A''<sub>2</sub>}} represent the connectivity of each pair of vertices in {{math\|''G''<sub>1</sub>}} and {{math\|''G''<sub>2</sub>}} by a colorful path, respectively, and let {{mvar\|B}} be the matrix describing the adjacency relations between vertices of {{math\|''V''<sub>1</sub>}} and those of {{math\|''V''<sub>2</sub>}}, the boolean product <math>A_1BA_2</math> gives all pairs of vertices in {{mvar\|V}} that are connected by a colorful path of length {{math\|''k'' − 1}}. Thus, the recursive relation of matrix multiplications is <math>t(k) \le 2^k\cdot t(k/2)</math>, which yields a runtime of <math>2^{O(k)}\cdot V^\omega</math>. Although this algorithm finds only the end points of the colorful path, another algorithm by Alon and Naor<ref>Alon, N. and Naor, M. 1994 Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions. Technical Report. UMI Order Number: CS94-11., Weizmann Science Press of Israel.</ref> that finds colorful paths themselves can be incorporated into it.

	==Derandomization==		==Derandomization==

CHHC(dec): delete a misleading inference.

2023-12-01T16:30:52Z

delete a misleading inference.

← Previous revision		Revision as of 16:30, 1 December 2023
Line 29:		Line 29:
	By applying random coloring method, each simple cycle has a probability of <math>k!/k^k > e^{-k}</math> to become colorful, since there are <math>k^k</math> ways of coloring the {{mvar\|k}} vertices on the cycle, among which there are <math>k!</math> colorful occurrences. Then an algorithm (described next) can be used to find colorful cycles in the randomly colored graph {{mvar\|G}} in time <math>O(V^\omega)</math>, where <math>\omega</math> is the matrix multiplication constant. Therefore, it takes <math>e^k\cdot O(V^\omega)</math> overall time to find a simple cycle of length {{mvar\|k}} in {{mvar\|G}}.		By applying random coloring method, each simple cycle has a probability of <math>k!/k^k > e^{-k}</math> to become colorful, since there are <math>k^k</math> ways of coloring the {{mvar\|k}} vertices on the cycle, among which there are <math>k!</math> colorful occurrences. Then an algorithm (described next) can be used to find colorful cycles in the randomly colored graph {{mvar\|G}} in time <math>O(V^\omega)</math>, where <math>\omega</math> is the matrix multiplication constant. Therefore, it takes <math>e^k\cdot O(V^\omega)</math> overall time to find a simple cycle of length {{mvar\|k}} in {{mvar\|G}}.

	The colorful cycle-finding algorithm works by first finding all pairs of vertices in {{mvar\|V}} that are connected by a simple path of length {{math\|''k'' − 1}}, and then checking whether the two vertices in each pair are connected. Given a coloring function {{math\|''c'' : ''V'' → {1, ..., ''k''} }} to color graph {{mvar\|G}}, enumerate all partitions of the color set {{math\|{1, ..., ''k''} }} into two subsets {{math\|''C''<sub>1</sub>, ''C''<sub>2</sub>}} of size <math>k/2</math> each. Note that {{mvar\|V}} can be divided into {{math\|''V''<sub>1</sub>}} and {{math\|''V''<sub>2</sub>}} accordingly, and let {{math\|''G''<sub>1</sub>}} and {{math\|''G''<sub>2</sub>}} denote the subgraphs induced by {{math\|''V''<sub>1</sub>}} and {{math\|''V''<sub>2</sub>}} respectively. Then, recursively find colorful paths of length <math>k/2 - 1</math> in each of {{math\|''G''<sub>1</sub>}} and {{math\|''G''<sub>2</sub>}}. Suppose the boolean matrix {{math\|''A''<sub>1</sub>}} and {{math\|''A''<sub>2</sub>}} represent the connectivity of each pair of vertices in {{math\|''G''<sub>1</sub>}} and {{math\|''G''<sub>2</sub>}} by a colorful path, respectively, and let {{mvar\|B}} be the matrix describing the adjacency relations between vertices of {{math\|''V''<sub>1</sub>}} and those of {{math\|''V''<sub>2</sub>}}, the boolean product <math>A_1BA_2</math> gives all pairs of vertices in {{mvar\|V}} that are connected by a colorful path of length {{math\|''k'' − 1}}. Thus, the recursive relation of matrix multiplications is <math>t(k) \le 2^k\cdot t(k/2)</math>, which yields a runtime of <math>2^{O(k)}\cdot V^\omega ~~= O(V^\omega)</math>~~. Although this algorithm finds only the end points of the colorful path, another algorithm by Alon and Naor<ref>Alon, N. and Naor, M. 1994 Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions. Technical Report. UMI Order Number: CS94-11., Weizmann Science Press of Israel.</ref> that finds colorful paths themselves can be incorporated into it.		The colorful cycle-finding algorithm works by first finding all pairs of vertices in {{mvar\|V}} that are connected by a simple path of length {{math\|''k'' − 1}}, and then checking whether the two vertices in each pair are connected. Given a coloring function {{math\|''c'' : ''V'' → {1, ..., ''k''} }} to color graph {{mvar\|G}}, enumerate all partitions of the color set {{math\|{1, ..., ''k''} }} into two subsets {{math\|''C''<sub>1</sub>, ''C''<sub>2</sub>}} of size <math>k/2</math> each. Note that {{mvar\|V}} can be divided into {{math\|''V''<sub>1</sub>}} and {{math\|''V''<sub>2</sub>}} accordingly, and let {{math\|''G''<sub>1</sub>}} and {{math\|''G''<sub>2</sub>}} denote the subgraphs induced by {{math\|''V''<sub>1</sub>}} and {{math\|''V''<sub>2</sub>}} respectively. Then, recursively find colorful paths of length <math>k/2 - 1</math> in each of {{math\|''G''<sub>1</sub>}} and {{math\|''G''<sub>2</sub>}}. Suppose the boolean matrix {{math\|''A''<sub>1</sub>}} and {{math\|''A''<sub>2</sub>}} represent the connectivity of each pair of vertices in {{math\|''G''<sub>1</sub>}} and {{math\|''G''<sub>2</sub>}} by a colorful path, respectively, and let {{mvar\|B}} be the matrix describing the adjacency relations between vertices of {{math\|''V''<sub>1</sub>}} and those of {{math\|''V''<sub>2</sub>}}, the boolean product <math>A_1BA_2</math> gives all pairs of vertices in {{mvar\|V}} that are connected by a colorful path of length {{math\|''k'' − 1}}. Thus, the recursive relation of matrix multiplications is <math>t(k) \le 2^k\cdot t(k/2)</math>, which yields a runtime of <math>2^{O(k)}\cdot V^\omega. Although this algorithm finds only the end points of the colorful path, another algorithm by Alon and Naor<ref>Alon, N. and Naor, M. 1994 Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions. Technical Report. UMI Order Number: CS94-11., Weizmann Science Press of Israel.</ref> that finds colorful paths themselves can be incorporated into it.

	==Derandomization==		==Derandomization==

Acasteigts: /* Results */

2022-10-13T20:37:40Z

Results

← Previous revision		Revision as of 20:37, 13 October 2022
Line 13:		Line 13:
	** <math>O(\|V\|^\omega \log \|V\|)</math> worst-case time, where {{mvar\|ω}} is the exponent of [[matrix multiplication]].<ref>[[Coppersmith–Winograd algorithm\|Coppersmith–Winograd Algorithm]]</ref>		** <math>O(\|V\|^\omega \log \|V\|)</math> worst-case time, where {{mvar\|ω}} is the exponent of [[matrix multiplication]].<ref>[[Coppersmith–Winograd algorithm\|Coppersmith–Winograd Algorithm]]</ref>
	* For every fixed constant {{mvar\|k}}, and every graph {{math\|''G'' {{=}} (''V'', ''E'')}} that is in any nontrivial [[Minor (graph theory)#Minor-closed graph families\|minor-closed graph family]] (e.g., a [[planar graph]]), if {{mvar\|G}} contains a simple cycle of size {{mvar\|k}}, then such cycle can be found in:		* For every fixed constant {{mvar\|k}}, and every graph {{math\|''G'' {{=}} (''V'', ''E'')}} that is in any nontrivial [[Minor (graph theory)#Minor-closed graph families\|minor-closed graph family]] (e.g., a [[planar graph]]), if {{mvar\|G}} contains a simple cycle of size {{mvar\|k}}, then such cycle can be found in:
	** {{math\|''O''(\|''V''\|)}} expected time, or		** {{math\|''O''(''V'')}} expected time, or
	** {{math\|''O''(\|''V''\| log \|''V''\|)}} worst-case time.		** {{math\|''O''(''V'' log ''V'')}} worst-case time.
	* If a graph {{math\|''G'' {{=}} (''V'', ''E'')}} contains a subgraph isomorphic to a bounded [[treewidth]] graph which has {{math\|''O''(log \|''V''\|)}} vertices, then such a subgraph can be found in [[polynomial time]].		* If a graph {{math\|''G'' {{=}} (''V'', ''E'')}} contains a subgraph isomorphic to a bounded [[treewidth]] graph which has {{math\|''O''(log ''V'')}} vertices, then such a subgraph can be found in [[polynomial time]].

	==The method==		==The method==

Acasteigts: /* Results */Further math typos

2022-10-13T20:35:46Z

Results: Further math typos

← Previous revision		Revision as of 20:35, 13 October 2022
Line 13:		Line 13:
	** <math>O(\|V\|^\omega \log \|V\|)</math> worst-case time, where {{mvar\|ω}} is the exponent of [[matrix multiplication]].<ref>[[Coppersmith–Winograd algorithm\|Coppersmith–Winograd Algorithm]]</ref>		** <math>O(\|V\|^\omega \log \|V\|)</math> worst-case time, where {{mvar\|ω}} is the exponent of [[matrix multiplication]].<ref>[[Coppersmith–Winograd algorithm\|Coppersmith–Winograd Algorithm]]</ref>
	* For every fixed constant {{mvar\|k}}, and every graph {{math\|''G'' {{=}} (''V'', ''E'')}} that is in any nontrivial [[Minor (graph theory)#Minor-closed graph families\|minor-closed graph family]] (e.g., a [[planar graph]]), if {{mvar\|G}} contains a simple cycle of size {{mvar\|k}}, then such cycle can be found in:		* For every fixed constant {{mvar\|k}}, and every graph {{math\|''G'' {{=}} (''V'', ''E'')}} that is in any nontrivial [[Minor (graph theory)#Minor-closed graph families\|minor-closed graph family]] (e.g., a [[planar graph]]), if {{mvar\|G}} contains a simple cycle of size {{mvar\|k}}, then such cycle can be found in:
	** {{math\|''O''(''V'')}} expected time, or		** {{math\|''O''(\|''V''\|)}} expected time, or
	** {{math\|''O''(''V'' log ''V'')}} worst-case time.		** {{math\|''O''(\|''V''\| log \|''V''\|)}} worst-case time.
	* If a graph {{math\|''G'' {{=}} (''V'', ''E'')}} contains a subgraph isomorphic to a bounded [[treewidth]] graph which has {{math\|''O''(log ''V'')}} vertices, then such a subgraph can be found in [[polynomial time]].		* If a graph {{math\|''G'' {{=}} (''V'', ''E'')}} contains a subgraph isomorphic to a bounded [[treewidth]] graph which has {{math\|''O''(log \|''V''\|)}} vertices, then such a subgraph can be found in [[polynomial time]].

	==The method==		==The method==

← Previous revision		Revision as of 20:37, 13 October 2022
Line 13:		Line 13:
	** <math>O(\|V\|^\omega \log \|V\|)</math> worst-case time, where {{mvar\|ω}} is the exponent of [[matrix multiplication]].<ref>[[Coppersmith–Winograd algorithm\|Coppersmith–Winograd Algorithm]]</ref>		** <math>O(\|V\|^\omega \log \|V\|)</math> worst-case time, where {{mvar\|ω}} is the exponent of [[matrix multiplication]].<ref>[[Coppersmith–Winograd algorithm\|Coppersmith–Winograd Algorithm]]</ref>
	* For every fixed constant {{mvar\|k}}, and every graph {{math\|''G'' {{=}} (''V'', ''E'')}} that is in any nontrivial [[Minor (graph theory)#Minor-closed graph families\|minor-closed graph family]] (e.g., a [[planar graph]]), if {{mvar\|G}} contains a simple cycle of size {{mvar\|k}}, then such cycle can be found in:		* For every fixed constant {{mvar\|k}}, and every graph {{math\|''G'' {{=}} (''V'', ''E'')}} that is in any nontrivial [[Minor (graph theory)#Minor-closed graph families\|minor-closed graph family]] (e.g., a [[planar graph]]), if {{mvar\|G}} contains a simple cycle of size {{mvar\|k}}, then such cycle can be found in:
	** {{math\|''O''(\|''V''\|)}} expected time, or		** {{math\|''O''(''V'')}} expected time, or
	** {{math\|''O''(\|''V''\| log \|''V''\|)}} worst-case time.		** {{math\|''O''(''V'' log ''V'')}} worst-case time.
	* If a graph {{math\|''G'' {{=}} (''V'', ''E'')}} contains a subgraph isomorphic to a bounded [[treewidth]] graph which has {{math\|''O''(log \|''V''\|)}} vertices, then such a subgraph can be found in [[polynomial time]].		* If a graph {{math\|''G'' {{=}} (''V'', ''E'')}} contains a subgraph isomorphic to a bounded [[treewidth]] graph which has {{math\|''O''(log ''V'')}} vertices, then such a subgraph can be found in [[polynomial time]].

	==The method==		==The method==

← Previous revision		Revision as of 20:35, 13 October 2022
Line 13:		Line 13:
	** <math>O(\|V\|^\omega \log \|V\|)</math> worst-case time, where {{mvar\|ω}} is the exponent of [[matrix multiplication]].<ref>[[Coppersmith–Winograd algorithm\|Coppersmith–Winograd Algorithm]]</ref>		** <math>O(\|V\|^\omega \log \|V\|)</math> worst-case time, where {{mvar\|ω}} is the exponent of [[matrix multiplication]].<ref>[[Coppersmith–Winograd algorithm\|Coppersmith–Winograd Algorithm]]</ref>
	* For every fixed constant {{mvar\|k}}, and every graph {{math\|''G'' {{=}} (''V'', ''E'')}} that is in any nontrivial [[Minor (graph theory)#Minor-closed graph families\|minor-closed graph family]] (e.g., a [[planar graph]]), if {{mvar\|G}} contains a simple cycle of size {{mvar\|k}}, then such cycle can be found in:		* For every fixed constant {{mvar\|k}}, and every graph {{math\|''G'' {{=}} (''V'', ''E'')}} that is in any nontrivial [[Minor (graph theory)#Minor-closed graph families\|minor-closed graph family]] (e.g., a [[planar graph]]), if {{mvar\|G}} contains a simple cycle of size {{mvar\|k}}, then such cycle can be found in:
	** {{math\|''O''(''V'')}} expected time, or		** {{math\|''O''(\|''V''\|)}} expected time, or
	** {{math\|''O''(''V'' log ''V'')}} worst-case time.		** {{math\|''O''(\|''V''\| log \|''V''\|)}} worst-case time.
	* If a graph {{math\|''G'' {{=}} (''V'', ''E'')}} contains a subgraph isomorphic to a bounded [[treewidth]] graph which has {{math\|''O''(log ''V'')}} vertices, then such a subgraph can be found in [[polynomial time]].		* If a graph {{math\|''G'' {{=}} (''V'', ''E'')}} contains a subgraph isomorphic to a bounded [[treewidth]] graph which has {{math\|''O''(log \|''V''\|)}} vertices, then such a subgraph can be found in [[polynomial time]].

	==The method==		==The method==