Is there a general term for elimination grid logic puzzles and can they be solved with Bipartite Graph Matching?

Question

There is a logic puzzle type that having a form of you are given some facts about the things of especially two groups, then you are asked about unclear relationships that are not given.

For example, see or see

I come across these questions occasionally and since I'm familiar with Graph Theory from my undergraduate computer science lectures, most of the time I tend to make a graph about relationships but then I can't figure out how to continue. It looks like a bipartite graph matching but I just can't be sure how technically Graph Theory can applied for that kind of questions.

I was in quest of finding a general name for this kind of puzzle questions and what I could find are Elimination Grids and Logic Grid Puzzles.

I have found some papers about solving these kind of puzzles and in one them they were using logic programming with Prolog, but I'm not interested in that aspect of them.

Also some popular puzzle questions like "Cheryl’s Birthday problem" looks similar to that puzzles and I have found an article “Now I know”: Solving logical puzzles using graphs by Catherine Greenhill.

Is there a general term(more technical than "logic grid") for this kind of puzzles and can we apply Graph Theory to solve that puzzles?

Answer 1

I am not aware of an "official" term for this style of puzzle. Pre-internet, these puzzles were popularized (in the United States) by being published by Dell Puzzle magazines under the uninspired name "logic puzzles" (as puzzles of this sort don't actually need to be solved with the grids, and some are more easily solved without them). Very similar sorts of problems come up on post-graduate entrance exams (like the GRE back in my day or the LSAT now), and they tend to be called Analytical Reasoning.

Matchings in bipartite (actually $n$-partite, based on the number of different "types" of information you need to link) graphs is a sensible model as a base. For all but the simplest sorts of problems, you'll need to build on top of that. For instance, a clue might be "Susan is two years older than the trumpet player" that doesn't automatically translate into graph-theoretic language as easily as "Susan is not the trumpet player" does (if part of the puzzle is finding the ages of the musicians).