How to find the branch a git commit is on? (Using libgit2sharp)

Not sure how much of helpful this answer would prove to you. The LibGit2Sharp equivalent call for "git branch --contains $SHA1" is a requested feature on GitHub, an open one!

Long back, I used a query over all refs like this, but for your use-case it might be prohibitively slow.

I was trying to think for possible ways to mitigate this problem, could not come up with any guiding light. :( And then I discovered this comment which asserts that you need to traverse the DAG and validate the actual branch which has the commit. It all hints that you would need to go the slow traverse-all-refs approach.