Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung
hal.structure.identifier
dc.contributor.authorSerna, Maria
hal.structure.identifier
dc.contributor.authorThilikos, Dimitrios M.
HAL ID: 178742
ORCID: 0000-0003-0470-1800
dc.date.accessioned2020-09-29T15:24:31Z
dc.date.available2020-09-29T15:24:31Z
dc.date.issued2018
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/21011
dc.language.isoenen
dc.subjectParameterized countingen
dc.subjectCompactoren
dc.subjectProtrusion decompositionen
dc.subject.ddc005en
dc.titleData-Compression for Parametrized Counting Problems on Sparse Graphsen
dc.typeCommunication / Conférence
dc.description.abstractenWe study the concept of compactor, which may be seen as a counting-analogue of kernelization incounting parameterized complexity. For a function F : Σ∗ → N and a parameterization κ : Σ∗ →N, a compactor (P, M) consists of a polynomial-time computable function P, called condenser, anda computable function M, called extractor, such that F = M◦P, and the condensing P(x) of x haslength at most s(κ(x)), for any input x ∈ Σ∗. If s is a polynomial function, then the compactoris said to be of polynomial-size. Although the study on counting-analogue of kernelization isnot unprecedented, it has received little attention so far. We study a family of vertex-certifiedcounting problems on graphs that are MSOL-expressible; that is, for an MSOL-formula φ withone free set variable to be interpreted as a vertex subset, we want to count all A ⊆ V (G)where |A| = k and (G, A) |= φ. In this paper, we prove that every vertex-certified countingproblems on graphs that is MSOL-expressible and treewidth modulable, when parameterized byk, admits a polynomial-size compactor on H-topological-minor-free graphs with condensing timeO(k2n2) and decoding time 2O(k). This implies the existence of an FPT-algorithm of running timeO(n2k2) + 2O(k). All aforementioned complexities are under the Uniform Cost Measure (UCM)model where numbers can be stored in constant space and arithmetic operations can be done inconstant time.en
dc.identifier.citationpages20:1-20:13en
dc.relation.ispartoftitleISAAC: International Symposium on Algorithms and Computationen
dc.relation.ispartofeditorWen-Lian, Hsu
dc.relation.ispartofeditorDer-Tsai, Lee
dc.relation.ispartofeditorChung-Shou, Liao
dc.relation.ispartofpublnameSchloss Dagstuhl--Leibniz-Zentrum fuer Informatiken
dc.relation.ispartofpages20:1--20:13en
dc.identifier.urlsitehttps://hal-lirmm.ccsd.cnrs.fr/lirmm-02342803en
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-3-95977-094-1en
dc.relation.conftitle29th International Symposium on Algorithms and Computation, ISAAC 2018en
dc.relation.confdate2018-12
dc.relation.confcityJiaoxi, Yilan Countyen
dc.relation.confcountry"Taiwanen
dc.relation.forthcomingnonen
dc.identifier.doi10.4230/LIPIcs.ISAAC.2018.20en
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2020-09-25T13:04:55Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record