Program that brute forces to find the minimum dominating set

Question

This program solves the minimum dominating set but it takes an insanely long time to run. In case you do not know, in graph theory, a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is either in D, or has a neighbor in D. Can someone help me make my code more efficient.

import java.io.FileNotFoundException;
import java.util.*;
import java.io.File;

public class FireStationPlacement {
    public static void main(String[] args) {
            Graph graph = new Graph();
          try {
                Scanner Layout2 = new Scanner( new File("text/LayoutSecond.txt") );  
                for (int x=0;x<5;x++) {
                    graph.addEdge(Layout2.nextInt(), 1, Layout2);
                }

                for (int x=0;x<20;x++) {
                     graph.addEdge(Layout2.nextInt(), 2, Layout2);
                }      

                for (int x=0;x<6;x++) {
                     graph.addEdge(Layout2.nextInt(), 3,Layout2);
                }
                Layout2.close();
            }
            catch (FileNotFoundException e) {
                // TODO Auto-generated catch block
                System.err.println( "File not found" );
            }

            // Print the adjacency list representation of the graph
            System.out.print(graph.minFireStationsBruteForce(graph.adjacencyList));
    }
}
    
    
class Graph {
        Map<Integer, List<Integer>> adjacencyList;
        Graph() {
            adjacencyList = new HashMap<>();
        }

        void addEdge(int vertex, int num, Scanner layout2) {
            if (num==1) {
                adjacencyList.put(vertex, Arrays.asList(layout2.nextInt()));
            }
            else if (num==2) {
                adjacencyList.put(vertex, Arrays.asList(layout2.nextInt(),layout2.nextInt()));
            }
            else if (num==3) {
                adjacencyList.put(vertex, Arrays.asList(layout2.nextInt(),layout2.nextInt(),layout2.nextInt() ));
            }
        }

        List<Integer> getNeighbors(int vertex) {
            return adjacencyList.getOrDefault(vertex, Collections.emptyList());
        }

        private void dfs(int currentVertex, Set<Integer> visited) {
            visited.add(currentVertex);
            for (int neighbor : adjacencyList.get(currentVertex)) {
                if (!visited.contains(neighbor)) {
                    dfs(neighbor, visited);
                }
            }
        }

        public void dfsHelper(int startVertex) {
            Set<Integer> visited = new HashSet<>();
            dfs(startVertex, visited);
        }
        
        static boolean isCovered(Set<Integer> subset,  Map<Integer, List<Integer>> graph) {
            Set<Integer> covered = new HashSet<>(subset);
            for (int neighborhood : subset) {
                covered.addAll(graph.get(neighborhood));
            }
            return covered.equals(graph.keySet());
        }

        public static int minFireStationsBruteForce( Map<Integer, List<Integer>>  graph) {
                int n = graph.size();
                System.out.println("Graph size is " + n);
                List<Integer> neighborhoods = new ArrayList<>(graph.keySet());      
                for (int k = 1; k <= 31; k++) {
                    for (Set<Integer> subset : combinations(neighborhoods, k)) {
                        if (isCovered(subset, graph)) {
                            System.out.println(subset.toString());
                            return k;
                        }
                }
            }
            return n;
        }

        private static Set<Set<Integer>> combinations(List<Integer> elements, int k) {
            Set<Set<Integer>> allCombinations = new HashSet<>();
            combinations(allCombinations, new HashSet<>(), elements, k, 0);
            return allCombinations;
        }

        private static void combinations(Set<Set<Integer>> allCombinations, Set<Integer> current, List<Integer> elements, int k, int start) {
            if (current.size() == k) {
                allCombinations.add(new HashSet<>(current));
                return;
            }
            for (int i = start; i < elements.size(); i++) {
                current.add(elements.get(i));
                combinations(allCombinations, current, elements, k, i + 1);
                current.remove(elements.get(i));
            }
        }
}



 

Answer 1

This ended up being a bit too long for a comment, but I wanted to present another avenue of attack that may result in better performance.

The dominating set problem can be easily formulated as an Integer Linear Program. Given a graph $$G = (V, E)$$ create variables x_i in {0, 1} for each v_i where x_i is zero if a vertex is not part of the dominating set or 1 if it is.

