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.

Added we learnt that this is known and the attack doesn't work.

For details see Martin Vatshelle paper: http://www.ii.uib.no/~martinv/Papers/MartinThesis.pdf p. 58.

Someone please answer the question, don't feel like answering my bounty.


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.