1
$\begingroup$

In a related question I've defined a class of graph problems which are verifiable using a time related only on the size of the witness:

$EasyVer=\{L\subset \mathcal{G}\times \mathbb{N}| $ a witness $w$ of $L$'s instance can be verified in $poly(k)$ time$\}$, i.e. independent of $|V|,|E|$.

You can assume that the verifier has random access to the graph adjacency matrix in $O(1)$ time.

Examples for $EasyVer$ problems will be $VC, Clique, IS$ and $Steiner Tree$.

Also, many packing and problems, $triangle-packing$, $k-path-packing$, or in general $H-packing$ for a graph $H$ with constant treewidth, are all in $EasyVer$.

Problems which aren't in (i.e. require more extensive interaction with the input) are also easily found: $VC, DominatingSet, FVS$(Feedback Vertex Set).

In order to get a sense of how $EasyVer$ relates to known complexity classes it would be useful to have a list of problem it contains.

Which other NP-complete problem (or even better, problem classes) can be verified in $poly(k)$ time, where $k$ is the size of the problem witness?

$\endgroup$
  • 2
    $\begingroup$ Is the verifier a word RAM? $\:$ If no, how do you show that $Clique$ and $IS$ are in $EasyVer$? $\;\;$ Even if the machine allows Random Access with the target provided as a given slice of a tape, I don't see any way, other than the verifier being a word RAM, to make verification run in less than $\:k\cdot \Omega(\log(\log(|V|)))\:$ time. $\;\;\;\;\;$ $\endgroup$ – user6973 Mar 8 '14 at 20:48
  • $\begingroup$ @RickyDemer - you can assume that the verifier has random access to the graph adjacency table, I've edited the question. $\endgroup$ – R B Mar 8 '14 at 20:58
  • $\begingroup$ That doesn't resolve my issue, since I don't see a way for anything other than a word RAM to even select the target entry (for random access) in less than $\Omega(\log(\log(|V|)))$ time. $\;$ $\endgroup$ – user6973 Mar 8 '14 at 21:02
  • $\begingroup$ @RickyDemer, perhaps we should then go back to my previuous question, where I asked what's the right way to define this class: cstheory.stackexchange.com/questions/21409/…. $\endgroup$ – R B Mar 8 '14 at 21:04
  • $\begingroup$ One could specify that the verifier receives the adjacency matrix of a vertex-induced subgraph, but not the rest of the original adjacency matrix. $\;$ $\endgroup$ – user6973 Mar 8 '14 at 21:09
1
$\begingroup$

If I get it right, you are interested in those parameterized problems that can be verified by a bounded-time NTM (running in time $f(k)$ for some function of the parameter). Up to fpt-reduction, these are precisely the problems in the class $W[1]$, see "On the parameterized complexity of short computation and factorization" by Cai, Chen, Downey and Fellows.

$\endgroup$
  • $\begingroup$ I'm not sure I understand your answer. FVS for example is even FPT, but it doesn't seem you can verify a feedback set without looking at all of the graph. $\endgroup$ – R B Mar 9 '14 at 15:23
  • $\begingroup$ That's why I wrote "up to fpt-reduction", as $W[1]$ can defined as the class of problems fpt-reducible to Short Nondeterministic Turing machine Computation. If you focus on bounded-time verification, it may be possible to define a variant of $W[1]$ using a different type of reduction... $\endgroup$ – Super8 Mar 9 '14 at 15:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.