Sara Zermani
email: sara.zermani@univ-brest.fr

Catherine Dezan

Reinhardt Euler

On Fault Diagnosis using Bayesian Networks ; A Case Study of Combinational Adders

Keywords: Bayesian inference, fault models, diagnosis, optimizations, adders

In this paper, we use Bayesian networks to reduce the set of vectors for the test and the diagnosis of combinational circuits. We are able to integrate any fault model (such as bit-flip and stuck-at models) and consider either single or multiple faults. We apply our method to adders and obtain a minimum set of vectors for a complete diagnosis in the case of the bit-flip model. A very good diagnosis coverage for the stuck-at fault model is found with a minimum set of test vectors and a complete diagnosis by adding few vectors.

Introduction

In recent years, the development of integrated circuit technology has accelerated rapidly. Accordingly, digital systems are built with more and more complexity. Fault diagnosis of circuits becomes an important and necessary part of the validation process, especially in the context of nanotechnology, where the fault rate becomes important. The classical diagnosis algorithms are based on either a "Cause-to-Effect" approach or an "Effect-to-Cause" approach [START_REF] Abramovici | Digital systems testing and testable design[END_REF]. The first one is based on a process of fault simulation. It generates a fault dictionary containing the responses of the circuit to a test sequence in the presence of a set of given faults [START_REF] Pomeranz | On dictionary-based fault location in digital logic circuits[END_REF]. The diagnosis is executed by comparing the responses of the circuit under test with those stored in the dictionary. The second approach uses a search process of failure position from information produced on the outputs of the circuit during the test application. This approach can be based on a process of critical path tracing (CPT) [START_REF] Abramovici | Digital systems testing and testable design[END_REF]. Recently, other methods of diagnosis combining both approaches have been presented in the literature [START_REF] Amyeen | Improving precision using mixed-level fault diagnosis[END_REF]. In addition, some diagnostic processes are based on the generation of a new type of test vectors called distinction vectors. In this case, the result provided by the logic diagnosis is used as input to a process of automatic generation of test vectors (ATPG, Automatic Test Pattern Generation) allowing to generate additional test vectors that are able to discriminate potential failures and thus to improve the diagnostic resolution [START_REF] Lin | Multiple-fault diagnosis based on adaptive diagnostic test pattern generation[END_REF] [START_REF] Zhang | A diagnostic test generation system[END_REF]. Bayesian network diagnoses are commonly based on models which exploit probabilities. The use of Bayesian inference can be viewed as a combination of both the "Effect-to-Cause" and the "Cause-to-Effect" approaches integrating a probability model. Many applications of Bayesian networks deal with the diagnosis of a limited number of representative elements of the system. For example, at the system level, the combination of genetic optimization with Bayesian networks provides a robust and powerful system-design tool [START_REF] Cao | Design of reliable system based on dynamic bayesian networks and genetic algorithm[END_REF]. At the architecture level, an approach of error modeling for nano-domain logic circuits using Bayesian networks is found in [START_REF] Rejimon | Probabilistic error modeling for nano-domain logic circuits[END_REF]. Bayesian networks have also been used for the diagnosis of the layout level [START_REF] Benware | Determining a failure root cause distribution from a population of layout-aware scan diagnosis results[END_REF]. (Master project from February 2013 to August 2013)

The objective and originality of this paper is to demonstrate the interest of Bayesian networks for the field of diagnosis of combinational circuits by integrating fault models to minimize the set of diagnosis vectors. Specific strategies are applied to regular arithmetic circuits like adders. The design of arithmetic structures with error detection and correction capabilities represents an important research topic, and since adders are essential building blocks in all arithmetic processing units, we have used them as our study case. In the first section of this paper, we present the Bayesian model for fault test and diagnosis and we show how the malfunctioning features can be improved by introducing logic fault models at different hierarchical levels. In the second section, we present an original algorithm for test and diagnosis with potential optimizations. We also present the adaptation of the algorithm to the hierarchical model. In the last section, we conclude with the presentation of different simulation results that we obtained with BNT (Matlab Toolbox for Bayesian Networks) applied to adders. As a result, we obtain a minimum set of diagnosis vectors with a very good diagnosis coverage.

A Bayesian fault model for test and diagnosis

Bayesian networks and combinational circuits

Bayesian networks are at the intersection of graph theory and probability theory. The system is modeled by a directed acyclic graph (DAG), in which the nodes represent random variables and arcs represent conditional dependencies between variables. The probability space is a set of a-priori (no direct cause) or conditional probabilities (one or more direct causes) associated with network variables. The Bayesian inference is to propagate certain information (evidences made on the system) in the network and to calculate the conditional probability of events connected to each other based on Bayes' rule [START_REF] Naim | Réseaux bayésiens[END_REF]. From the structural description of a combinational circuit, we can build a Bayesian network which expresses its functionality. Each input of the circuit is represented by a node having an a-priori probability table (at random or according to the context of use). Each component of the structure is also represented by a node together with a conditional probability table expressing its operation. Figure 1 illustrates an example of a Bayesian network representing an adder circuit. Using Bayesian inference, we can calculate the probabilities for all nodes by giving a few observations. If we have observed the value 0 at both the circuit outputs OR and XOR2, we can deduce the probabilities of the inputs Ret0, A1 and B1 using Bayesian inference. We obtain P(A1=0)=1, P(B1=0)=1 and P(Ret0=0)=1 which means A1=0, B1=0 and Ret0=0. FIGURE 1 -An example of a Bayesian network

The Bayesian network of a fault model

To simulate and study the malfunctioning of a circuit, we introduce several fault models in the Bayesian representation. In our case, the bit-flip and the stuck-at fault model are experimented, but other types could be introduced such as "open circuit", "bridge", etc. According to the fault model, the values are evolving as follows : -in the Bit-flip model, the value of the output is inverted permanently ; -in the Stuck-at model, the value of the output/input is permanently fixed to 0 or 1. Both models can be applied to single or multiple faults. They are integrated into the Bayesian network of the circuit as follows :

1. At the "graphical level", new nodes are added :

-A "Component State" node is connected to the related component node for each component, representing the potential states of components associated with the fault model.

-A "Global State" node is connected to all "Component State" nodes, managing the global fault distribution (simple/multiple faults) of all "Component State" nodes.

A graphical representation of the functioning/malfunctioning of a full adder is given in Figure 2.

FIGURE 2 -The Bayesian graphical model of a full adder 2. At the "probabilistic level", each node has its own probability table depending on the nodes adjacent to it and the model of faults. Some probability tables of the previous example are shown in Figure 3.

Circuits could be modeled only with the global state node but this makes the probability tables of components very large. To keep the size of these tables small, component states are used.

A Hierarchical Bayesian network model

The efficient treatment of large circuits is problematic due to the complexity of the inference algorithms. This complexity is generally exponential in the number of nodes of the network [START_REF] Delcroix | Diagnostic à base de réseaux bayésiens hérarchiques[END_REF]. A possible solution to this drawback is the use of a hierarchical representation.

A hierarchical Bayesian network corresponds to a set of Bayesian networks describing the components at a specific level. The lowest level (i.e., the most detailed one) is formed by elementary Bayesian networks consisting of basic components. Figure 4 shows the hierarchical Bayesian network model of a ripple carry adder. The probability table of each hierarchical node can either have complete information of the internal behavior of the lower level, or a reduced set of information (abstraction). In the first case, the probability tables can be very large and unmanageable, so we give preference to a reduced set of information for the node of higher level which in turn is detailed in the lower one.

An algorithm for test and diagnosis with optimization

An algorithm for test and diagnosis

In the following, we present an algorithm to determine a set of test vectors allowing the location of all possible faults by means of Bayesian inference.

Principle :

Based on the knowledge of the values injected as input and those observed as the output, the circuit states (global and component ones) can be computed using Bayesian inference. The computed value of each state determines the probability of malfunctioning of each component as represented in the Bayesian network. If one pair of values (input/output) is not sufficient, we select other couples to refine the diagnosis. A final goal is to reduce the number of input values (vectors) to a minimum.

Process :

