What is the minimum execution time that a query/statement for a parallel execution

As per documentation its 30 seconds
The parameter is (from 11gr2) is parallel_min_time_threshold which invokes the automatic degree of parallelism when the query execution goes beyond 30 seconds.

Nevertheless, whether you have object parallelism (table/index degree) set or not, if parallel_degree_policy is set to Limited or Auto, Oracle uses parallelism for any queries depends on the resources available if not it will wait until the resources available. So when it needed it further check that execution time goes beyond 30 seconds then DOP will be invoked.

This is 11g behavior, not sure if something exists prior to 11g.
The 11gR2 optimizer will first determine if the query could indeed benefit from parallel operations and what would be an appropriate DOP value. Oracle 11gR2 will next ascertain if the query’s estimated execution time is likely to run longer than the acceptable value (in seconds) for PARALLEL_MIN_TIME_THRESHOLD and, if sufficient resources for parallel execution exist right now, it will allow the query to execute; otherwise, it will delay its execution until sufficient resources exist. This helps prevent a single parallel query from consuming excessive resources – for example, all possible parallel execution threads, or  all CPUs in a clustered environment – at the cost of other non-parallelizable operations.

BTW, the documentation say’s 30 secs where in the metalink note 1264548.1 says 10 secs