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?

  • 1
    $\begingroup$ Crossposted to MO: mathoverflow.net/questions/279158/… $\endgroup$ – joro Aug 21 '17 at 8:13
  • $\begingroup$ 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. $\endgroup$ – holf Aug 21 '17 at 10:00
  • $\begingroup$ @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. $\endgroup$ – joro Aug 21 '17 at 10:55
  • $\begingroup$ Can you please remove one of these. Our site policy against simultaneously cross posting to several sites. (You can find the rational on help center.) $\endgroup$ – Kaveh Aug 21 '17 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.