Prof. Dr Annegret Wagler
email: wagler@isima.fr

Automatic network reconstruction from experimental time-series data: A survey

Keywords: Automatische Netzwerk-Rekonstruktion experimenteller Zeitserien-Daten: Ein Überblick G.2.1 [Mathematics of Computing: Discrete Mathematics: Combinatorics], G.2.3 [Mathematics of Computing: Discrete Mathematics: Applications], G.1.6 [Mathematics of Computing: Numerical Analysis: Optimization] Netzwerk-Rekonstruktion, kombinatorische Algorithmen, diskrete Strukturen Die Rekonstruktion von Modellen ausgehend von experimentellen Daten ist aufgrund der Komplexität biologischer Systeme ein schwieriges Problem. Wir stellen ein exaktes, ausschließlich auf der Analyse der gegeben Daten beruhendes Verfahren vor, um Petri-Netze zu rekonstruieren: Modelle, die sowohl statische Interaktionen als auch dynamische Prozesse abbilden können. Die rekonstruierten Modelle sollen dabei in einer Simulation das experimentell beobachtete dynamische Verhalten aufweisen. Dafür betrachten wir Petri-Netze mit zweierlei Erweiterungen, Prioritäten auf Transitionen und Testkanten, um zusätzliche Aktivierungsregeln zu erhalten, die das dynamische Verhalten kontrollieren. Wir geben einen Überblick über Resultate zur Rekonstruktion von Standard-Netzwerken mit und Netzwerke des betrachteten Typs zu rekonstruieren, die konform mit den gegeben experimentellen Daten sind, um alle möglichen Alternativen von Mechanismen aufzuzeigen, die den experimentell beobachteten Phänomenen zugrunde liegen können

The reconstruction of models from experimental data is a challenging problem due to the inherited complexity of the studied biological systems. We discuss an exact, exclusively data-driven approach to reconstruct Petri nets, a framework which turned out to coherently model static interactions and dynamic processes. The reconstructed models shall reproduce the experimentally observed dynamic behavior in a simulation. For that, we consider Petri nets with two types of extensions, priority relations among the transitions and control-arcs, to obtain additional activation rules that control the dynamic behavior. Here, we give an overview on results concerning the reconstruction of standard networks with and without priorities, extended Petri nets, and extended Petri nets with priorities. All these approaches aim at reconstructing all networks of the studied type that fit the given experimental data, to provide all possible alternatives of mechanisms behind the experimentally observed phenomena.

Introduction

The overall aim of systems biology is to analyze biological systems and to understand different phenomena therein as, e.g., responses of cells to environmental changes, host-pathogen interactions, or effects of gene defects. To gain the required insight into the underlying biological processes, experiments are performed and the resulting experimental data are interpreted in terms of models that reflect the observed phenomena.

Depending on the biological aim and the type and quality of the available data, different types of mathematical models are used and corresponding methods for their reconstruction have been developed, see for instance [START_REF] Andrec | Interference of signaling and gene regulatory networks by steady-state perturbation experiments: structure and accuracy[END_REF][START_REF] Krishna | A partial granger causality approach to explode causal networks derived from multi-parameter data[END_REF][START_REF] Laubenbacher | A computational algebra approach to reverse engineering of gene regulatory networks[END_REF]. Our work is dedicated to Petri nets, a framework which turned out to coherently model both static interactions in terms of networks and dynamic processes in terms of state changes, see e.g. [START_REF] Chen | Quantitative Petri net model fo gene regulated metabolic networks in the cell[END_REF][START_REF] Koch | Petri nets[END_REF][START_REF]Modeling in Systems Biology[END_REF][START_REF] Marwan | Petri nets as a framework for the reconstruction and analysis of signal transduction pathways and regulatory networks[END_REF][START_REF] Pinney | Petri net representations in systems biology[END_REF].

In fact, a network P = (P, T, A, w) reflects the involved system components by places p ∈ P and their interactions by transitions t ∈ T , the arcs in A ⊂ (P × T ) ∪ (T × P ) link places and transitions, and the arc weights w : A → N reflect stoichiometric coefficients of the corresponding reactions. Moreover, each place p ∈ P can be marked with an integral number x p of tokens defining a system state x ∈ Z |P | + ; we denote by X the set of all potential system states. A transition t ∈ T is enabled in a state x if x p ≥ w(p, t) for all p with (p, t) ∈ A, switching or firing t leads to a successor state x ′ with x ′ p = x pw(p, t) for all (p, t) ∈ A and x ′ p = x p + w(t, p) for all (t, p) ∈ A. Dynamic processes are represented by sequences of such state changes.

Our central question is to reconstruct models of this type from experimental time-series data by means of an exact, exclusively data-driven approach. This approach takes as input a set P of places and discrete time-series data X ′ given by sequences (x 0 , x 1 , . . . , x k ) of experimentally observed system states. The goal is to determine all Petri nets (P, T, A, w) that are able to reproduce the data, i.e., where T contains enough transitions to perform for each x j ∈ X ′ the experimentally observed state change to x j+1 ∈ X ′ , and where this behavior is indeed shown in a simulation. Hence, in contrast to the normally used stochastic simulation, we require that for states where at least two transitions are enabled, the decision between the alternatives is not taken randomly, but a specific transition is selected.

Thus, (standard) Petri nets have to be equipped with additional activation rules to force the switching of special transitions (to reach x j+1 from x j ), and to prevent all others from switching. For that, different types of additional activation rules are possible.

On the one hand, in [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF][START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF][START_REF] Wagler | Prediction of network structure[END_REF] the concept of priority relations among the transitions of a network was introduced in order to allow the modeling of deterministic systems. Note that these priorities typically reflect the rate of the corresponding reactions where the fastest reaction has highest priority and, thus, is taken. Priorities can prevent enabled transitions from switching: for each state, only a transition is allowed to switch if it is enabled and there is no other enabled transition with higher priority. In Marwan et al. [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF] it is proposed to model such priorities with the help of partial orders O on the transitions. We call (P, O) an Petri net with priorities, if P = (P, T, A, w) is a Petri net and O a priority relation on T × T .

On the other hand, the concept of control-arcs can be used to represent catalytic or inhibitory dependencies. An extended Petri net P = (P, T, (A∪A R ∪A I ), w) is a Petri net which has, besides the (standard) arcs in A, two additional sets of so-called control-arcs: the set of read-arcs A R ⊂ P × T and the set of inhibitor-arcs A I ⊂ P × T . Also control-arcs can prevent enabled transitions from switching: an enabled transition t ∈ T coupled with a read-arc (resp. an inhibitor-arc) to a place p ∈ P can switch only if a token (resp. no token) is present in p. We denote the set of all arcs by

A = A ∪ A R ∪ A I .
For consistently integrating both concepts, priority relations and control-arcs, into the modeling framework, the difficulty is that both are concurrent concepts to force or prevent the switching of enabled transitions.

Let (P, O) be an extended Petri net with priorities with a network P = (P, T, (A ∪ A R ∪ A I ), w) and a partial order O ⊂ T × T on its transitions. To enforce a deterministic behavior, the network has to be equipped with appropriate control-arcs in (A R ∪ A I ) and priorities in O such that each state x ∈ X has a unique successor succ X (x), see [START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF] for more details. Extended Petri nets with priorities satisfying this property are said to be X -deterministic. For our purpose, we consider a relaxed condition, namely that each experimentally observed state x ∈ X ′ has a unique successor succ X ′ (x) ∈ X ′ , but we do not require this property for non-observed states x ∈ X \ X ′ . To this end, in [START_REF] Wagler | On minimality and equivalence of Petri nets[END_REF][START_REF] Wagler | On minimality and equivalence of Petri nets[END_REF], the notion of X ′ -deterministic extended Petri nets is introduced as the desired output of an integrative reconstruction method, which show a prescribed behavior on the experimentally observed subset X ′ of states: the reconstructed Petri nets (P, T, A, w) do not only contain enough transitions to reach the experimentally observed successors x j+1 from x j , but exactly this transition will be selected (due to appropriate priorities and controlarcs) among all enabled ones in x j which is necessary to reach x j+1 .

In Section 2, we survey results on the reconstruction of standard networks [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF], standard networks with priorities [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF][START_REF] Wagler | Prediction of network structure[END_REF], extended Petri nets [START_REF] Durzinsky | Reconstructing extended Petri nets from time series data and its application to signal transduction and to gene regulatory networks[END_REF][START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF] and extended Petri nets with priorities [START_REF] Favre | Reconstructing X ′ -deterministic extended Petri nets from experimental timeseries data X ′ (extended abstract)[END_REF][START_REF] Favre | Reconstructing extended Petri nets with priorities: Handling priority conflicts revisited[END_REF].

In Section 3, we discuss possible further extensions, future applications and the potential impact of the presented approaches.

Reconstruction approaches

We briefly describe the common input (P, X ′ ) for network reconstruction, the main ideas, and the generated output of the different approaches to reconstruct Petri nets from experimental time-series data X ′ .

Firstly, a set of components P (later represented by the set of places of the reconstructed networks) is chosen which is expected to be crucial for the studied phenomenon.

To perform an experiment, one first triggers the system in some state (by external stimuli like the change of nutrient concentrations or the exposition to some pathogens), to generate an initial state x1 . Then the system's response to the stimulation is observed and the resulting state changes are measured for all components at certain time points. This yields a sequence of (discrete or discretized 1 ) states x j ∈ Z |P | reflecting the time-dependent response of the system to the stimulation in x 1 , which typically terminates in a terminal state x k where no further changes are observed. The corresponding experiment is

X ′ (x 1 , x k ) = (x 1 , . . . , x k ).
Several experiments starting from different initial states in a set X ′ ini ⊆ X ′ , reporting the observed state changes for all components p ∈ P at certain time points, and ending at different terminal states in a set X ′ term ⊆ X ′ describe the studied phenomenon, and yield experimental time-series data of the form

X ′ = {X ′ (x 1 , x k ) : x 1 ∈ X ′ ini , x k ∈ X ′ term }.
Thus, the input of the reconstruction approach is given by (P, X ′ ).

In the best case, two consecutively measured states x j , x j+1 ∈ X ′ are also consecutive system states, i.e., x j+1 is reached from x j by switching a single transition. This is, however, in general not the case (and depends on the chosen time points to measure the states in X ′ ), but x j+1 may be obtained from x j by a switching sequence of some length, where the intermediate states are not reported in X ′ .

For a successful reconstruction approach, the data X ′ need to satisfy two properties:

• reproducibility (each x j ∈ X ′ has a unique observed successor state x j+1 ∈ X ′ ) and

• monotonicity (the values of each place must not oscillate in the intermediate states between x j and x j+1 ).