The algorithm consists of the following steps : 3. According to the observed output values for a selected input vector, the state of the circuit expresses the correct functioning or the malfunctioning of the circuit. If the partial diagnosis corresponds to several potential faulty components, another input vector from the remaining nonchosen vectors is selected to reduce the set of possible faulty components. We continue with the vector selection and the redundancy elimination until we can locate all possible faults.

Example :

We have applied our algorithm to the example of a full adder for the single bit-flip fault model. Figure 5 shows the diagnosis matrix after redundancy elimination ; an entry "-" means that this case is impossible.

The different steps of the algorithm are illustrated in Figure 6.

3 ways to optimize

Each row of the diagnosis matrix represents an input vector, each column represents the output value and each cell contains a set representing possible states of the circuit (Ok or possible faulty components).

Optimization 1 : first test, then diagnose

The aim of this approach is to determine as early as possible whether the circuit is Ok or not. A reduced set of vectors is used to define the state (Ok or not Ok) of the circuit and gives at the same time a partial diagnosis of faulty components.To refine and to identify the exact faulty component, we apply the previous algorithm.

Criteria for the test vector selection

Let V be a column vector whose rows represent the possible diagnosis (including the Ok case) associated with a set of input/output values, and let E = {1, . . . , Card(V)}. Among the vectors that can possibly determine the good functioning of the circuit, we choose those which have in common a minimum of diagnosis cases. We define :

α = Min i∈E {Max j∈E\{i} {Card(V(j) ∩ V(i))}
We now run the algorithm. In case that the test is not successful to determine the state of the circuit, we select another test in the same way until termination.

Example :

We apply this approach to the full adder with double bit-flip fault model. If we take the diagnosis matrix without redundancy, as shown in Figure 7, we obtain α = 2, and we come up with the first test vector (011). At the end, we obtain the 3 test vectors (011), ( 110) and (001) with a partial location of 13/15= 86,67%.

If we want to obtain a complete location, the additional vector (111) is necessary. This approach gives a minimum set of vectors for the test but not necessarily a minimum set of such vectors for the diagnosis. In other words, the approach is interesting when we need to test the circuit and obtain some partial information about the location of possible faults.

Optimization 2 : set rules on the choice of vectors

This optimization takes into account the test and the complete diagnosis. We can also run it after the use of the first optimization to locate the remaining faults. The principle is to identify as soon as possible the faulty component (or component group) in the partial diagnosis.

Criteria for the selection of a diagnosis vector :

To identify the faulty component in each cell, we must choose the vector which diagnoses for every case of output values, the smallest number of components (or component groups). Let E 1 ={1, . . . , m} and E 2 ={1, . . . , n} with m, n representing the number of rows, columns of the diagnosis matrix M, respectively. We define :

β = Min i∈E 1 {Max j∈E 2 {Card(M(i, j))}}
β represents the smallest number of faulty components for the partial diagnosis. This value can correspond to the case of one or several vectors.

Example :

If we take matrix M from the previous example without redundancy, see Figure 8, we obtain β = 2 and the first vector chosen is the one reaching this value 2, i.e., either (011) or ( 110). The application of this optimization reduces the set of test vectors to 2 (in contrast to 4 vectors obtained previously).

Discussion :

This way to optimize is interesting since it reduces the set of test vectors for the diagnosis and it locates the precise fault. It should be used when the probability of a fault in the circuit increases.

Optimization 3 : Adding evidence

To speed up the diagnosis, we can add evidence due to hardware redundancy which provides certainty of information and hereby reduces the number of cases to be handled. In this approach, we try to find the best evidence for allowing a reduction of the number of vectors.

1. Process : When we introduce an evidence, we fix the probability value at 100% Ok or at 100% failed.

Example :

We have tested this approach on the full adder with the single bit-flip fault model. We were able to reduce the number of vectors by adding one evidence (see our results in subsection 3.4).

A hierarchical application

The diagnosis algorithm described in the previous section can be adapted to hierarchical Bayesian networks as follows :

-Apply the algorithm to the highest level.

-Find the faulty component on that level.

-Repeat until the elementary level.

Example :

We give an example of the N-bit adder shown in Figure 4 for the single bit-flip fault model. We start by locating the faulty 1-bit adder among all the others, then we apply the algorithm on the elementary circuit (a full adder at the lowest level with single bit-flip fault model). The size of the output vector increases with N and the algorithm's effort rapidly grows from N = 5 on. To face this problem, we first apply the algorithm to the 2-and 3-bit adder and then try to deduce the rest by recurrence. We can show that : -For the 2-bit adder, vector (0001) is the test vector locating the faulty 1-bit adder.

-For the 3-bit adder, vector (000101) is the test vector for locating the faulty 1-bit adder.

-For the N-bit adder, vector ( 00 (01) N-1 ) is the test vector for locating the faulty 1-bit adder.

3 test vectors are enough to locate the fault in an N-bit adder ; 1 test vector (00 (01) N-1 ) to determine the faulty 1-bit adder (full adder) and 2 to determine the fault within the full adder (as seen previously).

Demonstration :

We remind that the input vector (000) for (A(0)B(0)Ret(0)) gives the output (00) for (Res(1) Ret( 1)) if the full adder is Ok, else it gives (01) or [START_REF] Delcroix | Diagnostic à base de réseaux bayésiens hérarchiques[END_REF]. The input vector (010) for (A(i)B(i)Ret(i), 1<=i<=N) gives the output ( 10) for (Res(i+1) Ret(i+1)) if the full adder is Ok, else it gives [START_REF] Kajihara | On the adders with minimum tests[END_REF] or (00). Suppose that for an N-bit adder, the vector is (00 (01) N-1 ). Then we can demonstrate that for an N+1-bit adder, the vector is (00 (01) N ).

We have two cases :

(a) The fault is not on one of the N first adders :

We take (00 (01) N-1 ) as input vector for the first N adders. With no fault on the N first adders, this vector gives (0(1) N-1 0) as outputs on the N first adders. (i.e., (A(0)B(0)Ret(0)))=(000) gives (00) for (Res(1) Ret( 1)) (Ok state for the first full adder), then (A(1)B( 1)Ret( 1))=(010) gives [START_REF] Delcroix | Diagnostic à base de réseaux bayésiens hérarchiques[END_REF] for (Res(2) Ret( 2)) (Ok state for the second full adder), until (A(N-1)B(N-1)Ret(N-1))= (010) which gives [START_REF] Delcroix | Diagnostic à base de réseaux bayésiens hérarchiques[END_REF] for (Res(N) Ret(N)) (Ok state for the Nth full adder).) Finally, (A(N) B(N) Ret(N))= (010) can give [START_REF] Delcroix | Diagnostic à base de réseaux bayésiens hérarchiques[END_REF] for (Res(N+1) Ret(N+1)) (Ok state for the N+1st full adder) or ( 11)/(00) (faulty state for the N+1st full adder). We can conclude the following : if we apply as input (00 (01) N ) and we have as output (0(1) N 0), the (N+1) full adders are Ok. Otherwise, we have as output (0(1) N+1 ) or (0(1) N-1 00) and we can say that the N+1st full adder is faulty.

(b) The fault is on one of the first N adders :

We take (00(01) N-1 ) as input vector for the first N adders. With a fault on one of the first N adders, this vector determines the faulty adder (hypothesis) and then the N+1st adder must be Ok or it will be an impossible case with 2 faulty adders (context of a single fault). Altogether, we can say that (00(01) N ) is the test vector for the N+1-bit adder.

Results

In this section, we summarize the results of our approach and present a comparative study with a conventional test approach for an adder [START_REF] Kajihara | On the adders with minimum tests[END_REF] and a Diagnosis approach using Automatic Test Pattern Generation (DATPG) [START_REF] Zhang | A diagnostic test generation system[END_REF].

Comparison with existing work :

