Approximating Modular Decomposition Is Hard
| Autor: | Michel Habib, Mengchuan Zou, Lalla Mouatadid |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
050101 languages & linguistics Computer science Algebraic structure 05 social sciences Neighbourhood (graph theory) Order (ring theory) 02 engineering and technology Graph Vertex (geometry) Modular decomposition 0202 electrical engineering electronic engineering information engineering Decomposition (computer science) 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Time complexity Neighbourhood (mathematics) |
| Zdroj: | Algorithms and Discrete Applied Mathematics ISBN: 9783030392185 CALDAM |
| DOI: | 10.1007/978-3-030-39219-2_5 |
| Popis: | In order to understand underlying structural regularities in a graph, a basic and useful technique, known as modular decomposition, looks for subsets of vertices that have the exact same neighbourhood to the outside. These are known as modules and there exist linear-time algorithms to find them. This notion however is too strict, especially when dealing with graphs that arise from real world data. This is why it is important to relax this condition by allowing some noise in the data. However, generalizing modular decomposition is far from being obvious since most of the proposals lose the algebraic properties of modules and therefore most of the nice algorithmic consequences. In this paper we introduce the notion of \(\epsilon \)-module which seems to be a good compromise that maintains some of the algebraic structure. Among the main results in the paper, we show that minimal \(\epsilon \)-modules can be computed in polynomial time, on the other hand for maximal \(\epsilon \)-modules it is already NP-hard to compute if a graph admits an 1-parallel decomposition, i.e. one step of decomposition of \(\epsilon \)-module with \(\epsilon =1\). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|