[Rule] KColoring to BicliqueCover

[GiggleLiu]

[Rule] KColoring to BicliqueCover

Source

KColoring on general graphs, with general K.

Target

BicliqueCover.

Motivation

This rule adds a direct graph-theoretic bridge:

KColoring -> BicliqueCover

The direct KSatisfiability/K3 -> BicliqueCover construction from Chandran-Issac-Karrenbauer has better rank overhead for 3SAT-based lower bounds, but it is complex. This KColoring -> BicliqueCover rule is simpler and useful whenever the source is already a graph-coloring instance.

It also gives an alternate route:

3SAT -> KColoring -> BicliqueCover

The rule depends on the classical sub-biclique semantics of BicliqueCover: each selected biclique must satisfy L_b x R_b subseteq E.

Reference

This is a direct self-contained gadget reduction. It should not be attributed as a known construction from the references below; those are background references for graph coloring and biclique cover.

Background:

• Karp, "Reducibility among Combinatorial Problems", 1972.
• Garey and Johnson, "Computers and Intractability", 1979.
• Orlin, "Contentment in Graph Theory: Covering Graphs with Cliques", 1977.

Reduction Algorithm

Input: a KColoring instance (G, q) where G = (V, E) is an undirected graph and q is the number of colors.

Let:

n = |V|

Construct a bipartite graph H = (L, R, F).

For each source vertex v in V, create:

left vertices:  a_v, g_v
right vertices: b_v, h_v

Set the BicliqueCover rank to:

k = n + q

Add the following edges and no others.

1. Diagonal edges

For every v in V, add:

(a_v, b_v)

These are the edges that encode the coloring choices.

2. Compatibility edges

For every ordered pair u != v with {u,v} notin E, add:

(a_u, b_v)

These allow vertices with the same color to share a biclique exactly when they are nonadjacent in G.

3. Guard-anchor edges

For every v in V, add:

(a_v, h_v)
(g_v, h_v)

4. Guard compatibility edges

For every v in V and every w != v with {v,w} notin E, add:

(g_v, b_w)

Do not add (g_v, b_v). Do not add (a_u, h_v) for u != v.

The target instance is:

BicliqueCover(H, k = n + q)

Correctness

Forward direction

Assume G has a proper q-coloring.

For every source vertex v, create a guard biclique:

G_v = ({a_v, g_v}, {h_v} union {b_w : w != v and {v,w} notin E})

This is a valid sub-biclique because:

• (a_v, h_v) and (g_v, h_v) are guard-anchor edges.
• (a_v, b_w) exists for every nonneighbor w of v.
• (g_v, b_w) exists for every nonneighbor w of v.

For every color class C, create a color biclique:

C_color = ({a_v : v in C}, {b_v : v in C})

Because C is an independent set, all distinct u,v in C are nonadjacent in G, so both compatibility edges (a_u,b_v) and (a_v,b_u) exist. The diagonal edges (a_v,b_v) also exist.

The n guard bicliques cover all guard-anchor and guard compatibility edges. The q color bicliques cover all diagonal edges, and the guard bicliques cover compatibility edges. Therefore H has a biclique cover using n + q bicliques.

Reverse direction

Assume H has a biclique cover using at most n + q bicliques.

Each guard-anchor edge:

(g_v, h_v)

requires its own biclique. Two different guard-anchor edges (g_u,h_u) and (g_v,h_v) cannot be in the same biclique because cross edges such as (g_u,h_v) are absent.

A biclique covering (g_v,h_v) cannot cover any diagonal edge (a_u,b_u):

• If u = v, edge (g_v,b_v) is absent.
• If u != v, edge (a_u,h_v) is absent.

Therefore at least n bicliques are consumed by guard-anchor edges, leaving at most q bicliques to cover all diagonal edges (a_v,b_v).

Assign each vertex v a color corresponding to any remaining biclique that covers (a_v,b_v). If two vertices u and v receive the same color, that biclique contains:

a_u, a_v, b_u, b_v

