The time is now - Spring classes are filling up!

MIT PRIMES/Art of Problem Solving

CROWDMATH 2017: Graph Algorithms & Applications

G
Topic
First Poster
Last Poster
cop vs robber in a maze
JGeneson   16
N Nov 21, 2017 by JGeneson
Let $R$ be a connected region in the plane. Suppose that the cop is a segment of length $x$ and the robber is a segment of length $y$.

The cop starts inside $R$ (so we assume that a segment of length $x$ fits somewhere inside $R$), as does the robber. Based on $R$, $x$, $y$, and the initial positions, does the cop catch the robber if both use optimal play?

A good place to start might be regions $R$ where all sides are parallel to the coordinate axes.

How does the result change if the cop and robber are circles or squares instead of segments?

What if the game is played inside connected regions in space?
16 replies
JGeneson
Aug 22, 2017
JGeneson
Nov 21, 2017
problems about point visibility graphs
JGeneson   2
N Nov 13, 2017 by JGeneson
https://arxiv.org/pdf/1711.01811.pdf
This recent arxiv paper shows NP-hardness for the following problems on point visibility graphs:
Feedback Vertex Set
Longest Induced Path
Bisection
F-free Vertex Deletion (for certain sets F)

(Point visibility graphs are graphs induced by a set of points in the plane where the graph's vertices represent the points in the plane and two vertices are adjacent if and only if no other point lies on the line segment between the points.)

The paper mentions some cool open problems about point visibility graphs:

A dominating set is a set of vertices in a graph such that every vertex in the graph is in the set or has a neighbor in the set.
OPEN PROBLEM 1: Does every point visibility graph with $n$ vertices have a dominating set of size $O(\log{n})$?

OPEN PROBLEM 2: What is the computational complexity of the problems Dominating Set and Max Cut for point visibility graphs?
2 replies
JGeneson
Nov 13, 2017
JGeneson
Nov 13, 2017
graph pursuit paper
JGeneson   0
Nov 1, 2017
The first paper from this CrowdMath project is now on arxiv: https://arxiv.org/abs/1710.11352

There are many more unsolved problems about graph pursuit algorithms and visibility graphs that you can still work on. See this page for a partial list of open problems.
0 replies
JGeneson
Nov 1, 2017
0 replies
No more topics!
a