Another Graph algorithm puzzle

You have a graph containing N vertices with zero cost edges. Traveling on an edge has no cost but a vertex itself has an associated cost.
Your objective is to remove the nodes (and corresponding edges) such that it will not be possible to travel from vertex 1 to N while minimizing the cost of eliminated vertices.

The attached image shows an example. Removing nodes 2 and 3 costs 50 and is the cheapest way to break the paths from 1 to 6.  You could remove node 1 or node 6 but that will cost 100 and 200 and so these are not optimal solutions.

I couldn't come up with complete solution. For now I will post a hint which I think will be useful.
1. For each given vertex, you add two vertices (say 1-a, 1-b for vertex 1), and when there is an edge between 1 and 2, you add an edge between 1-a and 2-b and an edge between 2-a and 1-b with weight as cost of vertex.
2. Now to find the minimum cost, you remove edges with non-zero weight till vertex 1 and vertex 6 are disconnected. I am not sure which algorithm to use here.
You can use Krushkal's algorithm Union Find data structure. Keep adding zero weight edges and highest weight edges till 1-a n-b are of different parent groups. If there are making 1-a and n-b belong to same group, then dont add that edge(hopefully v-a v-b edge-> removing v vertex)

Difficult one, I could not think of anything better than this:

1) make a list of all paths that start at vertex 1 and end at vertex N, each path being a Set of the vertex numbers (so that each vertex only appears once)
2) for the rest of this story, ignore the vertices 1 and N
3) for each path, determine the minimum cost of all the vertices in that path; denote it as Min(i) for path number i
3) determine, for all the vertices in the paths, their frequency, and choose the one with the highest frequency (if there are more than one, take the one with lowest cost), and suppose that vertex B has cost cB and frequency fB
4) renumber all the paths with B as 1, 2, ..., fB
5) let Min be the minimum of Min(1) + Min(2) + ... + Min(fB) and cB (that would be the cost if we eliminate vertex B)
6) for the remaining paths, repeat this procedure, and let vertex C be the most frequent vertex with frequency fC and cost cC.
7) the new minimum Min of the first fB + fC paths is the minimum of Min + (minimum of (Min(1) + Min(2) + ... + Min(fC))) and cC)
8) et cetera, until all paths are handled.
9) the requested minimum cost is now min(cost of vertex 1, Min, cost of vertex N)

No idea what the O(x) is, but hopefully less than O(2 ^N).

Paul, does there exist some ingenious algo for this, that solves it in O(log N)?

Bhaskar, can you elaborate a little, and tell how far you got?

All: is my algo correct, or just bare nonsense?

While searching I found a similar problem in an assignment for students of DSA course in UG Computer Science engineering in one of the better known engineering institutes of India. They have to implement it in C...good Lord! So I am assuming there is an interesting algorithm to solve this even though I am still not able to get a handle on it.  

I am not sure if your algo is correct or not because I am still trying to understand it. But even if I did understand it, I think I will have to implement it and run some test cases to verify.

Unfortunately my algo is incorrect. After typing it and going to bed again. I realised the flaws in it. Then thought of another approach, but that was O(N^3). Still thinking...

can you elaborate a little, and tell how far you got?

For point 1: I am splitting a vertex into two vertices and adding an artificial edge with cost of the vertex. Now the graph will have additional n vertices and additional n-edges. For each split for vertex v, I am calling them split vertices with v-a, v-b with indices i, index + n. And for given edge from v1 to v2, I will add an edge from v1-b to v2-a (and also possibly v2-a to v1-b)
So if we want to find the cost of staying at vertex 1, we can find path 1-a to 1-b(that goes via 1-a to 1-b artificial edge introduced)
So overall, it will be easier if we are talking about shortest paths, as we can find the path between 1-a to n-b.

For strikethrough point, I am referring to Krushkal's algorithm and Union-Find Datastructure
I tried with normal dfs after getting nowhere(as after adding an artificial edge in union find datastructure, whole graph is connected), that also had no progress.

Btw, I just realized that the answer in my example is incorrect. We just need to remove node 3 (cost 20) and not node 2 & 3.

I was unable to come up with a clever solution, even after very long thinking, so I decided to use brute force. That sounds horrible with runtimes of O(2^N), but I think I found a way to ease the pain a little.

My idea was as I described above, albeit that the part of determining the most frequent node in all the generated paths is flawed, since there is no guarantee that the reduction achieved will the smallest one.

To represent a Path in an as cheaply way as possible, I used a List as I learned it in a Scala-course. I called it MuisList, and it has a head and a MuisList as tail. The advantage is that if I have a Path, and there are three more nodes to go to, I then get three new MuisLists that all share the existing MuisList as tail. Each node will be stored only once this way.

