- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Clique Is Hard for State-of-the-Art Algorithms
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Clique Is Hard for State-of-the-Art Algorithms de Rezende, Susanna
Description
Finding a maximum clique in a graph is one of the most basic computational problems on graphs. The various applications of this problem has motivated the design of algorithms which today can successfully solve real-world instances with thousands of vertices. However, from a theoretical point a view, it is widely believed that this is a hard problem: in particular that determining whether a graph on n vertices contains a k-clique requires time $n^{\Omega(k)}$. In terms of upper bounds, it is easy to determine this in time roughly $n^k$ by checking if any of the sets of vertices of size k forms a clique.
We analyse the running time of the most successful algorithms used in practice: colour-based branch-and-bound strategies and à stergård's algorithm based on Russian doll search. When analysing such algorithms, it is convenient to view the execution trace as a proof establishing the maximal clique size for the input graph. In particular, if this graph does not have a k-clique, then the trace provides an efficiently verifiable proof in so-called regular resolution of the statement that the graph is k-clique-free. We show that for any $k \ll n^{1/4}$ if the input graph is a k-clique-free random graph sampled from the right distribution then the size of such regular resolution proofs, and hence the running time of these algorithm, is at least $n^{\Omega(k)}$.
Item Metadata
| Title |
Clique Is Hard for State-of-the-Art Algorithms
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2018-08-27T18:08
|
| Description |
Finding a maximum clique in a graph is one of the most basic computational problems on graphs. The various applications of this problem has motivated the design of algorithms which today can successfully solve real-world instances with thousands of vertices. However, from a theoretical point a view, it is widely believed that this is a hard problem: in particular that determining whether a graph on n vertices contains a k-clique requires time $n^{\Omega(k)}$. In terms of upper bounds, it is easy to determine this in time roughly $n^k$ by checking if any of the sets of vertices of size k forms a clique.
We analyse the running time of the most successful algorithms used in practice: colour-based branch-and-bound strategies and à stergård's algorithm based on Russian doll search. When analysing such algorithms, it is convenient to view the execution trace as a proof establishing the maximal clique size for the input graph. In particular, if this graph does not have a k-clique, then the trace provides an efficiently verifiable proof in so-called regular resolution of the statement that the graph is k-clique-free. We show that for any $k \ll n^{1/4}$ if the input graph is a k-clique-free random graph sampled from the right distribution then the size of such regular resolution proofs, and hence the running time of these algorithm, is at least $n^{\Omega(k)}$. |
| Extent |
28.0
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: KTH Royal Institute of Technology
|
| Series | |
| Date Available |
2019-03-31
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0377700
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Graduate
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International