Graph Theory Problems

A decision problem can be both in P and NP sets.

NPC is a subset of NP-hard problems.

A problem can be proven to be NPC by reducing it to a known NPC problem.

A Hamiltonian cycle is a cycle that visits each vertex at least twice.

A vertex cover of a graph is a set of edges such that each vertex is incident to at least one edge of this set.

3-coloring a planar map is a problem that can be solved in polynomial time.

NP stands for 'not polynomial'.

A polynomial-time decision algorithm is used to verify solutions in NP problems.

P is a subset of NP (P ⊆ NP).

The question of whether P = NP is still an open problem.

A nondeterministic Turing machine can explore many paths of computation in parallel.

A polynomial-time decision algorithm can be used to decide whether a given integer is composite.

All the algorithms studied in CIS 606 have a worst-case running time of O(nk), where k is a constant.

A decision problem always has a feasible solution with the best (minimum or maximum) value.

A polynomial time algorithm can solve all problems.

The Knapsack problem is an example of a decision problem.

Dynamic programming is a technique used to solve decision problems.

Determining whether a number is prime is a decision problem.

Graph Problems

3-COLOR problem: Given a planar map, can it be colored using 3 colors so that no adjacent regions have the same color?
VERTEX COVER problem: Given a graph G(V,E) and a positive integer k, find a vertex cover of size at most k
HAMILTONIAN CYCLE problem: Given an undirected graph, is there a Hamiltonian cycle in this graph?

NP-Completeness

NPC problem: A problem B is NPC if B is in NP and every problem in NP can be reduced to B in polynomial time
To prove that a problem B is NPC: B is in NP, and there is a polynomial transformation from a known NPC problem A to B

P and NP

P: a set of decision problems that can be solved in polynomial time
NP: a set of decision problems that can be verified in polynomial time
NP is a subset of NP and as hard as other problems in NP
NP-Hard: the set of problems that every NP problem can be reduced to one of it

Decision Problems

Decision Problem: a problem of determining an answer to a class of yes/no questions
Examples: given a graph G, vertices u and v, an integer k, does a path exist from u to v consisting of at most k edges?; does a graph have a path that goes through every node exactly once?; is the number x prime?
A solution to a decision problem is given by an algorithm that answers yes or no

Optimization Problems

Optimization Problem: the answer of the problem is a feasible solution with the best (minimum or maximum) value
Examples: knapsack problem, single-source shortest path, maximum flow, dynamic programming, divide-and-conquer, prune-and-search

Test your knowledge of graph theory concepts, including graph coloring and vertex cover problems. Solve exercises and quizzes to improve your understanding of these fundamental computer science topics.