(PDF) Finding kernels or solving SAT

Journal of Discrete Algorithms 10 (2012) 146–164 Contents lists available at SciVerse ScienceDirect Journal of Discrete Algorithms www.elsevier.com/locate/jda Finding kernels or solving SAT Michał Walicki ∗ , Sjur Dyrkolbotn Department of Informatics, University of Bergen, Norway a r t i c l e i n f o a b s t r a c t Article history: We begin by offering a new, direct proof of the equivalence between the problem of the Received 9 September 2010 existence of kernels in digraphs, KER, and satisfiability of propositional theories, SAT, giving Received in revised form 24 June 2011 linear reductions in both directions. Having introduced some linear reductions of the input Accepted 18 November 2011 graph, we present new algorithms for KER, with variations utilizing solvers of boolean Available online 25 November 2011 equations. In the worst case, the algorithms try all assignments to either a feedback vertex Keywords: set, F , or a set of nodes E touching only all even cycles. Hence KER is fixed parameter Digraphs tractable not only in the size of F , as observed earlier, but also in the size of E. A slight Kernel modification of these algorithms leads to a branch and bound algorithm for KER which is Satisfiability virtually identical to the DPLL algorithm for SAT. This suggests deeper analogies between Propositional logic the two problems and the probable scenario of KER research facing the challenges known from the work on SAT. The algorithm gives also the upper bound O ∗ (1.427|G | ) on the time complexity of general KER and O ∗ (1.286|G | ) of KER for oriented graphs, where |G | is the number of vertices. © 2011 Elsevier B.V. All rights reserved. 1. Introduction The concept of a kernel of a digraph (an independent set reachable from every outside node by an edge) was introduced in [33] as a generalization of a solution of a cooperative game and has since then found applications in both positional and cooperative game theory as well as in logic. Determining the existence of a kernel has become a problem of independent interest in graph theory, starting with the classical results of Richardson, [29,30], and followed in the last decades by several publications, e.g., [26,14,15,1,18,12], with a recent overview [4]. The problem of the existence of kernels in digraphs, KER, is NP-complete, [6], so in a trivial sense it is equivalent to the satisfiability of propositional theories, SAT. The equivalence has been applied, e.g., in [24] for representing finitely branching dags as consistent propositional theories, in [11,12] for studying default logic, in [13] for correlating models of logic programs and kernels of appropriate digraphs and in [34] for analysing circularity in logical paradoxes. But it has not received a separate treatment, independent from particular applications. From an algorithmic perspective, it is natural to ask for a more fine-grained analysis of the exact relationship between SAT and KER. An answer should provide an indication both as to whether kernel theory can contribute to SAT-solving, and as to how techniques developed for SAT-solvers can be employed to increase the efficiency of deciding KER. Equivalence of the two problems with respect to some complexity class does not suffice to answer such questions because, in order for a reduction to be useful in practice, even constant factors may matter, requiring a more detailed analysis of the actual choices and possible heuristics. In this article we focus on KER, showing that the reducibility of KER to SAT has a practical, algorithmic content. This is found not so much in the direct application of SAT-solvers, although this too is a viable approach for some cases, but rather in the similarities between the problems encountered while trying to solve KER (directly) and those faced by * Corresponding author. E-mail address:

