Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBazgan, Cristina*
hal.structure.identifierLaboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes [LIMOS]
dc.contributor.authorFoucaud, Florent
HAL ID: 169708
*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
*
dc.date.accessioned2019-04-05T13:59:16Z
dc.date.available2019-04-05T13:59:16Z
dc.date.issued2019
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18610
dc.language.isoenen
dc.subjectVC dimension
dc.subjectDistinguishing Transversal
dc.subjectPartial problems
dc.subjectHypergraphs
dc.subjectParameterized complexity
dc.subjectApproximation complexity
dc.subject.ddc003en
dc.titleParameterized and approximation complexity of Partial VC Dimension
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe introduce the problem Partial VC Dimension that asks, given a hypergraph H = (X, E)and integers k and ℓ, whether one can select a set C⊆X of k vertices of H such that the set {e∩C, e∈E} of distinct hyperedge-intersections with C has size at least ℓ. The sets e∩ C define equivalence classes over E. Partial VC Dimension is a generalization of VC Dimension, which corresponds to the case ℓ= 2k, and of Distinguishing Transversal, which corresponds to the case ℓ=|E|(the latter is also known as Test Cover in the dual hypergraph). We also introduce the associated fixed-cardinality maximization problem Max Partial VC Dimension that aims at maximizing the number of equivalence classes induced by a solution set of k vertices. We study the algorithmic complexity of Partial VC Dimension and Max Partial VC Dimension both on general hypergraphs and on more restricted instances, in particular, neighborhood hypergraphs of graphs.
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol766
dc.relation.isversionofjnldate2019
dc.relation.isversionofjnlpages1-15
dc.relation.isversionofdoi10.1016/j.tcs.2018.09.013
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2019-12-10T01:13:46Z
hal.identifierhal-02091342*
hal.version1*
hal.update.actionupdateFiles*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record