Minimum vertex cover and odd cycles

Suppose we have a graph $ G$ . Consider the minimum vertex cover problem of $ G$ formulated as a linear programming problem, that is for each vertex $ v_{i}$ we have the variable $ x_{i}$ , for each edge $ v_{i}v_{j}$ we have the constraint $ x_{i}+x_{j}\geq 1$ , for each variable we have $ 0\leq x_{i}\leq 1$ and we have the objective function $ \min \sum\limits_{1}^{n}{x_{i}}$ . We say such a linear programming problem LP. Note that it is NOT an integer linear programming problem.

We find a half integral optimal solution of LP that we say $ S_{hi}$ . For each variable $ x_{i}$ that takes value 0 in $ S_{hi}$ , we add the constraint $ x_{i}=0$ to LP.

For each odd cycle of $ G$ , add to LP the constraint $ x_{a}+x_{b}+x_{c}+…+x_{i}\geq \frac{1}{2}(k+1)$ where $ x_{a},x_{b},x_{c},…,x_{i}$ are the vertices of the cycle and $ k$ is the number of vertices of the cycle. We find a new optimal solution of LP that we say $ S$ .

If $ x_{i}$ is a variable that takes value $ 0.5$ in $ S_{hi}$ and value $ \gt 0.5$ in $ S$ , can we say that there is at least a minimum vertex cover of $ G$ that contains the vertex associated to $ x_{i}$ ?

The idea behind the question: in an odd cycle $ c$ with $ k$ vertices, the number of vertices needed to cover the cycle is $ \frac{1}{2}(k+1)$ , therefore for each odd cycle we add to LP the constraint $ x_{a}+x_{b}+x_{c}+…+x_{i}\geq \frac{1}{2}(k+1)$ . If in $ S_{hi}$ the sum of the variables of $ c$ is $ \frac{k}{2}$ (that is all the variables of $ c$ take value $ \frac{1}{2}$ ), then in $ S$ at least a variable $ x_{i}$ of $ c$ takes vale $ \gt \frac{1}{2}$ and the vertex associated to $ x_{i}$ belongs to at least a minimum vertex cover of the given graph.

Greedy algorithm for vertex cover

Given a graph $ G(V, E)$ , consider the following algorithm:

  1. Let $ d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $ d\geq 1$ )
  2. Let $ v$ be one of the vertices with degree equal to $ d$
  3. Remove all vertices adjacent to $ v$ and add them to the proposed vertex cover
  4. Repeat from step 1. until in $ G$ there are only vertices with degree $ 0$ (no edges in the graph)

At the end the removed vertices are a vertex cover of the given $ G(V, E)$ , but is it a minimum vertex cover? Is there an example where the algorithm does not find a minimum vertex cover?

Sending light data from Vertex Shader to Pixel Shader?

We have a pixel shader constant buffer that contains the light data for the item that is currently rendered.

To implement tangent space normal mapping, i would need to transform each light into tangent space.

Is it a valid approach to instead bind the light data to the vertex shader and then send the transformed Light Data to the pixel shader since the vertex shader runs less frequently than the pixel shader?

As a side note: I am using forward rendering with a limited light count.
Our pixel shader constant buffer looks like this:

struct RendererLight {     float3 Position;     float3 Color;     float3 Direction;     float Intensity;     float In;     float Out;     float Range; };  cbuffer LightsBuffer : register(b2) {     RendererLight Lights[8];     uint NumLights; }; 

Finding an MST with one adding and removing vertex operation

I am facing the following problem: Given an undirected complete Euclidean weighted graph $ G(V, E)$ and its MST $ T$ . I need to remove an arbitrary vertex $ v_i \in V(G)$ , and given a vertex $ v_j \notin V(G)$ , I have to calculate the MST of $ G^{‘}((V(G) \backslash \{v_i\})\cup\{v_j\}, (E\backslash\{(v_i, v_k): v_k \in V(G)\})\cup\{(v_k, v_j): v_k \in V(G^{‘})\})$ , i.e, the graph $ G$ with the vertex $ v_j$ (and its respective edges) and without the vertex $ v_i$ (and its respective edges). To solve this, we can apply some well-know MST algorithms, such as Prim’s, Kruskal’s, Borukva’s algorithm. Neverthless, if we do this we would not use the already existing MST $ T$ , i.e., we would calculate a new whole MST. So, I would like to know if there is any way to reuse the existing MST $ T$ .

