Skip to main content
2 of 3
added 183 characters in body
joro
  • 25.4k
  • 10
  • 66
  • 121

Complexity consequence of logarithmic boolean width of co-bounded degree graphs?

The paper On graph classes with logarithmic boolean-width claims that the boolean width of co-k-degenerate graphs is at most $k\log{n}$ and a lot of graph vertex partition problems can be solved in polynomial time.

co-k-degenerate graphs include complements of bounded degree graphs. Clique is NP-hard on co-maximum degree 4.

On the other hand, graphclasses.org claims that clique is boolean width fixed parameter tractable, giving clique width as reference. Since $\exp{\log{n}}=n$ it could be polynomial.

Are there complexity consequence of logarithmic boolean width of co-bounded degree graphs? Like ETH not holding for them?

The paper gives polynomial algorithm for Dominating Set. It claims some vertex problems are polynomial and some are $O(n^{\log(n)})$, p.2 for graphs of logarithmic boolean-width.

joro
  • 25.4k
  • 10
  • 66
  • 121