8   On Difficulty of Graph Problems
How can one compare between easy and hard graph problems? How can one assess the difficulty of a newly formulated problem?
Brief outline of this lecture
• Examples of easily (and efficiently) solvable graph problems.
• Colouring and Hamiltonicity - two traditional hard grah problems.
• How to assess difficulty of a problem - using problem reductions.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
8.1   Some Easily Solvable Problems
During the course, we have provided several really simple algorithmic solutions for basic questions on graphs, e.g.:
• testing connectivity and finding the connected components, □
• computing the distance and a shortest path in a graph, □
• computing a minimum spanning tree in a weighted graph, □
• finding a maximum flow and a minimum cut in a network, □
• finding a maximum matching in a bipartite graph, □
• testing 2-colourability of graphs, □
• testing isomorphism of trees. □
Well, that was about algorithm design, and what about the theory side?
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
Nice characterizations of problems
Such "easily solvable" problems typically come hand in hand with nice theoretical characterizations of the solutions, and of their existence in greater generality. □
For example...
• Good characterizations of problems; either
- we have got an obvious or easily verifiable solution, or
- we can find an obvious or easily verifiable obstacle. □
Recall some examples of good characterizations:
• For connectivity in a graph; either
- we can find an x-y walk (or path) in the graph, or
- a vertex subset X CV such that x G X, y ^ X and no edge leaves X. □
• For maximum matching in a bipartite graph; either
- we can find a matching with k edges, or
- we have got a vertex cover with < k vertices. □
• For 2-colourability of a graph; either
- we can find a proper 2-colouring (bipartition), or
- a cycle of an odd length.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
On the dark side
For problems which are "hard to solve", nice theoretical characterizations of their solutions typically do not (and cannot) exist, e.g.; □
• for the 3-colourability problem one can easily verify that a given colouring is proper (or not), but that is not sufficient! □
• there is no known good way of showing that a 3-colouring does not exist in a given graph, other than trying all possibilities.
Even though we have no such directly provable relation, an absence of a nice characterization of the solutions indicates hardness of a problem... □
Much worse, for some other hard graph problems the correct solution is even not easily verifiable; □
• considering, say, 4-choosability of a given graph, how can one verify that for all possible assignments of lists of 4 colours a proper colouring does exist?
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
More Involved Problems
Obviously, life is not always as easy as in the previous slides... □
There exist graph problems for which an efficient algorithmic solution exists, but both the algorithms and related theoretical characterizations of their solutions are rather involved, e.g.; □
• a maximum matching in general graphs, and maximum weighted matching, □
• testing planarity and finding a plane drawing in linear time
(interestingly, the best algorithms are not dir. related to the Kuratowski thm.),
• the isomorphism of planar graphs in linear time (needs planarity as a tool). □
Though not so often, there are examples of problems having theoretically fast algorithms, but which are practically unusable, e.g.; □
• the isomorphism of 3-regular graphs, □
• testing graph embeddability in (fixed) higher surfaces,
• possibility to draw a graph in the plane with, say, < 100 edge crossings, □
• a graph minor testing, and consequently all minor-closed decision properties.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
Strange case of the isomorphism
partial obstacles practically very fast randomized obstacle
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
8.2   Colouring and Hamiltonicity
See Lecture 6.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
Hamiltonian Graphs
Another typical hard graph question is that about an existence of a cycle or a path through all the vertices of the given graph (an older and simplified setting of a "travelling salesman"):
Definition: A cycle C in a graph G is a Hamiltonian cycle if C spans all vertices of G. Analogously, a Hamiltonian path P in G is a path in G spanning all the vertices. □ A graph G is Hamiltonian if G contains a Hamiltonian cycle. The same terminology applies in the case of digraphs with dir. cycles and paths. □
The Hamiltonian cycle problem is also related to some attempts to solve the 4 colour problem: precisely, if every 3-regular planar graph was Hamiltonian, then the 4 colour theorem would follow easily. nWell, but this claim later turned out not to be true...
□
!HhmiCtonian ajcCe /path = 9{amiCti
zsta
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
Hamiltonian tournaments
Definition: A digraph G is called a tournament if for every vertex pair u,v G V(G), a/i), exactly one of the arcs (u, v), (v, u) is in G.
In other words, a tournament on n vertices results by arbitrarily orienting each edge of Kn. □
Proposition 8.1. Every tournament G contains a Hamiltonian (directed) path. Proof: We apply a straightforward induction on n, the number of vertices of G. □
• If n G {1, 2}, then G itself is a directed path.
• Assume n > 3, and choose vq G V(G) arbitrarily. Form Go — G\vo by deleting the vertex t>o, and let P — (t>i, t>2,..., be a dir. Hamiltonian path in Go (in this order of vertices), which exists by the induction assumption. □
• If (vn-i,vo) G E(G), then P with vq at the end is a Ham. path in G. Similarly, if {vq,v\) G E(G), then P prefixed with vq is a Ham. path in G. □
Otherwise, let j G {1,..., n — 1} be the least index such that {vq,vj) G E(G), and hence {vj-\,vq) G E(G). Then (t>i,..., fj-i, t>o, Vj, ■ ■ ■, vn-i) is a Ham. path in G.
C
tournament = tumaj (spec, druh or. grafu)
Petr Hlinený,   Fl MU Brno,  2014 9/24 Fl: MAOIO: Difficulty of Graph Problems
Proposition 8.2. A tournament G contains a Hamiltonian (directed) cycle if, and only if, G is strongly connected.
Proof:
□
Petr Hliněný.   Fl MU Brno. 2014
_
dmři or. grafu)
_
Dirac's theorem
Theorem 8.3. Every graph G on n > 3 vertices and with minimum degree > n/2 is Hamiltonian. □
Proof (a sketch): Let P C G be a longest possible path in the graph G, such that the vertices on P occur in this order; (uo, u\,..., u^).   It is easy to claim:
• every neighbour of uq or Uk belongs to P (since otherwise we prolong P),
• since dc(uo),dc(uk) > \n > \{k + 1), by the pigeon-hole principle, there is 0 < i < k such that Mo^i+i € E(G) and UkUi e E(G) (draw a picture), □
• consequently, we have got a cycle C C G on V(P) in the cyclic order of vertices
(u0,Ui+i,Ui+2, ■ ■ ■ ,Uk,Ui,Ui-i, . . . ,U0). □
That is all since, if there was a vertex x G V(G) \ V(C) (missed by C), then x would have a neighbour on C and we would get another path longer than original P, a contradiction. C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
8.3   Problem Reductions
The term polynomial reduction is formally defined in every computational complexity course. However, this course is not on complexity but on graphs, and so we stay with an informal explanation of the concept.
• Imagine that somebody asks us to solve an instance of Problem A, which we do not know how to solve, but we have a nice algorithm /solution for another Problem B.
• If we are lucky, then we can take an input of Problem A, and transform it to an input of Problem B such that a (possible) solution is preserved (meaning that we can always "decode" a solution for A from a solution for such transformed B). □
• Obviously, our tranformation should be "easy and efficient". We say that we have got a
reduction from Problem A to Problem B.
If we have got a reduction from A to B then, informally, Problem A is not harder (of at most the same difficulty) than Problem B.
From a different point of view; if we know that Problem A cannot be solved nicely, then neither can Problem B (a "hardness reduction").
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
Example 8.4. Show that the following two problems are of the same difficulty:
A: to decide whether a given graph G has a Hamiltonian path,
B: to decide whether G has a Hamiltonian path starting in a given vertex.
To provide a proof, we have to show two problem reductions; from A to B and from B to A. We start with the latter one.
• (From B to A): Imagine somebody asks for a Ham. path in G starting with v e V(G), and we could only solve the general Ham. path problem.
Then we construct a graph G' from G by adding a new vertex v' adjacent only to v. Any Ham. path in G' has to start in v' and continue with v, and so it gives a Ham. path in G starting with v.
• (From A to B): We could solve general Ham. path by asking for a Ham. path starting in every vertex of G separately, but there is a much nicer alt. solution.
Construct a graph G" from given G by adding a new vertex x adjacent to all V(G), and ask for a Ham. path starting in x. Trivially, a Ham. cycle in G exists iff such a cycle can be prolonged till x to make a Ham. cyce in G".
C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
Example 8.5. Show that the following two problems are of the same difficulty:
• to decide whether a given graph G is 3-colourable,
• to decide whether a given graph G is ^-colourable.
To reduce from 3-colourability to 4-colourability is very easy, simply make a graph G' from original G by adding a new vertex x adjacent to all V(G). Then every 3-colouring of G is in a one-to-one correspondece with a 4-colouring of G' using colour 4 at the vertex x.
A converse reduction is much more involved and tricky............... C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
' Class MV and MV-completeness Decision problems
• Decision problems are those, roughly saying, whose answer can be Yes/No.
• This seems quite restrictive, however;
— for the colouring problems, we usually ask if a graph G is fc-colourable, meaning whether x(G) < k, but not about the precise value of x(G), □
— simiarly, in the clique and independent set problems, we may ask whether uj(G) < k and a(G) < k, and □
— knowing how to solve the decision variant of a problem usually means we can also find a witnessing solution. □
Class AfV
• A prominent rank among graph decision problems belongs to those problems in which an answer Yes can be verified, with the help of a suitable advice (oracle), by an efficient procedure/algorithm. □
— In computational complexity, the class of such problems is called MV. □
• Actually, the decision version of most common graph problems are of this kind.
For example, in the colouring problem the advice is a proper colouring of the given graph which can be readily verified. Likewise for the Hamiltonian problem, the advice is a Hamiltonian cycle, etc. decisionpw6km = Tozfwdovadpw6Um
Petr Hliněný,   Fl MU Brno,   2014 15/24 Fl: MAOIO: Difficulty of Graph Problems
The Satisfiability problem
The following one is the "master ./VP-complete" problem:
Problem 8.6. 3-SAT (a special version of satisfiability SAT)
The following problem is NT'-complete (reading "hardest in MV"), meaning that it belongs to the class MV and no other problem in MV can be more difficult: □
Input: A propositonal logic formula $ in a conjunctive normal form, such that every
clause of $ contains < 3 literals. Output: Is there a valuation of the ^-variables that makes $ true?
For instance, $ = (ii V -12:3 V X4) A (x2 V -12:4) A (-izi V X2 V X3). □ The true informal meaning of A/'P-completeness of a problem is as follows;
• "I am the hardest problem in the very natural class MV, and if you could solve me, then you would be able to solve everything in MV."
• Consequently, it is very likely that A/'P-complete problems cannot be solved nicely (again, we refer to computational complexity courses for a precise definition of this).
• As it turns out, many typical problems in graph theory are of the same, "highest", difficulty—they are A/'P-complete. We will outline this fact, in a series of problem reductions, next.
Petr Hliněný,   Fl MU Brno,   2014 16/24 Fl: MA010: Difficulty of Graph Problems
8.4   Sample Reductions for Hard Problems
Problem 8.7. 3-COL (3-Colouring of graphs)
The following problem is as hard as SAT: Input: A graph G.
Output: Can the vertices of G be properly coloured using three colours?
Proof (a sketch): The problem is in MV and we construct a reduction from 3-SAT. □ For a given formula $ we construct a graph G$: The basis of the construction of G$ is a triangle with vertices denoted by X,T,F. Each variable Xj in $ is assigned a vertex pair adjacent to X. Each clause of $ is assigned a subgraph on 6 vertices (three of them adjacent to T), as in the picture. Then the remaining free "halfedges" are joined together in the way corresponding to the literals (xj or        in the clauses.
to clauses «— (val. T or F)
Then one may easily check that G$ has a 3-colouring iff $ is satisfiable. C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
Problem 8.8. IS (Independent Set)
The following problem is as hard as SAT and 3-COL:
Input: A graph G, and an integer k.
Output: Is there an independent set (i.e., a subset of the vertices with no edges between them) of size at least k in Gl □
Proof: The problem is in MV and we construct a reduction from 3-COL.
Let if be a graph on n vertices which should be 3-coloured.  We set k — n, and
construct a graph Gh made of three disjoint copies of H as shown in the picture:
Assume c : V(H) —>• {1,2, 3} is a 3-colouring of H. Then one can choose k — n indep. vertices in Gh', for each v e V(H) choosing the c(t>)-th copy of v in the graph Gh- d
Convers., if I is an indep. set in Gh of size k — n, then every triangle Tv, v e V(H), intersects I prec. in one vertex. This determines one of three colours for v in H. C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
Definition: A vertex cover in a graph G is such a set C C V(G) that every edge of G is incident with a vertex of C, i.e. G — C is independent.
Problem 8.9. VC (Vertex Cover)
The following problem is as hard as SAT and IS:
Input: A graph G, and an integer I.
Output: Is there a vertex cover of size at most i in Gl □
independent set
vertex cover
Proof: The problem is in MV and we construct a really trivial reduction from IS.
Notice that the complement C — V(G)\I of an arbitrary independent set I is actually a vertex cover, and vice versa. So the reduction works with the same graph G and with i — n — k (where k is the desired IS size). C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
Definition: A dominating set in a graph G is a set D C V(G) such that every vertex of G not in D has a neighbour in D.
Problem 8.10. DOM (Dominating set)
The following problem is as hard as SAT and VC:
Input: A graph G, and an integer I.
Output: Is there a dominating set of size at most i in Gin
Proof: The problem is in MV and we construct an easy reduction from VC.
Given any graph H, we construct an input graph Gh for the DOM problem as follows:
For every edge e G E(H), a new vertex ve is added, forming a triangle with e.
vertex cover dominating set
Now a vertex cover of the former graph is the same as a dominating set in the latter graph (any domin. set in the latter can be "pushed away" from the new vertices). C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
Problem 8.11. HC (Hamiltonian cycle, directed)
The following problem is MV-complete:
Input: A digraph G.
Output: Is there a directed cycle in G passing through all the vertices?n
Proof (a sketch): The problem is in MV and we outline a reduction from VC. Given any graph H and integer £ (an instance of VC), we construct a digraph Gh for the HC problem as follows. Every vertex v e V(H) is transformed into a directed cycle Cv of length (1h{v) and each arc of Cv is then further transformed into one side of the gadget in the following picture, for every edge uv e E(H):
edge uv e e(h) gadget:
The point of this gadget is that while traversing it, one has to return to the same Cu as started from. Finally, exactly i new vertices are added to Gh as adjacent to and from every one of transformed Cv's (this models that we can 'jump across" altogether t of Cv's while covering all the edge gadgets). C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
Problem 8.12. HAM (Hamiltonian cycle)
The following problem is as hard as SAT and HC:
Input: A graph G.
Output: Is there an (undirected) cycle in G passing through all the vertices? □
It is an easy reduction from the previous problem HC. Each vertex v of a directed graph H is replaced with three vertices forming a path Pv in the graph Gh- d
Then the directed edges coming into v are joined to the first vertex of Pv, while the edges leaving from v are joined to the last vertex of Pv. Having to travers also the middle vertex of Pv now "enforces" the right direction of passing throuh each Pv as through the original vertex v of H. C
Proof:
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
8.5   Appendix: The interesting story of Vertex Cover
Consider the (at first glance) very similar problems of a vertex cover and of a dominating set in a graph—both are among the classical NT'-complete problems. Yet, we discover a huge difference between them, briefly outlined as follows. □
• If, in the computational complexity analysis, we focus on the value of the input parameter k, then we still cannot solve Dominating Set in a better way than exhaustively checking (almost) all fc-tuples of vertices.
Even when k is fixed small, say k — 10, 20, this an intractable problem. □ What does it mean "cannot solve"?
In this particular case, a solution to Dominating Set significantly faster than checking all fc-tuples of vertices, would violate the Exponential Time Hypothesis. □
• On the other hand, a Vertex Cover of size k can be decided by a very simple algorithm running in time 0(2k ■ n), which is quite usable for small fixed values of k such as k — 10, 20, giving actually a linear time algorithm]
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems
^Algorithm 8.14. k-VC (Vertex Cover)
For any fixed parameter k we are solving the following problem.
Input: A graph G.
Output: Is there a vertex cover of size at most k in Gl □ We initialize C — % and F — E(G).
• If F —    then C is returned as a vertex cover.
If, otherwise, \C\ > k, then the return value is "NO". □
• We pick an arbitrary edge f — uv e F, and for each of its ends x — u, v we do:
— C' — C U {x}, and the edge set F' results from F by removing all the edges incident with x in G;
— the algorithm is called recursively for G, C' and F'. □
Finally, how many (self-)recursive calls occurs in Algorithm 8.14 altogether? Every call generates two further recursive calls, but only up to a fixed depth k. Hence the total running time is asymptotically only 0(2k ■ n). □
Remark: The factor 2fe can be improved by more careful choice of branching. (2006: 1.2738fe)
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Difficulty of Graph Problems