First of all, I want to mention that this is my **homework**. However, to solve my problem I can use any literature I want.

Even though I think that problem is clear from its name, I will give it description: *"For given undirected graph G and given integer k, does G contain totally connected (clique) subgraph of size k or totally disconnected subgraph (independent set) of size k."*

I know about polynomial reductions from `3-SAT`

to `CLIQUE`

and from `3-SAT`

to `INDEPENDENT-SET`

. (http://mlnotes.com/2013/04/29/npc.html) However, I have problem with this one because I cannot combine those two reductions. I also tried reduction from `CLIQUE`

to `CLIQUE-OR-INDEPENDENT-SET`

but without much success.

So I would really appreciate any hints!

Thanks in advance.

Answer:

I found out reduction from problem `INDEPENDENT-SET`

to `CLIQUE-OR-INDEPENDENT-SET`

. All you need to do is to add `n`

isolated vertices to graph `G`

(which is an instance of `INDEPENDENT-SET`

and has `n`

vertices). Let call this newly created graph `G'`

(instance of `CLIQUE-OR-INDEPENDENT-SET`

). Then it is not hard to prove that `G`

has `k`

independent-set iff `G'`

has `n+k`

independent-set of clique (since, by construction, it cannot have `n+k`

clique).

cuda,fortran,reduction

I am trying to perform reduction in CUDA Fortran; what I did so far is something like that, performing the reduction in two steps (see the CUDA kernels below). In the first kernel I am doing some simple computation and I declare a shared array for a block of threads...

c,cuda,atomic,reduction

I have the following algorithm: __global__ void Update(int N, double* x, double* y, int* z, double* out) { int i = blockIdx.x * blockDim.x + threadIdx.x; if (i < N) { x[i] += y[i]; if (y[i] >= 0.) out[z[i]] += x[i]; else out[z[i]] -= x[i]; } } Important to note...

computation-theory,turing-machines,np-complete,np,decidable

any expert could help me why this sentence is True? if L ∈ NP and L ≤p 3−SAT (i.e: reduce L to 3-SAT in poly time) then L is NP-Complete. ...

c++,opencl,reduction

I have recently started working with OpenCL in C++ and I'm trying to fully understand how to use 2D and 3D NDRange. I'm currently implementing Inverse Distance Weighting in OpenCL, but my problem is general. Below is the serial function to compute the weights and it consists of a nested...

matlab,data,increment,reduction,periodic-processing

it's some time i was thinking about solving this problem. I have a registration of angular data (Angle(~20000,1)) variating between 0 and 355 (a potentiometer attached to a rotary testing machine), and I wanted to convert it in an incremental form, since I want the final total angular displacement. The...

c,algorithm,scheduling,reduction,sat

I have some theorical/practical problem and I don't have clue for now on how to manage, Here it is: I create a SAT solver able to find a model when one is existing and to prove the contradiction when it's not the case on CNF problems in C using genetics...

c,pointers,for-loop,openmp,reduction

I'm trying to implement dotproduct in OpenMP with large arrays allocated with malloc. However, when I use reduction(+:result) it produces different results for each program run. Why do I get different results? How can I remedy that? And how can this example be optimized? Here's my code: #include <stdlib.h> #include...

c++,openmp,shared-memory,shared,reduction

I've tried this code snippet for reduction(op:var) proof of concept, it worked fine and gave a result = 656700 int i, n, chunk; float a[100], b[100], result; /* Some initializations */ n = 100; chunk = 10; result = 0.0; for (i=0; i < n; i++) { a[i] = i...

php,lambda,reduction,array-walk

Ran into a weird situation were using array_walk() will only partially remove matches from my method, not certain exactly what is going on. I am currently using PHP v5.6.4. The issue almost seems to be that it is only removing every secondary match. The kerning function private function strip(array $exceptions)...

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...

mapping,combinatorics,computation-theory,np-complete,set-theory

This problem is similar to the "Exact Hitting Set" problem (http://en.wikipedia.org/wiki/Exact_cover#Exact_hitting_set) but with slightly different constraints. I am looking for libraries, implementations, or papers that solve the following. Say I have a set of sets S, and is initialized as follows: S = {N, O, P, E}; N = {1,...

algorithm,np-complete,subset-sum

This is a homework assignment, so any help is appreciated. I should prove that the following problem is NP-complete. The hint says that you should reduce the subset sum problem to this problem. Given a set of shapes, like the below, and an m-by-n board, decide whether is it possible...

haskell,recursion,fibonacci,reduction

I am currently looking at this function in Haskell which returns the Fibonacci number at position n fib :: Integer -> Integer fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2) Now, it compiles, returns the correct result and everything... but I don't...

reduction,np-complete,np,clique-problem,independent-set

First of all, I want to mention that this is my homework. However, to solve my problem I can use any literature I want. Even though I think that problem is clear from its name, I will give it description: "For given undirected graph G and given integer k, does...