Whereas reproducibility is obviously necessary, it was shown in [START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF] that monotonicity has to be required or, equivalently, that all essential responses are indeed reported in the experiments. Note that reproducibility can be tested in a preprocessing step, which includes strategies to modify the given experimental data in order to ensure the required properties, see [START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF][START_REF] Wagler | Prediction of network structure[END_REF][START_REF] Wagler | Preprocessing for network reconstruction: Feasibility test and handling infeasibility[END_REF] for details.

A network P = (P, T, A, w) fits the given data X ′ when it is able to perform every observed state change from x j ∈ X ′ to x j+1 ∈ X ′ . More formally, with P, an incidence matrix C ∈ Z |P |×|T | is associated whose rows correspond to places and whose columns C •t to the update vectors r t of the transitions t ∈ T :

r t p = C pt :=      -w(p, t) if (p, t) ∈ A, +w(t, p) if (t, p) ∈ A, 0 otherwise.
Reaching x j+1 from x j by a switching sequence using the transitions from a subset T ′ ⊆ T is equivalent to obtain the state vector x j+1 from x j by adding the corresponding columns C •t of C for all t ∈ T ′ :

x j + t∈T ′ C •t = x j+1 .
Hence, T has to contain enough transitions to perform all experimentally observed switching sequences: P is conformal with X ′ if, for any two consecutive states x j , x j+1 ∈ X ′ , the linear equation system

x j+1 -x j = Cλ
has an integral solution λ ∈ N |T | such that λ is the incidence vector of a sequence (t 1 , ..., t m ) of according transition switches. Moreover, an extended Petri net is catalytic conformal with X ′ and a Petri net with priorities is X ′deterministic if there is a unique choice for the transitions to realize the switching sequences (due to appropriate control-arcs respectively appropriate control-arcs and priorities). Note that in all cases, the reconstructed networks have the same set P of places, as part of the input.

We next survey results on the reconstruction of

• standard networks [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF],

• standard networks with priorities [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF][START_REF] Wagler | Prediction of network structure[END_REF],

• extended Petri nets [START_REF] Durzinsky | Reconstructing extended Petri nets from time series data and its application to signal transduction and to gene regulatory networks[END_REF][START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF] and

• extended Petri nets with priorities [START_REF] Favre | Reconstructing X ′ -deterministic extended Petri nets from experimental timeseries data X ′ (extended abstract)[END_REF][START_REF] Favre | Reconstructing extended Petri nets with priorities: Handling priority conflicts revisited[END_REF].

Reconstructing standard networks

To reconstruct standard networks, the following approach is proposed in [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF].

Extraction of difference vectors. As initial step, extract the observed changes of states from the experimental data. For that, define the set

D := d j = x j+1 -x j : = (x j , x j+1 ) ∈ X ′ .
Decomposition of difference vectors. The first step is to describe the set of potential update vectors which might constitute the columns of C. Recall that two consecutively measured states x j , x j+1 ∈ X ′ are not necessarily consecutive system states, but x j+1 may be obtained from x j by some switching sequence whose intermediate states are not reported in X ′ . Due to monotonicity, the values of the elements cannot oscillate in the intermediate states between x j and x j+1 . By [START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF], it suffices to decompose any d j ∈ D using only sign-compatible vectors from the following set

Box(d j ) =    r ∈ Z |P | : 0 ≤ r p ≤ d j p if d j p > 0 d j p ≤ r p ≤ 0 if d j p < 0 r p = 0 if d j p = 0    \{0}.
Due to [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF], none of the reconstructed networks must contain a transition enabled at any of the observed terminal states x k of a time-series (x 0 , x 1 , . . . , x k ); hence all such vectors in Box(d j ) can be removed, resulting in a reduced set Box red (d j ).

Next, we determine for any d j ∈ D the set Λ(d j ) of all integral solutions λ of the equation system

d j = r t ∈ Box red (d j ) λ t r t , λ t ∈ Z + .
Due to [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF], Λ(d j ) is non-empty if and only if d j is not enabled at any of the terminal states.

For each λ ∈ Λ(d j ), construct the (multi-)set R(d j , λ) = {r t ∈ Box red (d j ) : λ t = 0} of update vectors used for this decomposition λ.

Composition of networks.

Selecting exactly one solution λ ∈ Λ(d j ) for each d j ∈ D and taking the union of the corresponding sets R(d j , λ), we yield the columns C •t = r t of an incidence matrix C of a (standard) network P . By construction, P is conformal with X ′ since the selected update vectors (corresponding to the transitions of the network) are able to reproduce all experimentally observed state changes.

We obtain all such networks by taking all possible combinations of sets R(d j , λ) for different choices λ ∈ Λ(d j ) for all d j ∈ D, see [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF][START_REF] Wagler | Prediction of network structure[END_REF].

Reconstructing standard networks with priorities

To generate standard networks with priorities, the first two steps of extracting and decomposing difference vectors are as in the case of standard networks without priorities. However, not all possible combinations of sets R(d j , λ) for different λ ∈ Λ(d j ) lead to X ′ -deterministic networks. Here, it is necessary to consider all possible switching sequences for a decomposition λ ∈ Λ(d j ), to detect priority conflicts between different sequences, and to only compose selections of non-conflicting sequences to networks. For that, the following approach is proposed in [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF] (see [START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF][START_REF] Wagler | Prediction of network structure[END_REF] for further details). We again extract difference vectors and decompose them as in the case of standard network reconstruction to determine the sets R(d j , λ) for all obtained difference vectors d j . Then, we proceed as follows:

Switching sequences and their conflicts. Every permutation π = (r t1 , . . . , r tm ) of the elements of a set R(d j , λ) gives rise to a sequence of intermediate states x j = y 1 , y 2 , ..., y m , y m+1 = x j+1 with σ = σ π,λ (x j , d j ) = (y 1 , r t1 ), (y 2 , r t2 ), . . . , (y m , r tm ) which induces a priority relation O σ since transition t i resulting from r ti is supposed to have highest priority in y i for 1 ≤ i ≤ m. Two sequences σ and σ ′ are in priority conflict if there are update vectors r t = r t ′ and intermediate states y, y ′ such that t, t ′ are enabled in y, y ′ and (y,

r t ) ∈ σ but (y ′ , r t ′ ) ∈ σ ′ (since this im- plies t > t ′ in O σ but t ′ > t in O σ ′ ).
Note that all sequences for the same d j ∈ D are mutually in conflict.

Selecting non-conflicting sequences. Construct a priority conflict graph G whose nodes correspond to all possible sequences σ π,λ (x j , d j ) and whose edges reflect their priority conflicts. In G, all node subsets S are generated that select exactly one sequence σ π,λ (x j , d j ) per difference vector d j ∈ D such that no priority conflicts occur between the selected sequences.

Remark. Each selected subset S corresponds to a socalled stable set in G, all nodes corresponding to sequences for the same d j ∈ D to a so-called clique in G. Note that we need to select one node from each such clique for a stable set S.

Composition of networks. Each subset S gives rise to a standard network P = (P, T, A, w), obtained by taking the union of the corresponding sets R(d j , λ) for each σ = σ π,λ (x j , d j ) ∈ S, which can be made X ′deterministic by adding the priority relations O σ for all σ ∈ S, see [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF][START_REF] Wagler | Prediction of network structure[END_REF].

Reconstructing extended networks

To generate extended Petri nets without priorities, the decomposition of difference vectors has to be further adapted. As before, no transition of a returned network must be enabled at any of the observed terminal states x k of a time-series (x 0 , x 1 , . . . , x k ). However, this cannot be done by excluding potential update vectors, but instead by inserting control-arcs to disable the resulting transitions at the terminal states. This task can be done by using the procedure proposed in [START_REF] Durzinsky | Reconstructing extended Petri nets from time series data and its application to signal transduction and to gene regulatory networks[END_REF][START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF].

Decomposition of difference vectors. Due to monotonicity, it suffices again to decompose any d j ∈ D using vectors from Box(d j ) only such that Λ(d j ) consists of all integral solutions λ of the equation system

d j = r t ∈ Box(d j ) λ t r t , λ t ∈ Z + and for each λ ∈ Λ(d j ), R(d j , λ) is constructed.
Composition of standard networks. We consider again permutations π of the elements of R(d j , λ) and the resulting switching sequences σ π,λ (x j , d j ). Due to [START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF], such a sequence is catalytic conformal if and only if none of its intermediate states (including x j = y 1 ) is an observed terminal state.

Selecting exactly one catalytic conformal sequence σ π,λ (x j , d j ) for each d j ∈ D and taking the union of the corresponding sets R(d j , λ) yields the columns C •t = r t of an incidence matrix C of a network. We obtain all such networks by taking all possible combinations.

Inserting control-arcs. It is assumed that controlarcs depend only on the presence or absence of a component, such that vectors x ∈ X ′ are mapped to binary vectors in {0, 1} |P | considering only the support of x and thus can be tested in terms of propositional logic.

For this purpose, it is useful to encode the test by conjunctions of literals. Hereby, a literal can be any component x p of a vector x or its logical negation ¬x p . A conjunction xp,¬xq∈P ′ of literals is true if and only if all positive variables x p ∈ P ′ have value greater than zero and all negated variables ¬x q ∈ P ′ have value zero. That way, each conjunction represents a pattern of components which need to be present or absent for the conjunction to be true. For details on how to find such a logical formula and the possible values to satisfy it, we refer to [START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF].

A conjunction can be modeled as a Petri net by connecting a transition to the places with read-arcs for every positive literal, and with inhibitor-arcs for every negative literal; the transition is enabled if and only if the conjunction is true.

Reconstructing extended networks with priorities

To generate extended Petri nets with priorities, the following approach is proposed in [START_REF] Favre | Reconstructing X ′ -deterministic extended Petri nets from experimental timeseries data X ′ (extended abstract)[END_REF] and detailed in [START_REF] Favre | Reconstructing extended Petri nets with priorities: Handling priority conflicts revisited[END_REF], based on previous works in [START_REF] Durzinsky | Reconstructing extended Petri nets from time series data and its application to signal transduction and to gene regulatory networks[END_REF][START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF][START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF][START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF].

Decomposition of difference vectors. Due to monotonicity, it suffices again to decompose any d j ∈ D using vectors from Box(d j ) only, to determine Λ(d j ) accordingly and to construct R(d j , λ) for each λ ∈ Λ(d j ).

Due to [START_REF] Favre | Reconstructing X ′ -deterministic extended Petri nets from experimental timeseries data X ′ (extended abstract)[END_REF], Box(d j ) and Λ(d j ) are always nonempty since d j itself is always a solution due to the required reproducibility of the input data X ′ (which particularly ensures d j = 0 for all d j ∈ D, see also [START_REF] Wagler | Preprocessing for network reconstruction: Feasibility test and handling infeasibility[END_REF]).

