Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces

Question

I am curious whether the following problems has been studied before, but wasn't able to find any papers about it:

Given a planar graph $G$, and two vertices $s$ and $t$, find an $s$-$t$ path $P$ which minimizes the number of distinct faces of $G$ containing vertices of $P$ on their boundaries.

Does anybody know any references?

• G. Bach: This may be a silly question, but would you need to fix an embedding for this?
• zarathustra: @G.Bach: from an algorithmic point of view, when we say "given a planar graph", we usually mean "given a combinatorial map for a graph", hence the embedding is indeed fixed.
• Joe: Do you have an application in mind, or just curiosity?
• A.Schulz: @zarathustra: No, if we say "given a planar graph" we mean "given a planar graph". If we assume that this graph is equipped with a combinatorial embedding we say, "given a plane graph". Of course, if the graph is 3-connected then the combinatorial embedding is fixed up to a global reflection.
• Ainsley H.: @zarathustra you need only go to Wikipedia for this distinction.

Answer 1

First off, note that this problem is only well-specified for a given planar embedding (or plane graph) of the planar graph, the planar graph itself is not enough as it doesn't encode which vertices share which incident faces.

Suppose we know and can access the incident faces of any given vertex of the graph in the given embedding, for example by a map $f:V\rightarrow F$ or a bipartite graph or similar suitable data structure.

The problem can then be solved with a slight modification of Dijkstra's algorithm: For every vertex $v$, we have to store a collection of path face sets that are incurred by some $s$-$v$ path. We expand nodes in priority by minimum cardinality of their attached face sets, propagating to the neighbours of the current vertex by taking the set union of each path face set with that neighbor's vertex face set. Terminate once some path face set at vertex $t$ is up for expansion.

For convenient solution extraction, one might want to store additional information in the data structure. E.g. instead of a mere collection of path face sets, store a map from path face sets to the neighbors of the vertex such that each path face set points at a neighbor from which it originated, or even a full path up to that point.

There's some optimizations possible, like keeping only the Pareto optimal path face sets to conserve memory, or doing lazy computation on the expansion step, but it should always return an optimal solution.

• Ainsley H.: I doubt this works (in polynomial time). You have to store, for each vertex, the set of visited faces. There are exponentially many possibilities.
• MarioVX: I don't claim it runs in polynomial time, but it will at least give the correct (i.e. optimal) solution because a path with smaller face set cannot have been skipped. I doubt an optimal algorithm that runs in polynomial time even in the worst case exists for this problem anyways, intuitively because the information about the face sets cannot always be discarded and that implies there are instances which will take at least 2^(number of faces). If you find asymptotic optimizations for this or even an optimal polynomial algorithm feel free to share though.
• Ainsley H.: If you're only claiming a 2ドル^f$ style algorithm, you might as well just guess the faces and run BFS, which should run in time $O(2^f n)$.
• Ainsley H.: I think it should at least be doable in time $O(2^{k \log k} +n)$ where $k$ is the "cost" of the path sought, hence the problem is in FPT.
• MarioVX: You mean trying face sets by running BFS on a copy of the graph with all vertices deleted that are incident to a face not in that set? Yup, that would work too. However, I strongly suspect the above method will be much faster on average due to planarity. For example, a face set is nonsensical if it disconnected by a gap wider than one edge as it cannot be the minimal cover for a path. All kinds of nonsensical face sets either don't show up at all or would only show up after the optimal solution is already found by the above method, which would then already terminate.