How to cope with NP-hardness
One strategy for addressing NP-hard problems is to leverage any underlying structure of the problem to design simpler and more efficient algorithms. One example of this approach is the use of interval representations. This structure is well-known and widely used in many different areas of computer science. In this context, it is possible to solve the independent set problem in linear time, which is a significant improvement over the general case where the problem cannot be approximated in polynomial time to a constant factor, unless P = NP.
Graph searching refers to the process of traversing a graph, visiting each vertex one at a time, according to a specific method. Two commonly used methods of graph searching are Breadth-First Search (BFS) and Depth-First Search (DFS). These are considered classical techniques in the field.
Chordal graphs are sometimes referred to as triangulated graphs as well. A graph G is chordal if the largest induced cycle in G is a triangle. It is not hard to convince yourself that chordality is a hereditary property i.e. if G is chordal, so is every induced subgraph of G. Recall that a graph G is perfect if for every induced subgraph H of G: the clique number of H is the same as the chromatic number of H. In the 1960s, Claude Berge introduced the concept of perfect graphs. Since then, they have been the subject of extensive research. One of the most interesting properties of perfect graphs is that they can be used to solve many NP-hard problems efficiently using the ellipsoid method. However, despite this progress, ongoing research is still dedicated to developing combinatorial algorithms that can solve these problems without relying on the ellipsoid method. Many graph families belong to the class of perfect graphs; interval graphs for instance, permutation graphs - which you may have seen in the longest subsequence problem.
Perfect elimination order (PEO)
Structural graph theory faces a significant challenge known as graph recognition. This involves determining whether a given graph belongs to a specific class of graphs that possess a particular structure. One example of this is chordal graph recognition, which can be achieved by computing a PEO (Perfect Elimination Ordering). This is because PEOs fully characterize chordal graphs, as stated in Theorem 6. However, before exploring the complexity of computing PEOs, it is worth considering other potential uses for them.
The GreedyCOL algorithm may not always produce optimal results when applied to certain graphs. In fact, it's easy to create examples where the algorithm performs poorly. However, when provided with a "good" ordering, such as for chordal graph families, the algorithm can produce an optimal coloring as stated in the following theorem.
Theorem If s is a PEO, algorithm GreedyCOL gives an optimal coloring.
Lexicographic Breadth First Search
Lexicographic breadth first search (LexBFS) is a modified version of the Breadth-First Search (BFS) algorithm, which assigns lexicographic labels to the vertices of a graph. The lexicographic labels are assigned in a way that follows a specific ordering of the vertices, and it uses these labels to break any ties that may occur during the search. In other words, it uses a dictionary-like ordering to decide which vertex should be visited next in case of ties. This method can be particularly useful in certain graph-theoretic problems, such as finding perfect elimination orderings, which are needed for chordal graph recognition. Additionally, LexBFS also produces a linear ordering of the vertices of a graph, which can be useful in other graph-related problems.