We have applied our approach by taking the hypotheses used in [START_REF] Kajihara | On the adders with minimum tests[END_REF]. With the same hypotheses, we have applied the DATPG method [START_REF] Zhang | A diagnostic test generation system[END_REF] on the adders. We evaluate the test and the diagnosis coverage. The Test Coverage (TC) or Fault Coverage is defined as the ratio of detected faults to the total number of faults. The Diagnosis Coverage (DC) is defined as the ratio of located faults to the total number of faults. In [START_REF] Kajihara | On the adders with minimum tests[END_REF], a minimum set of test vectors is given to have a 100% TC but the diagnosis is not done. We have taken these vectors and we have computed the DC. In [START_REF] Zhang | A diagnostic test generation system[END_REF], an approach of diagnosis is proposed using the classical ATPG. A 100% TC is given by a minimum set of test vectors that are used for a partial diagnosis and a DC is given. To achieve a 100% DC, extra vectors are necessary and are chosen in an exhaustive way. In our approach, we have applied the combination of optimization 1 and 2 to select the set of vectors properly and we have achieved a 100% TC and a 100%DC.

(a) Hypothesis : we consider two types of architecture for full adders (see Figure 9) together with an N-bit ripple adder (see Figure 4) with stuck-at input/output as fault model.

(b) Results : Table 1 represents the comparative study. The results show that all three approaches give the minimum set of test vectors for a full test coverage, but our approach has the best diagnostic coverage by adding the least number of vectors. We can explain this by the choice and the sequence of vectors. In the two approaches the test and the diagnosis are separated but in our approach we consider test and diagnosis at the same time.

Diagnosis exploration :

In this part, we are interested in evaluating the impact of the proposed optimization on the set of test/diagnosis vectors. For this, we consider the full adder of type 2 (see Figure 9) with bit-flip or stuck-at input/output as fault model. Type 2 is the most efficient as seen in the first part of our results.

Table 2 shows that the algorithm without optimization gives a complete localization, and it even reduces the number of test vectors, but the number of these is not minimum. Using the optimizations reduces this number more in the bit-flip fault model because we have less faults. Using optimizations 2 and 3, we can retain the complete localization. This approach is more useful as the number of faulty circuits increases. therwise optimization 1 is the most suitable. The proposed algorithm reduces the number of test vectors for diagnosis. The proposed optimizations minimize this number depending on the fault model and the need. Optimization 1 is suitable for a test with partial localization and optimizations 2 and 3 for complete localization. In the case of complex circuits, the best solution is to mix these optimizations. First, test the circuit using optimization 1. Then, if the coverage is not enough, use optimization 2 to improve the coverage, or pass to a complete localization.

Conclusion and perspectives

In this paper, we have proposed a fault diagnosis approach based on Bayesian networks. We have shown that we can introduce any fault model. The Bayesian network inference allowed to find for each input/output the sets of potential faults and this is easily done with appropriate Bayesian tools. From that, we have proposed an algorithm whose objective is to reduce the set of vectors for a complete or a partial fault location. A complete study was done on adder examples demonstrating that the diagnosis based on Bayesian networks together with different optimizations gives a minimum set of test vectors in case of complete or partial diagnosis.

As perspectives, we would like to apply our algorithm to other regular circuits and evaluate the performance for transient faults. We are also interested in online diagnosis with more efficient schemes of inference computation.

FIGURE 3 -

 3 FIGURE 3 -Some probability tables for a full adder

FIGURE 5 -FIGURE 6 -

 56 FIGURE 5 -The diagnosis matrix for the full adder single bit-flip fault model

FIGURE 7 -

 7 FIGURE 7 -The test vector selection for the full adder considering a double bit-flip fault model

FIGURE 8 -

 8 FIGURE 8 -The diagnosis matrix M for the full adder considering a single bit-flip fault model

  TC = Number of detected faults Total number of faults DC = Number of located faults Total number of faults

FIGURE 9 -

 9 FIGURE 9 -Two full adder types

TABLE 1 -

 1 Test and diagnosis for adders (TC : Test Coverage, DC : Diagnosis coverage)

TABLE 2 -

 2 Full adder result


Jan Kára
email: kara@kam.mff.cuni.cz

Jan Kratochvíl

David R Wood
email: david.wood@upc.es

On the complexity of the balanced vertex ordering problem †

Keywords: graph, graph drawing, vertex ordering, complexity Mathematics Subject Classification: 05C62 (graph representations)

We consider the problem of finding a balanced ordering of the vertices of a graph. More precisely, we want to minimise the sum, taken over all vertices v, of the difference between the number of neighbours to the left and right of v. This problem, which has applications in graph drawing, was recently introduced by Biedl et al. [Discrete Applied Math. 148:27-48, 2005]. They proved that the problem is solvable in polynomial time for graphs with maximum degree three, but N P-hard for graphs with maximum degree six. One of our main results is to close the gap in these results, by proving N P-hardness for graphs with maximum degree four. Furthermore, we prove that the problem remains N P-hard for planar graphs with maximum degree four and for 5-regular graphs. On the other hand, we introduce a polynomial time algorithm that determines whether there is a vertex ordering with total imbalance smaller than a fixed constant, and a polynomial time algorithm that determines whether a given multigraph with even degrees has an 'almost balanced' ordering.

Introduction

A number of algorithms for graph drawing use a 'balanced' ordering of the vertices of the graph as a starting point [START_REF] Kant | Drawing planar graphs using the canonical ordering[END_REF][START_REF] Kant | Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems[END_REF][START_REF] Papakostas | Algorithms for area-efficient orthogonal drawings[END_REF][START_REF] Wood | Minimizing the number of bends and volume in three-dimensional orthogonal graph drawings with a diagonal vertex layout[END_REF][START_REF] Wood | Optimal three-dimensional orthogonal graph drawing in the general position model[END_REF]. Here balanced means that the neighbours of each vertex v are evenly distributed to the left and right of v. The problem of determining such an ordering was recently studied by Biedl et al. [START_REF] Biedl | Balanced vertex-orderings of graphs[END_REF]. We solve a number of open problems from [START_REF] Biedl | Balanced vertex-orderings of graphs[END_REF] and study a few other related problems.

Let G = (V, E) be a multigraph without loops. An ordering of G is a bijection σ : V → {1, . . . , |V |}. For u, v ∈ V with σ(u) < σ(v), we say that u is to the left of v and that v is to the right of u. The imbalance of v ∈ V in σ, denoted by B σ (v), is |{e ∈ E : e = {u, v}, σ(u) < σ(v)}| -|{e ∈ E : e = {u, v}, σ(u) > σ(v)}| .

When the ordering σ is clear from the context we simply write B(v) instead of B σ (v). The imbalance of ordering σ, denoted by B σ (G), is v∈V B σ (v). The minimum value of B σ (G), taken over all orderings σ of G, is denoted by M (G). An ordering with imbalance M (G) is called minimum. The following two facts hold for every ordering:

• Every vertex of odd degree has imbalance at least one.

• The two vertices at the beginning and at the end of the ordering have imbalance equal to their degrees.

These two facts imply the following lower bound on the imbalance of an ordering. Let odd(A) denote the number of odd degree vertices among the vertices of A ⊆ V . Let (d 1 , . . . , d n ) be the sequence of vertex degrees of G, where d i ≤ d i+1 for all i ∈ {1, 2, . . . , n -1}. Then

B σ (G) ≥ odd(V ) -(d 1 mod 2) -(d 2 mod 2) + d 1 + d 2 .
An ordering σ is perfect if the above inequality holds with equality. PERFECT ORDERING is the decision problem whether a given multigraph G has a perfect ordering. This problem is clearly in N P.

Biedl et al. [START_REF] Biedl | Balanced vertex-orderings of graphs[END_REF] gave a polynomial time algorithm to compute a minimum ordering of graphs with maximum degree at most three. On the other hand, they proved that it is N Phard to compute a minimum ordering of a (bipartite) graph with maximum degree six.

One of the main results of this paper is to close the above gap in the complexity of the balanced ordering problem with respect to the maximum degree of the graph. In particular, we prove that the PERFECT ORDERING problem is N P-complete for simple graphs with maximum degree four.

In fact, the NP-completeness result even holds if we additionally restrict the graphs to be planar. This is of particular interest since a number of algorithms for producing orthogonal drawings of planar graphs with maximum degree four start with a balanced ordering of the vertices [START_REF] Biedl | A better heuristic for orthogonal graph drawings[END_REF][START_REF] Papakostas | Algorithms for area-efficient orthogonal drawings[END_REF]. We answer this question in the negative by proving that the PERFECT ORDERING problem is N P-complete for planar simple graphs with maximum degree four.