Switching sequences and their conflicts. We consider again permutations π of the elements of R(d j , λ), the resulting switching sequences σ = σ π,λ (x j , d j ) = (y 1 , r t1 ), (y 2 , r t2 ), . . . , (y m , r tm ) and the induced priority relations O σ . Recall that two sequences σ and σ ′ are in priority conflict if there are update vectors r t = r t ′ and intermediate states y, y ′ such that t, t ′ are enabled in y, y ′ and (y, r t ) ∈ σ but (y ′ , r t ′ ) ∈ σ ′ . We have a weak (resp. strong) priority conflict if y = y ′ (resp. y = y ′ ) which can (resp. cannot) be resolved by adding appropriate control-arcs. Note that all sequences for the same d j ∈ D are in strong conflict.

Composition of standard networks. Construct a priority conflict graph G whose nodes correspond to all catalytic conformal sequences σ π,λ (x j , d j ) and whose edges reflect weak and strong priority conflicts. In G, all node subsets S are generated that select exactly one sequence σ π,λ (x j , d j ) per difference vector d j ∈ D such that no strong priority conflicts occur between the selected sequences. Each such subset S gives rise to a standard network P = (P, T, A, w) which is conformal with X ′ and can be made X ′ -deterministic.

Inserting control-arcs and adding priorities. To resolve a weak priority conflict between σ, σ ′ ∈ S involving update vectors r t = r t ′ and intermediate states y = y ′ , include

• either a read-arc (p, t) ∈ A R with weight w(p, t) > y ′ p for some p with y p > y ′ p or • an inhibitor-arc (p, t) ∈ A I with weight w(p, t) < y p for some p with y p < y ′ p to disable transition t resulting from r t at y ′ . For each σ ∈ S, define O σ based on the soconstructed transition sequences to obtain the studied partial order to make the generated extended networks X ′ -deterministic, see [START_REF] Favre | Reconstructing X ′ -deterministic extended Petri nets from experimental timeseries data X ′ (extended abstract)[END_REF][START_REF] Favre | Reconstructing extended Petri nets with priorities: Handling priority conflicts revisited[END_REF] for details.

Discussion

Systems biology aims at the integrated experimental and theoretical analysis of cellular networks to obtain a holistic understanding of biological systems and processes. The large diversity of organisms and cell types and the huge variety of the involved biochemical processes requires advanced modeling and analysis approaches.

While metabolic networks are characterized by a flow of substance through biochemical intermediates that are interconverted into each other, regulatory or signal transduction networks function by a flow of information mediated by the reversible modification of functionally interacting components.

Since the information flow may occur through different molecular reaction mechanisms, it is not always trivial to unequivocally assign known biochemical reactions to a causal sequence of signaling events and vice versa. This is one reason why important control mechanisms like those for growth, differentiation, motility or apoptosis in eukaryotic cells are incompletely understood at the molecular systems level.

Reconstructing the functional interactions of genes and their products from experimental data by generating validated, composable, and predictive models of the underlying regulatory networks is one of the challenges of systems biology. To be useful for the reconstruction of causal interactions within regulatory networks from experimental data sets, it is suggested in [START_REF] Marwan | Petri nets as a framework for the reconstruction and analysis of signal transduction pathways and regulatory networks[END_REF] that a modeling framework should have the following properties. It should be able to

• represent the properties of the real system based on an unambiguous and strict syntax;

• reproduce qualitative and quantitative data in the particular formats as detected by different experimental techniques;

• connect functional elements or modules of arbitrary molecular complexity in the form of one single, coherent model;

• consistently represent the various molecular mechanisms or genetic interactions that occur in a living cell.

As exhibited in [START_REF] Koch | Petri nets[END_REF][START_REF]Modeling in Systems Biology[END_REF][START_REF] Marwan | Petri nets as a framework for the reconstruction and analysis of signal transduction pathways and regulatory networks[END_REF], all of these requirements are fulfilled by place/transition Petri nets and/or their various (stochastic or deterministic) extensions. As mathematical structures, Petri nets allow the application of graph theoretical approaches and the mathematical treatment of formalized problems related to the molecular networks they are representing. This is particularly useful for the reconstruction and analysis of the regulatory networks studied in molecular cell biology and genetics.

So far, Petri nets as well as other modeling frameworks have mostly been used for bottom-up modeling approaches which are based on pre-defined molecular models of a given network: Experimental results are evaluated, and by heuristic reasoning, a network of biochemical reactions is established in the form of a classical biochemical pathway or in the form of an informal graphically displayed molecular interaction model. This molecular model is then translated into a Petri net to study the functional properties of the net, to run simulations, and to predict the behavior of the real network in response to perturbation.

Petri nets can also be obtained directly by algorithmically evaluating experimental data; such an approach is called network reconstruction, network inference, or reverse engineering. In this survey, we addressed the challenging problem of Automatic Network Reconstruction: reconstructing Petri net models from experimental time-series data by means of an exact, exclusively data-driven method. In the previous section, we gave an overview on approaches to reconstruct

• standard networks [START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF][START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF],

• standard networks with priorities [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF][START_REF] Wagler | Prediction of network structure[END_REF],

• extended Petri nets [START_REF] Durzinsky | Reconstructing extended Petri nets from time series data and its application to signal transduction and to gene regulatory networks[END_REF][START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF], and

• extended Petri nets with priorities [START_REF] Favre | Reconstructing X ′ -deterministic extended Petri nets from experimental timeseries data X ′ (extended abstract)[END_REF][START_REF] Favre | Reconstructing extended Petri nets with priorities: Handling priority conflicts revisited[END_REF].

In all cases, a preprocessing is in order to ensure the required properties of the input data.

On the one hand, we discussed the influence of the quality of the given experimental data in [START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF] showing that monotone data X ′ are necessary (or, equivalently, that all essential responses are indeed reported in the experiments).

