I wonder whether there is mathematics about the combinatorics of turning directed graphs into DAGs and DAGs into path graphs (maybe with the intermediate step of trees?).
This feels kind of relevant to AI alignment: If we have the right level of abstraction (i.e. we don't just overfit to human behavior and biases), one way we can represent inconsistent preferences is via directed graphs (fully connected?). But we would like to turn these inconsistent preferences into consistent ones.
While this wouldn't tell us *how* we should make preferences consistent, it could give us a way of determining which ways of making preferences consistent exist and are more complex (maybe penalizing deleting edges differently from merging or adding edges?).
I should try to find out whether this has been done before, and if it hasn't, I really want to look into this more.
Example: If we have a cycle graph ({a,b,c},{(a,b),(b,c),(c,a)}), then we can turn it into a path graph by removing any of the three edges (three ways of pathizing the graph).
If we have a DAG ({a,b,c,d},{(a,b),(a,c),(b,d),(c,d)}) where b and c are deemed incomparable, we can turn that into a path graph in two different ways: either putting c before b or b before c (two ways of pathizing the graph).
There's probably some recursive thing going on here, if we have more complex graphs.