Our third N P-hardness result states that finding an ordering with minimum imbalance is N P-hard for 5-regular simple graphs. All of these N P-hardness results for ordering problems are presented in Section 3. The proofs are based on reductions from various satisfiability problems. Section 2 contains several N P-completeness results for used satisfiability problems. While the complexity of most of these satisfiability problems follows from a general result by Schaefer [START_REF] Thomas | The complexity of satisfiability problems[END_REF], we believe that our proofs are simpler and the result for PLANAR 2-IN-4SAT is of independent interest.

In Section 4 we present our positive complexity results. In particular, we describe a polynomial time algorithm that determines whether a given graph has an ordering with at most k imbalanced vertices for any constant k. This algorithm has several interesting corollaries. For example, the PERFECT ORDERING problem can be solved in polynomial time for a multigraph in which all the vertices have even degrees (in particular, for 4-regular multigraphs).

N P-Hardness of Satisfiability Problems

In this section we prove several N P-hardness results about various satisfiability problems. Note that the results in this section could be also achieved by verifying conditions of a general theorem of Schaefer [START_REF] Thomas | The complexity of satisfiability problems[END_REF], but we feel that our proofs are simpler. First we introduce several basic definitions about satisfiability. Throughout this paper, formulae are considered to be in a conjunctive normal form. That is, each formula ϕ is a conjunction of some m The decision problem asking whether a given formula ϕ is satisfiable is called SAT. If we assume that every clause in the given formula ϕ has size exactly three, then the decision problem asking whether ϕ is satisfiable is called 3SAT. Two common variants of 3SAT are Monotone Not-All-Equal 3-Satisfiability (MON-NAE-3SAT for short) and 1-in-3 Satisfiability (1-IN-3SAT). Both these problems are defined on formulae in which each clause has size exactly three. Furthermore in MON-NAE-3SAT the formulae are without negations. A truth assignment t is NAE satisfying if each clause has at least one true and at least one false literal. t is called 1-in-3 satisfying if each clause has exactly one true literal. The notions of NAE satisfiable and 1-in-3 satisfiable formulae, and the corresponding decision problems are defined in the obvious way. It is well known that SAT, MON-NAE-3SAT, and 1-IN-3SAT are N P-complete (see [START_REF] Thomas | The complexity of satisfiability problems[END_REF]).

