Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2017: Graph Algorithms & Applications

G
Topic
First Poster
Last Poster
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
No more topics!
a