5 ms·

I have a graph with weighted edges. I want to remove edges to make the graph colorable with N colors (e.g. N=40) such that the total weight of removed edges is

I have a graph with weighted edges. I want to remove edges to make the graph colorable with N colors (e.g. N=40) such that the total weight of removed edges is minimized. If I'm able to solve this problem, that will complete a project I've been working on for years now to make a working keyboard for a person I know that has cerebral palsy.

sabageti 5y ago
What are the needs in time?
- graphcolorer 5y ago
  Can take as long as needed as it only needs to be colored one time. About 10,000 nodes, reasonably dense (about half the nodes will have 1,000+ edges).
  - sabageti 5y ago
    What did you try to color the graph ? CSP ? Classic backtracking ? With how many colors it must be colored ?
oneepic 5y ago
Will the graph ever change? Is this a one-time computation?
- graphcolorer 5y ago
  One time.
  - oneepic 5y ago
    Also... is it possible for you to add nodes? Ie split a N>40 node into two nodes.
    - graphcolorer 5y ago
      No, though nodes can be deleted -- at a cost equal to the total cost of all the edges that contain it.
oneepic 5y ago
Similar to what another commenter said about time, have you tried a backtracking approach by: (1) coloring the whole graph (let's say you end with 42 colors) (2) start with the highest colored nodes (e.g. N=42, which exceeds your threshold of 40) and (3) greedily remove the lowest-weight edges (or maybe, edges to other high-colored nodes) until you are either all colored with 40 colors or we reach an invalid state (ie node no longer in the graph) -- with the latter you can add another edge back and try again by removing the next-lowest edge.
- graphcolorer 5y ago
  That's what I'm doing now, but the results aren't great. If there's a way to estimate a lower bound on the number of edges to remove, I can figure out if the results aren't great because of the approximation, or because of the nature of the graph...
david_allison 5y ago
Could you put the graph up in a gist/pastebin?
Const-me 5y ago
Graph coloring can mean vertex coloring, edge coloring, or total coloring. These are 3 different problems. Regardless on the answer, I think this gonna be way too slow for your use case. Especially if you want the global optimum. Wikipedia says the current state-of-the-art is randomized algorithms, I don’t think these algorithms are looking for global optima. I don’t recommend solving that, I think you’ll waste your time. How’s that related to the keyboard anyway?
minhmeoke 5y ago
Here is an algorithm that could work and run reasonably quickly, although it might not be optimal: 1. Find all vertices with degree N > 40 (eg: find all points in the graph with more than 40 outgoing edges). 2. For each pair (a, b) of these degree N > 40 vertices, find the set of common points (c) connected to both a and b by edges, eg: there exists 2 edges (a - c) and (b - c). In essence, you're forming V shapes (a - c - b) where the two tips (a, b) of the V have at least N > 40 outgoing edges. 3. Identify the pairs of vertices (a, b) that are connected by 40 or more Vs (eg: there are at least 40 pairs of (a - c) and (b - c) edges). 4. Remove the (a - c) or (b - c) edge with the highest weight. If (a - c) and (b - c) have equal weight, remove the edge which is connected to the node a or b with more outgoing edges. 5. Repeat steps 3 and 4 until each (a, b) pair has at most 39 Vs connecting them together. At this point, I think you can color the graph with N=40 colors (one color for a and b, then different colors for each in-between point of the 39 Vs between them). There might be a way to improve the criteria for which edge to remove in step 4 (maybe using the backtracking approach mentioned by other commenters), but this should be a decent starting point.

sabageti 5y ago

What are the needs in time?

graphcolorer 5y ago
Can take as long as needed as it only needs to be colored one time. About 10,000 nodes, reasonably dense (about half the nodes will have 1,000+ edges).
- sabageti 5y ago
  What did you try to color the graph ? CSP ? Classic backtracking ? With how many colors it must be colored ?

oneepic 5y ago

Will the graph ever change? Is this a one-time computation?

graphcolorer 5y ago
One time.
- oneepic 5y ago
  Also... is it possible for you to add nodes? Ie split a N>40 node into two nodes.
  - graphcolorer 5y ago
    No, though nodes can be deleted -- at a cost equal to the total cost of all the edges that contain it.

oneepic 5y ago

Similar to what another commenter said about time, have you tried a backtracking approach by: (1) coloring the whole graph (let's say you end with 42 colors) (2) start with the highest colored nodes (e.g. N=42, which exceeds your threshold of 40) and (3) greedily remove the lowest-weight edges (or maybe, edges to other high-colored nodes) until you are either all colored with 40 colors or we reach an invalid state (ie node no longer in the graph) -- with the latter you can add another edge back and try again by removing the next-lowest edge.

graphcolorer 5y ago
That's what I'm doing now, but the results aren't great. If there's a way to estimate a lower bound on the number of edges to remove, I can figure out if the results aren't great because of the approximation, or because of the nature of the graph...

david_allison 5y ago

Could you put the graph up in a gist/pastebin?

Const-me 5y ago

Graph coloring can mean vertex coloring, edge coloring, or total coloring. These are 3 different problems. Regardless on the answer, I think this gonna be way too slow for your use case. Especially if you want the global optimum. Wikipedia says the current state-of-the-art is randomized algorithms, I don’t think these algorithms are looking for global optima. I don’t recommend solving that, I think you’ll waste your time. How’s that related to the keyboard anyway?

minhmeoke 5y ago

Here is an algorithm that could work and run reasonably quickly, although it might not be optimal: 1. Find all vertices with degree N > 40 (eg: find all points in the graph with more than 40 outgoing edges). 2. For each pair (a, b) of these degree N > 40 vertices, find the set of common points (c) connected to both a and b by edges, eg: there exists 2 edges (a - c) and (b - c). In essence, you're forming V shapes (a - c - b) where the two tips (a, b) of the V have at least N > 40 outgoing edges. 3. Identify the pairs of vertices (a, b) that are connected by 40 or more Vs (eg: there are at least 40 pairs of (a - c) and (b - c) edges). 4. Remove the (a - c) or (b - c) edge with the highest weight. If (a - c) and (b - c) have equal weight, remove the edge which is connected to the node a or b with more outgoing edges. 5. Repeat steps 3 and 4 until each (a, b) pair has at most 39 Vs connecting them together. At this point, I think you can color the graph with N=40 colors (one color for a and b, then different colors for each in-between point of the 39 Vs between them). There might be a way to improve the criteria for which edge to remove in step 4 (maybe using the backtracking approach mentioned by other commenters), but this should be a decent starting point.