clauses c 1 ∧c 2 ∧• • •∧c m where each clause c i is a disjunction of n i literals l i 1 ∨l i 2 ∨• • •∨l i ni for all i ∈ {1, . . . ,
We say that a formula ϕ for which all clauses have five literals is 2-or-3-in-5 satisfiable if there exists a truth assignment such that in each clause either two or three literals are true. Let 2-OR-3-IN-5SAT denote the decision problem asking whether a given formula ϕ is 2-or-3-in-5 satisfiable.

Lemma 1

The problem 2-OR-3-IN-5SAT is N P-complete for formulae without negations.

Proof:

The problem clearly belongs to N P. We prove N P-completeness by a reduction from MON-NAE-3SAT, which is N P-complete [START_REF] Thomas | The complexity of satisfiability problems[END_REF]. Suppose we are given a formula ϕ without negations. Create a formula ϕ ′ from ϕ by adding a new clause c 0 = x ∨ x ∨ x ∨ x ′ ∨ x ′ , and by substituting each clause c with clause c ∨ x ∨ x ′ where x and x ′ are new variables. Given a NAE-satisfying truth assignment t for ϕ, a 2-or-3-in-5-satisfying truth assignment t ′ for ϕ ′ can be created by setting t ′ (x) = 0 and t ′ (x ′ ) = 1. Also, if t ′ is a 2-or-3-in-5 satisfying truth assignment for ϕ ′ , then t ′ (x) = ¬t ′ (x ′ ) by clause c 0 . Thus, restricting t ′ to the variables of ϕ, we obtain a NAE-satisfying truth assignment for ϕ. ✷

The next lemma uses the following version of the satisfiability problem. Let ϕ be a formula in which all clauses have four literals. A truth assignment t is 2-in-4 satisfying if each clause in ϕ has exactly two true literals. ϕ is 2-in-4 satisfiable if there exists a 2-in-4 satisfying truth assignment. 2-IN-4SAT is the decision problem asking whether a given formula ϕ is 2-in-4 satisfiable.

Lemma 2 The problem 2-IN-4SAT is N P-complete for formulae without negations.

Proof: The problem is obviously in N P. We prove its N P-completeness by reduction from 1-IN-3SAT, which is N P-complete for formulae without negations [START_REF] Thomas | The complexity of satisfiability problems[END_REF]. Let ψ be a formula given as an input for 1-IN-3SAT. Create a formula ψ ′ with a new variable v by adding v to each clause of ψ. We now show that ψ is 1-in-3 satisfiable if and only if ψ ′ is 2-in-4 satisfiable. If t is a 1-in-3 satisfying truth assignment for ψ, then by setting t ′ (v) = 1 and t ′ (x) = t(x) for each variable x = v of ψ ′ , we obtain a 2-in-4 satisfying truth assignment for ψ ′ . Conversely, if t ′ is a 2-in-4 satisfying truth assignment for ψ ′ , then either t ′ (in the case that t ′ (v) = 1) or 1t ′ (in the case that t ′ (v) = 0) restricted to variables of ψ is a 1-in-3 satisfying truth assignment for ψ. ✷

Now we strengthen the result from the previous lemma.

Lemma 3

The problem 2-IN-4SAT is N P-complete for planar formulae without negations.

v v ′ c ′ c v ee ′ v ee ′ v ′ v ee ′ v c ee ′ 1 c ee ′ 2 ¬ ¬ ¬ ¬ v c v vc n c vc 1 c vc 2 c vc 3 c vc 4 v vc 1 v vc 2 v vc 3 v vc 4 v vc 5 v vc 6
Fig. 1: The crossing gadget for two edges {v, c} and {v ′ , c ′ } (left) and the negation gadget for a negative occurrence of variable v in clause c (right) from the proof of Lemma 3. Empty circles represent clauses, and full circles represent variables. The symbol ¬ marks a negative occurrence.

Proof: Suppose we have a formula ϕ with clauses of size four without negations. We now show that if the formula ϕ is not planar we can alter it in polynomial time so that the resulting formula ϕ ′ is planar and ϕ is 2-in-4 satisfiable if and only if ϕ ′ is 2-in-4 satisfiable. The formula ϕ ′ will contain some negations but we also define a planar formula ensuring v = ¬v ′ for two of its variables v, v ′ and all 2-in-4 satisfying truth assignments. Hence by substitution of each edge representing the negative occurrence by this gadget we prove the lemma.

Let d be a drawing of the incidence graph of ϕ in the plane, such that any two edges cross at most once. We proceed by induction on the number of crossings in d. If there is no crossing, we are done. Now suppose there is some crossing and for all formulae having a drawing of their incidence graph with less crossings the lemma holds. Consider an edge e = (v, c) and the crossing with some edge e ′ = (v ′ , c ′ ) closest to v on the edge e. Create a new formula ψ by adding three new variables v ee ′ , v ee ′ v , v ee ′ v ′ and two clauses

c ee ′ 1 = ¬v ∨ ¬v ′ ∨ v ee ′ ∨ v ee ′ v , c ee ′ 2 = ¬v ∨ ¬v ee ′ ∨ v ee ′ v ′ ∨ v ee ′ v .
Then substitute occurrences of v in c by v ee ′ v , and occurrences of v ′ in c ′ by v ee ′ v ′ . See Figure 1 for an example of a gadget for two crossing edges. Note that only edges (v ′ , c ee ′ 1 ), (v ee ′ v , c), and (v ee ′ v ′ , c ′ ) of the gadget can be intersected by other edges of the incidence graph.

After the substitution we clearly obtain a formula with a drawing with one less crossing. It remains to show that ψ is 2-in-4 satisfiable if and only if ϕ is 2-in-4 satisfiable (we get the rest using the induction). Let t be a 2-in-4 satisfying truth assignment for ϕ. Setting

t ′ (x) = t(x) for all variables x of ϕ, t ′ (v ee ′ v ) = t(v) and t ′ (v ee ′ v ′ ) = t ′ (v ee ′ ) = t(v ′ )
, we obtain a 2-in-4 satisfying truth assignment for ψ. The other implication can be seen as follows. Let t ′ be a 2-in-4 satisfying truth assignment for ψ. We set t(x) = t ′ (x) for each variable

x of ϕ. If we show that t ′ (v) = t ′ (v ee ′ v ) and t ′ (v ′ ) = t ′ (v ee ′ v ′ )
, we immediately get that t is a 2-in-4 satisfying truth assignment for ϕ. We analyse two cases (the other two follow by symmetry):

• t ′ (v) = t ′ (v ′ ) = 1: In this case, c ee ′
1 has already two literals set to zero and so

t ′ (v ee ′ v ) = t ′ (v ee ′ ) = 1
. Now looking at c ee ′ 2 we see that two of its literals are set to zero and one literal is set to one. Thus t ′ (v ee ′ v ′ ) = 1.

• t ′ (v) = ¬t ′ (v ′ ) = 1: If t ′ (v ee ′ ) = 1, then c ee ′ 1
has two literals set one and one literal set to zero. Thus t ′ (v ee ′ v ) must be zero. But then c ee ′ 2 has three literals set to zero and we can conclude that this cannot be the case. Hence t ′ (v ee ′ ) = 0 and t ′ (v ee ′ v ) = 1 to satisfy c ee ′ 1 . Moreover c ee ′ 2 has two literals set to one and one literal set to zero showing that t ′ (v ee ′ v ′ ) = 0. Now it remains to show how to remove the negative occurrences from ϕ ′ . For each negative occurrence of variable v in clause c we add seven new variables v vc n , v vc 1 , . . . , v vc 6 and four new clauses

c vc 0 = v∨v vc n ∨v vc 1 ∨v vc 2 , c vc 1 = v vc 1 ∨v vc 2 ∨v vc 3 ∨v vc 4 , c vc 2 = v vc 3 ∨v vc 4 ∨ v vc 5 ∨ v vc 6 , c vc 3 = v vc 1 ∨ v vc 2 ∨ v vc 5 ∨ v vc 6 .
See Figure 1 for an example of a created gadget. We also substitute the negative occurrence of v in c by a positive occurrence of v vc n . Let ϕ ′′ be the resulting formula. It is straightforward to check that t ′′ (v) = ¬t ′′ (v vc n ) in any 2-in-4 satisfying truth assignment t ′′ of ϕ ′′ and by setting t

′′ (v vc 1 ) = t ′′ (v vc 3 ) = t ′′ (v vc 5 ) = t ′ (v) and t ′′ (v vc 2 ) = t ′′vc 4 = t ′′vc 6 = t ′′vc n = ¬t ′ (v)
we get a 2-in-4 satisfying truth assignment t ′′ of ϕ ′′ from a 2-in-4 satisfying truth assignment t ′ of ϕ ′ . ✷

Note that if we allowed multiple occurrences of one variable in a clause in the previous lemma the negation gadget would become trivial and for our purposes such a weaker lemma would be sufficient. But we decided to prove the stronger version as we find the lemma of independent interest.

N P-Hardness of Balanced Ordering Problems

In this section we prove several N P-hardness results about balanced ordering problems.

Theorem 1

The PERFECT ORDERING problem is N P-complete for planar graphs with maximum degree four.

Proof: N P-hardness is proved by a reduction from 2-IN-4SAT for planar formulae without negations (see Lemma 3). Given a formula ϕ, create a graph G ϕ with one vertex u c for each clause c. For each variable v that occurs o v times in ϕ, add a path on 3o v + 1 new vertices p v 1 , . . . , p v 3ov+1 to G ϕ , add o v additional vertices q v 1 , . . . , q v ov , and connect q v i , i ∈ {1, . . . , o v } with vertices p v 3i-2 and p v 3i . The path with the additional vertices is called a variable gadget. Finally for each i ∈ {1, . . . , o v }, connect vertex p v 3i-2 of the path to u c , where c is the clause corresponding to the i-th occurrence of the variable v. These edges are called clause edges. See Figure 2 for an example of this construction.

Observe that the maximum degree of G ϕ is four. In particular, deg

(u c ) = 4, deg(q v i ) = 2 for all i ∈ {1, . . . , o v }, deg(p v 3i ) = 3 for all i ∈ {1, . . . , o v }, deg(p v 3i-2 ) = 4 for all i ∈ {2, . . . , o v }, deg(p v 3i-1 ) = 2 for all i ∈ {1, . . . , o v }, deg(p v 1 ) = 3
, and deg(p v 3ov+1 ) = 1. Also note that the created graph is planar if the incidence graph of ϕ is planar.

We now prove that G ϕ has a perfect ordering if and only if ϕ is 2-in-4 satisfiable. Suppose G ϕ has a perfect linear ordering σ. For each variable v and for each i ∈ {1, . . . , o v } the vertex p v 3i-1 has one neighbour to the left and one neighbour to the right in σ (since deg(p v 3i-1 ) = 2). Similarly, q v i has one neighbour to the left and one neighbour to the right in σ. Thus they must be placed between p v 3i-2 and p v 3i . As p v 3i-1 and q v i are on one side (e.g., to the left) of vertex p v 3i-2 (p v 3i ) the other neighbours of the vertex must be on the other side. This implies that in σ, the path in each variable gadget is in the order given by its numbering or inverse numbering, and all the clause edges (the edges with exactly one endpoint in the variable gadget) have a clause vertex on the same end (for example, the left end of each clause edge is a vertex of a path). If the path in the gadget for variable v is ordered according to its numbering, then set t(v) := 0. Otherwise set t(v) := 1. This truth assignment is 2-in-4 satisfying because each clause vertex has two neighbours on each side.

For a given truth assignment t we can analogously construct a perfect linear ordering. First place each variable gadget corresponding to a variable with t(v) = 0 with the path placed according to the inverse ordering, and put each vertex q v i immediately after vertex p v 3i-1 , i ∈ {1, . . . , o v }. Then place vertices u c in an arbitrary order and finally the variable gadgets corresponding to variables with t(v) = 1 with the paths ordered according to the numbering and vertices q v i placed immediately after the vertex p v 3i-2 . ✷

The following two technical lemmas will be used later for removing parallel edges from a multigraph without changing an ordering with minimum imbalance.

Lemma 4 Let G be the multigraph drawn in Figure 3 with two parallel edges added between the vertices a and b. Then there exists a minimum ordering of G such that a is the leftmost and b the rightmost vertex. Such an ordering is called a natural ordering of G.

Proof: The ordering a, 1, 2, 3, 4, 5, 6, b has imbalance 20. We claim that there is no ordering with smaller imbalance. Let v 1 . . . , v 8 be some ordering of the vertices. We distinguish two cases:

1. There are two parallel edges between v 1 and v 2 (or symmetrically between v 7 and v 8 ). Because there is only one double-edge in our graph, v 1 = a and v 2 = b (the case v 1 = b and v 2 = a is the same) and we also know that there is at most one neighbour to the right of v 7 . Since each vertex of G is connected to exactly one of a and b, there is only one neighbour to the left of v 3 . Because the other vertices have imbalance at least one (they have odd degrees), the imbalance of the ordering is at least

B(v 1 ) + B(v 3 ) + B(v 7 ) + B(v 8 ) + 4 = 5 + 3 + 3 + 5 + 4 = 20.
2. There is no parallel edge between v 1 and v 2 nor between v 7 and v 8 . In this case there is at most one neighbour to the left of v 2 , and at most one neighbour to the right of Proof: Given an ordering of G with imbalance i, we can create an ordering of G ′ with imbalance i + 10 • c by inserting, for each triple-edge ab, the vertices 1, . . . , 6 from the gadget in Figure 3 between a and b and in this order (the imbalance of a and b does not change by the substitution). Thus M (G) ≥ M (G ′ ) -10 • c. On the other hand, if we have a minimum ordering of G ′ with imbalance i ′ , below we show that by changing the given ordering so that each gadget is in its natural ordering, we obtain an ordering with imbalance ≤ i ′ . Hence, the new ordering has imbalance i ′ , from the minimality of i ′ . By substituting each gadget with the triple-edge we obtain an ordering of G with imbalance i ′ -10 • c,

proving that M (G) ≤ M (G ′ ) -10 • c.
Suppose we have a triple-edge gadget in G ′ between vertices a and b, with a to the left of b. Each of the vertices has two neighbours u 1 , u 2 (u ′ 1 , u ′ 2 respectively) outside of the gadget. Let u 1 be to the left of u 2 , and let u ′ 1 be to the left of u ′ 2 . If u 1 , u 2 are both to the right of a and u ′ 1 , u ′ 2 are both to the left of b, then we are in the situation described by Lemma 4 (only the two parallel edges from the Lemma are now substituted by the edges to the vertices

u 1 , u 2 , u ′ 1 , u ′ 2 )
, and we can conclude that after reordering the vertices of the gadget (so that vertices a and b retain their ordering with respect to all other vertices of the graph), we obtain an ordering of G ′ with less or equal imbalance. If u 1 is to the left and u 2 to the right of a (u ′ 1 and u ′ 2 are both still to the left of b), then the imbalance of the gadget in the natural ordering in this situation is 18 and any ordering of the gadget cannot have smaller imbalance, as in the new situation only the ordering of vertices of one of the edges incident with the gadget has changed. Hence if we reorder the vertices of the gadget we obtain an ordering of G ′ with less or equal imbalance. Now consider the general situation. We have j neighbours of a outside of the gadget and j ′ neighbours of b outside of the gadget (0 ≤ j, j ′ ≤ 2) on the other side of a (b respectively). In the original situation the natural ordering of the gadget has imbalance 20 -2 • (j + j ′ ). There cannot be an ordering of the gadget with smaller imbalance because in the situation only the ordering of vertices of the j + j ′ edges incident with the gadget changed. Hence we can conclude that reordering the gadget into the natural ordering cannot increase the imbalance of the graph regardless of the ordering of v, u 1 , u 2 and v ′ , u ′ 1 , u ′ 2 . ✷

For the next reduction we use the 2-OR-3-IN-5SAT problem which we proved to be N P-complete in Section 2.

Theorem 2

The PERFECT ORDERING problem is N P-complete for 5-regular multigraphs.

Proof: We prove N P-hardness by a reduction from 2-OR-3-IN-5SAT for formulae without negations. Suppose that we are given a formula ϕ without negations and with all clauses of size five. Moreover, assume that each variable occurs in at least two different clauses in the formula. We can make a formula satisfy this condition by adding satisfied clauses of type x ∨ x ∨ x ∨ ¬x ∨ ¬x. Now create the following multigraph G from ϕ. For each clause c add a new vertex v c to G. For each variable x that occurs o x times in ϕ, add a new path (called a variable path) with 2o x -2 vertices v x 1 , . . . , v x 2ox-2 , where edges

v x 2i-1 v x 2i , 1 ≤ i ≤ o x -1, are triple-edges. Connect vertex v x 2i , 1 ≤ i ≤ o x -1,
of the path to the vertex corresponding to the clause with i-th occurrence of x. Furthermore, connect vertex v x 2ox-2 to the vertex corresponding to the clause with the o x -th occurrence of x (because x was in at least two different clauses we can without loss of generality assume that no parallel edges are created). Connect each vertex v x 2i-1 , 1 ≤ i ≤ o x -1, to the new vertex p x i , and connect each vertex v x 1 to the new vertex p x 0 . Now the only vertices which have degree other than five are in the set P = {p x j : x is a variable, 0 ≤ j ≤ o x -1} and these have degree one. By running the following procedure two times for the set P , all the vertices will have degree five. n := n + 2 end // Now P = {u i , u j } Add to G a complete bipartite graph on u i , u j and two new vertices s 1 , s 2 . Add a triple-edge s 1 s 2 to G.

See Figure 4 for an example of the construction. Let n 0 denote the value of n at the beginning of the procedure and n 1 the value of n at the end of the procedure. It is easy to check that G is 5-regular. We now show that G has a perfect ordering if and only if ϕ was 2-or-3-in-5 satisfiable. Suppose we have a perfect ordering of G. It holds that B(s 1 ) + B(s 2 ) > 2 for every ordering. Since the ordering is perfect, we can move s 1 , s 2 to the beginning without increasing the imbalance. By a similar argument, the ordering ends with vertices s ′ 2 , s ′ 1 , where s ′ 1 and s ′ 2 are the vertices added at the end of the second run of the procedure on P . Because all other vertices are balanced we know that every variable path is either in its natural ordering or reversed. Moreover all edges between the variable path and clauses have clause vertices to the right (or to the left in the reversed case). Because all clause vertices are balanced we get a 2-or-3-in-5 satisfying truth assignment of ϕ by assigning t(x) = 0 to the variables whose path is naturally ordered and t(x) = 1 to the variables whose path is reversed. For the converse, suppose we have a 2-or-3-in-5 satisfying truth assignment t of ϕ. First we place vertices s 1 , s 2 , u n1 , . . . , u n0+1 added in the first run. We continue by placing vertices p x j where x is a variable with t(x) = 0 and 0 ≤ j ≤ o x -1. Then we place variable paths for variables x such that t(x) = 0 in their natural ordering and after them the clause vertices. We finish by symmetrically placing the rest of paths and vertices added in the second run. It is straightforward to check that this ordering is perfect. ✷ Corollary 1 It is N P-hard to find a minimum ordering for 5-regular graphs.

Proof: Construct the multigraph G as in the reduction in the proof of Theorem 2. Say G has c triple edges. Construct G ′ from G by substituting each triple-edge by a triple-edge gadget. Observe that G ′ remains 5-regular and is a simple graph. From Lemma 5 we know that orderings of G ′ with imbalance |V | + 10 • c correspond to perfect orderings of G. This proves N P-hardness of finding the ordering with such imbalance. Hence finding a minimum ordering for 5-regular graphs is N P-hard. ✷

Algorithm

In this section we present an algorithm that determines in polynomial time whether a given multigraph has an ordering with constant imbalance. First we introduce a key lemma. Proof: Let imbalanced denote the ordered list of vertices (v 1 , . . . , v k ). The vertices not in the list imbalanced are called balanced. The algorithm works as follows: First we check that all odd-degree vertices are in the imbalanced list. If not, then we can reject since every odd-degree vertex must be imbalanced. Now assume that all balanced vertices have even degrees. Then start building an ordering σ from left to right. We append to σ those vertices that have not been placed yet and have half of their neighbours already placed. Such vertices are called saturated and are stored in the set saturated. Because saturated vertices are balanced each saturated vertex must be placed before any of its unplaced neighbours. In particular saturated vertices must form an independent set. Hence we cannot make a mistake when placing any saturated vertices. If there is no saturated vertex, the vertex which is placed next will be imbalanced and hence it must be the first unused vertex from the imbalanced list. The described algorithm can be clearly implemented in O(m + n) in a way analogous to the standard implementation of topological sorting. It remains to prove that it is not better to place some vertices from the imbalanced list while there are still some saturated vertices. If the order of vertices of any edge does not change then we have an equivalent ordering. Otherwise it does change, in which case some balanced vertex becomes imbalanced (as the order of vertices in an edge can change only for the edges which contain at least one balanced vertex) and we must reject. Thus we also see that all orderings satisfying the conditions from the statement of the lemma have the same imbalance. ✷

The following theorem is a consequence of Lemma 6.

Theorem 3 There is an algorithm that, given an n-vertex m-edge multigraph G, computes a minimum ordering of G with at most k imbalanced vertices (or answers that there is no such ordering) in time O(n k • (m + n)).

Proof: The algorithm is simple: just try all the possible choices of k imbalanced vertices and their orderings. For each such choice run the procedure from Lemma 6 and select the ordering with minimum imbalance from those orderings. There are O(n k ) k-tuples of imbalanced vertices, and for each such k-tuple, by Lemma 6, we can check in O(m + n) time whether there is an ordering with the chosen vertices imbalanced, and if so, compute the imbalance of the ordering. ✷

Corollary 2 There is a polynomial time algorithm to determine whether a given multigraph G has an ordering with imbalance less than a fixed constant c.

Proof: Apply the algorithm from Theorem 3 with k = c -1. If the algorithm rejects the multigraph or produces an ordering with imbalance greater than c, then the graph does not have an ordering with imbalance less than c (because any ordering with imbalance less than c must have at most c -1 imbalanced vertices). Otherwise the algorithm outputs some ordering with imbalance less than c, and we are done. ✷

Corollary 3

The PERFECT ORDERING problem is solvable in time O(n 2 (n + m)) for any n-vertex m-edge multigraph with all vertices of even degree.

Proof: Apply the algorithm from Theorem 3 with k = 2, and then check whether the achieved imbalance is equal to that required by the PERFECT ORDERING problem. A perfect ordering of a multigraph with even degrees must have exactly two imbalanced vertices (assuming there is at least one edge). ✷

2 eFig. 2 :

 22 Fig. 2: A graph constructed for formula (a ∨ b ∨ c ∨ d) ∧ (a ∨ c ∨ d ∨ e) ∧ (a ∨ b ∨ d ∨ e) in the proof of Theorem 1. The three clauses have numbers 1, 2, 3 in the picture.

Fig. 3 :

 3 Fig. 3: The triple edge gadget from Lemma 4 (left) and its natural ordering (right).

v 7 .Lemma 5

 75 Hence the total imbalance is at least B(v 1 ) + B(v 2 ) + B(v 7 ) + B(v 8 ) Let G be a 5-regular multigraph and let c be the number of triple-edges in G. Let G ′ be the graph obtained from G by replacing each triple-edge of G with endpoints a and b by the triple-edge gadget in Figure 3. The vertices a and b of the gadget are identified with the original end-vertices of the triple-edge. Then M (G) = M (G ′ ) -10 • c.

2 Fig. 4 :

 24 Fig. 4: A graph constructed for formula (a ∨ a ∨ b ∨ c ∨ d) ∧ (a ∨ b ∨ b ∨ c ∨ d) in the proof of Theorem 2. Clause vertices are marked 1 and 2. Clause vertices and variable paths are drawn in black colour, vertices p x i are drawn as squares in gray colour and vertices added by the procedure are drawn as circles in gray colour (vertices added in the first run are drawn in the left and vertices added in the second run are drawn in the right).

  of literals in it. Suppose ϕ is a formula with variables x 1 , . . . , x n . The incidence graph of ϕ is the bipartite graph with vertex set {c 1 , . . . , c m , x 1 , . . . , x n }, where {c i , x j } is an edge if and only if the variable x j occurs in the clause c i . A truth assignment of a formula ϕ with variables x 1 , . . . , x n is an arbitrary function t : {1, . . . , n} → {0, 1}. The values 0 and 1 are also sometimes called false and true respectively. A truth assignment t is satisfying if there is at least one true literal in every clause. The formula ϕ is satisfiable if it has at least one satisfying truth assignment.

m}. A literal is either a variable or its negation. The size of a clause is the number

  Lemma 6 Let vertices v 1 , . . . , v k be given. There is an O(n + m) time algorithm to test whether a multigraph G with n vertices and m edges has an ordering in which v 1 , . . . , v k are the only imbalanced vertices and appear in this order. Moreover all orderings with this property have the same imbalance.

