Stack Overflow
Stack Overflow

Questions tagged [vertex-cover]

32 questions
5
votes
1 answer

Algorithm for minimum vertex cover in Bipartite graph

I am trying to figure out an algorithm for finding minimum vertex cover of a bipartite graph. I was thinking about a solution, that reduces the problem to maximum matching in bipartite graph. It's known that it can be found using max flow in networ…
yrak
  • 61
  • 1
  • 3
5
votes
2 answers

minimum weight vertex cover of a tree

There's an existing question dealing with trees where the weight of a vertex is its degree, but I'm interested in the case where the vertices can have arbitrary weights. This isn't homework but it is one of the questions in the algorithm design…
john s
  • 51
  • 1
  • 3
3
votes
1 answer

Networkx min_weighted_vertex_cover in python returns whole set instead of vertex cover

I have an adjacency matrix A with nodes = {0, 1, 2, 3, 4, 5} A = [[0,1,1,0,0,0],[1,0,1,1,0,0],[1,1,0,0,1,0],[0,1,0,0,1,1],[0,0,1,1,0,0],[0,0,0,1,0,0]] I want to find the minimum weight vertex cover of this graph. I converted this adjacency matrix…
MD Abid Hasan
  • 339
  • 1
  • 3
  • 15
2
votes
1 answer

Find minimun Vertext-Cover using a ternary tree

I found some algorithms to find a minimun Vertex-Cover like using a binary search tree but I read that using a ternary tree is even better. But i can't find any info about it or think of an algorithm for it. Does somebody know how it can be done?
Emanuel Dementei
  • 23
  • 4
2
votes
1 answer

Theoretical computer science: is this problem related to vertex cover?

I have the following problem that seems to share some similarities to the vertex cover problem. We have a directed graph G=(V,E) with |V| vertices and |E| edges. Let us imagine that a vertex represents a person and that an edge from vertex A to…
SimpleProgrammer
  • 259
  • 3
  • 9
2
votes
0 answers

optimization in brute force vertex cover algorithm

I'm writing a brute-force algorithm to solve vertex cover like this: BruteForceVertexCover( Graph G = (V,E) ){ for size= 1 ... |V| vector v = {0...size-1} do{ if(test(G, v)) return v; //test if v covers G …
Daniel
  • 7,357
  • 7
  • 32
  • 84
2
votes
1 answer

Give an efficient greedy algorithm that finds an optimal vertex cover for a tree in linear time

I'm trying to work on this problem... Below mentioned is one algorithm..i figured out.. Input a graph select a vertex with highest degree of matching with all the other nodes. Remove the edges that are incident on this node. Add the selected…
sam
  • 83
  • 1
  • 9
1
vote
0 answers

Comparing Greedy, Pricing Algorithm, and LP-based Rounding for Vertex Cover Problem

I am working on the Vertex Cover problem and trying to compare the performance of three different algorithms: Greedy (GRY), Pricing Algorithm (PA), and LP-based Rounding (LR). Specifically, I want to compare them over randomly generated instances…
the weeknd
  • 11
  • 2
1
vote
1 answer

representive Vertex cycle cover

This problem may be related to this post. This problem also asked here but with a different taste. Consider an (undirected) square graph with a periodic boundary condition. Then find a complete cycle graph with length equal to 4. now I want to…
Rasoul-Ghadimi
  • 111
  • 4
1
vote
1 answer

A (Possible) Counterexample to a Common Minimum Vertex Cover on a Tree Algo and My Approach

There have been many posts in the past regarding this topic from a quick search on the site, many of which use this dynamic programming recurrence: C(x) = min(1 + sum (C(i) for i in x's children), len(x's children) + sum(C(i) for i in x's…
Lionblaze16
  • 23
  • 1
  • 7
1
vote
0 answers

Reductions from Vertex Cover to LP

I want to reduce the vertex cover problem to a specific decision problem. This decision problem is the following: I have a nxn matrix A, a vector b in R^n, and a positive integer k. Does there exists a vector x in R^n with at most k non-zero…
cs_user2017
  • 127
  • 1
  • 2
  • 12
1
vote
2 answers

Show that the heuristic solution to vertex cover is at most twice as large as the optimal solution

The heuristic solution that I've been given is: Perform a depth-first-search on the graph Delete all the leaves The remaining graph forms a vertex cover I've been given the question: "Show that this heuristic is at most twice as large as the…
jarrad_obrien
  • 391
  • 1
  • 4
  • 15
1
vote
1 answer

A variant of the minimum vertex cover

In my research I confront a variant of the vertex cover problem as follows: Given a graph G, a vertex v and a number k, to decide whether G has a vertex cover of size k that contain v. I have search all over literature and could not find a similar…
user12529
  • 19
  • 1
0
votes
0 answers

Vertex cover of size |v| - 5 P OR NPC

Let L to be all undirected graphs which has Vertex Cover of exact size |v| - 5. Is L P OR NPC? I'm totally confused, how can I prove that? Vertex Cover is NPC problem but what about now?
StarFish12
  • 1
0
votes
0 answers

minimum weight vertex cover of a tree by algorist.com

While getting through Algorithm Design Manual (by Skiena) I have faced the minimum weight vertex cover problem. Though I am aware of the DP solution for this problem algorist.com states another one through two coloring technique. It states the…
Rauf
  • 312
  • 3
  • 16
1
2 3