so both (a_u,b_v) and (a_v,b_u) must be target edges. By construction this is possible only if {u,v} notin E.

Thus each color class is independent, giving a proper q-coloring of G.

Solution Extraction

Given a valid BicliqueCover witness:

1. For each source vertex v, find any biclique index r such that both a_v and b_v are selected in biclique r.
2. Ignore bicliques that cover guard-anchor edges.
3. Compact the distinct remaining biclique indices into colors 0, 1, ..., q-1 in first-seen order.
4. Assign each source vertex v the compacted color for its diagonal-covering biclique.

The reverse proof shows that at most q non-guard bicliques cover all diagonal edges, so this produces a valid coloring.

Size Overhead

Let:

n = num_vertices
m = num_edges
q = num_colors

Target size fields for BicliqueCover are num_vertices, num_edges, and rank.

Target metric	Formula
num_vertices	4 * num_vertices
num_edges	2 * num_vertices * (num_vertices - 1) - 4 * num_edges + 3 * num_vertices
rank	num_vertices + num_colors

Edge count derivation:

• n diagonal edges.
• n(n-1) - 2m ordered compatibility edges.
• 2n guard-anchor edges.
• n(n-1) - 2m guard compatibility edges.

Total:

n + 2n + 2(n(n-1) - 2m)
= 2n(n-1) - 4m + 3n

Validation Method

Implementation should include:

1. A closed-loop YES test on a nontrivial 3-colorable graph.
2. A closed-loop NO test, for example K4 with q = 3.
3. A witness extraction test: solve the BicliqueCover target, extract a coloring, and verify it directly on the source graph.
4. A structure test checking num_vertices = 4n, rank = n + q, and the exact edge count above.
5. A test that the target rejects an invalid biclique that tries to group adjacent source vertices, confirming dependence on sub-biclique semantics.

Run the repo's verify-reduction workflow before implementation because this is a self-contained construction rather than a quoted textbook rule.

Example

Use the Petersen graph with q = 3. This is large enough to exercise nonedges and color-class structure but still hand-checkable.

Source graph:

n = 10
m = 15
q = 3
edges:
(0,1), (0,4), (0,5),
(1,2), (1,6),
(2,3), (2,7),
(3,4), (3,8),
(4,9),
(5,7), (5,8),
(6,8), (6,9),
(7,9)

A valid 3-coloring is:

color 0: {0, 2, 6}
color 1: {1, 3, 5, 9}
color 2: {4, 7, 8}

Constructed target:

left vertices:  a0..a9, g0..g9
right vertices: b0..b9, h0..h9
rank: 10 + 3 = 13
num_vertices: 40
num_edges: 2*10*9 - 4*15 + 3*10 = 150

Use ten guard bicliques:

G_v = ({a_v, g_v}, {h_v} union {b_w : w != v and w is nonadjacent to v})

and three color bicliques:

C_0 = ({a0, a2, a6}, {b0, b2, b6})
C_1 = ({a1, a3, a5, a9}, {b1, b3, b5, b9})
C_2 = ({a4, a7, a8}, {b4, b7, b8})

These 13 bicliques cover the target edges. Extraction from the three color bicliques recovers the listed Petersen coloring.

BibTeX

@incollection{karp1972,
  author    = {Richard M. Karp},
  title     = {Reducibility among Combinatorial Problems},
  booktitle = {Complexity of Computer Computations},
  publisher = {Plenum Press},
  year      = {1972},
  pages     = {85--103}
}

@book{garey1979,
  author    = {Michael R. Garey and David S. Johnson},
  title     = {Computers and Intractability: A Guide to the Theory of NP-Completeness},
  publisher = {W. H. Freeman},
  year      = {1979}
}

@article{orlin1977,
  author  = {James B. Orlin},
  title   = {Contentment in Graph Theory: Covering Graphs with Cliques},
  journal = {Indagationes Mathematicae (Proceedings)},
  volume  = {80},
  number  = {5},
  pages   = {406--424},
  year    = {1977},
  doi     = {10.1016/1385-7258(77)90055-5}
}