Acknowledgements

The authors would like to thank the anonymous referees for useful comments.

† This is a revised and extended version of the authors' conference paper [5]. ‡ Supported by project 1M0021620808 of the Ministry of Education of the Czech Republic § Research supported by a Marie Curie Fellowship from the European Commission under contract MEIF-CT-2006-023865, and by the projects MEC MTM2006-01267 and DURSI 2005SGR00692. Research completed at the Department of Applied Mathematics and the Institute for Theoretical Computer Science, Charles University, Prague, Czech Republic. Supported by project LN00A056 and 1M0021620808 of the Ministry of Education of the Czech Republic, and by the European Union Research Training Network COMBSTRU. 1365-8050

Conclusion and Open Problems

In this paper we have considered the problems of checking the existence of a perfect ordering for planar graphs with maximum degree four and 5-regular multigraphs. Both these problems were shown to be N P-complete, thus answering a number of questions raised by Biedl et al. [START_REF] Biedl | Balanced vertex-orderings of graphs[END_REF]. We have also established that it is N P-hard to find an ordering with minimum imbalance for 5-regular simple graphs. We have also introduced an algorithm for determining an ordering with imbalance smaller than k with the time complexity O(n k (n + m)). It would be interesting to obtain a fixed-parameter-tractable (FPT) algorithm for this problem -i.e., an algorithm with the time complexity O(f (k) • poly(n, m)) -as one cannot hope for a polynomial solution with k in the input unless P = N P.


