We know that a set of problems like minimum clique cover problem, coloring problem, vertex cover, ... are NP-hard for general graphs, but may be polynomial-time solvable for some classes of specific graphs, such as perfect graphs.

In my case, I have a specific class of graphs defined as follows. Define $f : \mathbb{N} \to \mathbb{N}$ by $f(k) = k(2^{k-1}-1)$. There is a function $g$ from natural numbers to graphs, so that $f(k)$ defines an undirected graph structure on $f(k)$ vertices (i.e., $g(k)$ defines the vertex set and edge set of the graph) for each natural number $k$. Now I want to consider the class of all vertex-weighted graphs that are consistent with $g(k)$ for some $k$, i.e., where the vertex and edge set is defined by $g(k)$ but the weights on the vertices can be arbitrary. (The full description of a class of graphs can be found here.)

Finally, I want to solve a problem such as minimum clique cover for this class of graphs. Is it NP-hard or can we always find a polynomial-time algorithm (polynomial in the size of the input, rather than polynomial in $k$) that finds the solution?

  • 3
    $\begingroup$ If there's a polynomial $p$ such that $L$ contains at most $p(n)$ strings of length $n$, for all $n$, then $L$ is "sparse". Mahaney's theorem says that no sparse language can be NP-complete, unless P=NP. But, even if there's only one graph of each size, there might still be exponentially many different ways of encoding that graph as a string (corresponding to the different ways of ordering the adjacency matrix), so Mahaney might not give the answer. $\endgroup$ – David Richerby Jan 22 '17 at 19:33
  • 3
    $\begingroup$ Well, by definition, complexity classes are classes of languages of strings. Normally, we can pretend that, for example, 3-COLOURABILITY is a language of graphs and forget about the need to encode them as strings so that a Turing machien can compute with them. But sometimes, it's important. $\endgroup$ – David Richerby Jan 22 '17 at 20:03
  • 1
    $\begingroup$ I've edited the question for you, to include the information you provided in the question. It's possible the answer is might be "it depends on the particular class of graphs, and in particular, on the specific function $g$ you have in mind", which would make this essentially a "duplicate in disguise" of the question in the link. But we'll see if anyone else can provide a useful answer! Perhaps there are some useful insights to be had from sparsity or such. $\endgroup$ – D.W. Jan 23 '17 at 20:19
  • $\begingroup$ @D.W. Thanks for editing the question. $\endgroup$ – m0_as Jan 23 '17 at 20:39

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.