24

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?

Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
Regularity
  • 901
  • 5
  • 13
  • 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 Nov 05 '10 at 15:58

2 Answers2

22

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.

András Salamon
  • 19,000
  • 3
  • 64
  • 150
  • 1
    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 Nov 05 '10 at 18:08
  • 8
    @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 Nov 05 '10 at 18:46
  • 1
    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 Nov 05 '10 at 20:02
9

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.

Szymon Toruńczyk
  • 191
  • 2
  • 3