$$\text{min} \sum_{v_i \in V} x_{i}$$ $$\text{subject to} \sum_{x_{j} \in N(v_{i})} x_j \geq 1, \forall v_{i} \in V$$

That is, you want to minimize the size of the dominating set and you must ensure that the closed neighborhood of every vertex must have at least one vertex

You can formulate the problem for a particular graph and then feed it to either an open source solver such as GLPK or CP-SAT or commercial solvers such as CPLEX or Gurobi.

I am not familiar with which options are available for Java but there appear to be interfaces to solvers such as this one.

Answer 2

magic numbers

                for (int x=0; x < 50; x++) { ...
                for (int x=0; x < 20; x++) { ...
                for (int x=0; x <  6; x++) { ...

Gosh, that sure is a lot of magic numbers! With no explanations. You might want to assign symbolic names to them. Or figure out how LayoutSecond.txt can convey those numbers to the program without any hardcodes.

        public static int minFireStationsBruteForce( ...
                ...
                for (int k = 1; k <= 31; k++) {

Maybe you wanted to define MAX_DIAMETER = 31 ? Or at least, I think it's expressing a constraint on allowed graph diameters.

Better to compute it dynamically from the graph you've read in. For example, you might shoot a minimum spanning tree through the graph from some starting node, and use the max path length that that gives you.

admissible heuristic

DFS is certainly one way to traverse the graph. A* is another which you might want to consider. But I don't see an admissible heuristic, some measure of "are we there yet?", "are we closer?", and you didn't include the original problem description. We want to be able to quickly discard candidate solutions that are clearly inferior to "best candidate" that we have so far discovered.

strategy

Your code includes no helpful comments, and the review context describes neither problem constraints nor the high level approaches that were considered.

Write a paragraph or two describing the problem, its challenges, and the tradeoffs involved in meeting each challenge. Think at a high level before diving down into the code. Think out loud -- your thoughts need to be written down. Cite the references you've consulted so far.

libraries

You didn't mention whether linking against external graph libraries is prohibited. Consider adopting JUNG or one of its competitors. You can even start out crafting a solution atop library calls, get it working well, and then one-by-one code up your own methods so you can drop the library dependency.

This would lower the barrier for trying out an idea based on Dijkstra's algorithm, or MST.

Answer 3

How to make brute force code more efficient

Currently the combinations pre-generates all combinations of size k, creating a lot of copies of hashsets as it does so. Alternatively, you could do something like what combinations already does but every time it generates a combination, you can use it right away. Then there's no copy, and no big list of those copies.

Secondly but more importantly, you can avoid generating some combinations. If you're keeping track of which vertices are covered while generating the combinations, the combination generator could easily detect situation where including a vertex in the combination would not change the number of covered vertexes, and in that case skip over it (or don't consider it in the first place, by only looping over uncovered vertices). The amount of work skipped in that case depends strongly on the "depth" at which it is detected, the higher up in the recursion to more work it skips: an exponential amount of work.

This also skips a separate isCovered check since the recursive search itself would already track a set of currently covered vertices, which you can simply check the count of. But that's not where the real time savings come from, that comes from pruning the search.

For example, let's say we have this graph:

During the recursive generation of combinations, once we add vertex 1, we already know that adding vertex 2 is pointless: 2, 4 and 6 are already covered, adding vertex 2 changes nothing. So instead of generating all combinations that start with { 1, 2 ... we can just not do that, and skip straight to { 1, 3 ....

31

If you're working with small fixed-size sets of for example 31 possible elements, you can replace all your sets with bit masks. Operations such as adding an element to a set, checking whether an element is in a set, checking whether one set is contained in another, taking the union of two sets, and much more, all translate into trivial integer operations. For example it would be possible to efficiently check for each vertex whether its set of neighbours (plus the vertex itself) has any uncovered vertices with something like ((adjacencyMatrix[vertex] | (1 << vertex)) & ~covered) != 0, which you could use in your recursion to avoid generating combinations with "useless" vertices in them (a combination with a useless vertex in it can never be the answer, because you would have found a smaller answer first).

other

main and addEdge are both jointly responsible for parsing the input data, each reading half of the edge. I would not split up reading an edge that way, and putting them in one place is also an opportunity to free the graph class from any IO responsibility.