7. Brute force
Deadline: 2022-04-05 24:00
- One possible way to solve NP-complete problems is to use “brute
force.” In this approach, we generate all possible witnesses
according to the input and check them one by one. If we find a
good witness, then the input is in the tested language, but if
none of the generated witnesses are good, then the input is
certainly not an element of the language. Of course, we cannot
expect this procedure to solve the problem in polynomial time.
- The language \(\textrm{CLIQUE}\) consists of pairs \((G, k)\) where
a simple non-directed graph \(G\) has a \(k\)-clique (a
\(k\)-element complete subgraph). It is a good
witness for \((G, k) \in \textrm{CLIQUE}\)
if there is a set \(F \subseteq V(G)\) which is a \(k\)-element
complete subgraph. If \(|V(G)| = n\), then it is possible to decide in
\(O(n^2)\) time on a set \(F\) of points if every two points is
joined by an edge.
- Write a program that determines whether \((G, k)\) is in the
\(\textrm{CLIQUE}\) language. \(G\) and \(k\) is described in a file
given in a command line argument. If you find a
\(k\)-clique, write it to the standard
output. Otherwise indicate that “there is no \(k\)-clique.”
- In the file
clique.py
a function
read_graph is given
which read the edges of \(G\) and the number \(k\) from the file
given in the command line argument. The format of the input file
and the return values described in the docstring
of the source code.
- Generate all \(k\)-element combinations of the vertex set
\(\{0, 1, \ldots, n - 1\}\) of the graph and decide if any of
them is a clique. Stop the search if you find a clique and write
it to the standard output. If there is no clique
indicate on the standard output that “there is no \(k\)-clique”
in the graph.
- To help coding we propose the function
combinations of the itertools
package.
- Try your program with the next files! For the inputs belonging
to the language \(\textrm{CLIQUE}\) we give a clique as a
verifier. Of course any other clique will be accepted as
a witness.