algorithm,graph,graph-algorithm,linear-programming,np-complete , Heuristic to find the maximum weight independent set in an arbritary graph


Heuristic to find the maximum weight independent set in an arbritary graph

Question:

Tag: algorithm,graph,graph-algorithm,linear-programming,np-complete

The MWIS (Maximum weight independent set) is a NP-complete problem, so if P!=NP we cannot find a solution in a good enough time complexity.

I am looking for an algorithm that can find an approximation of the MWIS in an arbitrary graph within a good time complexity. I am currently working on a connected graph with 128 nodes and 3051 edges.

I have found this paper, but it seems that it is only working for bipartite graph with an unique MWIS.

I will be glad if anyone can help me with some references or even better with a pseudo-code of a working algorithm.


Answer:

It's possible to formulate this as the following problem. Suppose each vertex v in the graph has weight w(v). You define a variable x(v), and use some out-of-the-box linear programming solver to solve

max \sum_v w(v) x(v) (maximize the weight of chosen vertices)

subject to

x(u) + x(v) <= 1, (u, v) \in E (don't take neighbors)

and

x(v) \in {0, 1} (can only choose to take or not take a vertex)


This is a combinatorical problem (the last constraint is exponential in the number of vertices). There are two ways to continue from here:


Related:


Should checking loop conditions be counted towards total number of comparisons?


c++,algorithm,sorting,c++11
I have implemented three different sorting algorithms and now I want to confirm that my approach of counting the total number of comparisons is correct. In my mind, the number of comparisons shouldn't be tied to the conditional branches because if the condition isn't met, the comparison was still made...

Getting Wrong Answer in “Longest non regular parentheses sub-sequence ”codechef june cook off


algorithm
I attended a programming competition(it has ended now). I don't know why my solution is giving WA, I read the editorial, saw other people solution but unable to find a flaw in my solution. Obviously I am missing somewhere. Please help! Question Link My Solution My approach If the pattern...

Project Euler # 5; this solution works - but why?


c++,algorithm
The project Euler problem 5 is stated as : "2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?" Here's...

Recursive solution doesn't iterate correctly


ruby,algorithm,search,recursion
I'm working through a toy problem in Ruby: how to produce all possible 10-digit phone numbers where each successive number is adjacent to the last on the keypad. I've represented the adjacent relationships between numbers, and have a recursive function, but my method isn't iterating through the whole solution space....

Responsive axis with percentage coordinates


javascript,svg,d3.js,graph,charts
In an attempt to build a responsive scatter graph with d3.js, I'm using %-based coordinates in a 100% x 100% svg element. How can I .call(axis) and get it to layout the axis using % and not px values, so that they always fit the svg and the plotted data?...

create specific permutation of a list in python [closed]


python,algorithm,permutation
I'm trying to write a function that would input a list (of pre-determined length) and output the permutation of that list according to my choice of re-ordering. For example, suppose I have the list [1,'a',12,'b','poppy'] and I have the permutation (3,4,5,2,1) Then the function output would be a list with...

Calculating completion time of scheduled dependent tasks


python,algorithm
I am trying to calculate least completion time of a project schedule, which has n number of tasks and each task can have a dependency task. example Task ID Duration Days Dependent ID 1 10 0 2 3 0 3 6 1 4 5 2 5 10 1 Task with...

Knapsack with unbounded items


algorithm,dynamic-programming,knapsack-problem
I am familiar with the 0-1 knapsack problem and when you are given a certain number of copies from each item but I can figure out how to solve it when you are given infinite copies of each item using dynamic programming. I am trying to solve it by hand...

Removing a prior sample while using Welford's method for computing single pass variance


algorithm,math,statistics,variance,standard-deviation
I'm successfully using Welford's method to compute running variance and standard deviation as described many times on Stack Overflow and John D Cook's excellent blog post. However in the stream of samples, sometimes I encounter a "rollback", or "remove sample" order, meaning that a previous sample is no longer valid...

Read CSV and plot colored line graph


python,csv,matplotlib,graph,plot
I am trying to plot a graph with colored markers before and after threshold value. If I am using for loop for reading the parsing the input file with time H:M I can plot and color only two points. But for all the points I cannot plot. Input akdj 12:00...

Dynamic programming: how to design algorithm for when there are two factors to consider?


algorithm,optimization,dynamic-programming,frequency
I have the following problem and I only have a slight idea about it: Consider a tape storage problem. Given n files of length l1,...,ln and frequencies with which they are accessed f1,...,fn, where sum of all frequencies is 1 and 0<fi<1. "Optimal" means to minimize the average retrieval time...

Does there exist an algorithm for iterating through all strings that conform to a particular regex?


c#,regex,algorithm
I'm making a script to try and hack into an account whose login password is at least 8 characters long and includes at least 1 number, 1 special character and 1 capital letter. I will use brute force. Is there a compact, elegant and efficient way to iterate through every...

How to reduce time to find the n-th place from consecutive digits number for less than 1 second


php,algorithm,digits
I'm following the programming test, and there are questions like this From this consecutive digits: 123456789101112131415161718192021.... For example The 10th digit is 1 The 11th digit is 0 and so on What is the 1,000,000th digit? What is the 1,000,000,000th digit? What is the 1,000,000,000,000th digit? Your solution should run...

C: sorted input serials


c,algorithm
I try find out what is wrong with the program that takes n - size of serials and this same number of elements numbers. With n = 4 and numbers 1, 2, 3, 4 I get output: 1, 0, 2293428, 1990567906. Somewhere in the code something is not okey, but...

Find the shortest path sum in a matrix. Is Dijkstra not optimal for this case?


algorithm,go
I am trying to solve the following problem from project euler (please take a look at description and the example in the link, but here is the short explanation). in the matrix, find the minimal path sum from the top left to the bottom right, by moving left, right, up,...

Determining if a graph has a cycle without using DFS


algorithm,graph,cycle,dfs
I came around one of those questions in my exams: Topologocial sorting using Kahn's Algorithm requires the graph to be DAG (Directed Acyclic Graph). How can we determine if a graph contains no cycles without using DFS/BFS first? I am trying to answer that for too long now and I...

Looking for a particular algorithm for numerical integration


algorithm,numerical-methods,numerical,numerical-integration
Consider the following differential equation f(x) = g'(x) I have a build a code that spits out values of the function f(x) for the variable x, where x goes from 0 to very large. Now, I'm looking for a scheme that will analyse these values of f(x) in order to...

3 X 3 magic square recursively


c++,algorithm,math,recursion
I'm trying to find all possible solutions to the 3X3 magic square. There should be exactly 8 solutions. My code gets them all but there are a lot of repeats. I'm having a hard time tracking the recursive steps to see why I'm getting all the repeats. // This program...

Where do I find the 'Edmonds' class in networkx?


python,graph,networkx
I am using the networkx framework for graph manipulation in python 2.7. For obtaining an optimal branching (arborescence) from a directed graph, I wanted to use the Edmond's algorithm. On networkx' website, one can find an implementation of that algorithm. The class 'Edmonds' is also listed in the reference. However,...

Ranking with time weighting


python,algorithm,sorting,math
I am looking for a basic algorithm that gives more weigh to the recent reviews. So, the output value of the algorithm is mutable. For example, two reviews with exactly the same score, will have a different ranking based on the timestamp of the creation. Review_1 Score 10 creation 10/5/2014...

Longest Increasing Subsequence code in O(N)?


python,algorithm,time-complexity,longest-substring
Someone asked me a question Find the longest alphabetically increasing or equal string composed of those letters. Note that you are allowed to drop unused characters. So ghaaawxyzijbbbklccc returns aaabbbccc. Is an O(n) solution possible? and I implemented it code [in python] s = 'ghaaawxyzijbbbklccc' lst = [[] for i...

Code knight's tour using backtracking is not showing any output


c++,c,graph
This code is not giving any output. It should output a matrix of 8X8 size. #include <iostream> #define N 8 using namespace std; This function prints the matrix: void print(int arr[][N]){ int i, j; for (i = 0; i < N; i++){ for (j = 0; j < N; j++)...

Read One Input File and plot multiple


python,numpy,matplotlib,graph,plot
I am trying to read one input file of below format. Where Col[1] is x axis and Col[2] is y axis and col[3] is some name. I need to plot multiple line graphs for separate names of col[3]. Eg: Name sd with x,y values will have one line graph and...

Explain the time complexity of these grouping functions


c++,algorithm,inheritance,time-complexity
Here I have 800 derived classes of Base and a list of 8000000 objects of these types, which can be of any order. The goal is to separate the list into the 800 types as efficiently as possible. Here I have written two functions to do that. The first is...

Travels using graph


c++,algorithm,graph
Someone can help me to think in the better way to adapt Dijkstra's Algorithm in these conditions? All I thought didn't was good. Example of input: GP4578 MADRID 01:00 PORTO 02:00 IK6587 PORTO 03:00 VALENCIA 05:00 05:30 TENERIFE 08:00 AB5874 VALENCIA 05:40 BERLIM 10:00 "VALENCIA 05:00 05:30" This is a...

How to print the right hemisphere of a square matrix


c++,algorithm,matrix
I am trying to print the right hemisphere of a matrix. If we draw the main and the secondary diagonals in a matrix we see that we got 4 equal parts, the right part is called (in my algorithms textbook) the right hemisphere of a square matrix. For example, in...

Construct bipartite graph from columns of python dataframe


python,graph,dataframes,networkx
I have a dataframe with three columns. data['subdomain'], data['domain'], data ['IP'] I want to build one bipartite graph for every element of subdomain that corresponds to the same domain, and the weight to be the number of times that it corresponds. For example my data could be: subdomain , domain,...

Identify that a string could be a datetime object


python,regex,algorithm,python-2.7,datetime
If I knew the format in which a string represents date-time information, then I can easily use datetime.datetime.strptime(s, fmt). However, without knowing the format of the string beforehand, would it be possible to determine whether a given string contains something that could be parsed as a datetime object with the...

Javascript: Detailed differences between !variable and variable == false?


javascript,algorithm
I accidentally got undefined == true and undefined == false that both of them returns false. But !undefined returns true. And this is the question: What's the algorithmic difference(s) between !someVariable and someVariable == false? If i want to explain it more, type undefined == false ? 't' : 'f'...

Reverse ^ operator for decryption


c,algorithm,security,math,encryption
I'm trying to reverse the following code in order to provide a function which takes the buffer and decrypts it. void crypt_buffer(unsigned char *buffer, size_t size, char *key) { size_t i; int j; j = 0; for(i = 0; i < size; i++) { if(j >= KEY_SIZE) j = 0;...

Highlighting specific ranges on a Graph in R


r,graph,highlight
library(season) plot(CVD$yrmon, CVD$cvd, type = 'o',pch = 19,ylab = 'Number of CVD deaths per month',xlab = 'Time') if i wanted to highlight a region of the graph based on x values say from 1994-1998 how do i do this? Any thought would be appreciated Thanks....

Recursive algorithm that returns a bool when checking if array[i] == i (must be O(log n))


c++,arrays,algorithm,recursion
I'm trying to write a recursive algorithm that returns true if at least one array[i] == i. And false if there is no array[i] = i. Also, the parameters needed are (int * arr, int start, int end). So i'll be traversing the array with a pointer. For example: int...

strcmp performance in C


c,string,algorithm,data-structures
int myStrCmp (const char *s1, const char *s2) { const unsigned char *p1 = (const unsigned char *)s1; const unsigned char *p2 = (const unsigned char *)s2; while (*p1 != '\0') { if (*p2 == '\0') return 1; if (*p2 > *p1) return -1; if (*p1 > *p2) return 1;...

How to give mathemarical proof or support my answer through reasoning as a general case?


algorithm
You are managing a software project that involves building a computer-assisted instrument for medical surgery. The exact placement of the surgical knife is dependent on a number of different parameters, usually at least 25, sometimes more. Your programmer has developed two algorithms for positioning the cutting tool, and is seeking...

Algorithmic big o order of growth code


algorithm,discrete-mathematics
I'm doing an online course and i'm stuck on this question. I know there are similar questions but they don't help me. What is the order of growth of the worst case running time of the following code fragment as a function of N? int sum = 0; for (int...

Assigning a label to a created node in Neo4jClient


c#,graph,neo4j,neo4jclient
I want to create some nodes of type Person and Books using Neo4jClient. To do that, I have class Person like this: Public Class Person { Public String Name; } To create node, I have written something like this: Var RefA = client.Create(new Person(){Name ="John"}); (Client -> GraphicClient) When I...

Algorithm for [inclusive/exclusive]_scan in parallel proposal N3554


c++,algorithm,parallel-processing,c++14
Proposal N3554 (A Parallel Algorithms Library) for C++14, proposes (among other things), what seem to be parallel versions of the current std::partial_sum, e.g.: template< class ExecutionPolicy, class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator inclusive_scan( ExecutionPolicy &&exec, InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); With the explanation Effects: For each...

Binary Search - Best and worst case


algorithm,data-structures
In an exam I see a question: Which one of the following is true? For a binary search, the best-case occurs when the target item is in the beginning of the search list. For a binary search, the best-case occurs when the target is at the end of the search...

R / SQL /Python : Extracting connected components from node-edge pairs


python,sql,r,graph,connected-components
I struggle to come up with a title that describes what I'm trying to solve, so please comment if you have a better title! The solution can be in R, Python, or SQL (Aster TeraData SQL to be exact, though a solution any SQL language is very helpful for learning...

Airport travels using graph


c++,graph,shortest-path
Can someone help me to think of a better way to adapt Dijkstra's Algorithm in these conditions? All I thought of so far wasn't good. Example of input: GP4578 MADRID 01:00 PORTO 02:00 IK6587 PORTO 03:00 VALENCIA 05:00 05:30 TENERIFE 08:00 AB5874 VALENCIA 05:40 BERLIM 10:00 "VALENCIA 05:00 05:30" This...

Disconnect all vertices in a graph - Algorithm


algorithm,graph
I am looking for an algorithm that finds minimal subset of vertices such that by removing this subset (and edges connecting these vertices) from graph all other vertices become unconnected (i.e. the graph won't have any edges). Is there such algorithm? If not: Could you recommend some kind of heuristics...

What is this algorithm mapping coordinates to numbers called?


algorithm,coordinates,coordinate-systems,coordinate
I'm writing a program for visualizing crystals. As a part of the program, I have to generate all different basic points in a lattice structure. For those that aren't familiar with crystallography, you can find the most general cases of these structures here: https://en.wikipedia.org/wiki/Hermann%E2%80%93Mauguin_notation#Lattice_types The problem was that I wanted...

Given length L find the shortest string formed only of as & bs >= L such that adding some character (Either a or b) doesn't produce a new palindrome


string,algorithm,palindrome
Given length L find the shortest string >= L formed only of as & bs such that adding some character (Either a or b) doesn't produce a new palindrome substring (never seen before palindrome) For example for L = 1 there is the string aabbaba, adding "a" to it to...

Best way to extract ODD digits from a binary number


algorithm,bit-manipulation
Given a 64 bit number, I need to extract every other bit from it, and convert it into a number: decimal: 357 binary: 0000 0001 0110 0101 odd bits: 0 0 0 1 1 0 1 1 decimal: 27 Any idea of a good algorithmic way to do it? And...

How can I declare a counter inside of my recursive function? (Additive Persistence: Coderbyte)


javascript,algorithm,recursion
While working through some Coderbyte challenges, I was able to solve the following problem recursively, but was hoping to get some feedback on how I can improve it. Have the function AdditivePersistence(num) take the num parameter being passed which will always be a positive integer and return its additive persistence...

algorithm to get all combinations of splitting up N items into K bins


algorithm,recursion,permutation
Assuming I have a list of elements [1,2,3,4,] and a number of bins (let's assume 2 bins), I want to come up with a list of all combinations of splitting up items 1-4 into the 2 bins. Solution should look something like this [{{1}, {2,3,4}}, {{2}, {1,3,4}}, {{3}, {1,2,4}}, {{4},...

Understanding Big-Ω (Big-Omega) notation


algorithm,big-o
I was doing some reading on logarithms and the rate of growth of the running time of algorithms. I have, however, a problem understanding the Big-Ω (Big-Omega) notation. I know that we use it for 'asymptotic lower bounds', and that we can express the idea that an algorithm takes at...