Next step is to determine all paths from startnode to endnode. I used plain old DFS for this, and to prevent infinite paths if there are cycles in the Graph, I made sure that a node can only appear once in a path. The method is called pathsFromTo.

Having this List of paths, I first determine all the unique nodes in these paths. Then comes the brute-force approach: first I delete all paths that contain the first node. If there are no remaining paths, then removing that node makes sure that there is no path from start to finish, and I store that first node, together with the cost of it, in a resultlist. If there are still paths, then I delete from them all paths that contain the second node, et cetera, until either we run out of nodes, or there are no remaining paths, and in that case I calculate the cost of the removed nodes.

The result is a List of costs and the list of removed nodes that go with that cost. And with that you can determine whatever you like.
That second method is called getCostsOfPaths. It uses recursion and a helper-method for that.

For Pauls example I get:
****************
Paths found:
[1, 5, 4, 3, 6]
[1, 5, 4, 3, 2, 6]
[1, 4, 3, 6]
[1, 4, 3, 2, 6]
****************
NodeRemoval[cost=100, removedNodes=[1]]
NodeRemoval[cost=50, removedNodes=[2, 3]]
NodeRemoval[cost=100, removedNodes=[2, 4]]
NodeRemoval[cost=240, removedNodes=[2, 5, 6]]
NodeRemoval[cost=230, removedNodes=[2, 6]]
NodeRemoval[cost=20, removedNodes=[3]]
NodeRemoval[cost=70, removedNodes=[4]]
NodeRemoval[cost=210, removedNodes=[5, 6]]
NodeRemoval[cost=200, removedNodes=[6]]
BUILD SUCCESSFUL (total time: 0 seconds)

