Recently I've been playing a nice little puzzle game called LYNE, which involves building a (special) graph out of a given set of vertices and prescribed valencies, and I've been wondering what could be said about the solutions to one such problem. More formally:
Definition 1: Let's call an L-set any finite set of pairs $\mathbf{v} = (v,d)$ with $v\in\mathbb{Z}^2$ and $d\in\{1,2,4,6,8\}$ such that each $v$ appears only once and the number of pairs with $d=1$ is even.
Definition 2: Let's call an L-graph any (finite) plane graph $G$ such that:
- The valency of any vertex is $1,2,4,6$, or $8$.
- The number of vertices with valency $1$ is even.
- The edges have length at most $\sqrt{2}$.
- The set of edges of $G$ can be partitioned in such a way that each subset can be ordered into a path(possibly with loops, but with no repetitions) from one vertex of valency $1$ to another.
Definition 3: Consider an L-set $\mathcal{V}$ and let $$ V = \left\{v\in\mathbb{Z}^2 : (v,d)\in\mathcal{V} \text{ for some } d\in\{1,2,4,6,8\} \right\} $$ Then a solution to the L-problem posed by $\mathcal{V}$ is a set of edges $E$ such that $(V,E)$ is an L-graph and each $v\in V$ has valency $d$, where $(v,d)\in\mathcal{V}$.
I would like to answer the following (possibly hard) questions:
- Given an L-set, are there any criteria to decide if the corresponding L-problem admits a solution, other than brute force? (bonus points for an effective way of computing the number of solutions)
Edit: As pointed out by wonce, it looks like finding a solution to a special L-problem is NP-complete. It is unclear (at least to me) if this is the general case: there may be some sizable subclasses of L-problems for which finding solutions is simpler.
- Can we find a reasonable bound on the number of solutions to an L-problem?
Note 1: By reasonable I mean any bound remotely useful. Clearly the number of solutions to the L-problem given by $\mathcal{V}$ is bounded by the number of planar graphs on $|\mathcal{V}|$ vertices each with valency at most $8$, but you can guess why I'm not happy with this piece of information.
Note 2: If such a bound exists, I would expect it to depend on the cardinalities of the sets $\mathcal{V}$ and $\{(v,d)\in\mathcal{V} : d=i\}$ for each $i\in\{1,2,4,6,8\}$.