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


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


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


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.


  signature loans . On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis Sale was obtained in Europe, Australia, New Zealand.