There are two a similar question to this here (with edges, considering only the removing of them), and here (with vertex, considering only the adding of them).

How can I generate a random sample of unique vertex pairings from a undirected graph, with uniform probability?

I’m working on a research project where I have to pair up entities together and analyze outcomes. Normally, without constraints on how the entities can be paired, I could easily select one random entity pair, remove it from the pool, then randomly select the next entity pair.

That would be like creating a random sample of vertex pairs from a complete graph.

However, this time around the undirected graph is now

  • incomplete
  • with a possibility that the graph might be disconnected.

I thought about using the above method but realized that my sample would not have a uniform probability of being chosen, as probabilities of pairings are no longer independent of each other due to uneven vertex degrees.

I’m banging my head at the wall for this. It’s best for research that I generate a sample with uniform probability. Given that my graph has around n = 5000 vertices, is there an algorithm that i could use such that the resulting sample fulfils these conditions?

  1. There are no duplicates in the sample (all vertices in the graph only is paired once).
  2. The remaining vertices that are not in the sample do not have an edge with each other. (They are unpaired and cannot be paired)
  3. The sample generated that meets the above two criteria should have a uniform probability of being chosen as compared to any other sample that fulfils the above two points.

There appear to be some work done for bipartite graphs as seen on this stackoverflow discussion here. The algorithms described obtains a near-uniform sample but doesn’t seem to be able to apply to this case.

Why minimum vertex cover problem is in NP

I am referring to the definition of the minimum vertex cover problem from the book Approximation Algorithms by Vijay V. Vazirani (page 23):

Is the size of the minimum vertex cover in $ G$ at most $ k$ ?

and right after this definition, the author states that this problem is in NP.

My question: What would be a yes certificate?

Indeed, our non-deterministic algorithm could guess a subset of vertices, denoted by $ V’$ , and we can verify if $ V’$ is a vertex cover of some cardinality in polynomial time, but how could we possibly show that $ V’$ is minimum in polynomial time?

Minimum Weighted Vertex Cover, Dynamic Programming

Problem

So my solution in my mind right now:

Let $ OPT(n, boolean)$ be the minimum vertex cover rooted at vertex n that includes that vertex if boolean is true, false otherwise.

So my idea is:

If a vertex is not included, any edges leading away from it, their vertices are to be part of the vertex cover. $ OPT(n, F) = OPT(n.left, T) + OPT(n.right, T)$

If a vertex is included, it can or can not be included, the vertex at the other end of an edge. $ OPT(n, T) = min\{OPT(n.left, T) + OPT(n.right, T), OPT(n.left, F) + OPT(n.right, F), OPT(n.left, F) + OPT(n.right, T), OPT(n.left, T) + OPT(n.right, F)\} + n.weight $

Then we can solve this problem with $ min\{OPT(root, T), OPT(root, F)\}$

Is this the right idea? Is there anything I might be missing? If so, what would be the correct approach?

NPC PROBLEM minimum sum of vertex coloring

For a graph G and a legal vertex-colouring ψ : V(G)→N of G,

let σψ(G) be the sum of ψ(v),

and set σ(G):=min σψ(G),

where the minimum ranges over all valid vertex colourings of G.

Prove that {(G,k): σ(G)≤ k}∈ NPC.

I thought of reduction from subset-sum but my problem is with the min and not with the sum, I don’t understand how to do a reduction to check the minimum. I got a hint to do a reduction from 3-NAE-SAT but I don’t understand how. would appreciate some help. even some source I can read about this problem if you know about something.