On the complexity of the identifiable subgraph problem, revisited

DOI10.1016/J.DAM.2017.04.028MaRDI QIDQ2357777zbMATH OpenOpenAlexFDO

Authors Stefan Kratsch, Martin Milanič

Publication date 14 June 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.06226

zbMATH Keywords

\(\mathsf{W} [1\)-hardness]bipartite graphcomputational complexityidentifiable graphmatchingpolynomial time algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: A bipartite graph $G=(L,R;E)$ with at least one edge is said to be identifiable if for every vertex $vinL$, 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. We show that the Identifiable Subgraph problem is polynomially solvable, along with the version of the problem in which the task is to delete as few vertices from $L$ as possible together with all their neighbors so that the resulting $ell$-subgraph is identifiable. We also complement a known APX-hardness result for the complementary problem in which the task is to minimize the number of remaining vertices in $L$, by showing that two parameterized variants of the problem are W[1]-hard.

Recommendations

• On the complexity of the identifiable subgraph problem
• Resilience and optimization of identifiable bipartite graphs
• The complexity of the identifying code problem in restricted graph classes
• More results on the complexity of identifying problems in graphs
• The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs

Cites work

• Blockers and transversals
• Fundamentals of parameterized complexity
• Graph theory
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Matching theory
• On the complexity of the identifiable subgraph problem
• Parameterized algorithms
• Resilience and optimization of identifiable bipartite graphs
• Structural Identifiability in Low-Rank Matrix Factorization
• Structural identifiability in low-rank matrix factorization

Cited in

(7)

• An optimal lower bound on the number of variables for graph identification
• A probabilistic upper bound for the edge identification complexity of graphs
• Resilience and optimization of identifiable bipartite graphs
• On the complexity of the identifiable subgraph problem
• On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths
• On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs
• The complexity of regular subgraph recognition

This page was built for publication: On the complexity of the identifiable subgraph problem, revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2357777)