1. Is there a situation when OS kill's the application, but doesn't kill the service?
tl;dr: Yes, this is possible. However, the Service must be started in it's own process.
Explaination:
It's important to realize that the Android OS kills processes when it's running low on memory, not individual components, such as Activities or Services (see this answer).
Given the above statement, it is clear that a Service can exist independent of the Application only if they are contained in separate processes. Otherwise, they will be destroyed together when their process is destroyed.
Now consider the case of the Service and Application existing on separate processes. In Android, processes are destroyed in low memory situations from lowest to highest priority. The priority order is: Empty < Background < Service < Visible < Foreground (see here). Therefore, it's possible that your Application will be destroyed while your Service stays alive (e.g. if your Application is in the background) and it's also possible that your Service will be destroyed while your Application stays alive (Application is in the foreground).
You can declare any component (Activity, Service, ContentProvider, etc.) of an application to run in it's own process by defining the android:process attribute in the components manifest tag.
From the official documentation of Processes:
By default, all components of the same application run in the same process and most applications should not change this. However, [...] the manifest entry for each type of component element — Activity, Service, Receiver, and Provider — supports an android:process attribute that can specify a process in which that component should run. You can set this attribute so that each component runs in its own process or so that some components share a process while others do not. [...] The Application element also supports an android:process attribute, to set a default value that applies to all components.
2. When the service is restarted by the system, will the application restart as well?
This is related to the answer in question 1.
If the Service exists in the same process as the Application then they will both be destroyed and restarted together.
If the Service exists in a separate process as the Application then they are completely separate processes, and therefore will be destroyed and restarted independent of each other as the Android OS deems appropriate.
