Skip to main content
Notice removed Draw attention by Gizmo
Bounty Ended with HEKTO's answer chosen by Gizmo
Notice added Draw attention by Gizmo
Bounty Started worth 100 reputation by Gizmo
edited title
Source Link
Gizmo
  • 73
  • 7

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never encountered along that path, or every edge that is colored $c$ is visited by that path.

Given $G,s,e$, I would like to find a valid coloring that uses the minimal number of colors. Is there an efficient algorithm for this problem?

I show below an example graph and a sample solution. The circle on the left is the starting vertex, the filled circle on the right is the end vertex.

Example Graph

How to edge-color a directed graph so that every path visits none or all edges of each color?

Given a directed graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never encountered along that path, or every edge that is colored $c$ is visited by that path.

Given $G,s,e$, I would like to find a valid coloring that uses the minimal number of colors. Is there an efficient algorithm for this problem?

I show below an example graph and a sample solution. The circle on the left is the starting vertex, the filled circle on the right is the end vertex.

Example Graph

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never encountered along that path, or every edge that is colored $c$ is visited by that path.

Given $G,s,e$, I would like to find a valid coloring that uses the minimal number of colors. Is there an efficient algorithm for this problem?

I show below an example graph and a sample solution. The circle on the left is the starting vertex, the filled circle on the right is the end vertex.

Example Graph

deleted 538 characters in body; edited tags
Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

How to identify certain sets of edges inedge-color a directed graph so that every path visits none or all edges of each color?

I'm havingGiven a hard time explaining my problem, therefore, I've drawn an example directed graph, as you can see below. The edges are annotated with colours. Those colours/annotations would be the output of the process. The input would be the graph without coloured edges. The circle on the left is the starting$G$ and a start vertex, the filled circle on the right is the $s$ and an end vertex.

The goal is to find sets of edges. Each edge in $e$, consider a set has thecoloring of the following property:edges valid if one edge is visited as a part of a possible, for every path from (from start$s$ to end) through the directed graph$e$ and every color $c$, iteither $c$ is guaranteednever encountered along that all other edges in this set will be visited as well. For example, the green edges are greenpath, because if the first greenor every edge that is visited, itcolored $c$ is guaranteed that all other green edges will be visited as well. Same goes for all coloursby that path.

What algorithm could achieve suchGiven $G,s,e$, I would like to find a valid coloring that uses the minimal number of colors. Is there an annotationefficient algorithm for this problem?

A test forI show below an example graph and a potential set would be checking all possible paths fromsample solution. The circle on the left is the starting vertex to, the end vertex and finding no path that just contains a subset offilled circle on the proposed set.

I feel like I'm missingright is the obvious solutionend vertex. Could anyone please help?

Example Graph

How to identify certain sets of edges in a directed graph?

I'm having a hard time explaining my problem, therefore, I've drawn an example directed graph, as you can see below. The edges are annotated with colours. Those colours/annotations would be the output of the process. The input would be the graph without coloured edges. The circle on the left is the starting vertex, the filled circle on the right is the end vertex.

The goal is to find sets of edges. Each edge in a set has the the following property: if one edge is visited as a part of a possible path (from start to end) through the directed graph, it is guaranteed that all other edges in this set will be visited as well. For example, the green edges are green, because if the first green edge is visited, it is guaranteed that all other green edges will be visited as well. Same goes for all colours.

What algorithm could achieve such an annotation?

A test for a potential set would be checking all possible paths from the starting vertex to the end vertex and finding no path that just contains a subset of the proposed set.

I feel like I'm missing the obvious solution. Could anyone please help?

Example Graph

How to edge-color a directed graph so that every path visits none or all edges of each color?

Given a directed graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never encountered along that path, or every edge that is colored $c$ is visited by that path.

Given $G,s,e$, I would like to find a valid coloring that uses the minimal number of colors. Is there an efficient algorithm for this problem?

I show below an example graph and a sample solution. The circle on the left is the starting vertex, the filled circle on the right is the end vertex.

Example Graph

added 123 characters in body
Source Link
Gizmo
  • 73
  • 7

I'm having a hard time explaining my problem, therefore, I've drawn an example directed graph, as you can see below. The edges are annotated with colours. Those colours/annotations would be the output of the process. The input would be the graph without coloured edges. The circle on the left is the starting vertex, the filled circle on the right is the end vertex.

The goal is to find sets of edges. Each edge in a set has the the following property: if one edge is visited duringas a graph traversal alongpart of a possible path (from start to end) through the directed edgesgraph, it is guaranteed that all other edges in this set will be visited as well. For example, the green edges are green, because if the first green edge is visited, it is guaranteed that all other green edges will be visited as well. Same goes for all colours.

What algorithm could achieve such an annotation?

A test for a potential set would be checking all possible paths from the starting vertex to the end vertex and finding no path that just contains a subset of the proposed set.

I feel like I'm missing the obvious solution. Could anyone please help?

Example Graph

I'm having a hard time explaining my problem, therefore, I've drawn an example directed graph, as you can see below. The edges are annotated with colours. Those colours/annotations would be the output of the process. The input would be the graph without coloured edges.

The goal is to find sets of edges. Each edge in a set has the the following property: if one edge is visited during a graph traversal along the directed edges, it is guaranteed that all other edges in this set will be visited as well. For example, the green edges are green, because if the first green edge is visited, it is guaranteed that all other green edges will be visited as well. Same goes for all colours.

What algorithm could achieve such an annotation?

A test for a potential set would be checking all possible paths from the starting vertex to the end vertex and finding no path that just contains a subset of the proposed set.

I feel like I'm missing the obvious solution. Could anyone please help?

Example Graph

I'm having a hard time explaining my problem, therefore, I've drawn an example directed graph, as you can see below. The edges are annotated with colours. Those colours/annotations would be the output of the process. The input would be the graph without coloured edges. The circle on the left is the starting vertex, the filled circle on the right is the end vertex.

The goal is to find sets of edges. Each edge in a set has the the following property: if one edge is visited as a part of a possible path (from start to end) through the directed graph, it is guaranteed that all other edges in this set will be visited as well. For example, the green edges are green, because if the first green edge is visited, it is guaranteed that all other green edges will be visited as well. Same goes for all colours.

What algorithm could achieve such an annotation?

A test for a potential set would be checking all possible paths from the starting vertex to the end vertex and finding no path that just contains a subset of the proposed set.

I feel like I'm missing the obvious solution. Could anyone please help?

Example Graph

deleted 16 characters in body
Source Link
Gizmo
  • 73
  • 7
Loading
added 74 characters in body
Source Link
Gizmo
  • 73
  • 7
Loading
added 260 characters in body
Source Link
Gizmo
  • 73
  • 7
Loading
added 260 characters in body
Source Link
Gizmo
  • 73
  • 7
Loading
added 1 character in body; edited title
Source Link
Gizmo
  • 73
  • 7
Loading
Fixed typo in title and added a couple of tags
Source Link
Loading
Source Link
Gizmo
  • 73
  • 7
Loading