DIKUL - logo
(UL)
PDF
  • On the complexity of the identifiable subgraph problem, revisited
    Kratsch, Stefan, 1983- ; Milanič, Martin, 1980-
    A bipartite graph ▫$G = (L, R; E)$▫ with at least one edge is said to be identifiable if for every vertex ▫$v \in L$▫, the subgraph induced by its non-neighbors has a matching of cardinality ▫$| L | ... - 1$▫. An ▫$\ell$▫ -subgraph of ▫$G$▫ is an induced subgraph of ▫$G$▫ obtained by deleting from it some vertices in ▫$L$▫ together with all their neighbors. The identifiable subgraph problem is the problem of determining whether a given bipartite graph contains an identifiable ▫$\ell$▫-subgraph. The min- and max-identifiable subgraph problems are defined similarly, taking into account a given upper, resp. lower bound on the number of vertices from ▫$L$▫ in an identifiable ▫$\ell$▫-subgraph. We show that the identifiable subgraph and max-Identifiable subgraph problems are polynomially solvable, thereby answering the question about the complexity of these two problems posed by E. Fritzilas et al. in 2013. We also complement a known APX-hardness result for the min-Identifiable subgraph problem by showing that two parameterized variants of the problem are W[1]-hard.
    Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 226, 2017, str. 78-86)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2017
    Jezik - angleški
    COBISS.SI-ID - 18075993

    Povezava(-e):

    http://doi.org/10.1016/j.dam.2017.04.028
    DOI

vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 226, 2017, str. 78-86)

loading ...
loading ...
loading ...

Vnos na polico