As a rule of thumb with RESTful APIs I've found that you should only ever need to do "one hop" when defining relationships between two entities. As soon as you need to start defining relationships across "two hops" it's normally a sign that the endpoint isn't very RESTful any more.
Endpoints should only really be concerned with one entity. Remember this isn't a web application where users can describe complicated relationships via dropdowns populated by AJAX requests. It's fine to have to make a couple of API calls to achieve your goal. API calls are fast and cheap.
Also you mention that you don't know their IDs. How else are you going to identify the linked entities? Unless they have a unique field that you can identify them by you're going to run into problems. All RESTful APIs rely on having an identifier of some type otherwise everything falls over because no one is ever quite sure what entity you're talking about.
TLDR, get the IDs and only allow the API to accept immediate relationships.
Edit: You also mention routes. The "one hop" rule applies here too. In a fictitious scenario with authors, posts and tags I would set up my routes like so:
- /authors
- /authors/1
- /authors/1/posts
- /posts
- /posts/1
- /posts/1/tags
- /tags
- /tags/1
This keeps your routes small and easy to immediately understand.