## Invited Session Fri.2.H 3004

#### Friday, 13:15 - 14:45 h, Room: H 3004

**Cluster 2: Combinatorial optimization** [...]

### Packing, covering and domination I

**Chair: Annegret K. Wagler**

**Friday, 13:15 - 13:40 h, Room: H 3004, Talk 1**

**Annegret K. Wagler**

Generalized row family inequalities for the set covering polyhedron

**Coauthor: Gabriela R. Argiroffo**

**Abstract:**

Set packing and set covering are dual concepts in combinatorial optimization. The associated polyhedra, the set covering polyhedron SCP and the set packing polyhedron SPP, turned out to have strong similarities. Many classical concepts have been transferred from SPP to SCP, see, e.g., Balas & Ng (1989), CornuĂ©jols & Sassano (1989), Nobili & Sassano (1989) and Sassano (1989).

Recently, row family inequalities have been introduced for SCP by Argiroffo & Bianchi (2010) as a counterpart of clique family

inequalities for SPP. While clique family inequalities are valid for SPP in general by Oriolo (2004), row family inequalities are valid for SCP only under certain conditions, but several known cases of facets for SCP fall into this class, see Argiroffo & Bianchi (2010).

We extend the class of row family inequalities for SCP, along a generalized concept for clique family inequalities by PĂȘcher & Wagler (2006) for SPP. We show that generalized row family inequalities provide a large class of constraints being valid for SCP in general, and discuss its potential for strengthening linear relaxations of SCP and describing SCP in terms of facet-defining inequalities.

**Friday, 13:45 - 14:10 h, Room: H 3004, Talk 2**

**Gabriela Argiroffo**

The identifying code polyhedron of cycles

**Coauthors: Silvia Bianchi, Annegret Wagler**

**Abstract:**

A subset *C* of vertices of a graph *G* is an identifying code of *G* if *C* intersects the closed neighbourhood

of the vertices of *G* in different sets. The problem of finding minimum identifying codes arises from natural applications

(fault detection in networks, fire detection and group tests, for example) and its study was introduced by Karpovsky, Chakrabarty and Levitin (1998).

We define the identifying code polyhedron of *G* as the convex hull of the integer solutions of *M(G)x ≥ 1*, where *M(G)*

is the matrix whose rows are the incidence vectors of the closed neighborhood of the vertices of *G* and their symmetric differences.

In this work we present some results on the polyhedral structure of the identifying code polyhedron of a graph. In particular,

this approach allows us to find a lower bound for the minimum cardinality of an identifying code of a graph that is tight for

even paths and even cycles.

We identify valid inequalities for the identifying code polyhedron of an arbitrary graph *G*. Finally, we study the

identifying code polyhedron of cycles. In particular we identify their *{0,1,2}* facet defining inequalities.

**Friday, 14:15 - 14:40 h, Room: H 3004, Talk 3**

**Petru Valicov**

Complexity of identifying codes in some subclasses of perfect graphs

**Coauthors: Florent Foucaud, Sylvain Gravier, Reza Naserasr, Aline Parreau**

**Abstract:**

An identifying code *C* of a graph *G=(V,E)* is a subset of vertices of *G* such that it is a dominating set and every vertex of *G* is identified within *C*. Formally speaking, let *N[x]* be the closed neighbourhood of a vertex *x* then *∀ x ∈ V, N[x]∩ C ≠ ∅* and *∀ u,v ∈ V, N[u]∩ C ≠ N[v]∩ C*. The concept of identifying codes was introduced by Karpovsky et al. in 1998 and since then became a well-studied one.

Determining the size of a minimum identifying code of a graph *G* (denoted * γ *^{ID}) was previously proved to be NP-complete even for restricted classes of graphs. We prove that the edge-identifying code problem i.e. identifying code problem in line graphs) is NP-complete even for the class of planar bipartite graphs of maximum degree 3 and arbitrarily large girth while the problem can be solved in linear time for graphs of bounded tree-width. As a corollary of this result we derive that the identifying code problem is NP-complete in a restricted subclass of perfect planar graphs. Moreover, for another family of perfect graphs - split graphs, the problem of computing the size of a minimum identifying code remains NP-complete.