Improved hardness for H-colourings of G-colourable graphs
<p>We present new results on approximate colourings of graphs and, more generally, approximate H-colourings and promise constraint satisfaction problems.</p> <p>First, we show NP-hardness of colouring k-colourable graphs with colours for every k ≥ 4. This improves the result of Bu...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Society for Industrial and Applied Mathematics
2020
|
| _version_ | 1826273408397082624 |
|---|---|
| author | Wrochna, M Zivny, S |
| author_facet | Wrochna, M Zivny, S |
| author_sort | Wrochna, M |
| collection | OXFORD |
| description | <p>We present new results on approximate colourings of graphs and, more generally, approximate H-colourings and promise constraint satisfaction problems.</p> <p>First, we show NP-hardness of colouring k-colourable graphs with colours for every k ≥ 4. This improves the result of Bulín, Krokhin, and Opršal [STOC'19], who gave NP-hardness of colouring k-colourable graphs with 2k – 1 colours for k ≥ 3, and the result of Huang [APPROX-RANDOM'13], who gave NP-hardness of colouring k-colourable graphs with colours for sufficiently large k. Thus, for k ≥ 4, we improve from known linear/sub-exponential gaps to exponential gaps.</p> <p>Second, we show that the topology of the box complex of H alone determines whether H-colouring of G-colourable graphs is NP-hard for all (non-bipartite, H-colourable) G. This formalises the topological intuition behind the result of Krokhin and Opršal [FOCS’19] that 3-colouring of G-colourable graphs is NP-hard for all (3-colourable, non-bipartite) G. We use this technique to establish NP-hardness of H-colouring of G-colourable graphs for H that include but go beyond K3, including square-free graphs and circular cliques (leaving K4 and larger cliques open).</p> <p>Underlying all of our proofs is a very general observation that adjoint functors give reductions between promise constraint satisfaction problems.</p> <p>The full version [55] containing detailed proofs is available at https://arxiv.org/abs/1907.00872.</p> |
| first_indexed | 2024-03-06T22:27:43Z |
| format | Conference item |
| id | oxford-uuid:573a79ed-831e-4f29-8092-7f7bdff8e972 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T22:27:43Z |
| publishDate | 2020 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:573a79ed-831e-4f29-8092-7f7bdff8e9722022-03-26T16:55:22ZImproved hardness for H-colourings of G-colourable graphsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:573a79ed-831e-4f29-8092-7f7bdff8e972Symplectic Elements at OxfordSociety for Industrial and Applied Mathematics2020Wrochna, MZivny, S<p>We present new results on approximate colourings of graphs and, more generally, approximate H-colourings and promise constraint satisfaction problems.</p> <p>First, we show NP-hardness of colouring k-colourable graphs with colours for every k ≥ 4. This improves the result of Bulín, Krokhin, and Opršal [STOC'19], who gave NP-hardness of colouring k-colourable graphs with 2k – 1 colours for k ≥ 3, and the result of Huang [APPROX-RANDOM'13], who gave NP-hardness of colouring k-colourable graphs with colours for sufficiently large k. Thus, for k ≥ 4, we improve from known linear/sub-exponential gaps to exponential gaps.</p> <p>Second, we show that the topology of the box complex of H alone determines whether H-colouring of G-colourable graphs is NP-hard for all (non-bipartite, H-colourable) G. This formalises the topological intuition behind the result of Krokhin and Opršal [FOCS’19] that 3-colouring of G-colourable graphs is NP-hard for all (3-colourable, non-bipartite) G. We use this technique to establish NP-hardness of H-colouring of G-colourable graphs for H that include but go beyond K3, including square-free graphs and circular cliques (leaving K4 and larger cliques open).</p> <p>Underlying all of our proofs is a very general observation that adjoint functors give reductions between promise constraint satisfaction problems.</p> <p>The full version [55] containing detailed proofs is available at https://arxiv.org/abs/1907.00872.</p> |
| spellingShingle | Wrochna, M Zivny, S Improved hardness for H-colourings of G-colourable graphs |
| title | Improved hardness for H-colourings of G-colourable graphs |
| title_full | Improved hardness for H-colourings of G-colourable graphs |
| title_fullStr | Improved hardness for H-colourings of G-colourable graphs |
| title_full_unstemmed | Improved hardness for H-colourings of G-colourable graphs |
| title_short | Improved hardness for H-colourings of G-colourable graphs |
| title_sort | improved hardness for h colourings of g colourable graphs |
| work_keys_str_mv | AT wrochnam improvedhardnessforhcolouringsofgcolourablegraphs AT zivnys improvedhardnessforhcolouringsofgcolourablegraphs |