The normal list of subsets from the list (1, 2, 3, 4, 5, 6) would involve 2^6 subsets, and here I only needed to check 9 of them. So, although it is O(2^N), I hope in practice it will be a lot less bad. One optimization would be that if we are creating a list of removals, and the current cost of it is higher that the minimum cost found sofar, then you can skip that path. Here is the full code:
package pietsjavaprobeersels01; import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Set; import static java.lang.System.out; import static java.util.stream.Collectors.toSet; public class GraphUtilities {        public static void main(String... args) {        var map = new HashMap<Integer, List<Integer>>(); //        map.put(0, List.of(1, 2, 3)); //        map.put(1, List.of(0, 2, 4)); //        map.put(2, List.of(0, 1, 4)); //        map.put(3, List.of(0, 4));        map.put(1, List.of(4, 5));        map.put(2, List.of(3, 6));        map.put(3, List.of(2, 6));        map.put(4, List.of(1, 3, 5));        map.put(5, List.of(1, 4));        map.put(6, List.of(2, 3));         //        var costs = Map.of(0, 100, 1, 10, 2, 15, 3, 40, 4, 160);        var costs = Map.of(1, 100, 2, 30, 3, 20, 4, 70, 5, 10, 6, 200);                var result = pathsFromTo(map, 1, 6);        System.out.println("****************");        System.out.println("Paths found:");        result.forEach(out::println);        System.out.println("****************");                var result2 = getCostsOfPaths(map, 1, 6, costs);        result2.forEach(out::println);    }        public static List<MuisList<Integer>> pathsFromTo(        Map<Integer, List<Integer>> adjacencyMap, int from, int to) {        if (!adjacencyMap.containsKey(from)) throw new RuntimeException("from is null");        var result = new ArrayList<MuisList<Integer>>();        var currentPath = new MuisList<>(from);        var queue = new LinkedList<MuisList<Integer>>();        queue.add(currentPath);        while (!queue.isEmpty()) {            var pl = queue.removeFirst();            for (var i: adjacencyMap.get(pl.head)) {                if (i == to) result.add(pl.add(i));                else if (pl.contains(i)) continue;                else queue.addFirst(pl.add(i));            }        }        return result;    }        public static List<NodeRemoval> getCostsOfPaths(        Map<Integer, List<Integer>> adjMap,        int from, int to,        Map<Integer, Integer> costs) {        var paths = pathsFromTo(adjMap, from, to).stream()            .map(ml -> ml.toList().stream().collect(toSet()))            .toList()        ;        var nodes = paths.stream().flatMap(set -> set.stream()).distinct().sorted().toList();        var removalsSofar = new ArrayList<Integer>();        var costOfRemovals = new ArrayList<NodeRemoval>();        getCostsOfPathsHelper(paths, nodes, 0, costs, removalsSofar, costOfRemovals);        return costOfRemovals;    }    private static void getCostsOfPathsHelper(        List<Set<Integer>> paths, List<Integer> nodes, int index,        Map<Integer, Integer> costs, List<Integer> removalsSofar,        List<NodeRemoval> costOfRemovals) {        if (paths.isEmpty()) {            var totalCost = removalsSofar.stream().mapToInt(costs::get).sum();            costOfRemovals.add(new NodeRemoval(totalCost, new ArrayList<>(removalsSofar)));            return;        }        if (index == nodes.size()) return;        var remainingPaths = paths.stream()            .filter(set -> !set.contains(nodes.get(index)))            .toList()        ;        if (remainingPaths.size() < paths.size()) removalsSofar.add(nodes.get(index));        getCostsOfPathsHelper(remainingPaths, nodes, index + 1, costs, removalsSofar, costOfRemovals);        removalsSofar.remove(removalsSofar.size() - 1);        getCostsOfPathsHelper(paths, nodes, index + 1, costs, removalsSofar, costOfRemovals);    } } /*************************************************************************/ class MuisList<E> {    E head;    MuisList<E> tail;        private MuisList(E e, MuisList tail) {        if (e == null) throw new RuntimeException("argument null!!!");        this.head = e;        this.tail = tail;    }        MuisList(E e) {        if (e == null) throw new RuntimeException("argument null!!!");        this.head = e;        this.tail = null;    }        public MuisList<E> add(E e) {        return new MuisList(e, this);    }        public MuisList<E> removeHead() {        return tail == null ? this : tail;    }            public List<E> toList() {        var result = new ArrayList<E>();        if (tail == null) result.add(head);        else {            result.addAll(tail.toList());            result.add(head);        }        return result;    }        public boolean contains(E e) {        return head.equals(e) ? true :               tail == null ? false :               tail.contains(e)        ;      }        @Override    public String toString() {        return toList().toString();      } } /************************************************************************/ record NodeRemoval(int cost, List<Integer> removedNodes) {}

I tried to test your code for the attached graph. I am not sure if this is how you intended to take the input but based on what I understood, I updated it for the given graph as follows:
       map.put(1, List.of(2));        map.put(2, List.of(3, 4));        map.put(3, List.of(5));        map.put(4, List.of(5));        map.put(5, List.of(6));         //        var costs = Map.of(0, 100, 1, 10, 2, 15, 3, 40, 4, 160);        var costs = Map.of(20, 30, 5 , 30, 40 , 50);



It printed the paths correctly but threw a NPE later.

**************** Paths found: [1, 2, 4, 5, 6] [1, 2, 3, 5, 6] **************** Exception in thread "main" java.lang.NullPointerException at java.base/java.util.stream.ReferencePipeline$4$1.accept(ReferencePipeline.java:214) at java.base/java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1625) at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:509) at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:499) at java.base/java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:921) at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234) at java.base/java.util.stream.IntPipeline.reduce(IntPipeline.java:515) at java.base/java.util.stream.IntPipeline.sum(IntPipeline.java:473) at pietsjavaprobeersels01.GraphUtilities.getCostsOfPathsHelper(GraphUtilities.java:84) at pietsjavaprobeersels01.GraphUtilities.getCostsOfPathsHelper(GraphUtilities.java:97) at pietsjavaprobeersels01.GraphUtilities.getCostsOfPaths(GraphUtilities.java:73) at pietsjavaprobeersels01.GraphUtilities.main(GraphUtilities.java:37)

hi Paul,

the costs-map is incorrect, it should be a Map<Node, Cost>,. This is the input that I used:
var map = new HashMap<Integer, List<Integer>>(); map.put(1, List.of(2)); map.put(2, List.of(1, 3, 4)); map.put(3, List.of(2, 5)); map.put(4, List.of(2, 5)); map.put(5, List.of(3, 4, 6)); map.put(6, List.of(5)); var costs = Map.of(1, 20, 2, 30, 3, 5, 4, 30, 5, 40, 6, 50);
with this output:

****************
Paths found:
[1, 2, 4, 5, 6]
[1, 2, 3, 5, 6]
****************
******************
nodes in these paths:
[1, 2, 4, 5, 6, 3]
******************
NodeRemoval[cost=20, removedNodes=[1]]
NodeRemoval[cost=30, removedNodes=[2]]
NodeRemoval[cost=70, removedNodes=[4, 5]]
NodeRemoval[cost=80, removedNodes=[4, 6]]
NodeRemoval[cost=35, removedNodes=[4, 3]]
NodeRemoval[cost=40, removedNodes=[5]]
NodeRemoval[cost=50, removedNodes=[6]]