Vincent Vajnovszki
email: vvajnov@u-bourgogne.fr

Gray code order for Lyndon words

Keywords: Lyndon words, Gray codes, generating algorithms

At the 4th Conference on Combinatorics on Words, Christophe Reutenauer posed the question of whether the dual reflected order yields a Gray code on the Lyndon family. In this paper we give a positive answer. More precisely, we present an O(1)-average-time algorithm for generating length n binary pre-necklaces, necklaces and Lyndon words in Gray code order.

Introduction and motivation

A k-Gray code for a set of binary strings B ⊂ {0, 1} n is an ordered list for B such that the Hamming distance between any two consecutive strings in the list is at most k; if k is minimal then the list is called a minimal Gray code.

The conjugacy class of a string x = uv is the set of all strings vu. A (binary) necklace is a binary string which is minimal with respect to lexicographic order in its conjugacy class and a Lyndon word is an aperiodic necklace. A pre-necklace is a binary string which is the prefix of a some necklace, or equivalently [START_REF] Ruskey | Combinatorial generation[END_REF], of some Lyndon word. Generation of necklaces and Lyndon words lexicographically have been widely studied in the literature: (2; 3; 5; 6; 8; 13; 14; 15; 16; 17; 22).

Binary strings (necklaces, Lyndon words) with a given number of ones are called binary strings (necklaces, Lyndon words) with fixed density. There are two algorithms for generating a Gray code for necklaces with fixed density. The first one published is due to Wang and Savage in 1996 [START_REF] Wang | A Gray code for necklaces of fixed density[END_REF] (where the representative used is not the lexicographically smallest); the second one, where Lyndon words with fixed density are also considered, is due to Ueda in 2000 [START_REF] Ueda | Gray codes for necklaces[END_REF]. It is worth mentioning that the second paper was submitted two years before the first one. Both Gray codes are 2-Gray codes and therefore minimal.

To the best of our knowledge, there is no Gray code for necklaces and Lyndon words with no density restriction. The aim of this note is to present the first one and it is an updated form of the preliminary conference version of the paper [START_REF] Vajnovszki | Gray viziting Lyndons[END_REF].

In the following, lower case bold letters represent length n binary strings, e.g., x = x 1 x 2 . . . x n . The lexicographical order is defined as: x is less than y iff x k = 0 and y k = 1, where k is the leftmost position with x k = y k ; and any proper prefix of a string x is less than x. The reflected Tab. 1: Combinatorial objects for which the reflected order or the dual reflected order yields Gray codes.

