Let $G = (V, E)$ be a graph, that contains directed and undirected edges.

$G$ has the following properties:

  • let $(v_1, \dots, v_k)$ be a directed Path form $v_1$ to $v_k$, then ther exists a directed edge $(v_1, v_k) \in E$
  • it follows, that the nodes of ever directed path form a clique
  • Only edges that are directed in $G$ have the transitive property
  • $G$ is a perfect graph
  • $G$ is acyclic

Now, let $H_G$ be a minimal acyclic orientation of $G$ so that.

  • the length of the longest path is minimal
  • every path of length $j$ cannot be shortened without creating a new path of at least length $j$

Shortening of a path: Let $p$ be a path in an acyclic Orientation $H_G$ of $G$. If follows, that p is directed in $H_G$. If $p$ contains an edge that is undirected in $G$, we could flip the orientation of said edge in $H_G$, and cut/shorten the path at this edge. However, this does not always work, as it is possible to create a new and even longer path.

I want to prove the following statement:

If the longste path in $H_G$ contains at least $k$ vertices and there exists a vertex $v \in E(G)$, so that the longest path in a minimal Orientation of the graph $G' = G[V \setminus \{v\}]$ contains less than $k$ vertices, then every path of length $k$ in $H_G$ contains v.

  • $\begingroup$ To me it's not very clear what you mean by "shortening" a path. And so it's not clear either what "minimal acyclic orientation of $G$" means. Minimal by what criterions, only those two ? $\endgroup$ – Hugo Manet Mar 16 at 15:02
  • $\begingroup$ @HugoManet thanks for your comment. I made an edit to further clarify the concept of shortening a path. And yes, the criteria for minimal is, as stated. $\endgroup$ – LukasB97 Mar 16 at 15:22
  • $\begingroup$ Actually, in your setup, all the orientations are isomorphic (see my answer) $\endgroup$ – Hugo Manet Mar 16 at 15:35

EDIT : The setup changed, this is no longer correct

Mixing directed and undirected edges is generally strange. And here, it turns out it doesn't really make sense.

First, your conditions imply that the graph is acyclic and transitive ($u \to v \wedge v \to w \Rightarrow u \to w$) so the undirected edges are all independent (no vertex is contained in two undirected edges).

Then, if two vertices are connected by an undirected edge ($u \leftrightarrow v$), then for every other vertex $w$, we have $u \to w \Leftrightarrow v \to w$ and $w \to u \Leftrightarrow w \to v$. The two vertices are indistinguishable, which means that if we swap $u$ and $v$, we get the same graph up to isomorphism.

Thus, all the orientations of the unoriented edges are isomorphic to each other. So, for every point of view, it doesn't matter which orientation you choose -- apart from one point of view, which is the labeling of the vertices that are part of an undirected edge.

For clarity, if $u \leftrightarrow v$ in $G$, I will write $s(u) = v$ and $s(v) = u$ : $s$ is the swapping function.

Now, the initial question becomes rather easy, because we don't have to worry about which orientation is minimal -- they're all the same, apart maybe from the position of the vertex $v$ that you're trying to remove. But since this vertex $u$ is indistinguishable from its counterpart $s(u)$ in $G$, the only way to tell them apart is the orientation of the edge $u \leftrightarrow s(u)$. When you remove either $u$ or $s(u)$, this way to tell them apart disappear. So $H_G \setminus \{u\}$ is isomorphic to $H_G \setminus \{s(u)\}$, whatever orientation we choose for $H_G$. So all orientations are really the same for your problems.

Now, forget the ambiguity of the choice of orientation, and fix any orientation. You're asking to prove that, if removing a vertex forbids the existence of a path of length $k$, then this vertex is part of every path of length $k$. This seems rather straightforward, no ?

  • $\begingroup$ Thanks for your answer. Only edges that are directed in $G$ have the transitive property, so an undirected edge $\{u, v\}$ and $u \to w$ does not imply $v \to w$. $\endgroup$ – LukasB97 Mar 16 at 15:43
  • $\begingroup$ Mixing directed and undirected edges is super strange. Where does this come from ? $\endgroup$ – Hugo Manet Mar 16 at 15:47
  • 1
    $\begingroup$ The Graph $G$ is a conflict graph that represents data from a practical problem (layered graph drawing). Some constraints are known, like $v_1$ must be above $v_2$ - expressed as a directed edge from $v_2$ to $v_1$ - and some constraints are more open (expressed by a undirected edge). $\endgroup$ – LukasB97 Mar 16 at 15:52
  • $\begingroup$ Ok, but then you don't actually need the transitive property. The longest path won't ever use an edge that is "created" by this transitive property. $\endgroup$ – Hugo Manet Mar 16 at 16:05
  • $\begingroup$ Just to check : the acyclic property, does it apply with undirected edges ? With a mix of directed and undirected edges ? $\endgroup$ – Hugo Manet Mar 16 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.