NP-Completeness

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Verify whether 'path' is a Hamiltonian path in an undirected graph G.
5
// G: adjacency list for vertices 0..n-1
6
// path: a permutation of 0..n-1 representing the claimed Hamiltonian path
7
// Returns true if path visits each vertex exactly once and each consecutive
8
// pair in 'path' is connected by an edge in G.
9
bool verifyHamiltonianPath(const vector<vector<int>>& G, const vector<int>& path) {
10
    int n = (int)G.size();
11
    if ((int)path.size() != n) return false;
12
13
    // Build adjacency sets for O(1) edge-existence queries
14
    vector<unordered_set<int>> adj(n);
15
    for (int u = 0; u < n; ++u) {
16
        for (int v : G[u]) adj[u].insert(v);
17
    }
18
19
    // Check that 'path' is a permutation of 0..n-1 (no repeats, all present)
20
    vector<int> seen(n, 0);
21
    for (int v : path) {
22
        if (v < 0 || v >= n) return false; // invalid vertex index
23
        if (seen[v]) return false;         // duplicate vertex
24
        seen[v] = 1;
25
    }
26
27
    // Check adjacency along the path
28
    for (int i = 0; i + 1 < n; ++i) {
29
        int u = path[i], v = path[i + 1];
30
        if (!adj[u].count(v)) return false; // missing required edge
31
    }
32
    return true;
33
}
34
35
int main() {
36
    ios::sync_with_stdio(false);
37
    cin.tie(nullptr);
38
39
    // Example graph: a simple path 0-1-2-3 plus extra edges
40
    int n = 4;
41
    vector<vector<int>> G(n);
42
    auto add_edge = [&](int u, int v){ G[u].push_back(v); G[v].push_back(u); };
43
    add_edge(0,1); add_edge(1,2); add_edge(2,3); // path edges
44
    add_edge(0,2); // extra edge
45
46
    vector<int> certificate = {0,1,2,3};
47
    cout << (verifyHamiltonianPath(G, certificate) ? "YES" : "NO") << "\n";
48
49
    // A wrong certificate (repeats or missing edges)
50
    vector<int> bad = {0,2,1,3};
51
    cout << (verifyHamiltonianPath(G, bad) ? "YES" : "NO") << "\n";
52
53
    return 0;
54
}
55

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Literal encoding: for variable x in [1..n]
5
// positive literal x  -> +x
6
// negative literal ~x -> -x
7
// A CNF clause is a vector<int> of literals (here of size exactly 3).
8
9
struct Graph {
10
    int N; // number of vertices
11
    vector<vector<int>> adj; // adjacency list
12
};
13
14
// Build the standard graph for the 3-SAT -> Clique reduction.
15
// Given m clauses (each 3 literals), create 3m vertices: one per literal.
16
// Connect vertices from different clauses if they are NOT complementary literals.
17
// A clique of size m exists iff the formula is satisfiable.
18
Graph buildCliqueReduction(const vector<vector<int>>& clauses) {
19
    int m = (int)clauses.size();
20
    Graph G; G.N = 3 * m; G.adj.assign(G.N, {});
21
22
    auto conflict = [&](int a, int b){
23
        // Return true if literals a and b are complementary (x and ~x)
24
        return a == -b;
25
    };
26
27
    // Map (clause i, position j) -> vertex id v = 3*i + j
28
    auto vid = [&](int i, int j){ return 3 * i + j; };
29
30
    // Build edges between literals from different clauses when not in conflict
31
    for (int i = 0; i < m; ++i) {
32
        for (int j = 0; j < 3; ++j) {
33
            for (int i2 = i + 1; i2 < m; ++i2) {
34
                for (int j2 = 0; j2 < 3; ++j2) {
35
                    int a = clauses[i][j];
36
                    int b = clauses[i2][j2];
37
                    if (!conflict(a, b)) {
38
                        int u = vid(i, j), v = vid(i2, j2);
39
                        G.adj[u].push_back(v);
40
                        G.adj[v].push_back(u);
41
                    }
42
                }
43
            }
44
        }
45
    }
46
    return G;
47
}
48
49
// Check if there exists a clique of size m by selecting exactly one vertex per clause
50
// ensuring pairwise adjacency (this is tailored to the reduction structure).
51
bool existsCliqueSizeM(const Graph& G, const vector<vector<int>>& clauses) {
52
    int m = (int)clauses.size();
53
    // Precompute adjacency as bitsets for speed on small instances
54
    vector<vector<char>> adjmat(G.N, vector<char>(G.N, 0));
55
    for (int u = 0; u < G.N; ++u) for (int v : G.adj[u]) adjmat[u][v] = 1;
56
57
    vector<int> choice(m, -1); // chosen literal index j in clause i
58
59
    function<bool(int)> dfs = [&](int i) -> bool {
60
        if (i == m) return true; // chosen one literal per clause, all consistent so far
61
        for (int j = 0; j < 3; ++j) {
62
            int u = 3 * i + j;
63
            bool ok = true;
64
            // check adjacency with all previously chosen vertices
65
            for (int ip = 0; ip < i && ok; ++ip) {
66
                int up = 3 * ip + choice[ip];
67
                if (!adjmat[u][up]) ok = false;
68
            }
69
            if (ok) {
70
                choice[i] = j;
71
                if (dfs(i + 1)) return true;
72
                choice[i] = -1;
73
            }
74
        }
75
        return false;
76
    };
77
    return dfs(0);
78
}
79
80
int main() {
81
    ios::sync_with_stdio(false);
82
    cin.tie(nullptr);
83
84
    // Example formula: (x1 ∨ ¬x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ x4) ∧ (x2 ∨ x3 ∨ ¬x4)
85
    // Variables are 1-indexed in literals; negative for negation.
86
    vector<vector<int>> clauses = {
87
        {+1, -2, +3},
88
        {-1, +2, +4},
89
        {+2, +3, -4}
90
    };
91
92
    Graph G = buildCliqueReduction(clauses);
93
    bool sat_via_clique = existsCliqueSizeM(G, clauses);
94
    cout << (sat_via_clique ? "SAT" : "UNSAT") << "\n";
95
96
    // A clearly UNSAT small instance: (x1) ∧ (¬x1) duplicated to fit 3-SAT form
97
    vector<vector<int>> clauses2 = {
98
        {+1, +1, +1},
99
        {-1, -1, -1}
100
    };
101
    Graph G2 = buildCliqueReduction(clauses2);
102
    cout << (existsCliqueSizeM(G2, clauses2) ? "SAT" : "UNSAT") << "\n";
103
104
    return 0;
105
}
106

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// 2-approximation for Vertex Cover on an undirected graph.
5
// Repeatedly pick an arbitrary uncovered edge (u,v), add both endpoints to the cover,
6
// and remove all incident edges. This guarantees a factor-2 approximation.
7
8
vector<int> vertexCover2Approx(int n, const vector<pair<int,int>>& edges) {
9
    vector<vector<int>> adj(n);
10
    vector<pair<int,int>> E = edges;
11
    vector<char> covered(n, 0);
12
13
    // Track which edges remain uncovered
14
    vector<char> removed(E.size(), 0);
15
16
    vector<char> inCover(n, 0);
17
    // While there exists an uncovered edge, add both endpoints
18
    for (size_t i = 0; i < E.size(); ++i) {
19
        if (removed[i]) continue;
20
        int u = E[i].first, v = E[i].second;
21
        // Add both endpoints to cover
22
        inCover[u] = inCover[v] = 1;
23
        // Remove all edges incident to u or v
24
        for (size_t j = i; j < E.size(); ++j) {
25
            if (removed[j]) continue;
26
            int a = E[j].first, b = E[j].second;
27
            if (a == u || a == v || b == u || b == v) removed[j] = 1;
28
        }
29
    }
30
31
    vector<int> cover;
32
    for (int v = 0; v < n; ++v) if (inCover[v]) cover.push_back(v);
33
    return cover;
34
}
35
36
int main() {
37
    ios::sync_with_stdio(false);
38
    cin.tie(nullptr);
39
40
    int n = 6;
41
    vector<pair<int,int>> edges = {
42
        {0,1},{1,2},{2,3},{3,4},{4,5},{0,5},{1,4}
43
    };
44
45
    vector<int> cover = vertexCover2Approx(n, edges);
46
    cout << "Vertex cover (2-approx) size = " << cover.size() << "\n";
47
    cout << "Vertices:";
48
    for (int v : cover) cout << ' ' << v;
49
    cout << "\n";
50
51
    return 0;
52
}
53