On the other hand, feasibility tests to test the given experimental data X ′ for reproducibility have been developed (in [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF] for standard networks and in [START_REF] Wagler | Preprocessing for network reconstruction: Feasibility test and handling infeasibility[END_REF] for extended Petri nets with priorities) to ensure that each observed state x ∈ X ′ has a unique successor in X ′ . If this test fails, the existence of previously undetected elements of regulatory function is proved since the given data do not suffice to explain the causal mechanisms behind the observed phenomenon [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Wagler | Preprocessing for network reconstruction: Feasibility test and handling infeasibility[END_REF]. To handle infeasible cases, additional elements are added to P and the given experimental data X ′ are extended by determining all possible values for the new elements in P such that any state x ∈ X ′ with previously two different successors is split into different states each having a unique successor [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Wagler | Preprocessing for network reconstruction: Feasibility test and handling infeasibility[END_REF]. Then, the regular reconstruction procedure is applied to every extended setting of P and X ′ meeting these properties.

All here presented reconstruction approaches aim at generating all models of the studied type that fit with the given experimental data, to provide all possible alternatives of mechanisms behind the observed biological phenomena.

In the latter three cases, the generated networks are also able to exhibit the experimentally observed dynamic behavior in a simulation, since priorities and/or control-arcs are used as additional activation rules to force the switching of special transitions. In particular, the reconstruction of extended Petri nets with priorities [START_REF] Favre | Reconstructing X ′ -deterministic extended Petri nets from experimental timeseries data X ′ (extended abstract)[END_REF] is an integrative method which generates models fully fitting the experimentally observed phenomena.

This typically causes a large number of solution alternatives, see e.g. [START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF][START_REF] Favre | Reconstructing X ′ -deterministic extended Petri nets from experimental timeseries data X ′ (extended abstract)[END_REF].

To keep this solution set as small as possible while still guaranteeing its completeness, a postprocessing should be applied to keep only "minimal" solutions in the sense that all other networks fitting the data contain the returned ones. For standard networks, minimality can be easily imposed by set inclusion of the transition sets [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF], for extended Petri nets with(out) priorities, an equivalence relation is defined on the underlying standard networks and minimal representatives are selected by means of priorities and/or control-arcs [START_REF] Wagler | On minimality and equivalence of Petri nets[END_REF][START_REF] Wagler | On minimality and equivalence of Petri nets[END_REF].

Moreover, it would be desirable to exclude solution alternatives that contradict well-established biological knowledge or insight gained during previous rounds of the reconstruction process.

Although the here-surveyed reconstruction approaches are all exclusively data-driven methods, it could be advantageous to integrate some a priori biological knowledge already during the reconstruction process, instead of afterwords applying a biological verification of the reconstructed network alternatives as, e.g., done in [START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF].

We next discuss several possibilities proposed in [START_REF] Favre | Integrating a priori biological knowledge in Automatic Network Reconstruction[END_REF] how certain biological knowledge could be integrated during the reconstruction process.

• Indecomposability of difference vectors. So far, all reconstruction approaches determine the set of potential update vectors which might constitute the networks by considering, for each d j ∈ D, all signcompatible vectors from the set Box(d j ).

In some cases, however, an observed response d j ∈ D might exactly correspond to a well-known biochemical reaction (including the correct stoichiometry) or to a well-known mechanism (that a certain trigger is detected by a suitable receptor).

In such cases, one could exclude the corresponding response d j ∈ D from decomposition and, instead, just define Box(d j ) := {d j } in accordance with the already established knowledge.

• Benefiting from known P-invariants. For a network P = (P, T, A, w) with incidence matrix C ∈ Z |P |×|T | , a P-invariant is an integer solution of the equation system

y T C = 0 T , y ∈ N |P | , y = 0.
P-invariants describe mass-preserving submoduls: subsets P ′ ⊆ P of places where the total number of tokens remains constant in each system state.

Typical examples of P-invariants are, e.g., different conformational states of a molecule, a receptor or a cell. If such P-invariants are known a priori within the experimentally studied set P of components, they can be provided as input in form of a set I P . This allows to reduce, for any d j ∈ D, the set Box(d j ) of potential update vectors to decompose d j by including the restriction p∈P ′ r p = 0, ∀P ′ ∈ I P , see also [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Wagler | Prediction of network structure[END_REF] for details.

• Treating equal difference vectors in the same way.

So far, all observed responses d j ∈ D are decomposed independently from each other. To generate standard networks, exactly one solution λ ∈ Λ(d j ) for each d j ∈ D is selected, for networks with priorities, permutations π of the elements of the corresponding sets R(d j , λ) give rise to sequences σ π,λ (x j , d j ), and non-conflicting sequences are selected.

If two difference vectors d i , d j ∈ D are equal, we have Box(d i ) = Box(d j ) and it would be natural to require that both d i , d j are decomposed in the same way (i.e., by the same λ ∈ Λ(d i ) = Λ(d j )) and that the involved reactions are applied in the same order (i.e., by the same permutation π of the elements of the corresponding sets R(d i , λ) = R(d j , λ)).

The latter could be achieved by adding (strong) priority conflicts between all other sequences stemming from a pair d i , d j of equal difference vectors while creating the priority conflict graph, since no two sequences in (strong) priority conflict are selected for the same network.

• Knowledge on reaction rates, catalysts or inhibitors. In the case of reconstructing extended Petri nets with priorities, sequences σ, σ ′ in weak priority conflict might be selected for a network.

To resolve a weak priority conflict between σ, σ ′ involving update vectors r t = r t ′ and intermediate states y = y ′ , either transition t has to be disabled at y ′ or transition t ′ at y, while the decision between t and t ′ on the other state can be handled by a priority.

Here, pre-knowledge about the reaction rates of t and t ′ (e.g. gained from the time-scales during the experiments) could help to decide whether t > t ′ or t < t ′ better reflects the reality.

Furthermore, to resolve the conflict on the remaining state, at least one control-arc of the following form is included:

a read-arc (p, t) with weight w(p, t) > y ′ p for some p with y p > y ′ p or an inhibitor-arc (p, t) with weight w(p, t) < y p for some p with y p < y ′ p . A priori knowledge on catalysts or inhibitors of the studied reactions r t , r t ′ can help to reduce the potential alternatives of control-arcs and, thus, the total number of generated network alternatives.

Note that a priori knowledge can also be obtained in terms of structural insights of an interplay of components gained in previous reconstruction steps. In fact, it is possible to step-wise refine Petri net models since places and transitions may summarize (lump) subnetworks of biochemical reactions of known or unknown molecular detail, see [START_REF] Marwan | Petri nets as a framework for the reconstruction and analysis of signal transduction pathways and regulatory networks[END_REF] for further details.

So, it is possible to run a reconstruction process on a currently known input and, as soon as it turns out that further components are crucial for the studied phenomenon or new experimental data becomes available, it is possible to re-run the reconstruction procedure on an extended input setting (P, X ′ ), thereby preserving insights and approved subnetworks gained in the previous reconstruction round(s).

Impact of Automatic Network Reconstruction.

To summarize, we surveyed an exact combinatorial approach to generate a complete list of all Petri nets that are conformal with the given data [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF] or even display the experimentally observed behavior in a simulation [START_REF] Durzinsky | Reconstructing extended Petri nets from time series data and its application to signal transduction and to gene regulatory networks[END_REF][START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF][START_REF] Favre | Reconstructing X ′ -deterministic extended Petri nets from experimental timeseries data X ′ (extended abstract)[END_REF][START_REF] Favre | Reconstructing extended Petri nets with priorities: Handling priority conflicts revisited[END_REF].

For standard and extended networks, we verified the correctness of the algorithm with the help of some small biological instances [START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF][START_REF] Durzinsky | Automatic reconstruction of molecular and genetic networks from experimental time series data[END_REF]. For standard networks, we provided an implementation of the reconstruction approach using Answer Set Programming [START_REF] Durzinsky | Automatic network reconstruction using ASP[END_REF].

The further goal is to provide such an implementation also for extended Petri nets with and without priorities, hereby including both options of integrating previous knowledge during the reconstruction as proposed in [START_REF] Favre | Integrating a priori biological knowledge in Automatic Network Reconstruction[END_REF] or of generating the whole set of all technically possible solution alternatives.

Finally, we plan to apply the presented reconstruction approaches to different biological experimental data, e.g., to

• cell differentiation processes depending on the correlated expression of developmentally regulated genes in polycephalum (a model organism for cell differentiation) like in [START_REF] Ebeling | Physarum polycephalum mutants in the photocontrol of sporulation display altered patterns in the correlated expression of developmentally regulated genes[END_REF];

• sulfur metabolism in wheat and its implications to the wheat grain protein composition like described in [START_REF] Ravel | Genetic mapping of wheat grain protein composition reveals that gliadin and glutenin composition are trans-regulated by different chromosomic regions[END_REF].

We indeed expect an important impact of Automatic Network Reconstruction in order to support the integrated experimental and theoretical analysis of biological systems and processes towards their holistic understanding.

Moreover, note that the here surveyed reconstruction procedures have a large potential as they can be applied in various contexts:

• Reverse engineering: The main application consists in determining all molecular or regulatory networks or networks of causal dependencies fitting given biological experimental data.

Note that this includes to detect causal interactions between host and pathogen or between cells of a tissue or tissues of an organ, with or without drug application.

• Experimental design: Once the reverse engineering step is performed, it is possible to analyze the obtained solution set in order to define further experiments to rule out inappropriate solution alternatives.

This can be done by defining experiments that allow and are sufficient to unequivocally distinguish between alternatives of a complete list of alternative networks, thereby avoiding to perform unnecessary or to miss necessary experiments.

•

Step-wise refining models: In an iterative process of experimentation and computation, it is possible to obtain a hierarchically defined Petri net where places and transitions are refined into subnetworks, resolving individual biochemical reactions at any level of kinetic detail while other nodes of the same net may still represent more complex processes like the activation of a cluster of differentially expressed genes or the assumption of a physiological state of the entire cell. This is possible since Petri nets provide a powerful modeling tool: Even if many molecular details are still unknown, models can be obtained and simulations run to predict or verify experimental results.

• Systems design: In synthetic biology, the goal is to design systems with predefined structural motives or a prescribed dynamic behavior.

This can be achieved by creating the complete list of all alternative networks, or changes in the structure of a given network, by applying reconstruction procedures to time-series data that describe those predefined motives or exhibit the prescribed dynamic behavior.

Some measured data are of a discrete nature, e.g., a gene can be expressed or not, an enzyme can be present or not, a protein occurs in one of its conformational states. If some measured data are continuous, e.g., concentrations of certain metabolites, it is necessary to appropriately discretize the continuous data into finitely many discrete states. Hereby, the chosen level of discretization has to be fine enough to preserve all dynamic features of the time course (in particular all local maxima or minima of the values), but rough enough to be robust to noise in the experimental data.

From 2000 to 2004, she was post-doc at the Zuse Institute Berlin. From 2004 to 2010, she was the head of a junior research group at the Otto-von-Guericke-University


Gabriela Argiroffo

Silvia Bianchi
email: sbianchi@fceia.unr.edu.ar

Annegret Wagler
email: annegret.wagler@univ-bpclermont.fr

Progress on the description of identifying code polyhedra for some families of split graphs

Keywords: identifying code problem, polyhedral approach, split graphs

The identifying code problem is a newly emerging search problem, challenging both from a theoretical and a computational point of view, even for special graphs like bipartite graphs and split graphs. Hence, a typical line of attack for this problem is to determine minimum identifying codes of special graphs or to provide bounds for their size.

In this work we study the associated polyhedra for some families of split graphs: headless spiders and complete suns. We provide the according linear relaxations, discuss their combinatorial structure, and demonstrate how the associated polyhedra can be entirely described or polyhedral arguments can be applied to find minimum identifying codes for special split graphs. We discuss further lines of research in order to apply similar techniques to obtain strong lower bounds stemming from linear relaxations of the identifying code polyhedron, enhanced by suitable cutting planes to be used in a B&C framework.

Introduction

Many practical applications can be stated as set covering problems. For instance, some newly emerging search problems like fault detection in networks, fire detection in buildings, or performing group tests, can be modeled as special variant of domination problems: so-called identifying codes in graphs [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF].

Consider a graph G = (V, E) and denote by N [i] = {i} ∪ N (i) the closed neighborhood of i. A subset C ⊆ V is dominating (resp. identifying) if N [i]∩C are non-empty (resp. distinct) sets for all i ∈ V . An identifying code of G is a node subset which is dominating and identifying, see Figure 1, and the identifying code number γ ID (G) of a graph G is the minimum cardinality of an identifying code of G.

(b) (c) (a) (d)
Fig. 1. A graph, where the subset of black nodes forms (a) a dominating (but not identifying) set, (b) an identifying (but not dominating) set, and (c), (d) minimum identifying codes.

Determining γ ID (G) is in general NP-complete [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard[END_REF]. It even remains hard for several graph classes where many other in general hard problems are easy to solve, including bipartite graphs [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard[END_REF], split graphs [START_REF] Foucaud | The complexity of the identifying code problem in restricted graph classes[END_REF] and, thus, chordal graphs. From a graph theoretical point of view, the problem has been actively studied, see e.g. [START_REF] Auger | Minimal identifying codes in trees and planar graphs with large girth[END_REF][START_REF] Bertrand | Identifying and locating dominating codes on chains and cycles[END_REF][START_REF] Foucaud | Identifying codes in line graphs[END_REF][START_REF] Gravier | Identifying codes of cycles[END_REF] for some recent papers in the area.

Polyhedral studies of the identifying code problem were initiated in [START_REF] Argiroffo | Polyhedra associated with identifying codes, submitted to Discrete Applied Mathematics[END_REF][START_REF] Argiroffo | Polyhedra associated to identifying codes (extended abstract)[END_REF]. For that, a suitable reformulation of the problem in terms of an integer linear program is in order. Determining a minimum identifying code in a graph G = (V, E) can be formulated as set covering problem min 1 T x, M ID (G) ≥ 1, x ∈ {0, 1} |V | by:

min 1 T x x(N [j]) = i∈N [j] x i ≥ 1 ∀j ∈ V (domination) x(N [j] △ N [k]) = i∈N [j]△N [k] x i ≥ 1 ∀j, k ∈ V, j = k (identification)
x ∈ {0, 1} |V | .

We call

M ID (G) =    N [G] △[G]   
the identifying code matrix of G, encoding the closed neighborhoods of the nodes of G (N [G]) and their symmetric differences (△[G]), and define the identifying code polyhedron of G as

P ID (G) = conv{x ∈ Z |V | + : M ID (G) x ≥ 1}.
It is clear by construction that γ ID (G) equals the covering number τ (M ID (G)) := min{1 T x : x ∈ P ID (G)}.

In addition, a graph G has an identifying code or is identifiable if and only if M ID (G) has no zero-row. As N [G] has clearly no zero-row, G is identifiable if and only if △[G] has no zero-row which is equivalent to the known condition that G is identifiable if and only if it has no true twins, i.e., nodes i, j with N [i] = N [j], see [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF].

As M ID (G) may contain rows which are equal to or dominated by other rows in M ID (G), we define the corresponding clutter matrix, the identifying code clutter C ID (G) of G, obtained by removing repeated or dominated rows from M ID (G). We clearly have that

P ID (G) = conv{x ∈ Z |V | + : C ID (G) x ≥ 1},
and obtain as a linear relaxation the fractional identifying code polyhedron

Q ID (G) = {x ∈ R |V | + : C ID (G) x ≥ 1}.
In [START_REF] Argiroffo | Polyhedra associated with identifying codes, submitted to Discrete Applied Mathematics[END_REF][START_REF] Argiroffo | Polyhedra associated to identifying codes (extended abstract)[END_REF] we characterized when P ID (G) is full-dimensional and which constraints of Q ID (G) define facets of P ID (G):

Lemma 1 ( [START_REF] Argiroffo | Polyhedra associated with identifying codes, submitted to Discrete Applied Mathematics[END_REF][START_REF] Argiroffo | Polyhedra associated to identifying codes (extended abstract)[END_REF]) Let G be a graph without isolated nodes and let

V 1 (G) be the set of nodes k ∈ V (G) such that {k} = N [i] △ N [j]
for two different nodes i and j in V (G). Then,

• P ID (G) is full-dimensional if and only if V 1 (G) = ∅. • The constraint x i ≥ 0 defines a facet of P ID (G) if and only if i / ∈ V 1 (G). • All constraints from C ID (G) x ≥ 1 define facets of P ID (G).
In this work we study the identifying code problem from a polyhedral point of view and focus on some families of split graphs: headless spiders and complete suns.

We provide the according linear relaxations, discuss their combinatorial structure, and demonstrate how the associated polyhedra can be entirely described or polyhedral arguments can be applied to find minimum identifying codes for special split graphs, see Section 2. Parts of the results appeared without proofs in [START_REF] Argiroffo | Study of identifying code polyhedra for some families of split graphs[END_REF].

We discuss further lines of research in order to apply similar techniques to obtain strong lower bounds stemming from linear relaxations of the identifying code polyhedron, enhanced by suitable cutting planes to be used in a B&C framework, see Section 3.

Preliminary definitions

Given a set F of vectors in {0, 1} n , we call y ∈ F a dominating vector (of F ) if there exists x ∈ F with x ≤ y. It can be also said that x is dominated by y. From now on, every matrix has 0, 1-entries, no zero columns and no dominating rows.

As there is a one-to-one correspondence between a vector x ∈ {0, 1} n and the subset S x ⊂ {1, . . . , n} having x as characteristic vector, we write x instead of S x . Remind that a cover of a matrix M is a vector x ∈ {0, 1} n such that M x ≥ 1. According to the previous convention, a cover of M is a subset of columns ({1, . . . , n}) that intersects all the rows of M .

In addition, the cardinality of a cover x is denoted by |x| and equals 1x. A cover x is minimum if it has the minimum cardinality and in this case |x| is called the covering number of the matrix M , denoted by τ (M ).

Recall that the set covering polyhedron of M , denoted by Q * (M ), is defined as the convex hull of its covers. The polytope

Q(M ) = {x ∈ [0, 1] n : M x ≥ 1} is known as the linear relaxation of Q * (A). When Q * (A) = Q(A) the matrix
A is ideal and the set covering problem can be solved in polynomial time (in the size of M ).

A cover of M is minimal if it does not dominate any other cover of M . The blocker of M , denoted by b(M ), is the matrix whose rows are the minimal covers of M . It is known that b(b(M )) = M and also that a matrix M is ideal if and only if its blocker is (see [START_REF] Lehman | On the width-length inequality[END_REF]). In addition, since b(b(M )) = M we can refer to Q * (M ) and Q(b(M )) as a blocking pair of polyhedra. Moreover, a is an extreme point of Q(b(M )) if and only if a T x ≥ 1 is a facet defining inequality of Q * (M ) (see [START_REF] Fulkerson | Blocking polyhedra[END_REF]). In the sequel we will refer to this property as blocking duality.

Given a matrix M and j ∈ {1, . . . , n}, we introduce two matrix operations: the contraction of j, denoted by M/j, means that column j is removed from M as well as the resulting dominating rows and hence, corresponds to setting x j = 0 in the constraints M x ≥ 1. The deletion of j, denoted by M \ j means that column j is removed from M as well as all the rows with a 1 in column j and this corresponds to setting x j = 1 in the constraints M x ≥ 1.

Given M and V 1 , V 2 ⊂ {1, . . . , n} disjoint, we will say that M/V 1 \ V 2 is a minor of M and this minor does not depend on the order of operations or elements in {1, . . . , n}. It is clear that M is always a minor of itself and we will say that a minor

M/V 1 \ V 2 is proper if V 1 ∪ V 2 = ∅. It is not hard to see that b(M/j) = b(M ) \ j and b(M \ j) = b(M )/j
for every j ∈ {1, . . . , n}. In addition, if a matrix is ideal then so are all its minors (see [START_REF] Cornuéjols | Combinatorial Optimization: Packing and Covering[END_REF] for details).

A rank inequality is

i∈M ′ x i ≥ τ (M ′ ) (1)
associated with a minor

M ′ = M \ U . If (1) is a facet of Q * (M ′
), then it is also a facet of Q * (M ) (see [START_REF] Sassano | On the facial structure of the set covering polytope[END_REF]).

In addition, if the rank constraint associated with some minor induces a facet defining inequality of Q * (M ) then this inequality is also induced by a minor obtained by deletion (see [START_REF] Argiroffo | On the set covering polyhedron of circulant matrices[END_REF] for further details).

2 Identifying code polyhedra of some split graphs

A graph G = (C ∪ S,
(G) = γ ID (G ′ )+|S ′ | holds.
This motivates the study of identifying codes in non-complete, connected split graphs G. We concentrate on three families of split graphs with a regular structure. This allows us to benefit from a certain combinatorial structure of the identifying code clutter C ID (G) of G and to draw conclusions for the polyhedra P ID (G) and the identifying code number γ ID (G) in a similar way as discussed for families of bipartite graphs in [START_REF] Argiroffo | Polyhedra associated with identifying codes, submitted to Discrete Applied Mathematics[END_REF][START_REF] Argiroffo | Polyhedra associated to identifying codes (extended abstract)[END_REF].

In particular, note that stars K 1,n are bipartite graphs as well as split graphs.

Their identifying code clutter is related to q-roses R q n , 0, 1-matrices with n columns whose rows encode the incidence vectors of all the q-element subsets of {1, . . . , n}. We have:

Theorem 1 ([2,3]) For a star K 1,n = (V, E) with n ≥ 3, we have • C ID (K 1,n ) = R 2 n+1 ; • P ID (K 1,n ) is entirely described by the inequalities x(V ′ ) ≥ |V | -1 for all nonempty subsets V ′ ⊂ V ; • γ ID (K 1,n ) = n.
In this paper, we study three families of split graphs with |S| = |C| ≥ 2 having a regular structure. A headless spider is a split graph G = (C ∪ S, E) with S = {s 1 , . . . , s n }, C = {c 1 , . . . , c n }, and n ≥ 2. In a thin headless spider, s i is adjacent to c j if and only if i = j, and in a thick headless spider, s i is adjacent to c j if and only if i = j. It is straightforward to check that the complement of a thin spider is a thick spider, and vice-versa. Moreover, headless spiders where s i is adjacent to exactly c i and c i+1 for all 1 ≤ i ≤ n are complete suns.

It is easy to see that for n = 2, the path P 4 equals the thin and thick headless spider, whereas the complete sun is not identifiable. For n = 3, the thin headless spider equals the net, and thick headless spider and complete sun its complement, the 3-sun. We consider headless spiders with n ≥ 4; Figure 2 illustrates all studied three families for n = 4. The partition (C, S) is called the spider partition and can be found in linear time [START_REF] Jamison | Recognizing P 4 -tidy graphs in linear time[END_REF]. 6

(b) (a) (c)

Thick headless spiders

For simplicity, we will denote thick headless spiders by their partition and we will consider that C = {1, . . . , n} and S = {n + 1, . . . , 2n}. Also, we denote by E a matrix with all entries at value one and recall that R q n stands for a q-rose of order n.

Lemma 2 For a thick headless spider G = (C ∪ S, E) with n ≥ 4, we have

C ID (G) =    R n-1 n I 0 R 2 n    .
Proof. Let G = (C ∪S, E) be a thick headless spider. The neighborhood matrix of G can be written as

N [G] =    E R n-1 n R n-1 n I    . Now, in order to find △[G]: (1) If i, j ∈ C, N [i] △ N [j] = {i + n, j + n}. (2) If i, j ∈ S, N [i] △ N [j] = [{i} ∪ (C -{i -n})] △ [{j} ∪ (C -{j -n})] = {i, j, i -n, j -
= i + n, N [i] △ N [j] = [C ∪ (S -{i + n})] △ [{j} ∪ (C -{j -n}) = {j -n} ∪ (S -{j, i + n}) is dominated by N[i]. (3.b) If i ∈ C and j = i + n ∈ S, N [i] △ N [j] = [C ∪ (S -{i + n})] △ [{j} ∪ (C -{j -n}) = [C ∪ (S -{i + n})] △ [{i + n} ∪ (C -{i}) = {i} ∪ S
and are dominated by a row of the case [START_REF] Argiroffo | On the set covering polyhedron of circulant matrices[END_REF].

As the first n rows of the matrix N [G] above are also dominated, we have that the clutter matrix C ID (G) can be written as

C ID (G) =    R n-1 n I 0 R 2 n    .

2

As an immediate consequence, we obtain: E) be a thick headless spider. Then:

Corollary 1 Let G = (C ∪ S,
• P ID (G) is full-dimensional. • The constraint x i ≥ 0 defines a facet of P ID (G) for each i ∈ C ∪ S. • All constraints from C ID (G) x ≥ 1 define facets of P ID (G). Observe that τ (I, I) = n. Then if G = (C ∪ S, E) is a thick headless spider, γ ID (G) ≥ n.
In fact, we have: E) be a thick headless spider. Then S is a minimum identifying code and, thus, γ ID (G) = n.

Corollary 2 Let G = (C ∪ S,
Proof. It is clear that every cover of C ID (G) must contain a subset of S having n -1 elements. Nevertheless no subset of S having n -1 elements covers the matrix C ID (G), but S does. Then, γ ID (G) = n. 2

In [START_REF] Argiroffo | On the set covering polyhedron of q-roses[END_REF], the set covering polyhedron

Q * (R q n ) = conv x ∈ Z n + : R q n x ≥ 1 of com- plete q-roses was studied. Theorem 2 ([5]) Let n ≥ q ≥ 2. An inequality ax ≥ 1 is a facet defining inequality for Q * (R q n ) if and only if ax ≥ 1 can be written as x(A s ) ≥ |A s |-q+1 for some A s ⊂ {1, . . . , n} where s ∈ {0, . . . , n -q -1} and |A s | = n -s. As R 2
n is a minor of C ID (G) obtained from the deletion of the nodes of C in the underlying graph G = (C ∪ S, E), we have: E) be a thick headless spider. Then, for all nonempty subsets A ⊂ S, the inequalities x(A) ≥ |A| -1 are facets of P ID (G).

Corollary 3 Let G = (C ∪ S,
In order to study the remaining facets of P ID (G) we need a description of the blocker of C ID (G).

From now on we consider vectors in {0, 1} l+k of the form e i ⊕ f j where e i for i = 1, . . . , l is the unit vector in {0, 1} l and f j for j = 1, . . . , k is a vector in {0, 1} k such that (f j ) t = 0 if j = t and (f j ) t = 1 if j = t.

Theorem 3 Let C ID (G) be the clutter matrix of a thick headless spider G = (C ∪ S, E). Every minimal cover x of C ID (G) is minimum. Moreover, either x = 0 ⊕ 1 where 0, 1 ∈ {0, 1} n or x = e i ⊕ f j where e i , f j ∈ {0, 1} n with i = j.
Proof. From Corollary 2, S is a minimum cover of C ID (G). Now, let x be a minimal cover of C ID (G) such that x j = 0 for some j ∈ {n + 1, . . . , 2n}. It is known that every row of R n-1 n covers (e i + e j ) for every i, j = 1, . . . , n [START_REF] Argiroffo | On the set covering polyhedron of q-roses[END_REF], then any cover x with x n+j = 0 for some j ∈ {n + 1, . . . , 2n} must be of the form x = y ⊕ f j with some y ∈ {0, 1} n . In order to cover the rows of submatrix (R n-1 n , I) it is enough to consider x i,j = e i ⊕ f j for i, j = 1, . . . , n and i = j. Then |x| = |x i,j | = n for every i, j = 1, . . . , n and i = j and they are all minimum covers. Now, let v be a cover of C ID (G), with v n+j = 0. Then v = y ⊕ f j and y ∈ {0, 1} n . But y must be a cover of R n-1 n , i.e., y = e i + h for some i = j and some h ∈ {0, 1} n . Then y is not minimal. 2 Now, we present some technical lemmas: Lemma 3 Let l ≥ k ≥ 2 and M be a matrix with l + k columns and rows

• 0 ⊕ 1 where 0 ∈ {0, 1} l and 1 ∈ {0, 1} k , • e 1 ⊕ f j , where e 1 ∈ {0, 1} l , f j ∈ {0, 1} k with j = 2, . . . , k, • e i ⊕ f 1 , where e i ∈ {0, 1} l , f 1 ∈ {0, 1} k and i = 2, . . . , l, • e l ⊕ f k Then M has rank l + k.
Proof. The proof follows from the fact that the l + k rows of matrix M are linearly independent. 2

As a consequence we can prove the following:

Corollary 4 Consider C ID (G) of a thick headless spider G = (C ∪ S, E). If x ∈ R 2n is an extreme point of Q(b(C ID (G))) such that x i = 0 for all i ∈ C ∪S then x = 1 n 1 ∈ R 2n .
Proof. From Theorem 3 it follows that every row of b(C ID (G)) is either 0 ⊕ 1 where 0, 1 ∈ {0, 1} n or e i ⊕ f j for i, j = 1, . . . Using blocking duality it can be seen that Corollary 4 gives an alternative proof of γ ID (G) = n and states that the only facet of P ID (G) with full support is the rank inequality associated with G.

In order to obtain the complete description of P ID (G), we need some further results. The proofs of the next two lemmas follow from straightforward computation of contraction of columns in matrices.

Lemma 4 Consider M = C ID (G) of a thick headless spider G = (C ∪ S, E) and let i ∈ C. Then M/i is a matrix with 2n -1 columns and whose rows are (1) e h ⊕ f i where f i ∈ {0, 1} n and e h ∈ {0, 1} n-1 for h = 1, . . . , n -1, h = i.

(2) 0 ⊕ f j where 0 ∈ {0, 1} n-1 and f j ∈ {0, 1} n for j = 1, . . . , n and j = i.

Lemma 5 Consider M = C ID (G) of a thick headless spider G = (C ∪ S, E) and let i ∈ S. Then M/i is a matrix with 2n -1 columns, having n -1 ones per row and whose rows are [START_REF] Argiroffo | On the set covering polyhedron of circulant matrices[END_REF] e i ⊕ f j where e i ∈ {0, 1} n and f j ∈ {0, 1} n-1 f orj = 1, . . . , n -1, (2) e h ⊕ f j where e h ∈ {0, 1} n and f j ∈ {0, 1} n-1 f orj = 1, . . . , n -1, j = h when i > h and j -1 = h when i < h, (3) 0 ⊕ 1 where 0 ∈ {0, 1} n and 1 ∈ {0, 1} n-1 .

Lemma 6 Let M be a matrix with 2n -1 columns and 2(n -1) rows such that the first n -1 rows are of the form e i ⊕ f 1 where e i ∈ {0, 1} n-1 for i = 1, . . . , n -1 and f 1 ∈ {0, 1} n and the remaining n -1 rows are 0 ⊕ f i where 0 ∈ {0, 1} n-1 and f i ∈ {0, 1} n for i = 2, . . . , n. Then every extreme point x ∈ Q(M ) having x l = 0 for some l = 1, . . . , n -1 is of the form x j = 1 for all j = 1, . . . , n and x j = 0 if j = n + 1, . . . , 2n -1.

Proof. Consider the system M x ≥ 1 with 2(n-1) rows. Adding a slack variable s i to each row i of the system, we get M x -Is = 1 where I is the identity matrix of size 2(n -1).

If x is an extreme point of Q(M ) then there must be a basic feasible solution associated with it, i.e., there must be a subdivision of (M, I) of the form (B, N ) where B is a regular submatrix of M of maximum rank. Also, if j is an index corresponding to a column in N then x j = 0.

It is easy to check that the rows of M are linearly independent, so the rank of B is 2(n -1). The total number of variables in M x -Is = 1 including the original variables and the slack variables is 2n -1 + 2(n -1), but 2(n -1) must be basic variables then there are at least 2n -1 variables at value zero. Then, there must be at least one index of a column in M , say j, such that xj = 0. Observe that for every i = 1 . . . , n -1 the variable x i and the slack s i appear in the system M x -Is = 1 only in row i, i.e., the columns corresponding to variables s i and x i are the same for all i = 1, . . . , n -1. Hence, for all i = 1, . . . , n -1 if x i is a basic variable then s i is a nonbasic variable.

From assumption xl > 0 we obtain s l = 0 and then it holds that xl + i=1,...,n-1 xn+i = 1. If i=1,...,n-1 xn+i = 0 then xi = 1 for all i = 1, . . . , n and the lemma follows.

Assume that i=1,...,n-1 xn+i = t > 0. Then xi = 1t + s i = xl + s i > 0 for all i = 1, . . . , n with i = l. Then x i with i = 1, . . . , n -1 are all basic variables and consequently s i are nonbasic for i = 1, . . . , n -1. Now, consider the last n -1 equalities of M x -Is = 1. They are: xn + i=1,...,n-1 i =k xn+is n-1+k = 1 for all k = 1 . . . , n -1.

Then it holds that xn = 1t + xn+k + s n-1+k for all k = 1 . . . , n -1.

So, xn > 0 and then x i is basic for i = 1, . . . , n. Remind that xj = 0 for some j ∈ {1, . . . , 2n -1} then n + 1 ≤ j ≤ 2n -1. But, xn = 1t + xn+j + s n-1+j and if s n-1+j > 0 then one of xn+k and s n-1+k must be positive for every k = 1 . . . , n-1. This implies that we have n-1 more basic variables, contradicting the fact that they are 2(n -1).

Then the basic solution of M x-Is = 1 corresponds to xj = 1 for j = 1, . . . , n, s j = 0 for j = 1, . . . , 2(n -1) and xj = 0 if j = n + 1, . . . , 2n -1. 2 Now, we can further show: It is clear that x ∈ Q(b(C ID (G)))∩{x i = 0 : i ∈ A}. Then x can be partitioned into (x A , x Ā) where Ā is the complement of A in {1, . . . , 2n}. In order to ease notation let us call ȳ = x Ā ∈ R n-|A| . Then it holds that ȳ is an extreme point of Q(b(C ID (G))/A) with all components different from zero. Now, let A be such that i ∈ A and j / ∈ A with {i, j} ⊂ {1, . . . , n}. W.l.o.g. we may assume that i = 1. Then, by Lemma 4 we can see that matrix b(C ID (G))/i is of the form of matrix M in Lemma 6 with 2(n -2) rows and 2n -1 columns. Then using Lemma 6, the extreme point ȳ ∈ {0, 1} 2n-|A| contradicting the fact that x is a fractional extreme point. Hence if i ∈ A for some i ∈ {1, . . . , n} then C ⊂ A. In this case the rows of matrix b(C ID (G)/A) are of the form f i ∈ {0, 1} 2n-|A| for every i = 1, . . . , 2n -|A|. Then the only possible solution is ȳi =

(C) + x(S ′ ) ≥ n -|S -S ′ | when 2 ≤ |S ′ | ≤ n -1 and x(S ′ ) ≥ |S ′ | -1 when 2 ≤ |S ′ | ≤ n are facets of P ID (G).
As a consequence of Corollary 5 and Theorem 4, we obtain the main result of this section: E) be a thick headless spider. Then, the facets of P ID (G) are

Corollary 6 Let G = (C ∪ S,
• the constraint x i ≥ 0 for all i ∈ C ∪ S, • the constraints C ID (G) x ≥ 1, • the constraints x(C) + x(S ′ ) ≥ n -|S -S ′ | and x(S ′ ) ≥ |S ′ | -1 for every S ′ ⊆ S with 2 ≤ |S ′ |.

Thin headless spiders

Lemma 7 For a thin headless spider G = (C ∪ S, E) with n ≥ 4, we have

C ID (G) =        I I 0 R 2 n R n-1 n 0        .
Proof. Let G = (C ∪ S, E) be a thin headless spider with C = {1, . . . , n} and S = {n + 1, . . . , 2n}. The neighborhood matrix of (C, S) can be written as

N [G] =    E I I I    .

Now, in order to find △[G]:

(1

) If i, j ∈ C, N [i] △ N [j] = {i + n, j + n}.
(

) If i, j ∈ S, N [i] △ N [j] = {i, i -n} △ {j, j -n} and are dominated by N [i]. (3.a) If i ∈ C and j ∈ S, j = i + n, N [i] △ N [j] = [C ∪ {i + n})] △ {j, j -n} = {j, i + n} ∪ (C -{j -n}) is dominated by N [i]. (3.b) If i ∈ C and j = i + n ∈ S, N [i] △ N [j] = [C ∪ {i + n})] △ [{i, i + n} = C -{i}. 2
As the first n rows of the matrix N above are also dominated, we have that the clutter matrix C ID (G) can be written as claimed. 2

Corollary 7 Let G = (C ∪ S, E) be a thin headless spider. Then we have:

• P ID (G) is full-dimensional. • The constraint x i ≥ 0 defines a facet of P ID (G) for all i ∈ C ∪ S. • All constraints from C ID (G) x ≥ 1 define facets of P ID (G).
In [START_REF] Sassano | On the facial structure of the set covering polytope[END_REF], it is proved that τ

(R 2 n ) = n -1. Then if G = (C ∪ S, E) is a thin headless spider, γ ID (G) ≥ n -1.
In fact, we have:

Corollary 8 Let G = (C ∪ S, E) be a thin headless spider. Then, γ ID (G) = n + 1.
Proof. Let G = (C ∪ S, E) be a thin headless spider with C = {1, . . . , n} and

S = {n + 1, . . . , 2n}. It is immediate to observe that γ ID (G) ≥ τ (R n-1 n ) + τ (R 2 n ) = 2 + n -1 = n + 1. In addition, if T = {1,

Proof. As R 2

n is a minor of C ID (G) obtained after deletion of the nodes in C, as a consequence of Theorem 2 we have that the inequalities x(A) ≥ |A| -1 for all nonempty subsets A ⊂ S are facets of P ID (G). Also, R n-1 n is a minor of C ID (G) obtained after deletion of the nodes in S, and again using Theorem 2 we obtain x(C) ≥ 2 as a facet of P ID (G). 2

In [START_REF] Argiroffo | Study of identifying code polyhedra for some families of split graphs[END_REF], it was conjectured that there are no further facets necessary to entirely describe the identifying code polyhedron of thin headless spiders. In the remaining part of this section, we present the proof of this conjecture.

As an immediate observation, the rank inequality x(C ∪ S) ≥ n + 1 is not a facet of P ID (G) since it can be obtained as the sum of the facets x(S) ≥ n -1 and x(C) ≥ 2.

Theorem 5 Let C ID (G) be the clutter matrix of a thin headless spider G = (C ∪ S, E). Every minimal cover x of C ID (G)) is minimum. Moreover, x = (e i + e j ) ⊕ f j where e i , f j ∈ {0, 1} n with i = j.

Proof. Let x be a minimal cover of C ID (G)). It is clear that x = v ⊕ u where v ∈ {0, 1} n covers the rows of matrix R n-1 n and u ∈ {0, 1} n covers the rows of R 2 n . Hence v = e i + e j with i, j ∈ {1, . . . , n} and i = j and u = f l with l ∈ {1, . . . , n}. Also, x must cover the first n rows of matrix C ID (G)), then if x = v ⊕ u with v = e i + e j then either u = f i or u = f j . Then |x| = n + 1 for every i, j = 1, . . . , n and i = j and they are all minimum covers. 2

In order to identify the complete description of P ID (G) when G = (C ∪S, E) is a thin headless spider, we use blocking duality again. Consider the polyhedron

Q(b(C ID (G))).
As a consequence of the previous theorem all the rows in matrix b(C ID (G)) have n + 1 ones, then the point x =

1 1 n+1 ∈ Q(b(C ID (G))). But x cannot be an extreme point of Q(b(C ID (G)
)) since we have already mentioned that the rank inequality x(C ∪ S) ≥ n + 1 is not a facet of P ID (G). So, every fractional extreme point of Q(b(C ID (G))) must have some of its components at value zero. From Corollary 9 we know that the point x of the form x i = 1 2 for all i ∈ C and x i = 0 for all i ∈ S is an extreme point as well as all the points of the form x i = 1 |A|-1 for all i ∈ A ⊂ S with A nonempty and x i = 0 for i / ∈ A. The following results show that these are the only fractional extreme points of Q(b(C ID (G))).

Lemma 8 Let M be the n × 2n matrix whose rows are the characteristic vectors of e i ⊕f i for i ∈ {1, . . . , n} and e i , f i ∈ {0, 1} n for every i ∈ {1, . . . , n}.

Let x ∈ Q(M ) such that xl = 0 for some l ∈ {1, . . . , n}. If x is an extreme point of Q(M ) then x ∈ {0, 1} 2n .
Proof. It is easy to check that the nontrivial inequalities describing Q(M ) are

x i + k=1,...,n;k =i x n+k ≥ 1 for all i = 1, . . . , n.
After adding the slack variables to the inequalities above we obtain

x i + k=1,...,n;k =i x n+k -s i = 1 for all i = 1, . . . , n.
For every i = 1, . . . , n it holds that variable x i is basic if and only if variable s i is nonbasic, since their respective columns are the same. By assumption there is l ∈ {1, . . . , n} such that xl > 0, then s l = 0 and xl = 1-k=1,...,n;k =l xn+k . If xi > 0 for all i ∈ {1, . . . , n} then all basic variables are x i with i ∈ {1, . . . , n}. Then xn+i = 0 for i ∈ {1, . . . , n} and x1 = 1 for i ∈ {1, . . . , n} and the lemma follows.

Observe that there is i ∈ {1, . . . , n} such that xn+i = 0, otherwise variables x n+i with i = 1, . . . , n are basic contradicting the fact that x l > 0 for some l ∈ {0, . . . , n}. So, let I = {i : 1 ≤ i ≤ n and xi = 0}. By assumption I = {1, . . . , n} and consider I nonempty. Recall that xl > 0 and xl + k=1,...,n;k =l xn+k = 1. Let i ∈ I then k=1,...,n;k =i xn+ks i = 1. Thus x n+lx lx n+i = s i and then x n+l ≥ x l > 0. Therefore, if x is an extreme point then x i , x i+n is a pair of basic variables for every i / ∈ I. Since there are n basic variables, then n -|I| ≤ n 2 .

W.l.o.g assume that I = {1, . . . , l} with l ≤ n 2 . If xn+i > 0 for some i ∈ I then variable s i is nonbasic, since adding the columns corresponding to the variables x n and x 2n yields the sum of columns corresponding to the variables s i and x n+i . Let us call J = {i ∈ I : xn+i = 0}.

Again, we can assume that J = {1, . . . , m} with m < l ≤ n 2 . Hence we have It holds that for every j ∈ J, s j > 0 follows and is thus basic. But, we have that for every i = 1 . . . , n either x n+i > 0 and is thus basic or s i > 0 and is thus basic. These variables together with every x i with i / ∈ I make more than n positive variables. It follows that x is not an extreme point. 2 x n+k ≥ 1 for all i = 2, . . . , n.

Consider the system of equalities obtained after adding the slack variables to the inequalities above as follows:

x i + k=2,...,n
x n+ks i = 1 for all i = 2, . . . , n and x i + k=1,...,n;k =i x n+ks n+i-1 = 1 for all i = 2, . . . , n.

So we have 2n -2 basic variables and 2n -1 nonbasic variables. Suppose that xi > 0 for every i ∈ 2, . . . , n, then xn+i > 0 for i ∈ 1, . . . , n. This implies that variables x i for every i ∈ {2, . . . , n} and x n+i for i ∈ {1, . . . , n} are basic variables, a contradiction.

There must be some l ∈ {2, . . . , n} such that x l = 0. Therefore, our set of basic variables includes variables x i for every i such that xi > 0 and every Observe that one between s l and s l+n-1 must be nonbasic, since x l is a basic variable. It follows that s l+n-1 > 0 and s l = 0. Also xl + k=2,...,m xn+k = 1. So we have that for every j / ∈ I, s j+n-1 is a basic variable. Now, let i ∈ I it holds that k=2,...,m xn+ks j = 1.

But as we have already seen k=2,...,m xn+k < 1 and hence s j > 0 for all j ∈ I. So we have 2n basic variables which is a contradiction. 2

In summary, we obtain the main result of this section:

Corollary 10 Let G = (C ∪ S, E) be a thin headless spider. Then, the facets of P ID (G) are

• the constraint x i ≥ 0 for all i ∈ C ∪ S; • all constraints from C ID (G) x ≥ 1; • the constraint x(C) ≥ 2;
• the constraints x(A) ≥ |A| -1 for all nonempty subsets A ⊂ S.

Case 1: the symmetric differences between two nodes in C have the form

• N [c i ] △ N [c i+1 ] = {s i-1 , s i+1 }; • N [c i ] △ N [c i+j ] = {s i-1 , s i , s i+j-1 , s i+j } for 1 < j ≤ n 2 .
For all n ≥ 4, the former symmetric differences remain in C ID (G) as submatrix

( 0 | C 1+1 n ) ∀n ≥ 5
(but yield for n = 4 not the whole circulant matrix). The latter symmetric differences are dominated by the former if j = 2, 3. Thus, for each 4 ≤ j ≤ n 2 , the symmetric differences

N [c i ] △ N [c i+j ] remain in C ID (G) as submatrix ( 0 | C 2+2 n ) ∀n ≥ 9
(but yield for j = n 2 not the whole circulant matrix).

Case 2: the symmetric differences between nodes in C and S have the form Case 3: the symmetric differences between two nodes in S have the form

• N [c i ] △ N [s i ] = (C -{c i-1 , c i }) ∪ {s i-1 }; • N [c i ] △ N [s i-1 ] = (C -{c i-2 , c i-1 }) ∪ {s i }; • N [c i ] △ N [s j ] = (C -{c j-1 , c j }) ∪ {s i-1 , s i } for j = i, i -1. Thus, N [c i ]△N [s j ] is dominated by N [s i ] if j = i, i-1,
• N [s i ] △ N [s i+1 ] = {c i , c i+2 , } ∪ {s i , s i+1 }; • N [s i ] △ N [s j ] = {c i , c i+1 , c j , c j+1 } ∪ {s i , s j } for j = i. Thus, N [s i ] △ N [s j ] is dominated by N [s i ] if j = i + 1, and remains in C ID (G) for j = i + 1, forming a submatrix of the form ( C 1+1 n | C 2 n ) ∀n ≥ 4.
This together completely describes the identifying code clutter C ID (G). 2

Corollary 11 Let G = (C ∪ S, E) be a complete sun with n ≥ 4.

• P ID (G) is full-dimensional. • The constraint x v ≥ 0 defines a facet of P ID (G) for each v ∈ C ∪ S. • All constraints from C ID (G) x ≥ 1 define facets of P ID (G).
Unfortunately, the whole system of facet-defining inequalities for the identifying code polyhedra P ID (G) of complete suns is not easy to describe since non-rank facets are required for all cases n ≥ 4 (in fact, most facets of P ID (G) are non-rank and involve large coefficients). However, from a careful analysis of the constraints involved in the identifying code clutter C ID (G) of complete suns, we derive at the following conjecture:

Conjecture 1 For a complete sun G = (C ∪ S, E) with n ≥ 4, the stable set S is a minimum identifying code.

Note that it is easy to see that S is always an identifying code for a complete sun G = (C ∪ S, E), since all rows of C ID (G) have at least one 1-entry in S.

Hence, γ ID (G) ≤ |S| = n follows. On the other hand, for some cases, it has been already verified that S is a minimum identifying code, by generating the full rank constraint x(C) + x(S) ≥ |S| = n by means of the Chátal-Gomory procedure. This implies γ ID (G) ≥ |S| = n, and together equality follows for these cases. Our goal is to find a general construction of this type for all n ≥ 4.

Concluding remarks

The identifying code problem is hard in general and challenging both from a theoretical and a computational point of view, even for special graphs like split graphs [START_REF] Foucaud | The complexity of the identifying code problem in restricted graph classes[END_REF]. Hence, a typical line of attack for this problem is to determine minimum identifying codes of special graphs, or to provide lower and upper bounds.

In this paper, we studied three families of split graphs with |S| = |C| ≥ 2 having a regular structure: thin headless spiders, thick headless spiders, and complete suns. For all three families, we determined the identifying code clutter and discussed according consequences.

In the case of thin and thick spiders G, C ID (G) is composed from certain q-roses. Based on related results from [START_REF] Argiroffo | On the set covering polyhedron of q-roses[END_REF][START_REF] Sassano | On the facial structure of the set covering polytope[END_REF], we could give the complete description of P ID (G) for thick and thin spiders. As a consequence for both classes, we found the exact value for γ ID (G): |S| for thick spiders and |S| + 1 for thin spiders. Moreover, the complete descriptions of P ID (G) also allow us to compute minimum weight identifying codes of thin and thick spiders for all possible node weights.

It turned out that the identifying code clutters of complete suns have a more complex structure involving different circulant matrices and, accordingly, more involved facets are required to describe P ID (G). For this class, we showed γ ID (G) ≤ |S| and conjecture that γ ID (G) = |S| holds, too. So, all three families seem to have small minimum identifying codes close to the lower bound of order log(|S| + |C|).

This demonstrates how the polyhedral approach can be applied to find identifying codes of minimum size for special graphs G, just by determining and analyzing the identifying code clutter C ID (G), even in cases where no complete description of P ID (G) is known yet.

As future lines of research, we plan to apply similar and more advanced techniques to obtain either the identifying code of minimum size or strong lower bounds stemming from linear relaxations of the identifying code polyhedron, enhanced by suitable cutting planes. For that, note that facets associated with deletion minors of C ID (G) remain facets in P ID (G), so according facets identified for special graphs are relevant for every graph having such subgraphs.

Fig. 2 .

 2 Fig. 2. (a) thin headless spider, (b) complete sun, (c) thick headless spider.

  n} and are dominated by a row of the case (1). (3.a) If i ∈ C and j ∈ S, j

  , n and i = j. Then they all have n ones per row. By Lemma 3 there are 2n linearly independent rows in b(C ID (G)). It follows that if x = 1 n 1 ∈ R n then it satisfies b(C ID (G))x = 1. Hence x is a fractional extreme point of Q(b(C ID (G))). Now, if ȳ is an extreme point of Q(b(C ID (G))) with all nonzero components then it must satisfy 2n linearly independent inequalities of Q(b(C ID (G))) at equality having n ones per row. It follows that ȳ = x. 2

Theorem 4

 4 Let b(C ID (G)) be the blocker of the identifying code clutter matrix of a thick headless spider G = (C ∪ S, E). Let x ∈ R 2n be a fractional extreme point of Q(b(C ID (G))) such that the set A = {i : xi = 0} is nonempty. Then either (1) A S and xi = 1 n-|A| when i / ∈ A or (2) C A and |A| ≤ 2(n -1) and xi = 1 2n-|A|-1 for all i / ∈ A. Proof. Let x be a fractional extreme point of Q(b(C ID (G))) and let A = {i : x i = 0} with A a nonempty set.

First consider A ⊂ S = {n + 1 ,

 1 . . . , 2n}. If n -|A| = 1, it is easy to check that matrix b(C ID (G)/A) is the n × n identity matrix. Then ȳ ∈ {0, 1} n+1 contradicting the fact that x is a fractional extreme point. If n -|A| ≥ 2 we can iteratively apply Lemma 5 and then we get a matrix b(C ID (G)/A) whose rows all have n -|A| ones and using Lemma 3 it holds that there are n + n -|A| linearly independent rows of b(C ID (G))/A with n -|A| ones per row. Then if ȳ is an extreme point of Q(b(C ID (G))/A) with all nonzero components then ȳ = 1 n-|A| 1.

1 2n-

 1 |A|-1 for all i = 1, . . . , 2n -|A|. 2 As a consequence of Theorem 4 and blocking duality, we conclude: Corollary 5 Let G = (C ∪ S, E) be a thick headless spider and S ′ ⊂ S nonempty. Then, the inequalities x

2 , 2 +

 22 n, 3 + n, . . . , 2n} then x T satisfies C ID (G)x T ≥ 1 and |T | = n + 1, we conclude γ ID (G) = n + 1. 2 Moreover, we obtain: Corollary 9 Let G = (C ∪ S, E) be a thin headless spider. Then, (1) the inequalities x(A) ≥ |A| -1 for all nonempty subsets A ⊂ S are facets of P ID (G), (2) the inequality x(C) ≥ 2 is a facet of P ID (G).

  k=m+1,...,n xn+ks i = 1 for all i = 1, . . . , m and k=m+1,...,n;k =i xn+k = 1 for all i = m + 1, . . . , l.

Lemma 9

 9 Let x ∈ Q(b(C ID (G))) such that xl = 0 and xj = 0 for l, j ∈ {1, . . . , n}. If x is an extreme point of Q(b(C ID (G))) then x ∈ {0, 1} 2n . Proof. W.l.o.g. assume j = 1 and consider an extreme point x of Q(b(C ID (G))) with x1 = 0 and xl > 0. If xn+1 = 0 we can study the extreme points ofQ(b(C ID (G))) ∩ {x ∈ R 2n : x 1 = x n+1 = 0}. It is easy to see that the matrix b(C ID (G))/1, n + 1 corresponds to a n -1 × 2(n -1)matrix whose rows are the characteristic vectors of e i ⊕ f i for i ∈ {1, . . . , n -1} and e i , f i ∈ {0, 1} n for every i ∈ {1, . . . , n -1}. Hence the result follows from Lemma 8. Now, assume that xn+1 > 0. Moreover, we assume that any time if xi = 0 then xn+i > 0. Observe that the rows of matrix b(C ID (G))/1 correspond to the characteristic vectors of e i ⊕ f 1 and e i ⊕ f i+1 for i ∈ {1, . . . , n -1} where e i ∈ {0, 1} n-1 and f i ∈ {0, 1} n . So the inequalities describing Q(b(C ID (G))/1) are x i + k=2,...,nx n+k ≥ 1 for all i = 2, . . . , n andx i + k=1,...,n;k =i

  x n+i for wich xi = 0. These are n basic variables. W.l.o.g assume I = {1, . . . , m} such that xi = 0 when i ∈ I and xi > 0 otherwise. Then let l / ∈ I. Then xl + k=2,...,m xn+ks l = 1, but also xl + k=1,...,m xn+ks l+n-1 = 1.

  and remains in C ID (G) for j = i, i -1, forming two submatrices of the form (

  E) is a split graph if its node set can be partitioned into a clique C and a stable set S. Hence, split graphs are closed under taking complements by definition.Moreover, split graphs form the complementary core of chordal graphs (graphs without chordless cycles of length ≥ 4) since G is a split graph if and only if G and G are chordal[START_REF] Földes | Split graphs[END_REF]. This is also reflected in terms of forbidden subgraphs since a graph is a split graph if and only if it is (C 4 , C 4 , C 5 )-free[START_REF] Földes | Split graphs[END_REF] (note that C 5 is self-complementary and that C 4 occurs as induced subgraph in any chordless cycle C k with k ≥ 6 such that all chordless cycles C k with k ≥ 4 are excluded in G as well as in G).Moreover, a split graph is connected if and only if no node in S is isolated. Every non-connected split graph G contains a connected split graph G ′ and a non-empty subset S ′ ⊂ S of isolated nodes, and clearly γ ID

	The relation between chordal and split graphs
	can also be interpreted in terms of intersection graphs: while chordal graphs
	are the intersection graphs of distinct subtrees of a tree, split graphs are the
	intersection graphs of distinct substars of a star, see e.g. [8].
	Our aim is to study identifying codes in split graphs from a polyhedral point
	of view. First note that a split graph is identifiable if and only if no two nodes
	in C have the same neighbors in S. For instance, a complete split graph (i.e.,
	a split graph where all edges between C and S are present) is not identifiable
	as soon as C contains 2 nodes (as any two nodes in C are true twins). For
	instance, crowns (the complete split graphs with |C| = 2) are not identifiable.
	Next, recall that finding a minimum identifying code in split graphs is NP-hard
	[11]. So far, γ ID (G) is only known for two families: on the one hand, stars (the
	complete split graphs G = (C ∪ S, E) with |C| = 1) are the only identifiable
	complete split graphs and have γ ID (G) = |S|; on the other hand, split graphs
	G = (C ∪ S, E) where every node in S is connected to a distinct 2-node subset
	of C have γ ID (G) of order log(|S| + |C|), see [11]. The two families show the
	wide range of the possible size of minimum identifying codes in split graphs:
	while the lowest possible lower bound of log n is attained for the latter, stars
	achieve almost the highest possible value n.

Acknowledgement. This work was supported by an ECOS-MINCyT cooperation France-Argentina, A12E01.

Complete suns

As third family of headless spiders G = (C ∪ S, E) having a regular structure, we consider complete suns, where S = {s 1 , . . . , s n }, C = {c 1 , . . . , c n } and s i is adjacent to exactly c i and c i+1 for all 1 ≤ i ≤ n (indices are taken modulo n).

In contrary to thin and thick headless spiders whose identifying code clutters are composed by few q-roses, the identifying code clutters of complete suns have a more complex structure, involving different combinations of submatrices with a circular structure, where some submatrices occur for all n ≥ 4, others not (depending on the parity of n and the size of the graph).

A circulant matrix is a square matrix where each row vector is shifted one element to the right relative to the preceding row vector. We denote by C k n a circulant matrix in {0, 1} n×n having as first row the vector starting with k 1entries and having 0-entries otherwise. Moreover, we denote by C k+k n a matrix in {0, 1} n×n with n ≥ 2k + 2 having as first row the vector starting with k 1-entries, then having at least two 0-entries, again k 1-entries, and 0-entries otherwise (at least two again).

Lemma 10 For a complete sun G = (C ∪ S, E) with n ≥ 4, the identifying code clutter C ID (G) is composed by the following submatrices

) ∀n ≥ 8, n even

where the first part refers to C, the second part of the matrices to S.

Proof. Let G = (C ∪ S, E) be a complete sun. The neighborhood matrix N [G] of (C, S) is composed by

Thus, only N [S] is in C ID (G). To find △[G], we distinguish three cases.