Colorful Connected Graph Problem Overview
The Colorful Connected Graph
Problem
Richard Karp
Manuel Rodriguez Torres
The Problem
Input: a graph
G
= (V,E), a set C of
colors
and a function
c from V onto C. c(v) is the color of vertex v.
Problem: Find a connected subgraph with a minimum
number of vertices containing at least one vertex of
each color.
A
perfect solution
is a connected subgraph containing
exactly one vertex of each color.
NP-complete decision problem: does a perfect solution
exist?
A Generalization
Associated with each vertex is a set of eligible
colors.
Problem: find a connected subgraph with |C|
vertices such that its vertices can be assigned
distinct eligible colors.
Applications
•
Protein-Protein Interaction Networks: the vertices are proteins, the edges
indicate physical interactions between proteins, and the eligible colors of a
protein are its possible functions in the cell. Each protein must be assigned
one color.
•
Sensor Networks: the vertices are sensors in a distributed network, the
edges represent direct communication between sensors, and the eligible
colors of a sensor are the activities that it can be assigned to monitor. Each
sensor must be assigned one color.
•
Recruiting a baseball team: the vertices are players, the edges represent
acquaintanceships, and the colors of a player are the positions he/she can
play.
Dynamic Programming Algorithm
•
Predicate A(v, S): vertex v lies in a connected
subgraph whose vertices can be assigned
exactly the set S of colors, without repetition.
•
Recursively, evaluate the predicate for all pairs
(v,S), for increasing values of |S|.
•
Running time: polynomial in the size of the
graph, exponential in the number of colors.
Linear Size Integer Programming
Formulation
Choose
•
An assignment of the colors to distinct eligible
vertices
•
|C|- 1 edges between pairs of chosen vertices
•
An integral flow on the chosen edges such
that one vertex is a sink for |C| -1 units of
flow, and the net flow out of each of the other
vertices is 1.
•
The
gap
of a subgraph H is the minimum
number of vertices whose addition to H
results in a connected graph.
•
A subgraph is
pure
if it contains at most one
vertex of each color
•
A subgraph is
colorful
if it contains exactly one
vertex of each color.
•
Our goal is to find a colorful subgraph of
minimum gap.
The simple case: each vertex has a
unique color
Remoteness
•
The
remoteness
of vertex v from subgraph H is
a list of the distances in G from v to the
connected components of H, in increasing
order.
•
The remoteness of color c from H is the
lexicographically smallest remoteness from H
of a vertex of color c.
Key Subroutine
Sort the colors in increasing order of their
frequencies
Construct a nested sequence H
0
, H
1
, H
2
,
…
of pure subgraphs, where H
0
is the empty graph
and H
k+1
is obtained from H
k
by inserting the
vertex least remote from H
k
, among those of
color k+1.
Halt when all colors have been included.
A Refinement
•
Instead of sorting the colors in increasing
order of frequency, let the (k+1)th color
be the color whose minimum remotenesss
from H
k
is greatest.
•
This refinement is motivated by an analogy to
the max-min insertion heuristic for the TSP, in
which the next vertex inserted in a growing
tour is the one whose cheapest insertion cost
is greatest.
Example
L
G Q
E K
P I
A
J
O F C
H B N D M
R
Example
L
G Q
E K
P I
A
J
O F C
H
B
N D M
R
Example
L
G Q
E K
P I
A
J
O F
C
H
B
N D M
R
Example
L
G Q
E K
P I
A
J
O F
C
H
B
N
D
M
R
Example
L
G Q
E
K
P I
A
J
O F
C
H
B
N
D
M
R
Example
L
G Q
E
K
P I
A
J
O
F
C
H
B
N
D
M
R
Example
L
G
Q
E
K
P I
A
J
N O
F
C
H
B
N
D
M
R
Example
L
G
Q
E
K
P I
A
J
N O
F
C
H
B
N
D
M
R
Example
L
G
Q
E
K
P
I
A
J
N O
F
C
H
B
N
D
M
R
Example
L
G
Q
E
K
P
I A
J
O
F
C
H
B
N
D
M
R
Example
L
G
Q
E
K
P
I
A
J
N O
F
C
H
B
N
D
M
R
Example
L
G
Q
E
K
P
I A
J
N O
F
C
H
B N
D
M
R
Example
L
G
Q
E
K
P
I
A
J
N O F
C
H
B
N D
M
R
Example
L
G
Q
E
K
P
I
A
J
O
F
C
H
B
N D M
R
Example
L
G
Q
E
K
P
I
A
J
O
F
C
H
B
N
D
M
R
Example
L
G
Q
E K
P I A J
O F C
H B
N D M
R
Example
L
G Q
E K
P I A J
O F C
H B N D M
R
Example
L
G Q
E K
P I A J
O F C
H B N D M
R
Example of Phase 1
Example of Phase 1
Local Improvement
•
Start with the result of the key subroutine:
a graph containing one occurrence of each
color, but not necessarily connected.
Cycle through the colors. Let the current graph be
H. Upon considering color c, delete the vertex v of
color c, obtaining H\v. Then insert a random vertex
of color c adjacent to the maximum number of
connected components of H\v. If no vertex of color
c is adjacent to a component, choose a vertex with
the lexicographically smallest remoteness from H\v.
Example of Phase 2
Example of Phase 2
Example of Phase 2
Full Algorithm
Recall: the gap of a pure subgraph H as the
minimum number of vertices whose insertion into
H creates a connected structure.
Let T be the set of least frequent colors. Choose a
set of start vertices whose colors are in T. For each
such vertex, run the key subroutine until a t-vertex
subgraph is obtained. Among these subgraphs,
choose one with minimum gap, and run the key
subroutine and local improvement to completion.
Extension to the case where a vertex
may have several eligible colors.
•
A subgraph is
assignable
if its vertices can be
assigned distinct eligible colors.
•
A subgraph is
colorful
if it is assignable and
has |C| vertices.
•
Problem: find a colorful subgraph of minimum
gap.
Key Subroutine
•
Sort the colors in increasing order of
frequency.
•
A k-vertex subgraph is
perfectly assignable
if
its vertices can be assigned distinct eligible
colors drawn from the first k colors.
•
Construct perfectly assignable subgraphs H
0
,
H
1
,
…, H
k
,... Here H
k+1
= H
k
+ x, where x is the
least
remote vertex whose addition to H
k
yields a perfectly assignable subgraph.
Color Reassignment
•
The construction of H
k+1
from H
k
involves
augmenting along an alternating path in the
bipartite graph of the eligibility relation
between the vertices and the first k+1 colors,
starting at the (k+1)th color.
•
The color assignment to each vertex may
change at each iteration.
Random Experimental Model
•
The graph is a 2-dimensional grid.
•
In each experiment the dimensions of the
grid, the number of colors and the frequency
distribution of the colors are chosen.
•
Colors are assigned randomly to the vertices,
subject to the frequency distribution.
Results
In each experiment near-perfect solutions
are obtained in the great majority of runs,
except when the number of frequency-1 vertices
is large or some colors have extremely high
frequency. The more even the frequency
distribution, the better the results.
Nonexistence of Perfect Solution
•
A threshold result from percolation theory
implies that a perfect solution is unlikely to
exist when a single color is assigned to more
than 41% of the nodes. More refined results
from percolation theory should yield more
refined impossibility results.
Planted Experimental Model
•
In every case the graph is a 2-dimensional grid.
•
In each experiment the dimensions of the grid,
the number of colors and the frequency
distribution of the colors are chosen.
•
A perfect solution is planted by choosing a
random connected subgraph with |C| vertices,
choosing a random 1-1 map from the set of
colors onto this set of vertices, and completing
the color assignment randomly subject to the
frequency distribution.
Results
•
With high probability a perfect solution was
found, but it usually was not the planted one.
Results
Finding many perfect solutions in the
planted model
•
Using an oracle for solving the colorful subgraph problem, an
implicit enumeration algorithm can list all the perfect
solutions.
•
General step: given a subgraph, find a perfect solution if one
exists. Then choose an ordering of the vertices in the solution,
and recursively generate ICI subproblems, where the kth
subproblem seeks a solution which includes the first k-1
vertices in the solution, and excludes the kth vertex in the
solution.
•
This algorithm generates each perfect solution exactly once.
Generating Many Perfect Solutions
•
Run the implicit enumeration algorithm, but
using our heuristic algorithm in place of the
oracle.
•
Depending on the color frequency distribution,
this algorithm generates the planted solution
between 20% and 70% of the time. We infer that,
if the planted solution is drawn randomly from
the set of perfect solutions, then in expectation,
the algorithm generates between 20% and 70%
of the perfect solutions.
The Colorful Connected Graph Problem involves finding a connected subgraph with a minimum number of vertices containing at least one vertex of each color. Considered an NP-complete decision problem, it has various real-world applications in fields such as Protein-Protein Interaction Networks, Sensor Networks, and Baseball Team Recruitment. Dynamic Programming and Linear Size Integer Programming are two key algorithms used to address the complexity of this problem.
Uploaded on Feb 26, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
The Colorful Connected Graph Problem Richard Karp Manuel Rodriguez Torres
The Problem Input: a graph G= (V,E), a set C of colors and a function c from V onto C. c(v) is the color of vertex v. Problem: Find a connected subgraph with a minimum number of vertices containing at least one vertex of each color. A perfect solution is a connected subgraph containing exactly one vertex of each color. NP-complete decision problem: does a perfect solution exist?
A Generalization Associated with each vertex is a set of eligible colors. Problem: find a connected subgraph with |C| vertices such that its vertices can be assigned distinct eligible colors.
Applications Protein-Protein Interaction Networks: the vertices are proteins, the edges indicate physical interactions between proteins, and the eligible colors of a protein are its possible functions in the cell. Each protein must be assigned one color. Sensor Networks: the vertices are sensors in a distributed network, the edges represent direct communication between sensors, and the eligible colors of a sensor are the activities that it can be assigned to monitor. Each sensor must be assigned one color. Recruiting a baseball team: the vertices are players, the edges represent acquaintanceships, and the colors of a player are the positions he/she can play.
Dynamic Programming Algorithm Predicate A(v, S): vertex v lies in a connected subgraph whose vertices can be assigned exactly the set S of colors, without repetition. Recursively, evaluate the predicate for all pairs (v,S), for increasing values of |S|. Running time: polynomial in the size of the graph, exponential in the number of colors.
Linear Size Integer Programming Formulation Choose An assignment of the colors to distinct eligible vertices |C|- 1 edges between pairs of chosen vertices An integral flow on the chosen edges such that one vertex is a sink for |C| -1 units of flow, and the net flow out of each of the other vertices is 1.
The simple case: each vertex has a unique color The gap of a subgraph H is the minimum number of vertices whose addition to H results in a connected graph. A subgraph is pure if it contains at most one vertex of each color A subgraph is colorful if it contains exactly one vertex of each color. Our goal is to find a colorful subgraph of minimum gap.
Remoteness The remoteness of vertex v from subgraph H is a list of the distances in G from v to the connected components of H, in increasing order. The remoteness of color c from H is the lexicographically smallest remoteness from H of a vertex of color c.
Key Subroutine Sort the colors in increasing order of their frequencies Construct a nested sequence H0, H1, H2, of pure subgraphs, where H0is the empty graph and Hk+1is obtained from Hkby inserting the vertex least remote from Hk, among those of color k+1. Halt when all colors have been included.
A Refinement Instead of sorting the colors in increasing order of frequency, let the (k+1)th color be the color whose minimum remotenesss from Hkis greatest. This refinement is motivated by an analogy to the max-min insertion heuristic for the TSP, in which the next vertex inserted in a growing tour is the one whose cheapest insertion cost is greatest.
Example L G Q E K P I A J O F C H B N D M R
Example L G Q E K P I A J O F C H B N D M R
Example L G Q E K P I A J O F C H B N D M R
Example L G Q E K P I A J O F C H B N D M R
Example L G Q E P I A J O F C H B N D M R K
Example L G Q E P I A J O F C H B N D M R K
Example L G Q E P I A J N O F C H B N D M R K
Example L G Q E P I A J N O F C H B N D M R K
Example L G Q E P I A J N O F C H B N D M R K
Example L G Q E P I A J O F C H B N D M R K
Example L G Q E P I A J N O F C H B N D M R K
Example L G Q E P I A J N O F C H B N D M R K
Example L G Q E P I A J N O F C H B N D M R K
Example L G Q E K P I A J O F C H B N D M R
Example L G Q E P I A J O F C H B N D M R K
Example L G Q E K P I A J O F C H B N D M R
Example L G Q E K P I A J O F C H B N D M R
Example L G Q E K P I A J O F C H B N D M R
Local Improvement Start with the result of the key subroutine: a graph containing one occurrence of each color, but not necessarily connected. Cycle through the colors. Let the current graph be H. Upon considering color c, delete the vertex v of color c, obtaining H\v. Then insert a random vertex of color c adjacent to the maximum number of connected components of H\v. If no vertex of color c is adjacent to a component, choose a vertex with the lexicographically smallest remoteness from H\v.
Full Algorithm Recall: the gap of a pure subgraph H as the minimum number of vertices whose insertion into H creates a connected structure. Let T be the set of least frequent colors. Choose a set of start vertices whose colors are in T. For each such vertex, run the key subroutine until a t-vertex subgraph is obtained. Among these subgraphs, choose one with minimum gap, and run the key subroutine and local improvement to completion.
Extension to the case where a vertex may have several eligible colors. A subgraph is assignable if its vertices can be assigned distinct eligible colors. A subgraph is colorful if it is assignable and has |C| vertices. Problem: find a colorful subgraph of minimum gap.
Key Subroutine Sort the colors in increasing order of frequency. A k-vertex subgraph is perfectly assignable if its vertices can be assigned distinct eligible colors drawn from the first k colors. Construct perfectly assignable subgraphs H0, H1, , Hk,... Here Hk+1= Hk+ x, where x is the least remote vertex whose addition to Hk yields a perfectly assignable subgraph.
Color Reassignment The construction of Hk+1from Hkinvolves augmenting along an alternating path in the bipartite graph of the eligibility relation between the vertices and the first k+1 colors, starting at the (k+1)th color. The color assignment to each vertex may change at each iteration.
Random Experimental Model The graph is a 2-dimensional grid. In each experiment the dimensions of the grid, the number of colors and the frequency distribution of the colors are chosen. Colors are assigned randomly to the vertices, subject to the frequency distribution.
Results In each experiment near-perfect solutions are obtained in the great majority of runs, except when the number of frequency-1 vertices is large or some colors have extremely high frequency. The more even the frequency distribution, the better the results.
Nonexistence of Perfect Solution A threshold result from percolation theory implies that a perfect solution is unlikely to exist when a single color is assigned to more than 41% of the nodes. More refined results from percolation theory should yield more refined impossibility results.
Planted Experimental Model In every case the graph is a 2-dimensional grid. In each experiment the dimensions of the grid, the number of colors and the frequency distribution of the colors are chosen. A perfect solution is planted by choosing a random connected subgraph with |C| vertices, choosing a random 1-1 map from the set of colors onto this set of vertices, and completing the color assignment randomly subject to the frequency distribution.
Results With high probability a perfect solution was found, but it usually was not the planted one.
Finding many perfect solutions in the planted model Using an oracle for solving the colorful subgraph problem, an implicit enumeration algorithm can list all the perfect solutions. General step: given a subgraph, find a perfect solution if one exists. Then choose an ordering of the vertices in the solution, and recursively generate ICI subproblems, where the kth subproblem seeks a solution which includes the first k-1 vertices in the solution, and excludes the kth vertex in the solution. This algorithm generates each perfect solution exactly once.
Generating Many Perfect Solutions Run the implicit enumeration algorithm, but using our heuristic algorithm in place of the oracle. Depending on the color frequency distribution, this algorithm generates the planted solution between 20% and 70% of the time. We infer that, if the planted solution is drawn randomly from the set of perfect solutions, then in expectation, the algorithm generates between 20% and 70% of the perfect solutions.
