4 Replies - 323 Views - Last Post: 20 May 2019 - 06:19 AM

#1 Larry71   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 82
  • Joined: 05-June 12

Algorithm for vertex cover problem

Posted 20 May 2019 - 02:22 AM

Hallo again,

I have come up with a problem that belongs to the family of minimum vertex cover and I have solved it by using a smart greedy algorithm.
The solution is satisfying when the data is little but it needs much time when it goes bigger.
The problem:

I have many arrayLists of integers, all of a certain length, let's say length N. The question is:
What is the minimum set of subarrayLists of integers, of length M, that M<N that cover all of the arrayLists, meaning choosing a random subarraylist, there is at least one arraylist that contains it.

I will give an example:

I have three arraylists, [1,2,3,4],[1,3,5,6],[2,3,5,7] of length 4. I am looking for a set of subarraylists of length 2.
A solution would be [2,3],[5,6] because [2,3] is contained in list 1 and 3 and [5,6] in list 2.It is also the minimum set as you can't have only 1 subarraylist of length 2, that can be a solution.

My greedy algorithm goes like this:

1.For every arraylist, construct all subarraylists possible and add them to an array.Allow no duplicates.
2.For every subarraylist, count in how many arraylists is contained and keep that in an array.
3.Select the subarraylist with maximum appearances in arraylists.
4.Add this subarraylist in the solution set, remove all arraylists that contain this subarraylist.
5.Continue until there is no subarraylist.

This algorithm runs in short time when dealing with about 100 lists of small length, let's say up to length 8. But I need an algorithm that can handle lists of length 15 or so and subarraylists of 7,8,9 length.
I have googled for other algorithms or solutions but haven't found something good.

Thanks a lot for your answers.

Is This A Good Question/Topic? 0
  • +

Replies To: Algorithm for vertex cover problem

#2 Atspulgs   User is offline

  • D.I.C Addict

Reputation: 100
  • View blog
  • Posts: 537
  • Joined: 29-July 09

Re: Algorithm for vertex cover problem

Posted 20 May 2019 - 05:35 AM

Not sure I understand the problem at all here... but the way I understood.... I came up with this...
I am also not sure if its any faster or more efficient, but the idea is to have a list of strings rather than list of lists... and just use string patterns to see if the string contains it.

Its also a very very rough implementation and I do not advise to use it as is, its very destructive and mutates a ton of stuff. But hopefully it somewhat demonstrates the idea.
public static void main(String... args) {
        ArrayList<String> lists = new ArrayList();
        lists.add("123489742233986876146465532481215");
        lists.add("135622334355468761464659175609818");
        lists.add("235223371094466876146465324216384");
        lists.add("265227371687614646584563413483594");
        lists.add("230227371468761464653421315343004");
        lists.add("235224371075466876146465834241334");
        lists.add("574168761464651475132735271436844");
        lists.add("235224371070466876146865834241334");
        lists.add("235224371075366876149465834241334");
        lists.add("235224371046934636144646584555514");
        
        while(!lists.isEmpty()) {
            String str = lists.get(0);
            int bestRun = 1;
            String bestRunStr = str.substring(0,9);
            for(int start = 0, end = 9; end <= str.length() ;start++, end++) {
                String pattern = str.substring(start,end);
                int currentRun = 1;
                for(int i = 1; i < lists.size(); i++) {
                    if(lists.get(i).contains(pattern))
                        currentRun++;
                }
                if(currentRun > bestRun) {
                    bestRun = currentRun;
                    bestRunStr = pattern;
                }
            }
            System.out.println(bestRunStr+": "+bestRun);
            lists.remove(0);
            for(int i = lists.size()-1; i >= 0; i--) {
                if(lists.get(i).contains(bestRunStr))
                    lists.remove(i);
            }
        }
    }


This post has been edited by Atspulgs: 20 May 2019 - 05:39 AM

Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12617
  • View blog
  • Posts: 45,775
  • Joined: 27-December 08

Re: Algorithm for vertex cover problem

Posted 20 May 2019 - 06:01 AM

The Minimum Vertex Cover problem is NP-Hard. Unless P=NP, you will not find an efficient algorithm to solve this problem in general.
Was This Post Helpful? 0
  • +
  • -

#4 Larry71   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 82
  • Joined: 05-June 12

Re: Algorithm for vertex cover problem

Posted 20 May 2019 - 06:14 AM

View Postmacosxnerd101, on 20 May 2019 - 06:01 AM, said:

The Minimum Vertex Cover problem is NP-Hard. Unless P=NP, you will not find an efficient algorithm to solve this problem in general.


Yes, I know that, but I was wondering, if there was something smarter than a greedy algo, to use in my case.

Thank you.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12617
  • View blog
  • Posts: 45,775
  • Joined: 27-December 08

Re: Algorithm for vertex cover problem

Posted 20 May 2019 - 06:19 AM

Picking a maximal matching is the best approximation algorithm. A maximal matching returns at most twice the number of vertices in the minimum vertex cover. This bound is tight, as in the case of the complete bipartite graph K_{m,n}.

Also, since this isn’t terribly Java specific, I will move this to the Computer Science forum for better discussion. :)

This post has been edited by macosxnerd101: 20 May 2019 - 07:01 PM
Reason for edit:: Typo

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1