As an aside: I wondered (in the previous posts already) why in this case the also correct removals ( 3, 5), (3, 6), (3, 4) et cetera are not mentioned.  There is a good reason for, but I am not sure whether that is correct or not. For the very simple graphs so far, it works nicely, but I don't know how it will work in the case of much larger.

Anyway, it gives you a change to eliminate a complete network in the cheapest possible way!    

Well, there is indeed a bug, giving an NPE, for instance if you try the paths between nodes 3 and 6. This is the renewed getCostsOfPathsHelper-method:
private static void getCostsOfPathsHelper(    List<Set<Integer>> paths, List<Integer> nodes, int index,    Map<Integer, Integer> costs, List<Integer> removalsSofar,    List<NodeRemoval> costOfRemovals) {    if (paths.isEmpty()) {        var totalCost = removalsSofar.stream().mapToInt(costs::get).sum();        costOfRemovals.add(new NodeRemoval(totalCost, new ArrayList<>(removalsSofar)));        return;    }    if (index == nodes.size()) return;    var remainingPaths = paths.stream()        .filter(set -> !set.contains(nodes.get(index)))        .toList()    ;    // this is the new part    if (remainingPaths.size() < paths.size()) {        removalsSofar.add(nodes.get(index));        getCostsOfPathsHelper(remainingPaths, nodes, index + 1, costs, removalsSofar, costOfRemovals);        removalsSofar.remove(removalsSofar.size() - 1);    }    getCostsOfPathsHelper(paths, nodes, index + 1, costs, removalsSofar, costOfRemovals); }

4-5 and 4-6 are not valid solutions unless you consider 123456 also a valid solution, right?

No. 123456 is not a valid path. But 45 and 46 are valid (but expensive) solutions.

I now do a sort of my candidate-nodes list, such that the start- and endvertex are at the start of the list. By the look of it, that gives another reduction of paths-to-investigate.

Do you have some other examples for me to test?

Piet Souris wrote:No. 123456 is not a valid path. But 45 and 46 are valid (but expensive) solutions.

Yes, sorry, I meant all nodes in a path such as 12356 or 12456.

I implemented the shortcut that I mentioned: if some nodes are being eliminated, and the cost of these nodes is larger than the minimum cost found sofar, then that attempt is skipped. Saves some more work of what is in fact an O(2^N) method. If someone knows a real clever solution, let me know.
public static List<NodeRemoval> getCostsOfPaths(    Map<Integer, List<Integer>> adjMap,    int from,    int to,    Map<Integer, Integer> costs) {    var paths = pathsFromTo(adjMap, from, to).stream()        .map(ml -> ml.toList().stream().collect(toSet()))        .toList()    ;    var nodes = paths.stream()        .flatMap(set -> set.stream())        .distinct()        .toList()    ;    System.out.println("******************");    System.out.println("nodes in these paths:");    System.out.println(nodes);    System.out.println("******************");    var removalsSofar = new ArrayList<Integer>();    var costOfRemovals = new ArrayList<NodeRemoval>();    int[] minimumCostSofar = {Integer.MAX_VALUE};    getCostsOfPathsHelper(paths, nodes, 0, costs, removalsSofar, costOfRemovals, 0, minimumCostSofar);    return costOfRemovals; } and
private static void getCostsOfPathsHelper(    List<Set<Integer>> paths,    List<Integer> nodes,    int index,    Map<Integer, Integer> costs,    List<Integer> removalsSofar,    List<NodeRemoval> costOfRemovals,    int costSofar,    int[] minimumCostSofar) {    if (costSofar >= minimumCostSofar[0]) return;    if (paths.isEmpty()) {        minimumCostSofar[0] = costSofar;        costOfRemovals.add(new NodeRemoval(costSofar, new ArrayList<>(removalsSofar)));        return;    }    if (index == nodes.size()) return;    var currentNode = nodes.get(index);    var remainingPaths = paths.stream()        .filter(set -> !set.contains(currentNode))        .toList()    ;    if (remainingPaths.size() < paths.size()) {        removalsSofar.add(currentNode);        getCostsOfPathsHelper(            remainingPaths,            nodes,            index + 1,            costs,            removalsSofar,            costOfRemovals,            costSofar + costs.get(currentNode),            minimumCostSofar)        ;        removalsSofar.remove(removalsSofar.size() - 1);    }    getCostsOfPathsHelper(        paths,        nodes,        index + 1,        costs,        removalsSofar,        costOfRemovals,        costSofar,        minimumCostSofar)    ; }