24
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Derrick Stolee
    Nov 5, 2010 at 15:58

2 Answers 2

Reset to default
22
$\begingroup$

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. There are settings where core computation can be done efficiently, see Efficient Core Computation in Data Exchange 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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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 ? $\endgroup$
    – Suresh Venkat
    Nov 5, 2010 at 18:08
  • 8
    $\begingroup$ @Suresh: I think that pointing out the NP-completeness is one of the good ways to answer a question asking for an algorithm. $\endgroup$
    – Tsuyoshi Ito
    Nov 5, 2010 at 18:46
  • 1
    $\begingroup$ 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) $\endgroup$
    – Suresh Venkat
    Nov 5, 2010 at 20:02
9
$\begingroup$

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.uwaterloo.ca/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.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.