(M. Walicki). 1570-8667/$ – see front matter © 2011 Elsevier B.V. All rights reserved. doi:10.1016/j.jda.2011.11.004 M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 147 SAT-solvers. We present a series of novel algorithms for KER, utilizing new observations of graph-theoretical nature but also the possibility of solving SAT at appropriate places. These can be very efficient for some classes of graphs, but are hardly optimal in general. We then present our final algorithm for KER, which is very similar to the central SAT-algorithm DPLL, [10,9]. We review several issues which, arising from earlier experiences with SAT, are likely to affect future work on KER. The question of how kernel theory can be used to solve SAT more effectively is left for future work, but we hope that the connection we demonstrate here indicates strongly that SAT-solvers might indeed have something to gain from utilizing the graphical nature of KER. Section 2 introduces the basic definitions and establishes the equivalence of KER and SAT, giving new linear reductions in both directions, simpler than previously available. The problem of finding a kernel is formulated in terms of assigning boolean values to the nodes of the graph, an assignment is a solution when it determines a kernel and a graph is solvable if it has a solution. Section 3 presents some linear (or low polynomial) graph reductions which preserve and reflect solvability and are later used by the discussed algorithms. Section 4 presents several results relating solvability to various conditions on feedback vertex sets. In Subsection 4.1 we also show how to solve KER by constructing a dag from a digraph. This is essentially the technique used in the algorithms from [11,12]. In our case, however, a single dag suffices for either finding a kernel or concluding its non-existence. In the worst case, we try all assignments to a feedback vertex set, and thus the complexity of the trivial brute-force O ∗ (2|G | ) is reduced to O ∗ (2| F | ), where F ⊆ G is a feedback vertex set.1 Following that, we show that one can reduce this factor even further to the number of even cycles only. Subsection 4.2 gives an algorithm which, for each assignment to a subset of nodes E touching all even cycles, determines in linear time if the resulting, induced assignment is a solution, thus giving the complexity O ∗ (2| E | ). Both these algorithms show that the problem is fixed parameter tractable, FPT, taking the size of F , respectively E, as the parameter. We also discuss a variation which, instead of inducing the values along the obtained dag, decides solvability of the appropriate system of | E | boolean equations over | E | variables. Section 5 introduces the main, recursive algorithm, based on the simplifications introduced in Section 3. It subsumes the algorithm from [12] as a special case and allows to show the complexity bound O∗ (1.427|G | ) for the general case and O∗ (1.286|G | ) for oriented graphs (with no 2-cycles). It turns out that, except for the fact that it works on digraphs and not on CNFs, it is exactly the DPLL algorithm – the basis of most modern SAT-solvers. This brings a new aspect of the relationship to SAT, and we conclude listing a series of conjectures and hypotheses on the expected issues and choices in the further development of the algorithms for KER, originating from the experiences with SAT-solvers. 2. Background A digraph (directed graph) is a pair G = G , N , where G is a finite set of nodes and N ⊆ G × G is a binary relation that describes the directed edges of G.2 For a vertex x ∈ G, we denote by N + (x) = { y ∈ G | N (x, y )} the set of out-neighbours of x, and by N − (x) = { y ∈ G | N ( y , x)} the set of in-neighbours of x with respect to the directed edge relation of G. Neighbours of x is the union of its out-neighbours and in-neighbours, N + (x) ∪ N − (x). The degree of x ∈ G, d(x), is its number of neighbours. Letting ( N + )∗ denote the transitive closure of N + , we use [x) = { y | y ∈ ( N + )∗ (x)} to denote the set of vertices reachable from x and (x] = { y | x ∈ [ y )} to denote the set of vertices from which x is reachable. These notational conventions are extended to subsets of vertices, for example, for all X ⊆ G, we let N − ( X ) = x∈ X N − (x). For an X ⊆ G, we also write G \ X to denote the subgraph of G induced by the subset G \ X . A walk p is a sequence of vertices x0 , x1 , x2 , . . . , xn such that ∀0 i < n: xi +1 ∈ N + (xi ) and such that all edges traversed are distinct, i.e. whenever xi = x j for 0 i = j < n, we have xi +1 = x j +1 . The length of a walk is the number of edges it uses, l( p ) = n. A walk is a path if it is also a sequence of distinct vertices. A cycle is a walk x0 , . . . , xn−1 , xn such that x0 , . . . , xn−1 is a path and xn = x0 ∈ N + (xn−1 ). A sink in G is a vertex x ∈ G without out-neighbours and sinks(G) = {x ∈ G | N + (x) = ∅} denotes the set of sinks of G. A vertex which is not a sink is internal, int (G) = G \ sinks(G). A root of G is a vertex x ∈ G such that every other vertex is reachable by a path from x. A subset of vertices S ⊆ G is strongly connected if (∗): ∀x, y ∈ S: x ∈ [ y ) ∧ y ∈ [x). Such an S is a strongly connected component if there is no set S ⊃ S such that (∗) holds. A strongly connected component S is final whenever N + ( S ) = S. Since this will be of relevance for some algorithms, we remind the reader that it is possible, for instance by using Tarjan’s algorithm [32], to decompose a graph into its strongly connected components in linear time. For a digraph G, G denotes the undirected graph obtained by turning every directed edge x, y into an undirected one {x, y }. An oriented graph is a digraph G obtained from G by giving every undirected edge some direction. Such a graph does not contain any cycles of length 2. A kernel of a digraph G = G , N is a subset of vertices K ⊆ G such that: 1 The notation O ∗ () suppresses polynomial factors from exponential functions. 2 Some results presented below apply to the infinite digraphs and infinitary propositional logic. However, in the present context of algorithm design, we assume all involved sets to be finite. Also, unless stated otherwise, by a graph we always mean a digraph. 148 M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 (i) G \ K ⊇ N − ( K ) (K is an independent set in G) and (ii) G \ K ⊆ N − ( K ) (from every non-kernel vertex there is at least one edge to a kernel vertex). Any kernel of G is an independent and dominating set in G. These two properties are equivalent to K being a maximal independent subset of G. Conversely, given a maximal independent subset K , we can determine if it is a kernel of G by verifying that every vertex x ∈ G \ K has a directed edge into K (a G-edge in G might be only to x). Consequently, a possible (if not most efficient) algorithm for finding the kernels would unorient the input digraph G, find G’s maximal independent subsets, and for each such check if every node outside it has a directed edge to the subset. The |G | number of maximal independent subsets of any G is limited by Moon and Moser’s 3 3 bound, [25], and such subsets can be produced with polynomial delay, [22]. It follows that there is an algorithm that finds all kernels in a graph, by just checking |G | each such subset, in time O ∗ (3 3 ). This running time is in fact tight for the problem of finding all kernels, as can be seen considering G that is a collection of disjoint symmetric cycles of length 3, i.e. the reversal of every edge is also present. For |G | such a graph every maximal independent subset of G is a kernel and there are 3 3 of them. Even though for most digraphs only a proper subset of the maximal independent sets will be kernels, finding all kernels is not a computationally feasible problem. We consider only the problem of determining the existence of a kernel which, when one exists, amounts usually to producing it. The problem is addressed using the equivalence between the existence of kernels and the satisfiability of propositional theories, arising from an equivalent definition of kernels. For a digraph G = G , N , an assignment α ∈ {0, 1}G (of truth- values to the vertices of G) is correct at a vertex x ∈ G if α (x) = 1 ⇔ α ( N + (x)) ⊆ {0} or equivalently, if: α (x) = 1 ∧ α N + (x) ⊆ {0} ∨ α (x) = 0 ∧ 1 ∈ α N + (x) . (2.1) An α ∈ {0, 1}G is a solution for G, α ∈ sol(G), if α is correct at every vertex of G, and if such an α exists G is solvable. For any α ⊆ G × {0, 1}, we denote α 1 = {x ∈ G | x, 1 ∈ α } and α 0 = {x ∈ G | x, 0 ∈ α }. For all graphs G and all assignments α ∈ {0, 1}G it holds that α is a solution iff α 1 is a kernel: α ∈ sol(G) ⇐⇒ α1 = G \ N − α1 ⇐⇒ α 1 is a kernel of G. (2.2) A possible algorithm for finding kernels is then based on the fact that every digraph G induces a propositional theory T (G) by taking, for each x ∈ G, the formula x↔ ¬ y, (2.3) y ∈ N + (x) with the convention that 1 = y ∈∅ y.3 Then, letting mod(T) denote all models of a theory T, the following equality holds: sol(G) = mod T (G) . (2.4) Since determining kernels is a special case of determining the models of propositional theories, we can feed Eqs. (2.3) together with z = 1 for all z ∈ sinks(G) to a solver of systems of boolean equations, to determine if G has a kernel. Alterna- tively, we can feed the problem to a clausal SAT-solver. First, each Eq. (2.3) is equivalent to 1= x∨ y ∧ (¬ y ∨ ¬x). (2.5) y ∈ N + (x) y ∈ N + (x) Collecting now the right-hand sides of these new equations and adding the requirement for all z ∈ sinks(G), yields the formula in CNF: CNF (G) = x∨ y ∧ (¬ y ∨ ¬x) ∧ z. (2.6) x∈int(G) y ∈ N + (x) y ∈ N + (x) z∈sinks(G) Satisfiability of CNF (G) is equivalent to the solvability of the system of equations (2.5) for all internal nodes, with all sinks assigned 1 which, in turn, is equivalent to the existence of a kernel in G, by (2.4).4 The above reduction and the resulting CNF (G) are essentially the same as in [7]. The linear reduction in the opposite direction used there 3-Colorability, so we give a direct reduction from SAT: every propositional theory T can be transformed in linear time into a digraph G (T) such that mod(T) = sol(G (T)). Many different graphs can satisfy these requirements, so we give only one example. First, assume a theory T given as a set of equivalences of the form x↔ ¬ yi , (2.7) i∈I x 3 Satisfiability of such a theory is equivalent to the existence of solutions for the corresponding system of boolean equations. This motivates the use of the name “solution”, which was also used in the early days of kernel theory, e.g., in [33], p. 588, or [30]. 4 Assuming the adjacency list representation of the argument G = G , N , CNF is linear in the number of vertices, |G |, and edges, | N | (each edge x, y giving rise to two pieces of data: ¬ y ∨ ¬x and the element y in the disjunction for x: x ∨ · · · ∨ y ∨ · · ·). M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 149 where all y, xi are variables, and where every variable occurs at most once on the left of ↔. The digraph G (T) is obtained by taking variables as vertices and, for every formula, introducing edges x → y i for all i ∈ I x . In addition, for every variable z not occurring on the left of any ↔, we add a new vertex z and two edges z → z and z → z. This last addition ensures that each variable z of T which would become a sink of G (T), and hence could only be assigned 1 by any solution of G (T), can be also assigned 0 (when the respective z is assigned 1). Letting V (T) denote all variables of T, and sol(X)|Y the restriction of assignments in sol(X) to the variables in Y , we have that mod(T) = sol G (T) V (T) . (2.8) Now, an arbitrary theory T can be transformed into the above form. To simplify the transformation, assume T to be given as a set of clauses, each clause C = C + , C − consisting of the set of positive, C + = {x p | p ∈ P }, and negative, C − = {¬xn | n ∈ N }, literals. First, let aC be a new variable. The formula C : aC ↔ ¬aC ∧ ¬C is equisatisfiable with C , with models relatedby the equation mod(C ) = mod(C ) × {aC , 0}. Substituting for ¬C , we obtain a more explicit form of C : aC ↔ ¬aC ∧ p ∈ P ¬x p ∧ n∈ N xn . We introduce for every variable in the initial theory x ∈ V (T), a new variable x. For every such pair of variables we introduce the formulae (i), and for every clause C the formula (ii): (i) x ↔ ¬x and x ↔ ¬x. (ii) aC ↔ ¬aC ∧ p ∈ P ¬x p ∧ n∈ N ¬xn . The theory C containing formulae (i) and (ii) is equisatisfiable with C and mod(C ) = mod(C )| V (C ) . Defining T = C ∈T C and letting G (T) = G (T ), the equality (2.8) remains valid. Example 2.9. For T1 = {¬x}, respectively, T2 = {¬x ∨ y }, we obtain the digraphs: aC 1 x x aC 2 x x G (T1 ) G (T2 ) y y We note that G (T) can be defined so that it is oriented and has no loops. In addition to aC , add two more nodes in a 3-cycle aC , b C , c C , aC , and for every x ∈ V (T), introduce in (i) two more new nodes, replacing the 2-cycle by the 4-cycle: x, x, x , x , x. Both Eqs. (2.4) and (2.8) hold for arbitrary digraphs but when they have infinite branchings, the corresponding theory is in infinitary propositional logic. In this paper, we are concerned exclusively with usual propositional logic and finite graphs, so “graph” and “arbitrary graph” mean here only a finite digraph. 3. Preprocessing This section presents some simplifications reducing the input graph, which will be later combined with different algo- rithms. In Subsection 3.1, we show that we can consider only the problem for graphs without sinks, since kernels of an arbitrary graph G are determined by the kernels of its appropriate, sinkless subgraph which can be obtained from G in linear time. Subsection 3.2 presents some further simplifications of a graph which are based on local dependencies and are of linear, or low polynomial, complexity. 3.1. Forcing values The obvious brute-force approach, simply checking the condition (2.1) for every possible assignment, can be improved by observing consequences of a given partial assignment. The following definition captures some such consequences that are recognizable locally in the graph. Definition 3.1. A partial assignment to a graph G is an α ∈ {0, 1} X for any X ⊆ G. Given such an α , we define inductively its extension to the nodes which obtain forced values: α11 = α 1 , α10 = α 0 , αi0>1 = N + αi1−1 ∪ N − αi1−1 ∪ αi0−1 , αi1>1 = sinks G \ αi0 ∪ αi1−1 ∪ x ∈ N + ( y ) | y ∈ αi0 ∧ {x} = N + ( y ) \ αi0 . Fixed-point is reached when αk1 = αk1−1 , no later than for k = |G |. We then let α 1 = αi1 , α 0 = αi0 and set α = {(n, 1) | n ∈ α 1 } ∪ {(n, 0) | n ∈ α 0 }. 150 M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 Example 3.2. Consider the following two graphs: x y a b C: z d c G: e f In C, α = {x, 1} gives α20 = { z, y }, α21 = {x, z} and then α30 = {x, y , z}, α31 = {x, y , z}, i.e., α = {x, y , z} × {0, 1}. In G, from α = {c , 0} we obtain α = {c , 0, b, 1, a, 0, f , 0, e , 1, d, 0}, while β = {c , 1} leads to β = {c , 1, d, 0, b, 0, a, 1, f , 1, e , 0}. In both cases, the resulting assignment is a solution of G. Starting with γ = {e , 0} does not induce any values, i.e., γ = γ . C shows that α may happen to be a (non-functional) relation, i.e., α 1 ∩ α 0 = ∅. If this is the case, then we cannot find a correct assignment that extends α . However, if α is a function, then for all x ∈ dom(α ) we have the following weaker form of correctness: α (x) = 1 ∧ α N + (x) ⊆ {0} ∨ α (x) = 0 ∧ ∃ y ∈ N + (x): y ∈/ α 0 . (3.3) We say that α is consistent in this case. Given a consistent partial assignment α , it might, but need not, be possible to extend it to a solution for G. This depends on the solvability of the subgraph yet to be assigned, but also on the possibility of finding a solution for the remaining graph such that each vertex assigned 0 by α is eventually justified by the assignment of 1 to one of its out-neighbours. In particular, we have to meet this constraint on the border of α , defined as follows: Definition 3.4. Given a partial assignment α to a graph G, the border of α is the set bord(α ) = {x ∈ dom(α ) | α (x) = 0 ∧ 1 ∈/ α ( N + (x))}. The formula (3.3) implies that a consistent partial assignment is correct everywhere with the possible exception of its border. Remark 3.5. When a partial assignment α is correct on its whole domain, i.e., α ∈ sol(dom(α )), then α 1 ⊆ G is called a local kernel (sometimes semi-kernel) in kernel theory. Local kernels are used in inductive proofs of sufficient conditions for the existence of kernels in digraphs from certain classes, e.g. in [2,15,14,18]. Deciding if a graph has a local kernel is NP-complete, [13]. Any β ∈ sol(G) must be such that its restriction to any subset B ⊆ G is consistent on the subgraph induced by B. Also, every solution respects all values induced by its own restrictions, in particular, induced from the empty assignment. Consequently, the values induced from the empty assignment are the same in all solutions (if any). These observations are gathered in the following lemma. G◦α denotes the subgraph G \ dom(α ), ∅ denotes the empty assignment, and we abbreviate G◦ = G◦∅ . Lemma 3.6. For an arbitrary G: 1. bord(∅) = ∅; 2. for any partial assignment α : sinks(G◦α ) = ∅; 3. ∀β ∈ sol(G) ∀ B ⊆ G: β| B = β|dom(β| B ) ; 4. sol(G) = {β ∪ ∅ | β ∈ sol(G◦ )}. Proof. 1. It follows by induction that each ∅i satisfies (2.1), i.e., N + (∅1i ) ⊆ ∅0i ∧ ∀x ∈ ∅0i : N + (x) ∩ ∅1i = ∅. This holds trivially at the start with ∅1 = ∅, and after first iteration when ∅12 = sinks(G) and ∅02 = ∅. Assuming (2.1) as IH for ∅i , then for each new x ∈ ∅0i +1 : x ∈ N − (∅1i ), because N + (∅1i ) ⊆ ∅0i by IH; for each new x ∈ ∅1i +1 : x ∈ sinks(G \ ∅0i +1 ) – the last component of Definition 3.1 does not apply, since for any y ∈ ∅0i there is a z ∈ N + ( y ) ∩ ∅1i by IH. α = αi = αi+1 for some i 0 and assume x ∈ sinks(G◦α ), i.e., N + (x) ⊆ dom(α ). If N + (x) ∩ α 1 = ∅, then x ∈ αi0+1 and 2. otherwise x ∈ αi1+1 . In either case x ∈ dom(αi +1 ) = dom(α ). Contradiction. M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 151 3. By induction on the steps used in the construction of β| B , Definition 3.1, we show that for all i: (β| B )i = β|dom((β| B )i ) . The basis is trivial since (β| B )1 = (β| B ) = β|dom((β| B )) . For the induction step, any x ∈ (β| B )i +1 gives one of the following cases: (0) x ∈ (β| B )0i +1 i.e., either • x ∈ (β| B )0i which, by IH, means that x ∈ β 0 or • x ∈ N + ((β| B )1i ) ∪ N − ((β| B )1i ) which, by IH and correctness of β , means that x ∈ N + (β 1 ) ∪ N − (β 1 ) ⊆ β 0 , or (1) x ∈ (β| B )1i +1 i.e., either • x ∈ (β| B )1i which, by IH, means that x ∈ β 1 or • x ∈ sinks(G \ (β| B )0i +1 ), i.e., N + (x) ⊆ (β| B )0i +1 ⊆ β 0 by point (0), and x ∈ β 1 by correctness of β , or • {x} = N + ( y ) \ (β| B )0i +1 : y ∈ (β| B )0i +1 , i.e. by point (0) we have y ∈ β 0 and N + ( y ) \ {x} ⊆ β 0 . Then by correctness of β we must have {x} = N + ( y ) \ β 0 with x ∈ β 1 . 4. For every x ∈ G ◦ : N + (x) ∩ ∅1 = ∅ and, by 2, N + (x) ∩ G ◦ = ∅. Hence, every β ∈ sol(G◦ ) can be combined with ∅ into a correct solution for G. But the values on dom(∅) cannot be chosen otherwise since, by 3, ∀α : α ∈ sol(G) → α |dom(∅) = ∅. 2 The construction from Definition 3.1, together with Lemma 3.6, will provide the basic simplification mechanism used in all our algorithms. According to point 4, we can first (in linear time) induce all values from the sinks of G, removing dom(∅) from the graph. Then, trying various partial assignments σ to the remaining, sinkless subgraph G◦ , point 3 ensures that it suffices to consider only the induced assignment σ , thus reducing the search space. In the following subsection, we identify some particular, structural patterns allowing local simplifications of the graph. 3.2. Simplification The number of possible simplifications, preserving and reflecting solvability, can be unlimited. In practice, one has to choose some which can be expected to occur frequently and can be performed cheaply. Two such simplifications are given, providing also some information about the structural properties of kernels. The first one concerns a special type of path. Definition 3.7. A path p = x0 , x1 , . . . , xl( p ) is isolated if ∀0 i < l( p ): N + (xi ) = {xi +1 }. It follows from Definition 3.1 that any assignment, of 0 or 1, to any vertex on an isolated p will induce values to every other vertex on the path. So the vertices on isolated paths do not contribute anything to the structural properties of G determining its kernels. They can be removed. Definition 3.8. For an isolated path p = x0, p , . . . , xl( p ), p with l( p ) 2, let P ⊆ G denote all nodes xi , p on p. The graph C (G, p ), the contraction of G on p, is defined by a mapping f : G → C (G , p ): • C (G , p ) = G \ {xi , p | xi , p ∈ P } ∪ {x0p , x1p }; • f : G → C (G , p ) is defined by f (x) = x when x ∈ C (G , p ), f (xi , p ) = x0p when i + l( p ) is even and f (xi , p ) = x1p otherwise; • C ( N , p ) = {x, y | ∃x , y ∈ ( f − (x) × f − ( y )) ∩ E: x = x ∨ x = xl( p ), p ∨ y = xl( p ), p }. Example 3.9. We contract the isolated path p = x0 , x1 , x2 , x3 , x4 in the digraph G, obtaining the digraph C (G, p ) where f is defined on p by f (x0 ) = f (x2 ) = f (x4 ) = x0p , f (x1 ) = f (x3 ) = x1p . Also shown is the digraph C (G, q) obtained by contracting q = b, x1 , x2 , x3 , x4 with f (b) = f (x2 ) = f (x4 ) = xq0 , f (x1 ) = f (x3 ) = xq1 . G: C (G, p ) : C (G, q) x0 b x1p b x0 xq1 x1 c x0p c xq0 x2 c d x3 d x4 d 152 M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 Contraction of isolated paths preserves and reflects solutions as stated in the following fact. ( f ; g denotes function composition in diagrammatic order: f followed by g.) Fact 3.10. For any isolated path p with l( p ) 2 in any G: sol(G) = α | ∃β ∈ sol C (G, p ) : α = f ; β . Proof. ⊇) For a β ∈ sol(C (G, p )) define α ∈ {0, 1}G by ∀x ∈ G: α (x) = β( f (x)). To show α ∈ sol(G) it suffices, by definition of f , to show that α is correct on p. For xi , p such that i + l( p ) is odd or i = l( p ), correctness follows since by definition of + f and the fact that p is isolated we have f ( N + (xi , p )) = N C (G, p ) ( f (xi , p )). All other xi , p ’s are such that i + l( p ) is even, and since p is isolated we have f ( N + ( N + (xi , p ))) = f (xi , p ) = f (xl( p ), p ). So correctness follows from correctness of α (xl( p ), p ). ⊆) Assume α ∈ sol(G). By definition of f and the fact that p is an isolated path it follows that ∀x: ∀ y 1 , y 2 ∈ f − (x): α ( y 1 ) = α ( y 2 ). Then we define β for every x ∈ C (G , p ) by choosing arbitrary y ∈ f − (x) and taking β(x) = α ( y ). Then β is correct and it satisfies ∀x ∈ G: α (x) = β( f (x)). 2 As the second simplification we remove basic contradictions. Definition 3.11. An x ∈ G is a basic contradiction if ∃ y ∈ N + (x): N + ( y ) ⊆ N + (x). Important special cases include the in-neighbours of sinks, loops, and triangles such as the following graph: z x y The following fact is obvious: Fact 3.12. If x is a basic contradiction in G then ∀α ∈ sol(G): α (x) = 0. Proof. Let y ∈ N + (x) be such that N + ( y ) ⊆ N + (x) and α ∈ sol(G). If α ( y ) = 1 then α (x) = 0, while if α ( y ) = 0 then, for some z ∈ N + ( y ): α ( z) = 1. But then also α (x) = 0 since z ∈ N + ( y ) ⊆ N + (x). 2 The notion of basic contradiction is motivated by the fact that a (general) contradiction, i.e. an x such that ∀α ∈ sol(G): α (x) = 0, may not be identifiable as such locally by inspecting its fixed neighbourhood. For instance, in the fol- lowing graph, x is a contradiction since x = 0 is necessary (and sufficient) for the existence of a correct assignment to the rest of the graph. b x a c y The contraction of isolated paths can turn a contradiction into a basic one, as the following example illustrates. Example 3.13. The graph C (G, p ) results from contracting the isolated path p = x0 , x1 , x2 in G. After contraction, c becomes a basic contradiction, revealing that it is a contradiction in G: G: C (G, p ) : y y c x0 x1 x2 c x0p x1p The specific case of Fact 3.10, covered by the following fact, characterizes the contradictions which become basic after contraction of isolated paths. (Basic contradiction is a special case when l( p ) = 0 and l(q) = 1.) Fact 3.14. Given isolated paths p = x0, p , x1, p , . . . , xl( p ), p , q = x0,q , x1,q , . . . , xl(q),q = xl( p ), p such that l( p ) + l(q) is odd. If c ∈ G is such that x0, p , x0,q ∈ N + (c ), then ∀α ∈ sol(G): α (c ) = 0. M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 153 Proof. Assume arbitrarily that p has odd length and that we start by contracting p to obtain H = C (G, p ). Then we have + x1p ∈ N H (c ), and there is an isolated path q = x0,q , x1,q , . . . , xl(q),q = x0p in H. Contracting q to obtain K = C (H, q) we obtain a graph where xq0 = x0p ∈ N K+ (c ) and N K+ (x1p ) = {xq0 }. So by Facts 3.10 and 3.12 it follows that ∀α ∈ sol(G): α (c ) = 0. 2 Similar facts can be proven for other situations, where contracting some collection of paths reveals a basic contradiction (for instance in the case of isolated cycles of odd length, or with two paths p , q as in Fact 3.14 but admitting also outgoing edges at nodes with even indices x2i ). We do not attempt to give a complete classification, however. Towards an algorithm for KER, we gather the two rules for isolated paths and basic contradictions into the simplification procedure simp(G) as shown in Algorithm 3.15. The algorithm returns the error value ⊥ if it discovers the non-existence of solutions. Otherwise, by Facts 3.10, 3.12 and Lemma 3.6, every solution to the input graph G can be obtained from a solution to the returned graph.5 Algorithm 3.15 simp (G) if there is an isolated path p with l( p ) 2 then return simp (C (G, p )) else if there is a basic contradiction x ∈ G then α := {x, 0} if α is a function then return simp(G \ dom(α )) else return ⊥ else return G 4. Breaking cycles According to Richardson’s theorem [30], every finitely branching (in particular, finite) graph not containing odd cycles has a kernel. Consequently, a possible approach to KER is to try breaking the odd cycles. Below, we reduce the number of cycles to consider and give a general treatment of this approach utilizing the following concept. Definition 4.1. For a graph G, we define B (G) = { X ⊆ G | ∀β ∈ sol(G): ∃α ∈ {0, 1} X : α = β}. An X ∈ B(G) is called a basis for sol(G). Thus, for any X ∈ B (G), any solution for G can be obtained by inducing from some assignment to X , reducing the complexity of the brute-force approach to 2| X | . (As inducing from a partial assignment takes linear time, the notion of a basis is almost the same as the concept of strong backdoor from SAT.) It remains to be proven that suitable X ∈ B (G) exists. Below we provide two types of bases, guaranteed to exist for any graph. In algorithmic terms this means that KER, when parameterized by the size of either of these bases, is FPT. It should be noted here that a more obvious choice of parameter for KER, the size of the kernel we are looking for, does not make the problem FPT for general graphs unless collapses, deemed unlikely, occur among the parameterized complexity classes.6 So the result in Subsection 4.2, admitting as a basis any set of vertices touching all even cycles, appears to be the best currently available regarding the parameterized complexity of KER. 4.1. Feedback vertex sets A feedback vertex set for a graph G is a subset F ⊆ G such that G \ F is acyclic (a dag). Proposition 4.2. For any graph G, if F is a feedback vertex set for G then F ∈ B (G). Proof. Let F be a feedback vertex set for G and consider arbitrary β ∈ sol(G). Then by Lemma 3.6 we have β| F = β|dom(β| F ) . All we need to prove is dom(β| F ) = G. So consider G \ dom(β| F ). By Lemma 3.6.2, this graph has no sinks, and as F is a feedback vertex set, it has no cycles. Since G is finite, it follows that G \ dom(β| F ) = ∅, as desired. 2 This observation gives a simple algorithm for KER: find some feedback vertex set F and try all possible assignments to its nodes, verifying if the induced assignments are correct on the whole graph. More cleverly, Proposition 4.2 can be 5 Inducing and checking the existence of isolated paths can be done in linear time. The trivial search for basic contradictions would visit, for every node x, each of its out-neighbours y ∈ N + (x), checking if N + ( y ) ⊆ N + (x). The worst case |G |2 hardly ever obtains and, in practice, even this trivial procedure is sub-quadratic. 6 In [19] it is shown that using the size of the kernel as parameter does make the problem FPT for planar digraphs. ([27] provides an introduction to parameterized complexity.) 154 M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 used to construct a branch and bound algorithm that only branches at vertices from F . An algorithm based on this idea is presented in [12]. We will return to branch and bound algorithms in Section 5, but note here that as the success of such an approach depends on finding small feedback vertex sets, we cannot expect it to be optimal for all graphs. It will be good enough, though, for solving KER effectively on graphs that admit small feedback vertex sets. This follows from the recent work in [5], showing that the problem of finding a minimum feedback vertex set is FPT in the size of such a set. In particular, KER is FPT in the size of a minimum feedback vertex set. Feedback vertex sets are useful tools when graphs are viewed algebraically as systems of boolean equations. In this context they allow for a systematic substitution of equals for equals that both preserves and reflects solutions, allowing us to represent G more compactly than the system T (G) from (2.3). In the rest of this subsection we present this construction, linking substitution in systems of boolean equations with feedback vertex sets of graphs. We do this by introducing labeled dag’s that are nice in their own right in that they provide a visualization of the bases originating from feedback vertex sets.7 F denotes such a set and given it, we represent G as a (labeled) dag D( F ) = D F , N F , where F = {x | x ∈ F } is a set of new elements and: D F = G ∪ F , N F = N G \ y , x x ∈ F ∪ y , x x ∈ F ∧ x ∈ N + ( y ) . (4.3) The new vertices are exactly the new sinks F = sinks(D( F ))\ sinks(G) and | F | number of cycles in G. The labeling, defined by l(x) = x for x ∈ G and l(x ) = x for the new x ∈ F , serves to establish a unique correspondence between solutions of D( F ) and of G. Example 4.4. D(a, b) ∈ dag(G) is obtained from the feedback vertex set {a, b}. a b b c d e f b d c D(a, b) a a G e f The double ‘a’ would disappear if we constructed the dag D(b) from the feedback set {b}. It would have an edge from a (which became a) to b and no extra a without incoming edges. Let dag(G) denote the set of so obtained dags from a given G. Given a D( F ) ∈ dag(G), we can use inductive defini- tions over this representation. In particular, any assignment to the new sinks, β ∈ {0, 1} F , induces an assignment β to the whole D, in linear time. We only verify that the values assigned to the new sinks x ∈ F are the same as the values induced at the respective x ∈ F . In the above D(a, b), trying a = 1 = b fails inducing a = 0. Trying b = 1 and a = 0 induces the same values at b and a, allowing to conclude the existence of a kernel for G. sol(G) becomes thus captured by a new system of equations requiring the values assigned to F to agree with the values induced in F . The system is defined as follows. For every vertex x ∈ G \ sinks(G) = int (D( F )), divide the set of its out-neighbours N + + + + + + F (x) into two disjoint subsets: N L (x) = N F (x) ∩ F and N R (x) = N F (x) \ N L (x). Definition 4.5. For x ∈ sinks(G) let FRMD( F ) (x) = 1 and for x ∈ int (D( F )) define: FRMD( F ) (x) = ¬y ∧ ¬FRMD( F ) ( z). y ∈l( N + L (x)) z∈ N + R (x) The reduced system is EQU D( F ) (G) = {FRMD( F ) (x) = x | x ∈ F }. Example 4.6 (4.4 continued). The reduced system EQU D(a,b) (G) has two equations: a = ¬b and b = ¬(¬b ∧ ¬(¬a ∧ ¬(¬a ∧ ¬¬b))). The dag D(b) ∈ dag(G) would give the corresponding reduced system with only one equation (equivalent to the one obtained by substituting a = ¬b in the above system), namely: b = ¬(¬b ∧ ¬(¬¬b ∧ ¬(¬¬b ∧ ¬¬b))). Simplifying its right- hand side, we gradually obtain the trivial equation b = ¬(¬b ∧ ¬(¬¬b ∧ ¬¬¬b))) = ¬(¬b ∧ ¬0)) = b. 7 The question whether this correspondence could be applied for solving more general systems of boolean equations seems an interesting research challenge in its own right. M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 155 Each FRMD( F ) (x) contains only variables from F , so an α ∈ {0, 1} F can be extended to α ∗ ∈ {0, 1}G as follows (α [φ] denotes the usual evaluation of the formula φ under the assignment α ): ∗ α (x) if x ∈ F , α (x) = (4.7) α [FRMD( F ) (x)] otherwise. This makes α ∗ a function consistent with α induced according to Definition 3.1, i.e., α ∗ ⊆ α . Every solution for G is, in fact, such an α ∗ obtained from a solution for EQU D( F ) (G). Proposition 4.8. For any D( F ) ∈ dag(G): sol(G) = α ∗ α ∈ {0, 1} F ∧ ∀x ∈ F : α (x) = α FRMD( F ) (x) . Proof. ⊇) If the equality holds for F , then (4.7) makes it hold also for all other nodes. Then, for every x ∈ G, we have that (∗) α ∗ (x) = 1 ⇔ α [FRMD( F ) (x)] = 1, and hence α ∗ (x) = 1 ⇔ ¬α ∗ ( y ) ∧ ¬α FRMD( F ) ( z) = 1 (∗) y ∈l( N + L (x)) z∈ N + R (x) ∗ ∗ ⇔ ¬α ( y ) ∧ ¬α ( z) = 1 (∗) y ∈l( N + L )(x) z∈ N + R (x) ⇔ ¬α ∗ ( y ) = 1 N + (x) = l N + + L (x) ∪ N R (x) y ∈ N + (x) ⇔ ∀ y: y ∈ N + (x) → α ∗ ( y ) = 0. ⊆) For an arbitrary β ∈ sol(G), let α = β| F . Since F ∈ B (G), so α = β . But since α and α ∗ both are functions and α ∗ ⊆ α , so α∗ = α = β . 2 In Example 4.6, the reduced system simplified to one trivial equation b = b, so the graph G has exactly two solutions, each induced from a solution to this equation. Expressing this proposition in terms of the assignment α , induced in the dag D( F ) ∈ dag(G) from the assignment α ∈ {0, 1} F to its new sinks F , gives the following claim: sol(G) = α |G α ∈ {0, 1} F ∧ ∀x ∈ F : α x = α (x) . The above algorithms, whether utilizing the reduced system of equations EQU D( F ) (G) or merely inducing values directly in D( F ), rely on finding an arbitrary feedback vertex set. The following subsection presents an algorithm for which it suffices to find a subset of nodes breaking only the even cycles. 4.2. Breaking even cycles Dually to Richardson’s theorem, we have the following fact. Lemma 4.9. If G = ∅, sinks(G) = ∅, and G has no even cycles, then sol(G) = ∅. Proof. Assume towards contradiction that α ∈ sol(G). Clearly, α 1 = ∅. So choose a ∈ α 1 and consider a sequence of sets V i : N → P ([a)) such that V 0 = {a}, V 2i +1 = x∈ V 2i N + (x), V 2i +2 = x∈ V 2i+1 { y x }, where y x ∈ N + (x) is such that α ( y x ) = 1 (if it exits). By correctness of α , such a sequence satisfies i V 2i ⊆ α 1 and i V 2i +1 ⊆ α 0 and, as sinks(G) = ∅ so ∀i ∈ N: V i = ∅. Also, for every n ∈ N and every an ∈ V n there is a sequence of edges a, a1 , a2 , . . . , an such that ∀i: ai ∈ V i ∩ N + (ai −1 ). So there is an infinite sequence of edges p = a, a1 , a2 , . . . such that ∀i: ai ∈ V i ∩ N + (ai −1 ). Since G is finite this is only possible if ∃ j > i: ai = a j . Let i , j be a pair satisfying this condition and such that for all i k < l < j: ak = al . The sequence of edges C = ai , ai +1 , . . . , a j must be of even length since otherwise ai ∈ α 1 ∩ α 0 . We have found an even cycle, contradicting our assumption about G. 2 156 M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 From an algorithmic point of view, the observation that odd cycles are the only obstacle to the existence of kernels suggests (not always efficient) algorithms based on breaking the odd cycles. The above observation suggests that we can restrict attention to even cycles, and the following proposition makes this suggestion precise. A subset of vertices X ⊆ G is an even cycle transversal, if G \ X contains no even cycles. Proposition 4.10. If X ⊆ G is an even cycle transversal, then X ∈ B (G). Proof. For an arbitrary β ∈ sol(G), Lemma 3.6 gives that β| X = β|dom(β| X ) . Assume towards contradiction that G = G \ dom(β| X ) = ∅. By Lemma 3.6.2, G has no sinks, and also ∀x ∈ G : ∀ y ∈ N + (x) ∩ dom(β| X ): β( y ) = 0. This implies that β = β|dom(β| X ) ∪ β for some β ∈ sol(G ). However, as G is a graph with no sinks and no even cycles we have sol(G ) = ∅ by Lemma 4.9. This is our contradiction. 2 Clearly, for many graphs this represents a significant improvement over the algorithms from the previous subsection, reducing the worst case exponent from the number of cycles to the number of even cycles. Even though an implementation seeking to take advantage of this encounters the problem of finding an even cycle transversal (finding a minimum such is NP-hard, and not known to be FPT), one can argue also for the practical relevance of Proposition 4.10, besides the merely theoretical improvement. In some situations, it can happen that an even cycle transversal can be easily obtained from the input. In general, it often suffices to find a small – and not a minimum – such set and this can be done relatively efficiently.8 Example 4.11 (3.2, 4.4 continued). The graph G has two even cycles: b, c , b and b, c , d, a, b. Trying b = 1 (respectively, 0), induces the assignment α (respectively, β ) as in Example 3.2. The induced assignments are functions and hence solutions by Proposition 4.10 and Definition 4.1. The above example might be insufficient since b is, in fact, a feedback vertex set, so the conclusion follows already by Proposition 4.2. The following example, shows the difference. Example 4.12. In the following graph G b d f a c e the only even cycle is C = a, b, d, c , a. Breaking it at, say a, leads to two trials: a = 1 induces b = c = d = 0 but then d = 0 gives a conflict inducing b = 1, and a = 0 induces b = 1, d = 0, but no more vertices obtain any induced values. Neither assignment induces a solution, so Definition 4.1 and Proposition 4.10 imply sol(G) = ∅. In the graph G \ {e }, we have the same even cycle. Trying a = 1 gives a conflict as above, but from a = 0, we obtain b = 1 = c and d = 0 = f , yielding a solution. This concludes the first set of our algorithms for KER. Except for the obvious algorithm using CNF (G) from (2.6), testing SAT (of boolean equations) is of use here only as a possible enhancement. The algorithms from the present section can be very efficient when applied to graphs with few (even) cycles and, particularly, when cycles or feedback vertex sets are easily read from the input. We do not think, however, that they will be optimal for all kinds of instances. Their likely shortcoming will arise from the comparison to the algorithm proposed in the following section, which also shows much tighter connections between KER and SAT. 5. KER and SAT Algorithms in the previous section perform the initial simplification, Algorithm 3.15, extract a relevant subset X of ver- tices and then answer KER solving a system of equations or trying blindly assignments to X , which induce the assignments to the whole graph. 8 Finding a minimum feedback vertex set is shown to be FPT in [5]. Given a graph with vertices G, and such a subset V ⊆ G, one can try moving, one at a time, a vertex x from V back to the induced subgraph G \ V , checking if the resulting, induced subgraph G \ V ∪ {x} has an even cycle. This last problem is in P by the recent result from [31]. If no even cycle appears, we continue with V \ {x} and the induced subgraph extended with x, while if some does, x remains in V . What remains in V , after trying all its vertices, is an even cycle transversal. M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 157 The following, recursive Algorithm 5.1 performs simplification and induction at each recursive call, returning an element of sol(G), if such exists, and ⊥ otherwise. It takes an additional argument, the partial assignment α , and constructs its extension to a complete solution, if possible, or returns ⊥ if not. Algorithm 5.1 sol(G, α ) Input: A digraph G and a partial assignment α (initially α = ∅). Output: β ∈ sol(G) with α ⊆ β if it exists, ⊥ otherwise. 1: α := α . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . / Definition 3.1 applied to G ∪ dom(α ) 2: if α is not a function then return ⊥ 3: G := G \ dom(α ) 4: if G = ∅ then return α 5: G := simp (G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . / Algorithm 3.15 6: if G = ⊥ then return ⊥ 7: if G has maximum degree 2 return sol2 (G, α ) 8: Choose some x ∈ G 9: return sol(G, α ∪ {x, 1}) ⊕ sol(G, α ∪ {x, 0}) The sub-routine sol2 is used to solve more efficiently graphs that have maximum degree 2. It is given in Algorithm 5.2 and is probably best explained by simply stating Lemma 5.3. Algorithm 5.2 sol2 (G, α ) Input: A digraph G of maximum degree 2 and some partial assignment α Output: β ∈ sol(G) such that α ⊆ β , ⊥ otherwise. 1: α := α . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . / Definition 3.1 2: if α is not a function then return ⊥ 3: G := G \ dom(α ) 4: if G contains an odd cycle without any reversed edge then 5: return ⊥ 6: if bord(α ) = ∅ then 7: return α ∪ β for any β ∈ sol(G) 8: Choose some connected component S ∈ G 9: B = {β ∈ sol( S ) | N + (bord(α )) ∩ β 1 = ∅} 10: if B = ∅ return β∈ B sol2 (G, α ∪ β) 11: else return sol2 (G, α ∪ β) for any β ∈ sol( S ) Lemma 5.3. For any, sinkless, loopless graph G of maximum degree 2: G has a solution iff every odd cycle in G has a reversed edge. Proof. Let G S = { S 1 , S 2 , . . . , S n } be the n connected components of G. Clearly, sol(G) = ∅ iff ∀1 i n: sol( S i ) = ∅. Since each component S i has maximum degree 2, so its underlying graph S i is either a path or a chordless cycle. So either S i does not have an odd cycle or else it is an odd cycle, possibly with some reversed edges. Solvability of S i follows from Richardson’s theorem in the first case. For the second case of S i being an odd cycle, if S i has no reversed edge then, by Lemma 4.9, S i does not have a solution. If S i has one or more reversed edges we show that it has a solution. Write S i as x0 x1 x2 . . . xn where n + 1 = | S i | is odd, and xi + + 1 ∈ N (xi ) for all i 0, with addition modulo n. Choose xi , xi +1 such that also xi ∈ N + (xi +1 ), and define α by α 1 = {xi } ∪ 0 j <i {x j | (i = j ) mod 2} ∪ i +1< j n {x j | (i = j ) mod 2}. It is easily verified that α is a solution for S i 2 Correctness of Algorithm 5.2 follows readily from Lemma 5.3. In particular, line 4 determines if G has an odd cycle without reversed edge and the algorithm proceeds only if it does. After this the question of solvability of G is settled by Lemma 5.3. We must acquire the actual solutions for use later in the algorithm. But this is easy – the brute-force approach, for instance, would do it by simply computing all maximal independent sets in all components. In lines 7 and 11 we require only one solution (to G and a component S ⊆ G respectively), and this is even easier. For the case of odd cycles with reversed edges we refer to the proof of Lemma 5.3 where we construct an actual solution. For all other components, S, a solution is found by simply assigning 1 and 0 to every other vertex along S, which works since S is either a path or an even cycle without any sinks nor loops. Consequently, the vertices assigned 1 form an independent set, while every other vertex, on pain of contradicting sinklessness, will have some edge going into this set. Now, the reason why the algorithm cannot simply stop upon having noted that G is solvable is that each vertex in bord(α ) requires that one of the vertices it points to is 1. This means we have to search through a potentially large collection of solutions for G. This happens in lines 8–10 and is considered in more detail in the proof of Proposition 5.5 below. Correctness of Algorithm 5.1 is now quite obvious, although strictly speaking, it is not an algorithm but a class of algo- rithms. For instance, the simplification of a graph, as well as inducing of values from a given partial assignment, could be defined otherwise and replace those used here. Also, several minor issues are left for more detailed decisions. For instance, α is only a solution to the reduced graph obtained after a possible series of contractions at line 5. The solution for the actual input graph has to be reconstructed from it by a corresponding series of applications of Fact 3.10. 158 M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 The polynomial (in the size of the original graph) time, spent in each recursive call on the computation of α , can be improved since, once it starts going, it only needs to consider border vertices from dom(α ), Definition 3.4. A conflict (a vertex assigned two values so that α is no longer a function) must occur at these vertices, and once it is detected, the algorithm can return the failure value at line 2. Two more central decisions are left open. The operation ⊕ denotes angelic choice, ignoring the possible argument ⊥, i.e., x ⊕ ⊥ = ⊥ ⊕ x = x, and x = ⊥ ∧ y = ⊥ → (x ⊕ y ) ∈ {x, y }. (It is also used in line 10 of Algorithm 5.2.) An implementation has to decide how to perform the choice of the first value tried. Finally, we have not specified how to choose an x ∈ G for branching at line 8. A specific instance of the above algorithm was presented in [12]. It performs no simplification and branches only from maximal degree cyclic vertices. Proposition 4.2 guarantees sufficiency of branching only from cyclic vertices, and choosing maximal degree is often sound.9 However, it is not always the best choice, as evidenced by the following example. Example 5.4. Consider the graph G: w q y z x r The minimal degree is 2 = deg( y ) = deg( z) = deg(r ). Branching from y gives two cases: y = 1 induces the solution with x = q = z = 0 and y = w = r = 1, y = 0 induces the solution with q = z = r = 1 and x = y = w = 0. Similarly, each branching from z induces a solution. So, Algorithm 5.1 branching first on some nodes with minimal degree, terminates successfully in just one recursive call. This need not happen when branching on x, the only vertex with maximal degree. Inducing from x = 1 gives y = q = 0 which yields a conflict at y, while x = 0 induces only r = 1, i.e., requires further recursive calls. It is probably too much to ask for an algorithm that always makes the optimal choice of branching vertex. As a simple and general rule for arbitrary graphs, choosing a vertex with maximal degree may be a good heuristic. Taken in conjunction with Algorithm 5.2, it suffices to establish the following upper bound on the time spent by Algorithm 5.1. Proposition 5.5. Algorithm 5.1 can be made to run in time O ∗ (1.427|G | ), for all G. Proof. Sinks are removed already when inducing from the empty assignment and loops when removing the contradictions, so all graphs, G , considered by Algorithm 5.1 after these initial steps are loopless and sinkless. Thus, all vertices have degree 1 or more. (A) Consider first the case of repeated branching at line 8 on vertices with degree 3 or more. Methods invoked in lines 1–6 are linear (or low polynomial). Trying assignment of 0 may not induce any values, while assignment of 1 induces values to at least 3 neighbours. This gives the recurrence T (|G |) = T (|G | − 1) + T (|G | − 4) for arbitrary subgraph G ⊆ G. So if the algorithm branches always at line 8 and terminates at 2, 4 or 6, we get the upper bound of O ∗ (1.381|G | ). (B) Another case occurs when recursion terminates at line 7 with calls to sol2 . There are then two subcases: (B.1) If bord(α ) = ∅, then if G = G \ dom(α ) is solvable, any solution to G extends α and its existence is checked in polynomial time in line 4. (If needed, a solution can be found as suggested in the discussion following Lemma 5.3.) The whole case is therefore handled, lines 1–7, in polynomial time with no branching. (B.2) The complex case is when bord(α ) = ∅. Then, if the subgraph G = G \ dom(α ) is solvable, we may risk having to generate all its solutions, in search for one matching its 1’s against all border vertices. This happens in lines 8–10 of Algorithm 5.2. The algorithm chooses some component S of G at line 8, and branches on its every solution that leads to a reduction in the size of the border. The depth of the recursion in sol2 is thus bounded by the minimum among the number of disjoint components in G and the size k = |bord(α )| of the border. Taking all |G | components to be of the same size l, gives l as their number in G . (This simplification is justified by the cases identified below.) At each recursion level, line 9 of Algorithm 5.2 inspects all solutions of the current connected component S with max degree 2 and size l. Denoting the number of such solutions by S (l), gives the following formula for the upper bound on the complexity of sol2 (G , α ): |G | S (l)min( l ,k) . (5.6) 9 Whether degree refers to the in-degree, out-degree or their sum may depend on the implementation and, in particular, on the way of inducing. In our case, inducing happens both along and against the direction of the edges, so degree of a vertex means for us the number of all (both in and out) neighbours. M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 159 This reflects the worst case of branching at line 10, for each component of G , which contributes a multiplicative factor S (l) ∗ · · · to the complexity. Recursive calls at line 11 contribute only an additive factor S (l) + · · ·, since they allow to use and propagate arbitrary solution β of the current component. Now, S (l) is limited from above by the number of maximal independent sets which, for the concerned graphs with max degree 2, satisfy the recurrence S (l) = S (l − 2) + S (l − 3), with S (l) approaching 1.321l as l grows, cf. [17]. Still, this is only the behaviour in the limit, while the initial conditions for low l’s give worse bounds, as can be seen considering the following two cases: (B.2.1) If for all S i ∈ G , li = | S i | 4, then the number of solutions in any such S i is bounded from above by 1.381l , the worst case obtaining for 5-cycles, l = 5, with up to 5 < 1.3815 solutions. By substituting into (5.6) we |G | |G | get 1.3815∗min( 5 ,k) 1.3815∗ 5 = 1.381|G | , i.e. the upper bound not exceeding that from case (A). (B.2.2) If for some S i ∈ G , we have li 3, the worst case obtains when all components of G are symmetric 3-cycles (i.e., with all edges reversed), since they have 3 solutions each.10 Now, let n denote the number of times we encounter the upper-bound in (5.6), i.e., the number of times Algorithm 5.1 terminates in line 7 with a call to sol2 on such a collection of 3-cycles. Let G1 , G2 , . . . , Gn and k1 , k2 , . . . , kn denote the subgraphs and the numbers of border vertices in each of these n instances of the problem (assuming always the greatest possible ki = |dom(αi )|, i.e. |G i | = |G | − ki ). Instead of giving the running time in terms of each |G i | we express it directly in terms of |G |, as the sum of all n instances of (5.6), each with S (3) = 3 for symmetric 3-cycles: n |G |−ki 3min( 3 ,ki ) . (5.7) i =1 |G |−ki We maximize 3min( 3 ,ki ) for each ki , noting that since both functions of ki are monotone, one decreasing |G | and the other increasing, the maximum is obtained when both are equal, i.e., for ki = 4 . Now, n and the ki ’s are mutually dependent but (5.7) reaches the maximum when all branches of the recursion tree |G | 3| G | |G | have already processed ki = 4 vertices, and call sol2 with |G i | = 4 . Then, according to (A), n = 1.381 4 . To see that this is the worst case, first assume that any of the branches continues splitting, i.e., that Al- |G | gorithm 5.1 continues branching at line 9 with subgraphs smaller than 4 . This amounts to increasing |G |−ki |G |−ki |G | 3| G | ki , so min( 3 , ki ) = 3 . Consequently, in (5.7) the term t = 3 4 =3 12 is replaced by two terms, 3|G |−4 3|G |−16 t1 = 3 and t 2 = 3 12 , for the subgraph reduced by 1, respectively 4 vertices, according to the recur- 12 rence from (A). But t 1 + t 2 < t, and the sum keeps thus decreasing if splitting and reducing the size of the subgraphs continues in this way. If, on the other hand, there are fewer than n branches since some termi- |G | |G | nate earlier for ki < 4 , then (5.7) has fewer terms, some smaller than 3 4 . Thus, the maximum of (5.7) is |G | |G | |G | 1.381 4 ∗3 4 = 4.143 4 1.427|G | . |G | (B.2.2) is the overall worst case. The obtained 1.427|G | dominates 1.381 4 , which should be added as the time spent on reaching the n calls to sol2 terminating all the branches. We obtain thus O ∗ (1.427|G | ) as the overall upper bound for the whole Algorithm 5.1. 2 A more detailed analysis might improve this bound but even the estimate given here shows that Algorithm 5.1 is better than checking every possible maximal independent subset of G, i.e., every potential solution. In particular situations it is possible to specify the choice of branching vertex more carefully and thereby get improved running times for certain classes of graphs. This is done below for the class of oriented graphs. 5.1. Oriented graphs Many possibilities of improvements of Algorithm 5.1 exist in the interplay of the different choices involved and an interesting, related, question is how much the complexity can be improved when attention is restricted to special classes of graphs. We show that for the oriented graphs it is possible, by choosing x ∈ G for branching in a certain way, to obtain a better bound than O ∗ (1.427|G | ). For the analysis in this subsection Algorithm 5.2 will play no role, so for simplicity we assume that Algorithm 5.1 is run to completion, i.e. without calling sol2 in line 7. In fact, we establish an upper bound on the number of kernels in oriented graphs, not just the time it takes to decide if one exists. Proposition 5.8. For oriented G: |sol(G)| 1.286|G | and Algorithm 5.1 can run in O ∗ (1.286|G | ). 10 This might not be immediately obvious, but the analysis performed here for 3-cycles can be performed in exactly the same way for 2-cycles, yielding an upper bound which is smaller than for 3-cycles. The result for 3-cycles below is worse than for li 4 in B.2.1, so assuming only some (but not all) components to be 3-cycles gives a better case. 160 M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 Proof. We run Algorithm 5.1 on some oriented graph G. Since sinks, contractible paths and basic contradictions are removed without branching we assume that G is free of these. We analyze the running time by considering the following possible cases: 1. G has a vertex x with one or more in-neighbours, | N − (x)| 1, and a single out-neighbour { y } = N + (x). Branching from any such x ∈ G, gives the two cases: (a) x has a single in-neighbour: Then, since G does not contain any contractible paths, the in-neighbour of x must be y and then we have a cycle of length 2. Since G is obtained from some oriented graph this cycle must originate from the contraction of some path which led to the reduction of input size by at least 2. We are thus justified to view the actual size as |G | − 2, this earlier reduction being polynomial. The assignment of either 1 or 0 to x induces a value at least to y, giving the recurrence T (|G |) = T (|G | − 2 − 2) + T (|G | − 2 − 2) = 2T (|G | − 4). (b) x has two in-neighbours: Then there are two further subcases: • y is an in-neighbour of x: Then there is a 2-cycle in G and we can view its size as in the previous case, |G | − 2. Since x has another neighbour, distinct from y, we induce values to at least 2 other vertices when we assign 1 to x while we induce 1 to y when we assign 0 to x. So we obtain the recurrence T (|G |) = T (|G | − 5) + T (|G | − 4). • y is not an in-neighbour of x: Then we induce values to 3 other nodes when we assign 1 to x. If we assign 0 to x we induce 1 to y. But since G is sinkless and y is not an in-neighbour of x, there is some out-neighbour of y, distinct from x, that is induced 0 in this case. It follows that we get the recurrence T (|G |) = T (|G |− 4)+ T (|G |− 3). This is the worst possible situation for case 1. Every G with maximum degree 3 or less will fall under the current case, i.e., have a vertex x with a single out- neighbour. This follows since G is sinkless and therefore has at least one final strongly connected component S with | S | 2. Clearly, every vertex in S has at least one in-neighbour and one out-neighbour. But if every vertex in S has two out-neighbours then since S is final it follows that there is a vertex in S with two or more in-neighbours, contradicting the fact that no vertex has degree more then 3. Consequently, in the following case, when no vertex with a single out-neighbour exists, the degree of G is at least 4. 2. Case 1 does not apply and G has maximum degree 4. Then there is some final strongly connected component S ⊆ G where every vertex has more then one out-neighbour. It follows that every vertex in S has exactly two out-neighbours and exactly two in-neighbours. To see this note that since S is final the sum of out-neighbours over vertices in S must be less then or equal to the sum of in-neighbours over vertices of S. So either every vertex has two in-neighbours or else there is some vertex that has more then two in-neighbours, the latter option being ruled out by G having maximum degree 4. We analyze the situation with branching on an arbitrary vertex x from S, obtaining two cases: (a) x has some out-neighbour that is also an in-neighbour. Then there is a cycle of length two that has been obtained from contracting a path. This yields T (|G |) = T (|G | − 2). Also, on assignment of 1 to x we induce values to at least 2 other vertices while on assignment of 0 to x we do not necessarily induce any values. So the recurrence becomes T (|G |) = T (|G | − 5) + T (|G | − 3). (b) All neighbours of x are distinct. Then, on assignment of 1 to x we induce values to 4 other vertices while if we assign 0 to x then we might not induce anything and so might have to solve a problem of size T (|G | − 1). However, since we removed x from G to obtain the graph corresponding to this subproblem there is a vertex with only one out-neighbour in this graph. This gives us, by case 1), the worst case recurrence T (|G | − 1) = T (|G | − 1 − 4) + T (|G | − 1 − 3) = T (|G | − 5) + T (|G | − 4). The recurrence is thus T (|G |) = 2T (|G | − 5) + T (|G | − 4). 3. Case 1 does not apply and G has a vertex of degree 5. Then we branch on such a vertex obtaining T (|G |) = T (|G | − 1) + T (|G | − 6). The recurrence from 3 is the overall worst-case in this analysis, giving the bound O ∗ (1.286|G | ). 2 Notice that the proofs of Propositions 5.5 and 5.8 do not specify completely how to choose a branching vertex, but only narrow the choices down to sets of vertices with some desired properties. The question about the exact choice is still highly relevant for an implementation. 5.2. DPLL If, in Algorithm 5.1, we take G to be a CNF formula, the algorithm turns out to be exactly the pseudo-code for the DPLL algorithm for satisfiability, [10,9], which is the basis of virtually all modern SAT-solvers (for a relatively recent overview, one can consult e.g., [23]). Inducing in the first line amounts then, typically, to the unit propagation and the condition ‘α is not a function’ amounts to the ‘conflict’ in the SAT-solving parlance. An α satisfying all clauses in G is returned, line 4. Otherwise, the remaining problem is preprocessed for the next recursive call, line 5. Simplification may include elimination of clauses with pure literal (occurring only positively or only negatively), as well as learning and many other heuristics depending on the implementation. We suggested, similarly, a wide range of possible choices in Section 3. Choosing then wisely the branching literal x is one of the crucial aspects of successful SAT-solvers. The coincidence of Algorithm 5.1 and DPLL goes beyond the mere fact of both instantiating the general branch and bound schema. It involves also the fact that kernels can be seen as solutions, (2.2), and that during their gradual construction, M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 161 partial assignments induce values to the neighbourhoods, in analogy to unit propagation and other constraint propagation techniques in SAT. One may therefore expect the lessons from SAT-solving to be relevant for KER-solving. The crucial aspects of SAT-solvers concern the efficiency and range of inducing values from a given, partial assignment, line 1, and the choices of the branching point and its value required to get the most out of the propagation of constraints implied by the performed choices, line 8. These two elements occupy the critical position, as SAT-solvers spend around 80% of time on this phase. It is reasonable to expect a similar situation in KER-solving. The importance of this aspect has been illustrated by the complexity analysis. The bound O ∗ (1.427|G | ) for the general case and its improvement to O ∗ (1.286|G | ) for oriented graphs, were obtained due to the respective graphs enabling, at each recursive call, some minimal extension of the current partial assignment, thus reducing the remaining search space. This justifies also the expectation that Algorithm 5.1, propagating partial assignments recursively, will outperform the algorithms from Section 4, which do not take any advantages of the attempted partial assignments. There seems to be no general guidance in actually performing the choice of branching vertex. High degree may often work well but, as we saw in Example 5.4, is not necessarily optimal. It might be too much to ask for a strategy working best in all cases but uncertainty at this point may also reflect the lack of experience and overview of the problem instances. In SAT-solvers, the choice is performed depending on the subclass of instances for which the solver is designed. Choice of the branching literal in solvers for random-SAT uses a lookahead procedure, which determines the reduction in the search space effected by each choice. Solvers for industrial-SAT can use the results of learning from the earlier encountered conflicts. We have thus mentioned another important aspect: a SAT-solver is designed for a specific category of instances. A solver deciding SAT quickly on instances from industrial, or other rational and systematic contexts (using additional techniques of conflict analysis and clause learning), may perform poorly on random instances. For random instances, “local search” heuristics for merely finding a solution may be extremely efficient but remain incomplete, being unable to conclude un- satisfiability. The winner of several categories of the SAT-competition in previous years, SATzilla, is actually a collection of various algorithms, which are only chosen appropriately depending on the analysis of the actual instance. The lack of one, uniform approach and the need to adjust solutions and heuristics to appropriately limited subclasses of instances is a general lesson from SAT. One can expect KER to face the same challenge of identifying such relevant subclasses. It is likely, however, that just as the DPLL schema is at the core of virtually all efficient procedures for solving SAT, so does Algorithm 5.1 express the core structure of efficient approaches for solving KER. An important case of subclasses are those for which the problem becomes tractable. For instance, 2-SAT is NL-complete and Horn-SAT is P-complete. Search for sufficient conditions for kernel existence is an active research field, e.g., [1,14,15,18, 3], with a recent overview in [4]. Further research should, in our opinion, consider also the problem of finding classes of graphs which may not admit kernels but have complexity bounds for the KER-problem below NP-completeness.11 Finally, let us mention an interesting SAT phenomenon – phase transition. When the clausal density (the ratio of number of clauses to the number of variables) is below 4, the theory is, with high probability satisfiable, while when it exceeds 4.5, the theory is almost certainly unsatisfiable. The instances with the clausal density around the transition value, 4.25, are the most difficult to solve. It is not obvious how to translate this into the graph language. Graph density (average degree) seems to be a relative of the clausal density, so one might conjecture that sparse graphs should be solvable with high probability (as are, e.g., all trees, dags and 50% of all cycles.) Very dense graphs might be expected to be relatively easy (e.g., kernels in a weakly complete digraph G (one with a complete underlying graph G) are exactly nodes x satisfying N − (x) = G \ {x}) but should be expected to be unsolvable. A naive guess might expect the most difficult problems somewhere in the middle between these two extremes. This is partially confirmed by the tests of the algorithm presented in [12]. According to them, sparse graphs and graphs with density over 50% are relatively easy, while those with density around 15–20% are most difficult. On the other hand, it has been shown in [16] that the kernel problem is NP-complete for planar digraphs of degree at most 3, so the “easy” instances of KER can certainly be difficult enough. It remains to be seen if phase transition from SAT has a counterpart in KER and, if so, under what measure of graph density. 5.2.1. Why not reducing to SAT? The relevance of SAT for KER should not be overestimated to the point of dismissing the latter by merely translating its instances into SAT and using SAT-solvers. Sophistication of modern SAT-solvers might suggest such a move and can even be expected to yield good results in various cases. The main reasons, justifying our separate treatment of KER, are complexity considerations. According to the bound on the |G | number of maximal independent subsets, 3 3 , and the possibility to produce them with polynomial delay, general KER can be solved in O ∗ (1.443|G | ). The analysis of Algorithm 5.1 lowers this bound to O ∗ (1.427|G | ). For general SAT, on the other 1 n(1− hand, the best known upper bound is of order O ∗ (2 ) O (log (m/n)) ), where n is the number of variables and m the number of clauses, [8]. (Note that this converges to O ∗ (2n ) as the ratio m/n grows. For DPLL solving k-SAT, 2n is also the lower bound, as k goes towards infinity, [28].) SAT-instances of form (2.6), representing KER, provide thus a non-trivial subclass which can be solved more efficiently than this general upper bound, irrespectively of the m/n ratio. 11 One non-trivial result of this kind follows from the work done on stable matchings. An algorithm presented in [21] decides existence of stable matchings for the roommates problem in polynomial time. This solves KER in polynomial time for any digraph that is an orientation of a line graph and for which every weakly complete subgraph is acyclic. 162 M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 On a more practical side, it is possible that instances of KER, when translated into SAT, would be amenable to a uniform processing with the gains comparable to the difference between these two upper bounds. It is also possible that subclasses of digraphs, like the oriented ones, making KER easier, could be translated into instances making also SAT easier. But the gains in complexity, both for the general KER and for the oriented graphs, were based on specific strategies for selecting active literals, which do not seem to be reflected in those applied in SAT-solvers. To use SAT-solvers with comparable increase in efficiency will almost certainly require their adjustments and is a possible direction for further research. Similar remark applies to the simplifications from Section 3. When translated into the operations on the translated SAT instances, they correspond to techniques used in SAT-solving: basic contradictions can be discovered by means of implication graphs for binary clauses, while contraction of isolated paths amounts to detection of equivalent variables from binary clauses. Many SAT-solvers perform such simplifications only at the stage of preprocessing, while Algorithm 5.1 performs them dynamically at each recursive call. Indeed, for general instances of SAT, the cost of their repetitive use tends to exceed the gains (though some use of such “inprocessing” may be viable, [20]). But for KER instances, propagation of values along the isolated paths and checking neighbourhood of a vertex are among the simplest possible operations. As many isolated paths or basic contradictions can be expected to appear only dynamically, their repeated simplification may be worthwhile. A similar move could be easily implemented in a SAT-solver, but it is typically not included, due to low average cost/gain ratio. In special situations, the difference may be of exponential order. Example 5.9. Consider the following graph which should be seen as arising only during computation from removal of nodes assigned 0. All nodes c i and ai can have more outgoing edges. y z x ··· a1 ... a2 ... ··· ak ... b1 c 1 ... b2 c 2 ... ··· bk ck ... Its translation into CNF, following (2.6), yields the clauses: (i) ai ∨ b i ∨ c i , ¬ai ∨ ¬b i , ¬ai ∨ ¬c i and b i ∨ c i , ¬b i ∨ ¬c i – for each lower triangle, and (ii) x ∨ y i ai , ¬x ∨ ¬ y, ¬x ∨ ¬ai (for all 1 i k), y ∨ z, ¬ y ∨ ¬ z and x ∨ z, ¬x ∨ ¬ z. Assume a SAT-solver selects, as the active literals, consecutive c i ’s. Trying c 1 = 1, the unit propagation yields a1 = b1 = 0 and this operation is repeated k times, after which the clauses in (ii) are reduced to: (iii) x ∨ y, ¬x ∨ ¬ y, y ∨ z, ¬ y ∨ ¬ z and x ∨ z, ¬x ∨ ¬ z. Now a conflict results trying both values 0, 1 with any choice of the active literal. Backtracking one c i literal at the time, and trying c i = 0, gives the same result, so that after 2k+1 trials, this backtrack search concludes unsatisfiability.12 Algorithm 3.15 identifies contradictions efficiently (footnote 5) and sets first all ai = 0. The rest of the graph is processed in linear time. Algorithm 5.1 may assign various c i ’s and/or b i ’s before going to x, y , z, where two attempts with 0 and 1 at any of these nodes unveil unsatisfiability. In short, solving KER directly gives gains in complexity and efficiency and corresponding gains could be achieved by fine-tuning a SAT-solver to the specific form of SAT-instances arising from KER. However, in order for this fine-tuning to give comparable effects, it would have to follow the results of the direct analysis of KER, as presented in this paper. 6. Conclusions We have studied the problem, KER, of solvability of digraphs or, in the more standard language, of determining if a given digraph has a kernel. We began by observing its equivalence to the problem of satisfiability of propositional formulae, 12 Such claims must, of course, be taken with serious reservations. A particular solver, using a particular strategy and heuristic, might actually happen to avoid the problem. Although the example seems also to depend on the strategy for selecting the active literals, one can adjust it to many different strategies, since all c i might possess other outgoing edges (e.g., occur in most clauses). The main point is that simplifications of such form are, typically, performed by a SAT-solver only in preprocessing and not during the computation. M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 163 whether in usual or infinitary propositional logic. Seeing different applications of digraph kernels, in areas such as game theory and non-classical logics, it is conceptually rewarding in itself to see that kernels can be expressed – equivalently and naturally – as models of propositional theories. We have proposed a series of graph reductions which preserve and reflect solvability and, being linear (or low polyno- mial), can be incorporated into the algorithms for KER-solving. In Section 4, we gave two such algorithms: one based on the extraction of a feedback vertex set, F , and another reducing the complexity even to O ∗ (2| E | ), where E is an even cycle transversal. As a consequence, KER is FPT not only in the size of F but also of E. (As an instance of reducing KER to SAT, we gave a variant of the first algorithm where solving a reduced system of boolean equations replaced blind trials of all assignments to the sinks of a labeled dag, representing the input graph.) These algorithms can be expected to perform well on graphs with few (even) cycles and, especially, when even cycle transversal or, at least, feedback vertex set can be easily obtained from the input. The question about a general algorithm for arbitrary instances of KER, led in Section 5 to another, new algorithm, which turns out to be virtually identical to the well-known DPLL algorithm, underlying modern SAT-solvers. From this we dare draw a series of conjectures for further development of the research on KER. It suggests that this final algorithm may outperform others on the large, practical instances of KER. This, however, will depend on more detailed decisions, because the presented sketch gives only a class of algorithms. It leaves open the possibility for further choices and improvements at points were such possibilities were realised or are still investigated in the context of SAT-solving. Experience with SAT- solving suggests that one will have to adjust choices and heuristics to specific subclasses of instances. As a particular case, we showed that, with a specific branching strategy, oriented digraphs guarantee a certain minimum of inducing during the recursive trials, allowing to reduce their worst case bound to O ∗ (1.286|G | ). For the general case of arbitrary graphs, one can still ensure minimum inducing guaranteeing the worst case bound not exceeding O ∗ (1.427|G | ). We have shown that SAT-solving can be, to some extent, incorporated in KER-algorithms. More importantly and gen- erally, however, solving KER appears to pose the same kind of choices and challenges, as met earlier in the design of SAT-algorithms. One can therefore expect that issues known from SAT, like those exemplified in Section 5.2, have graph- theoretic counterparts that will come up in the design of KER-algorithms. This itself may provide an independent motivation, and a specific direction, for the further study of KER. On the other hand, it does not seem unreasonable to expect that SAT- solvers may eventually benefit from KER-algorithms. The fact that KER can be formulated just as naturally in the language of graphs as in the language of logic or of game-theory, suggests that the problem can act as a useful point of reference for the exchange of ideas between these different fields. A better understanding of KER might very well foster a better under- standing of the relationship between different problems that, apart from being computationally demanding, often appear to have little in common. Having seen several new algorithms, the reader might expect also a report of their implementation and performance in practice. However, the analogy to SAT suggests that one should not rely here on any simple statements of the kind “algorithms perform well in practice”. More precisely, any such statement should be qualified by a careful description of the instances and actual performance measures. Experimentation with various implementations seems to be, in the case of KER as it is in the case of SAT, an independent and extensive field of work, not to be dismissed in a few sentences. We leave this important aspect for future work. References [1] Martine Anciaux-Mendeleer, Pierre Hansen, On kernels in strongly connected graphs, Networks 7 (3) (1977) 263–266. [2] Claude Berge, Pierre Duchet, Recent problems and results about kernels in directed graphs, Discrete Mathematics 86 (1990) 27–31. [3] Mostafa Blidia, A parity digraph has a kernel, Combinatorica 6 (1) (1986) 23–27. [4] Endre Boros, Vladimir Gurvich, Perfect graphs, kernels and cooperative games, Discrete Mathematics 306 (2006) 2336–2354. [5] Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, Igor Razgon, A fixed-parameter algorithm for the directed feedback vertex set problem, Journal of the ACM 55 (5) (2008) 1–19. [6] Vašek Chvátal, On the computational complexity of finding a kernel, Technical Report CRM-300, Centre de Recherches Mathématiques, Université de Montréal, 1973. http://users.encs.concordia.ca/~chvatal. [7] Nadia Creignou, The class of problems that are linearly equivalent to satisfiability or a uniform method for proving NP-completeness, Theoretical Computer Science 145 (1995) 111–145. [8] Evgeny Dantsin, Edward A. Hirsch, Worst-case upper bounds, in: Handbook of Satisfiability, 2008, pp. 341–362. [9] Martin Davis, George Logemann, Donald Loveland, A machine program for theorem proving, Communications of the ACM 5 (7) (1962) 394–397. [10] Martin Davis, Hillary Putnam, A computing procedure for quantification theory, Journal of the ACM 7 (3) (1960) 201–215. [11] Yannis Dimopoulos, Vangelis Magirou, A graph theoretic approach to default logic, Information and Computation 112 (1994) 239–256. [12] Yannis Dimopoulos, Vangelis Magirou, Christos H. Papadimitriou, On kernels, defaults and even graphs, Annals of Mathematics and Artificial Intelli- gence 20 (1997) 1–12. [13] Yannis Dimopoulos, Alberto Torres, Graph theoretical structures in logic programs and default theories, Theoretical Computer Science 170 (1-2) (1996) 209–244. [14] Pierre Duchet, Graphes noyau-parfaits, ii, Annals of Discrete Mathematics 9 (1980) 93–101. [15] Pierre Duchet, Henry Meyniel, Une géneralization du théorème de Richardson sur l’existence de noyaux dans les graphes orientés, Discrete Mathemat- ics 43 (1) (1983) 21–27. [16] Aviezri S. Fraenkel, Planar kernel and Grundy with d 3, dout 2, din 2 are NP-complete, Discrete Applied Mathematics 3 (4) (1981) 257–262. [17] Zoltán Füredi, The number of maximal independent sets in connected graphs, Journal of Graph Theory 11 (1987) 463–470. [18] Hortensia Galeana-Sánchez, Victor Neumann-Lara, On kernels and semikernels of digraphs, Discrete Mathematics 48 (1) (1984) 67–76. [19] Gregory Gutin, Ton Kloks, Chuan Min Lee, Anders Yeo, Kernels in planar digraphs, Journal of Computer and System Sciences 71 (2) (2005) 174–184. 164 M. Walicki, S. Dyrkolbotn / Journal of Discrete Algorithms 10 (2012) 146–164 [20] Marijn Heule, Matti Järvisalo, Armin Biere, Efficient CNF simplification based on binary implication graphs, in: Theory and Application of Satisfiability Testing, in: Lecture Notes in Computer Science, vol. 6695, 2011, pp. 201–215. [21] Robert W. Irving, An efficient algorithm for the stable roommates problem, Journal of Algorithms 6 (4) (1985) 577–595. [22] David S. Johnson, Mihalis Yannakakis, Christos H. Papadimitriu, On generating all maximal independent subsets, Information Processing Letters 27 (1988) 119–123. [23] Inês Lynce, João P. Marques-Silva, An overview of backtrack search satisfiability algorithms, Annals of Mathematics and Artificial Intelligence 37 (2003) 307–326. [24] Eric C. Milner, Robert E. Woodrow, On directed graphs with an independent covering set, Graphs and Combinatorics 5 (1989) 363–369. [25] John W. Moon, Leo Moser, On cliques in graphs, Israel Journal of Mathematics 3 (1965) 23–28. [26] Victor Neumann-Lara, Seminúcleos de una digráfica, Technical report, Anales del Instituto de Matemáticas II, Universidad Nacional Autónoma México, 1971. [27] Rolf Niedermeier, Invitation to Fixed Parameter Algorithms, Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, USA, 2006. [28] Pavel Pudlák, Russell Impagliazzo, A lower bound for dll algorithms for k-sat, in: Proceedings of the 11th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA’00, 2000. [29] Moses Richardson, On weakly ordered systems, Bulletin of the American Mathematical Society 52 (1946) 113–116. [30] Moses Richardson, Solutions of irreflexive relations, Annals of Mathematics. Second Series 58 (3) (1953) 573–590. [31] Neil Robertson, Paul D. Seymour, Robin Thomas, Permanents pfaffian orientations and even directed cycles, Annals of Mathematics. Second Se- ries 150 (3) (1999) 929–975. [32] Robert Tarjan, Depth-first search and linear graph algorithms, in: 12th Annual Symposium on Switching and Automata Theory, 1971, Oct. 1971, pp. 114–121. [33] John von Neumann, Oscar Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, 1944 (1947). [34] Michał Walicki, Sjur Dyrkolbotn, The graphical structure of paradox, 2010; http://www.ii.uib.no/~michal/graph-paradox.pdf.