Gray code order on {0, 1} n , due to Frank Gray in 1953 [START_REF] Gray | Pulse code communication[END_REF], is given by (4): x < y iff k j=1 x j is even (and k j=1 y j is odd), where k is the leftmost position with x k = y k . We say that an order relation on a set of strings induces a k-Gray code if the set listed in this order yields a k-Gray code. For example, the reflected Gray code order induces a 1-Gray code on {0, 1} n ; and its restriction to the strings with fixed density (i.e., strings with a constant number of 1's) induces a 2-Gray code, called revolving door code by Nijenhuis and Wilf [START_REF] Nijenhuis | Combinatorial Algorithms for Computers and Calculators[END_REF].

The next definition gives a slight modification of reflected order and like lexicographical order, both of them are particular cases of genlex order [START_REF] Walsh | Generating Gray codes in O(1) worst-case time per word[END_REF], that is, any set of strings listed in such an order has the property that strings with a common prefix are contiguous.

Definition 1 [START_REF] Vajnovszki | A loopless generation of bitstrings without p consecutive ones[END_REF] We say that x is less than y in dual reflected order (or local reflected order), denoted by x ≺ y, if x 1 x 2 . . . x k , the length k prefix of x contains an odd number of 0's, where k is the leftmost position with x k = y k .

Remark 1

1. x ≺ y iff x > y in reflected Gray code order, with x and y the bitwise complement of x and y, 2. Like reflected Gray code order, dual reflected order ≺ induces a 1-Gray code on {0, 1} n and a 2-Gray code on the strings in {0, 1} n with fixed density, 3. In ( 19) and ( 1) it is shown that, unlike reflected Gray code order, dual reflected order ≺ induces a 1-Gray code on the set of generalized Fibonacci strings (the set of length n binary strings such that there are no p consecutive 1's) and on the set of generalized Lucas strings (the set of Fibonacci strings where the pattern 1 p is regarded circularly).

See Table 1.

The Gray code

Definition 2 A binary string set X ⊂ {0, 1} n is called absorbent if for any x ∈ X and any k,

1 ≤ k < n, x 1 x 2 . . . x k 1 n-k is also a string in X.
The next lemma shows that, in contrast to the Fibonacci or Lucas strings, the sets of prenecklaces, necklaces and Lyndon words are absorbent (see again Table 1). Its proof is based on the following result (10, Proposition 5.1.2): a binary string is a Lyndon word iff it is lexicographically less than any of its proper suffixes. Equivalently, using the definition of lexicographic order, we have the following characterization: a binary string is a Lyndon word iff any of its proper prefixes is less than its suffix of same length.

Lemma 1

The sets of length n Lyndon words, necklaces and pre-necklaces are absorbent.

Proof: Let x = x 1 x 2 . . . x n be a binary string and

x ′ = x 1 x 2 . . . x k 1 n-k = x with 1 ≤ k < n.
When x is a Lyndon word it is easy to check that x ′ satisfies the above characterization of Lyndon words.

If x is a necklace or a pre-necklace (but not a Lyndon word) then there exists j, 1 ≤ j < n, such that the prefix x 1 x 2 . . . x j is a Lyndon word and x = (x 1 x 2 . . . x j ) p x 1 x 2 . . . x r with p = ⌊ n j ⌋ and r = n mod j. The final segment x 1 x 2 . . . x r is empty iff x is a necklace, see for instance [START_REF] Ruskey | Combinatorial generation[END_REF]. Thus a suffix of x ′ must have the form x s . . . x j x 1 . . . x t 1 n-k with the initial segment x s . . . x j possibly empty. Such a suffix is greater than the same length prefix and therefore x ′ is a Lyndon word. ✷ Let X ⊂ {0, 1} n , x ∈ X and k be the leftmost position where x differs from its predecessor in X in ≺ order (assuming that x is not the first string in X in this order). In other words, since ≺ is a genlex order, x 1 x 2 . . . x k is the shortest prefix of x such that for all y ≺ x one has y 1 y 2 . . . y k ≺ x 1 x 2 . . . x k . We call x k+1 x k+2 . . . x n the first discriminant suffix of x. Similarly, x k+1 x k+2 . . . x n , the last discriminant suffix of x, is the nk suffix of x where k is the leftmost position where x differs from its successor in ≺ order (assuming that x is not the last string in X in this order). Let |y| 0 denote the number of 0's in the binary string y.

Lemma 2 If x is a string in an absorbent subset X of {0, 1} n and x k+1 x k+2 . . . x n the first or the last discriminant suffix of x, then |x k+1 x k+2 . . . x n | 0 ≤ 1.

Proof: The proof is by contradiction. Let x k+1 x k+2 . . . x n be a first discriminant suffix of x such that |x k+1 x k+2 . . . x n | 0 > 1. Then there are at least two indices i and j, k + 1 ≤ i < j ≤ n, such that x i = x j = 0 and

x i+1 = x i+2 = . . . = x j-1 = 1. Since X is absorbent, x ′ = x 1 x 2 . . . x i-1 1 n-i+1 and x ′′ = x 1 x 2 . . . x j-1 1 n-j+1
are both in X. In addition, by Definition 1, either x ′ ≺ x or x ′′ ≺ x. So, since ≺ is a genlex order on X, the leftmost position where x differs from its predecessor is greater than k; this is in contradiction with x k+1 x k+2 . . . x n is the first discriminant suffix of x. The case where x k+1 x k+2 . . . x n is the last discriminant suffix of x is similar. ✷ Corollary 1 If X is an absorbent subset of {0, 1} n then X listed in ≺ order is a 3-Gray code.

Proof: Let y be the successor of x in X with respect to ≺ order and k be the leftmost position where x differs from y. Then, x k+1 x k+2 . . . x n (resp. y k+1 y k+2 . . . y n ) is the last (resp. the first) discriminant suffix of x (resp. y). By Lemma 2, x i = y i = 1 for all i, k + 1 ≤ i ≤ n, except possibly two of them. Since x i = y i for all i, 1 ≤ i ≤ k -1, the Hamming distance between x and y is at most three. ✷

We now state the main result of this note, which follows directly from Lemma 1 and Corollary 1.

Theorem 1 The ≺ order yields a 3-Gray code on the sets of pre-necklaces, necklaces and Lyndon words of length n.

Notice that similar results can be obtained for bracelets (minimal necklaces under the operation of reversal). Also, the first element in these Gray code lists is 01 n-1 and the last one is 1 n (for pre-necklaces and necklaces) and 001 n-2 (for Lyndon words and n ≥ 3). Thus all these Gray codes are circular, i.e., the first and last strings differ also in at most three positions.

Generating algorithm

Here we give an efficient algorithm for generating length n pre-necklaces, necklaces and Lyndon words in dual reflected order. It is based on Ruskey's implementation [START_REF] Ruskey | Combinatorial generation[END_REF] of the FKM algorithm (6; 8), which generates pre-necklaces, necklaces and Lyndon words in lexicographical order. In our Gray code version, when two values are possible for a[t], the current entry in the generated string, then either 0 or 1 is assigned first, depending upon the parity of the number of 0's in the prefix a[1]a [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF] . . . a[t -1]. This suffices to impose dual reflected order on the outputs and is obtained by adding a new binary parameter z which has the same parity as the number of 0's in this prefix.

Like the Ruskey-FKM algorithm, our algorithm gen Gray below generates length n prenecklaces; if P rint(a) is called only when p is a divisor of n or when p = n, then the algorithm lists, respectively, necklaces or Lyndon words. The main call is gen Gray(0, 1, 1) and a[0] = 0.

In ( 14) is shown that the Ruskey-FKM algorithm, and therefore also our Gray code version, generates necklaces and Lyndon words in constant average time; see also [START_REF] Ruskey | Combinatorial generation[END_REF]. The output of our algorithm for n = 5 is shown in Table 2 pre-necklaces necklaces Lyndon words 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1

Tab. 2: The set of length 5 pre-necklaces, necklaces and Lyndon words in dual reflected order. Note that for n ≤ 5 the Hamming distance between successive strings never exceeds two.

Final remarks

It can be shown that, in general, there is no listing for length n necklaces in which successive representatives differ in just one bit [START_REF] Wang | A Gray code for necklaces of fixed density[END_REF]. The existence of Gray codes for necklaces or Lyndon words where successive objects differ in at most two positions and a loopless implementation (O(1) in the worst case) of our algorithm remain open problems. Finally, the author would like to thank Frank Ruskey for providing improvements to the algorithm and one of the referees for helpful comments. Note added in proof: A recent subsequent generalization of our results to a k-ary alphabet (k > 2) appears in [START_REF] Weston | Gray codes for necklaces and Lyndon words of arbitrary base[END_REF].

  1365-8050 c 2007 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

  .

	procedure gen Gray(z, t, p)
	if t > n then P rint(a)
	else if a[t -p] = 1
	then a[t] := a[t -p]; gen Gray(z, t + 1, p)
	else a[t] := z; gen Gray(1, t + 1, p)
	a[t] := 1 -z; gen Gray(0, t + 1, t)
	end.