Beehaw
  • Communities
  • Create Post
  • search
    Search
  • Login
  • Sign Up
☆ Yσɠƚԋσʂ ☆ ( yogthos@lemmy.ml )  to Mathematics@lemmy.ml · 2 months ago

k-Coloring is Faster than Computing the Chromatic Number

arxiv.org

external-link
message-square
1
link
fedilink
  • cross-posted to:
  • math@mander.xyz
1
external-link

k-Coloring is Faster than Computing the Chromatic Number

arxiv.org

☆ Yσɠƚԋσʂ ☆ ( yogthos@lemmy.ml )  to Mathematics@lemmy.ml · 2 months ago
message-square
1
link
fedilink
  • cross-posted to:
  • math@mander.xyz
We prove that $k$-coloring on $n$-vertex graphs has a randomized algorithm running in time $(2-\varepsilon_k)^n$, where $\varepsilon_k>0$ for every fixed $k$. Previously, only the cases $k\leq 6$ were known to have faster solutions than the general $O^\star\bigl(2^n\bigr)$ time algorithm of [Björklund, Husfeldt, Koivisto, SICOMP 2009] that computes the chromatic number. In fact, our algorithm solves the more general problem of $k$-list-coloring, even when the overall color palette is of unbounded size. We resolve this long-standing open problem by generalizing and combining tools from the $(k+2)$-coloring to $k$-list-coloring reduction of [Zamir, ICALP 2021] and the hypergraph-containers based approach in [Zamir, STOC 2023]. Together with new algorithms for list-coloring instances mixing long and short color lists, this yields an iterable reduction from $(k+1)$-list-coloring to $k$-list-coloring over arbitrary palettes.
alert-triangle
You must log in or # to comment.
  • balsoft ( balsoft@lemmy.ml ) 
    link
    fedilink
    arrow-up
    1
    ·
    2 months ago

    Will this algo be applicable in practice, e.g. for job scheduling?

Mathematics@lemmy.ml

mathematics@lemmy.ml

Subscribe from Remote Instance

Create a post
You are not logged in. However you can subscribe from another Fediverse account, for example Lemmy or Mastodon. To do this, paste the following into the search field of your instance: !mathematics@lemmy.ml

A community for discussing mathematics and developments in mathematics.

Visibility: Public
globe

This community can be federated to other instances and be posted/commented in by their users.

  • 1 user / day
  • 3 users / week
  • 3 users / month
  • 49 users / 6 months
  • 30 local subscribers
  • 686 subscribers
  • 107 Posts
  • 46 Comments
  • Modlog
  • mods:
  • obbeel ( obbeel@lemmy.ml ) 
  • BE: 0.19.15
  • Modlog
  • Legal
  • Instances
  • Docs
  • Code