<p>Computing the core of a graph is hard: even deciding if a given 3-colourable graph is a core is co-NP-complete, see <a href="http://dx.doi.org/10.1016/0012-365X(92)90282-K" rel="nofollow">Hell and Nesetril</a>.  There are settings where core computation can be done efficiently, see <em><a href="http://dx.doi.org/10.1145/1346330.1346334" rel="nofollow">Efficient Core Computation in Data Exchange</a></em> by Georg Gottlob and Alan Nash for a database setting; here some reasonable restrictions on the kinds of constraints in the database schema allow cores to be computed efficiently.</p>

<p><em>Edit:</em> Other than the Gottlob/Nash work mentioned above, I am not aware of any other attempts to provide efficient algorithms for core computation.  Pointers to any algorithms better than brute force (exact or otherwise) would be welcome.</p>

CC BY-SA 2.5
2010-11-05T18:08:22.310Z
Andras, the paper you link to seems to show (reading the abstract) that checking if a graph is its own core is NP-complete. Does the paper also answer the question the OP poses ?
Suresh Venkat
CC BY-SA 2.5
2010-11-05T18:46:03.457Z
@Suresh: I think that pointing out the NP-completeness is one of the good ways to answer a question asking for an algorithm.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-05T20:02:04.137Z
right. i was just wondering if there was more in the paper (i.e can you check if the core is small, or if the core is trivial, etc etc)
Suresh Venkat
CC BY-SA 3.0
2010-11-05T16:22:11.177Z
2016-06-05T02:19:25.003Z
2016-06-05T02:19:25.003Z
András Salamon
<p>The problem of determining whether a given graph is a core graph is easily seen to be in co-NP. In fact, it is co-NP complete.</p>
<p>The problem of determining whether a given subgraph H is a core of a given graph G is in the larger class DP (<a href="https://complexityzoo.net/Complexity_Zoo:D#dp" rel="nofollow noreferrer">https://complexityzoo.net/Complexity_Zoo:D#dp</a>), and is in fact complete for this class (the archetypical complete problem for this class consists of pairs of boolean formulas, where the first one is satisfiable and the second one is unsatifiable). Containment in DP is clear: test that G maps homomorphically to H (this is encoded as satisfiability) and simultaneously that H has no homomorphism to itself which is not onto (this is encoded as unsatisfiability). DP-hardness is nontrivial, and is proved in the paper:</p>
<p>Fagin, Ronald, Phokion G. Kolaitis, and Lucian Popa. &quot;Data exchange: getting to the core.&quot; ACM Transactions on Database Systems (TODS) 30.1 (2005): 174-210.</p>

CC BY-SA 3.0
2016-06-05T02:43:21.600Z
The paper is at http://dx.doi.org/10.1145/1061318.1061323
András Salamon
CC BY-SA 4.0
2016-06-03T09:20:08.820Z
2024-09-23T18:22:35.727Z
2024-09-23T18:22:35.727Z
Szymon Toruńczyk
<p>A graph H is a core if any homomorphism from H to itself is a bijection. A subgraph H of G is a core of G if H is a core and there is a homomorphism from G to H. 
<a href="http://en.wikipedia.org/wiki/Core_%28graph_theory%29">http://en.wikipedia.org/wiki/Core_%28graph_theory%29</a></p>

<p>Given a graph G, what is the best known exact algorithm to find its core?</p>

CC BY-SA 2.5
2010-11-05T15:58:11.680Z
At first glance, this problem seems very hard, but a reduction from Graph Isomorphism or other related problems is not obvious (to me).  Great question.
Derrick Stolee
<ds.algorithms><graph-theory><graph-algorithms>
What is the best exact algorithm to compute the core of a graph?
Regularity
# What is the best exact algorithm to compute the core of a graph?

(Asked by: username_0 on 2010-11-05)

A graph H is a core if any homomorphism from H to itself is a bijection. A subgraph H of G is a core of G if H is a core and there is a homomorphism from G to H.
<http://en.wikipedia.org/wiki/Core_%28graph_theory%29>

Given a graph G, what is the best known exact algorithm to find its core?

**Tags:** ds.algorithms, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: At first glance, this problem seems very hard, but a reduction from Graph Isomorphism or other related problems is not obvious (to me).  Great question.  

---

## 2 answers

### Answer by username_2 on 2010-11-05. Score: 23

Computing the core of a graph is hard: even deciding if a given 3-colourable graph is a core is co-NP-complete, see [Hell and Nesetril](http://dx.doi.org/10.1016/0012-365X(92)90282-K). There are settings where core computation can be done efficiently, see *[Efficient Core Computation in Data Exchange](http://dx.doi.org/10.1145/1346330.1346334)* by Georg Gottlob and Alan Nash for a database setting; here some reasonable restrictions on the kinds of constraints in the database schema allow cores to be computed efficiently.

*Edit:* Other than the Gottlob/Nash work mentioned above, I am not aware of any other attempts to provide efficient algorithms for core computation. Pointers to any algorithms better than brute force (exact or otherwise) would be welcome.

> **Comments:**
> **username_3**: Andras, the paper you link to seems to show (reading the abstract) that checking if a graph is its own core is NP-complete. Does the paper also answer the question the OP poses ?  
> **username_4**: @Suresh: I think that pointing out the NP-completeness is one of the good ways to answer a question asking for an algorithm.  
> **username_3**: right. i was just wondering if there was more in the paper (i.e can you check if the core is small, or if the core is trivial, etc etc)  

---

### Answer by username_5 on 2016-06-03. Score: 11

The problem of determining whether a given graph is a core graph is easily seen to be in co-NP. In fact, it is co-NP complete.

The problem of determining whether a given subgraph H is a core of a given graph G is in the larger class DP (<https://complexityzoo.net/Complexity_Zoo:D#dp>), and is in fact complete for this class (the archetypical complete problem for this class consists of pairs of boolean formulas, where the first one is satisfiable and the second one is unsatifiable). Containment in DP is clear: test that G maps homomorphically to H (this is encoded as satisfiability) and simultaneously that H has no homomorphism to itself which is not onto (this is encoded as unsatisfiability). DP-hardness is nontrivial, and is proved in the paper:

Fagin, Ronald, Phokion G. Kolaitis, and Lucian Popa. "Data exchange: getting to the core." ACM Transactions on Database Systems (TODS) 30.1 (2005): 174-210.

> **Comments:**
> **username_2**: The paper is at http://dx.doi.org/10.1145/1061318.1061323  

---

