<p>The paper <a href="https://arxiv.org/abs/1009.0216" rel="nofollow noreferrer">On graph classes with logarithmic
boolean-width</a> 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.</p>

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

<p>On the other hand,
<a href="http://graphclasses.org/classes/par_21.html" rel="nofollow noreferrer">graphclasses.org</a> claims
that clique is boolean width fixed parameter tractable, giving clique
width as reference. Since $\exp{\log{n}}=n$ it could be polynomial.</p>

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

CC BY-SA 3.0
2017-08-21T08:13:51.207Z
Crossposted to MO: https://mathoverflow.net/questions/279158/complexity-consequence-of-logarithmic-boolean-width-of-co-bounded-degree-graphs
joro
CC BY-SA 3.0
2017-08-21T10:00:01.297Z
FPT doesn't necessarily means that the dependence is exponential, thus it does not imply anything on ETH as long as you do not check the exact dependence. I may have time to check everything later this week, but from the top of my head, I think I remember that you may have an exponential blowup between cw and boolw, thus even if you have a single exponential dependency on the parameter for cw, it would not give much on boolw.
holf
CC BY-SA 3.0
2017-08-21T10:55:07.890Z
@holf Thanks. I think cliquewidth can be exponential in booleanwidth, but this need not answer the question. Some polynomial algorithms using only logarithmic booleanwidth are known, e.g. for dominating set.
joro
CC BY-SA 3.0
2017-08-21T11:51:36.617Z
Can you please remove one of these. Our site policy against simultaneously cross posting to several sites. (You can find the rational on [help/on-topic].)
Kaveh
<cc.complexity-theory><graph-theory><graph-algorithms>
Complexity consequence of logarithmic boolean width of co-bounded degree graphs?
joro
# Complexity consequence of logarithmic boolean width of co-bounded degree graphs?

(Asked by: username_0 on 2017-08-21)

The paper [On graph classes with logarithmic
boolean-width](https://arxiv.org/abs/1009.0216) 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](http://graphclasses.org/classes/par_21.html) 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?

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms
> **Comments:**
> **username_0**: Crossposted to MO: https://mathoverflow.net/questions/279158/complexity-consequence-of-logarithmic-boolean-width-of-co-bounded-degree-graphs  
> **username_1**: FPT doesn't necessarily means that the dependence is exponential, thus it does not imply anything on ETH as long as you do not check the exact dependence. I may have time to check everything later this week, but from the top of my head, I think I remember that you may have an exponential blowup between cw and boolw, thus even if you have a single exponential dependency on the parameter for cw, it would not give much on boolw.  
> **username_0**: @holf Thanks. I think cliquewidth can be exponential in booleanwidth, but this need not answer the question. Some polynomial algorithms using only logarithmic booleanwidth are known, e.g. for dominating set.  
> **username_2**: Can you please remove one of these. Our site policy against simultaneously cross posting to several sites. (You can find the rational on [help/on-topic].)  

---

## 0 answers

