Finding Triangles or Independent Sets; and Other Dual Pair Approximations
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910324660109312 |
|---|---|
| author | Dumitrescu, Adrian |
| author_facet | Dumitrescu, Adrian |
| contents | We revisit the algorithmic problem of finding a triangle in a graph (\textsc{Triangle Detection}), and examine its relation to other problems such as \textsc{3Sum}, \textsc{Independent Set}, and \textsc{Graph Coloring}. We obtain several new algorithms:
\smallskip (I) A simple randomized algorithm for finding a triangle in a graph. As an application, we study the range of a conjecture of Pǎtraşcu (2010) regarding the triangle detection problem.
\smallskip (II) An algorithm which given a graph $G=(V,E)$ performs one of the following tasks in $O(m+n)$ (ie, linear) time: (i)~compute a $Ω(1/\sqrt{n})$-approximation of a maximum independent set in $G$ or (ii)~find a triangle in $G$. The run-time is faster than that for any previous method for each of these tasks.
\smallskip (III) An algorithm which given a graph $G=(V,E)$ performs one of the following tasks in $O(m+n^{3/2})$ time: (i)~compute an $\sqrt{n}$-approximation for \textsc{Graph Coloring} of $G$ or (ii)~find a triangle in $G$. The run-time is faster than that for any previous method for each of these tasks on dense graphs, with $m =ω(n^{9/8})$.
\smallskip (IV) The second and third results suggest the following broader research direction: if it is difficult to find (A) or (B) separately, can one find one of the two efficiently? This motivates the \emph{dual pair} concept we introduce. We discuss and provide several instances of dual-pair approximation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2105_01265 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Finding Triangles or Independent Sets; and Other Dual Pair Approximations Dumitrescu, Adrian Data Structures and Algorithms We revisit the algorithmic problem of finding a triangle in a graph (\textsc{Triangle Detection}), and examine its relation to other problems such as \textsc{3Sum}, \textsc{Independent Set}, and \textsc{Graph Coloring}. We obtain several new algorithms: \smallskip (I) A simple randomized algorithm for finding a triangle in a graph. As an application, we study the range of a conjecture of Pǎtraşcu (2010) regarding the triangle detection problem. \smallskip (II) An algorithm which given a graph $G=(V,E)$ performs one of the following tasks in $O(m+n)$ (ie, linear) time: (i)~compute a $Ω(1/\sqrt{n})$-approximation of a maximum independent set in $G$ or (ii)~find a triangle in $G$. The run-time is faster than that for any previous method for each of these tasks. \smallskip (III) An algorithm which given a graph $G=(V,E)$ performs one of the following tasks in $O(m+n^{3/2})$ time: (i)~compute an $\sqrt{n}$-approximation for \textsc{Graph Coloring} of $G$ or (ii)~find a triangle in $G$. The run-time is faster than that for any previous method for each of these tasks on dense graphs, with $m =ω(n^{9/8})$. \smallskip (IV) The second and third results suggest the following broader research direction: if it is difficult to find (A) or (B) separately, can one find one of the two efficiently? This motivates the \emph{dual pair} concept we introduce. We discuss and provide several instances of dual-pair approximation. |
| title | Finding Triangles or Independent Sets; and Other Dual Pair Approximations |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2105.01265 |