Re: Question on computational complexity

The construction I described encodes an arbitrary tally language into a
set of graphs satisfying your uniformity condition. You can easily
adapt it to encode languages over a binary alphabet and that will give
you what you want. Here is one way you could do it.
Suppose you have a binary string w of length n. Define the graph G_w to
consist of a disjoint union of cliques of different sizes.
Specifically, it contains one clique of size k and in addition a clique
of size k+i for each i such that the i-th bit of w is 1 and finally a
clique of size k+n+1.

Now, for any language A of binary strings take the class of graphs S_A =
{G_w | w in A}. There is an easy reduction from A to S_A. Moreover,
S_A clearly has the property you wanted. So, if you start with A that
is hard for the complexity class you want, so is S_A.

This one works fine, thank you very much!

.

Relevant Pages

  • Re: Maximum split subgraph
    ... > The size of the decomposition should still be linear in the size of the ... I'm interested in doing this on some prime graphs, ... I think for graphs of bounded clique width the above procedure could be ... Chordal graphs can have unbounded clique width since every grid ...
    (comp.theory)
  • Upper bounds for chromatic number
    ... Are there any known upper bounds for the chromatic number ... S2 of undirected simple graphs? ... graphs whose clique number is c. ... Thomas ...
    (sci.math)
  • Re: Upper bounds for chromatic number
    ... > graphs whose clique number is c. ... I think this is the simplest construction: ... given positive integer n> 2, consider the graph with vertex set ...
    (sci.math)