Online course on digraphs, Shandong University, spring 2026

On this web page I will add new material each week as long as the course is running so visit it often!

NB: If you have something you think would be good to have on this page, please inform me and give me the material or information.

Litterature

Notes on what we did so far

The videos from these lectures should be made available to you by Jia or Xiaoying :-)
  1. March 4: I introduced the course and gave a quick recap on basic results on flows. I also showed how to use minimum value flows to prove that every
    tournament T on n vertices and minimum in- and out-degree at least k has a spanning subdigraph D' which also has minimum in and out-degree at least k
    and D' has at most nk+(k+1)k/2 arcs. This provides support to the conjecture that every k-arc-strong tournament contains a k-arc-strong spanning subdigraph with at most nk+(k+1)k/2 arcs.
    The conjecture and the proof above can be found in this paper.

  2. March 11: I lectured on NP-completeness and gave several examples of how to prove NP-completeness results.
    In particular I showed that the following two problems are NP-complete: given a digraph D with two special vertices s,t
    and disjoint subsets W_1,...,W_k each of size 3; decide whether D has an (s,t)-path that
    contains (avoids) at least one vertex from each W_i. See the proof in this paper
    This simple digraph can be extended to give
    many different NP-completeness proofs. I used it to showed that deciding whether a digraph is supereulerian is NP-Complete.
    I also gave a proof (using circulations in networks) that every digraph D whose arc-connectivity is at least as large as its independence number
    has an eulerian factor. This provides some support to my conjecture with Thomasse that every digraph whose independence number is not larger than its arc-connectivity is supereulerian.

  3. March 18: I first gave you the famous proof by Fortune Hopcroft and Wyllie that the 2-linkage problem is NP-complete. See these pages from my book
    While doing so I pointed out why the proof works,
    even though it seems there could be a problem. In fact the so-called widget they use has more properties than they mentioned (and I also ignored that in our book)
    and this is why the proof is correct. After that lectured on fixed parameter tractability of vertex cover, that is, I showed that the problem vertex cover
    (given a graph G and an integer k; does G have a vertex cover of size at most k) can be solved in time O(f(k)n^c) for some constant (c at most 3) and finite function f.
    I did this by showing that every instance (G,k) can be reduced in time O(n^c) to an equivalent instance (G',k') (called a kernel) such that G' has at most k^2 edges and at most k^2 vertices.
    Finally I showed you how to use linear programming to obtain a much smaller kernel of size only 2k.

  4. March 19: Not really part of the course as I gave a talk in the new Combinatorics seminar but as I know many of you attended I add a short summary here.
    Most of the lecture was about the acyclic dichromatic number of a digraph D.
    This is the minimum number of sets V_1,...,V_k we need to divide the vertices into so that each of the induced subdigraphs D[V_i] are acyclic
    (as in the normal dichromatic number) AND each of the bipartite digraphs D[V_i,V_j] induced by the arcs between the sets V_i and V_j is also acyclic for i not equal j
    I demonstrated several differences between this new parameter and the dichromatic number. In particular I showed how to construct bipartite digraphs with arbitrarily high acyclic dichromatic number (bipartite digraphs always have dichromatic number at most 2).
    Then I used this to show that deciding whether the acyclic dichromatic number is at most k is NP-complete for all k>=2 even for bipartite digraphs.
    Finally I introduced a number of new linkage problems tghat should be of interest to you. These problems can all be found in the problem list under suplementary notes.

  5. March20: I added a new version of the problem list (see suplementary notes).

  6. March 25: Zirui and Hangling gave presentations based on this paper.
    Zirui showed that it is NP-complete to decide for a digraph D and a given vertex s of D, whether D has an out-branching B from s so that the digraph D'
    that we obtain from D after removing all arcs of B is connected in the underlying sense, that is there is a spanning tree T in the underlying graph UG(D') of D'.
    He also proved three other results based on the same construction.
    One of these is the fact that it is NP-complete to decide a digraph D and two given vertices s,t of D, whether D has an (s,t)-path P so that the digraph D'' that we obtain from D by removing the arcs of P still has an out-branching B from s.
    Note that, because every spanning tree T contains an (s,t)-path for every choice of s,t, one might think that the NP-completeness of the first problem
    (out-branching and spanning tree) would follow directly from the second result. In some sense this is what we do in the proof of Theorem 1.5
    as we prove that, as soon as the digraph D constructed from the clauses has an (s,t)-path that is arc-disjoint from some out-branching, then we can extend that path to a spanning tree. The important thing is that the proof of Theorem 1.5 uses the same underlying subdigraph as the proof of Theorem 3.3 (ii).

    After this Hangling presented the proof of our result that it is NP-complete to decide whether a 2-regular digraph has a pair of arc-disjoint hamiltonian cycles.
    In this proof the gadgets we need to represent the clauses are more complicated and we reduce NAE-3-SAT (instead of 3-SAT) to our problem.
    The clause gadget has the property that it contains a hamiltonian path P and a 2-factor R+Q which are arc-disjoint and if P starts in x1 then it ends in x6 and
    R, Q start in y1, repsectively z1 and end in y6, respectively z6. These properties are used heavily in the construction of the digraph corresponding to an instance of NAE-3-SAT.
    A third property of the clause gadget that we used is the fact that if we remove the arcs of any 3-path factor of the gadget we are left with 6 isolated 3-cycles.
    This implies that for every pair of arc-disjoint hamilton cycles C,C' and every clause gadget H each of C and C' pass through H at least once and at most twice.
    This property is used to derive a truth assignment that satisfies each clause and which has at most 2 true literals per clause.

  7. April 1: I showed how to reduce the 2-SAT problem (the SAT variant where each clause has exactly two literals) to a digraph problem.
    Namely, I showed how to construct a digraph D(F) from a 2-SAT formula F so that we can decide whether
    F is satisfiable just by looking at the strong components of D(F). Then I showed how to formulate many 2-partition problems for digraphs (e.g. the (independent,semicomplete)-partition problem)
    as 2-SAT problems and thus obtaining a polynomial algorithm for these problems. After this I introduced a so-called ring-digraph D_F which one can construct from an instance F of 3-SAT.
    The digraph D_F has a set W_j of 3 vertices corresponding to the literals clause C_j and it has the property that F is satisfiable
    if and only if D_F has a cycle which avoids at least one vertex from each W_j.
    It also has a cycle which contains a vertex from each W_j if and only if F is satisfiable and finally, if F is an instance of NAE-3-SAT
    (at least one false and at least one true literal in each clause), then D_F has two disjoint cycles,
    each containing at least one vertex of each W_j if and only if F is NAE-satisfiable. I then showed how to use the above properties of the ring digraph to show that the (strong,connected)-[k1,k2]-partition problem is NP-complete for digraphs.
    The digraph we use has many vertices of out-degree 0 so it it not strongly connected. In fact, it turns out that when the input digraph
    must be strongly connected then the (strong,connected)-[k1,k2]-partition problem becomes polynomial. I also showed you a polynomial algorithm to decide for a fixed integer k and given semicomplete digraph D
    whether D has a 2-partition V1, V2 so that each of the induced sub digraphs D[Vi] have minimum out-degree at least k.
    That algorithm used the very important fact that the number of vertices in a tournament that have out-degree at most 2k-2 is at most 4k-3.
    This allowed us to try all possible partitions of the set of such vertices in polynomial time (exponential in k, but k is a constant). Finally I showed that a digraph D has a 2-partition V1,V2 into two subdigraphs with minimum out-degree at least 1
    if and only if D has minimum out-degree at least 1 and D has a pair of disjoint cycles C1,C2.
    I also gave Thomassens beautiful proof that every digraph with minimum out-degree 3 has a pair of disjoint cycles.

  8. Plan for April 8: Zhimin Wang and Hanzi Bai will present some of the results from this paper (Theorems 3.9,4.3 and 4.7) and this paper (Theorem 4.4)


Supplementary Notes

Joergen Bang-Jensen (jbj@imada.sdu.dk)