7
\$\begingroup\$

Given a graph \$G(V, E)\$ with vertices \$V\$ and edges \$E\$, where each vertex is associated with a single color from a set of colors \$C=\{1, 2, ..., k\}\$, we define the following problem:

Problem Statement:

  • Input: A graph \$G(V, E)\$ and a set of colors \$C\$, with a constraint that each vertex \$v\$ in \$V\$ is assigned exactly one color from \$C\$.
  • Objective: Determine if there exists a connected subgraph of \$G\$ that is "\$C\$-colorful". A subgraph is considered "\$C\$-colorful" if it contains exactly one vertex of each color present in \$C\$.

Background:

Topology-Free Querying of Protein Interaction Networks SHARON BRUCKNER et al. (2010, Journal of Computational biology)

Complexity:

The problem has been proven to be NP-complete, the authors say there is a solution using Dynamic Programming that is \$\mathcal{O}(3^k \times E)\$.

Example Inputs:

example_input = {
    "vertices": ["v1", "v2", "v3", "v4", "v5"],
    "edges": [
        ("v1", "v2"),
        ("v2", "v3"),
        ("v3", "v4"),
        ("v4", "v5"),
        ("v1", "v3"),
        ("v2", "v4"),
    ],
    "color_constraints": {"v1": 1, "v2": 2, "v3": 3, "v4": 1, "v5": 2},
    "num_colors": 3,
}  # Should be True

example_input_2 = {
    "vertices": ["v1", "v2", "v3", "v4", "v5"],
    "edges": [
        ("v1", "v2"),
        ("v2", "v3"),
        ("v3", "v4"),
        ("v4", "v5"),
        ("v1", "v3"),
        ("v2", "v4"),
    ],
    "color_constraints": {"v1": 2, "v2": 1, "v3": 1, "v4": 1, "v5": 3},
    "num_colors": 3,
}  # Should be False

example_input_3 = {
    "vertices": ["v1", "v2", "v3", "v4", "v5"],
    "edges": [
        ("v1", "v2"),
        ("v2", "v3"),
        ("v3", "v4"),
        ("v4", "v5"),
        ("v1", "v3"),
        ("v2", "v4"),
    ],
    "color_constraints": {"v1": 2, "v2": 1, "v3": 1, "v4": 2, "v5": 3},
    "num_colors": 3,
}  # should be True

My implementation of the authors' DP solution

from itertools import combinations

def powerset(iterable):
    s = list(iterable)
    list_all_combinations = []
    for r in range(len(s)+1):
        list_all_combinations += list(combinations(s, r))
    return list_all_combinations
# powerset([1, 2, 3]) -> [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

def find_colorful_subtree(graph_info) -> bool:
    """
    graph_info is a dictionary which keys are 'vertices', 'edges', 'color_constraints', and 'num_colors' and values are
    dictionaries.
    """
    vertices: list[str]
    edges: list[tuple[str, str]]
    vertices, edges = graph_info['vertices'], graph_info['edges']
    v_to_idx: dict[str, int] = {v: idx for idx, v in enumerate(vertices)}  # idx_to_v is not needed, it's vertices
    color_map: dict[str, int] = graph_info['color_constraints']
    num_colors: int = graph_info['num_colors']
    
    # Create graph
    g = {v: set() for v in vertices}
    for u, v in edges:
        g[u].add(v)
        g[v].add(u)
    
    # DP table dp[v][S] = True if a subtree rooted at v is S-colorful
    # We encode S with integers (bitmask) 
    dp = [[False for _ in range(1 << num_colors)] for _ in range(len(vertices))]

    # Initialize the DP table
    for v_idx, v in enumerate(vertices):
        color = color_map[v]
        dp[v_idx][1 << color - 1] = True
    
    # Recursive function to fill the DP table
    for subset in powerset(range(num_colors)):
        if len(subset) <= 1:
            continue
        # generate all s1, s2 such that s1 + s2 = subset and s1 & s2 = {}
        s: int = 0
        for color in subset:
            s |= 1 << color
        for left_subset in powerset(subset):
            if len(left_subset) == 0 or len(left_subset) == len(subset):
                continue
            left_mask: int = 0
            for color in left_subset:
                left_mask |= 1 << color
            right_mask: int = s ^ left_mask  # ^ -> XOR

            for v_idx, v in enumerate(vertices):
                if (1 << color_map[v] - 1) & left_mask != 0:
                    for u in g[v]:
                        if (1 << color_map[u] - 1) & right_mask == 0:
                            continue
                        if dp[v_idx][left_mask] and dp[v_to_idx[u]][right_mask]:
                            dp[v_idx][s] = True
                            break  # no need to check other neighbors, we found a colorful subtree rooted at v
            
    ans: bool = False
    for v_idx, v in enumerate(vertices):
        ans |= dp[v_idx][(1 << num_colors) - 1]
    
    return ans

# Running the algorithm on the examples
assert find_colorful_subtree(example_input)
assert not find_colorful_subtree(example_input_2)
assert find_colorful_subtree(example_input_3)

A naive implementation in complexity \$\mathcal{O}(V 2^V)\$.

def find_colorful_subtree_naive(graph_info) -> bool:
    """
    graph_info is a dictionary which keys are 'vertices', 'edges', 'color_constraints', and 'num_colors' and values are
    dictionaries.
    """
    vertices: list[str]
    edges: list[tuple[str, str]]
    vertices, edges = graph_info['vertices'], graph_info['edges']
    v_to_idx: dict[str, int] = {v: idx for idx, v in enumerate(vertices)}  # idx_to_v is not needed, it's vertices
    color_map: dict[str, int] = graph_info['color_constraints']
    num_colors: int = graph_info['num_colors']
    
    # Create graph
    g = {v: set() for v in vertices}
    for u, v in edges:
        g[u].add(v)
        g[v].add(u)
    
    # we take a set of vertices (2^(|V|)) and check if it is colorful (O(|V|))
    for s in range(1 << len(vertices)):
        if bin(s).count('1') < num_colors:
            continue
        # Check if the set is colorful
        colors: set[int] = set()
        for v_idx, v in enumerate(vertices):
            if (1 << v_idx) & s:
                if color_map[v] in colors:
                    break
                colors.add(color_map[v])
        if len(colors) == num_colors:
            # Check if the set of vertices is connected
            visited: set[str] = set()

            def dfs(v: str):
                visited.add(v)
                for u in g[v]:
                    if u not in visited and (1 << v_to_idx[u]) & s:
                        dfs(u)

            for v_idx, v in enumerate(vertices):
                if (1 << v_idx) & s:
                    dfs(v)
                    break
                    
            if len(visited) == bin(s).count('1'):
                return True

    return False


# Running the algorithm on the examples
assert find_colorful_subtree_naive(example_input)
assert not find_colorful_subtree_naive(example_input_2)
assert find_colorful_subtree_naive(example_input_3)

Are there things I could improve for my implementations? Are there things I got wrong?

\$\endgroup\$
3
  • \$\begingroup\$ I'm new to this StackExchange I hope this post follows the rules. \$\endgroup\$ Mar 21 at 15:26
  • 1
    \$\begingroup\$ You're doing fine. But when you say ... where each vertex is associated with a unique color from a set of colors ..., don't you mean that each vertex is associated with a single color from a set of colors? To me the word "unique" suggests that no color is duplicated on another vertex. But maybe I am reading the wrong interpretation. \$\endgroup\$
    – Booboo
    Mar 24 at 16:14
  • 1
    \$\begingroup\$ Oh yes, single works too and is less ambiguous. I didn't mean to say that no colour was duplicated on another vertex. \$\endgroup\$ Mar 24 at 19:20

1 Answer 1

5
+100
\$\begingroup\$

As I am not a professional Python developer, I won't concentrate on language stylistic issues such as explicit typing. However, I have some background in algorithms and, so, I will stick to that point of view in my answer.

First of all, note that DFS runs in \$\mathcal{O}(V + E)\$ time, not \$\mathcal{O}(V)\$. It's kind of funny that the DP solution runs in \$\mathcal{O}(3^k E)\$ time without mentioning \$V\$. I guess that something changes as we, for example, double the \$\vert V \vert\$, right?

As a starter, I thought about another brute-force algorithm:

class IndexIterator:
    def __init__(self, n, k):
        self.n = n
        self.k = k
        self.indices = []
        for i in range(k):
            self.indices.append(i)

    def __str__(self):
        return ','.join(str(x) for x in self.indices)

    def get_indices(self):
        return self.indices

    def increment(self):
        if self.indices[self.k - 1] < self.n - 1:
            self.indices[self.k - 1] += 1
            return True

        for i in range(self.k - 2, -1, -1):
            if self.indices[i] < self.indices[i + 1] - 1:
                self.indices[i] += 1

                for j in range(i + 1, self.k):
                    self.indices[j] = self.indices[j - 1] + 1

                return True

        return False


def check_is_colorful(nodes, indices, k):
    # Your check code here!
    return True


def is_colorful(nodes, k):
    it = IndexIterator(len(nodes), k)

    while True:
        if check_is_colorful(nodes, it.get_indices(), k):
            return True

        if not it.increment():
            return False

The idea is to consider only \$k\$ combinations of the nodes. There are that many of them: $$ \binom{|V|}{k}. $$ For each of them, we do the \$\mathcal{O}(V + E)\$ DFS check for connectedness and so the total running time is $$ \mathcal{O}\Bigg( \binom{V}{k} k(V + E)\Bigg), $$ where \$k\$ is the cost for producing the next \$k\$-combination of \$V\$ and also check for color assignment runs in \$\mathcal{O}(k)\$ worst case time.

More precisely, the running time of the algorithm I am rolling here is $$ \mathcal{O}\Bigg( \binom{V}{k} k (k + \Delta k) \Bigg) = \mathcal{O}\Bigg( \binom{V}{k} k^2(1 + \Delta) \Bigg), $$ where $$ \Delta = \frac{E}{V} $$ is the average degree of the graph and \$k(1+\Delta)\$ goes to connectedness check that is restricted to a \$k\$-subgraph.

Finally, note that $$ 2^{\vert V \vert} = \sum_{i = 0}^{\vert V \vert} \binom{\vert V \vert}{i}, $$ and so we have that $$ \binom{\vert V \vert}{k} < 2^{\vert V \vert} $$ for any \$k \in \{ 1, 2, \ldots, \vert V \vert \}.\$

Summa summarum

All in all, I had this (runnable) program:

import time
import random


example_input_1 = {
    "vertices": ["v1", "v2", "v3", "v4", "v5"],
    "edges": [
        ("v1", "v2"),
        ("v2", "v3"),
        ("v3", "v4"),
        ("v4", "v5"),
        ("v1", "v3"),
        ("v2", "v4"),
    ],
    "color_constraints": {"v1": 1, "v2": 2, "v3": 3, "v4": 1, "v5": 2},
    "num_colors": 3,
}  # Should be True

example_input_2 = {
    "vertices": ["v1", "v2", "v3", "v4", "v5"],
    "edges": [
        ("v1", "v2"),
        ("v2", "v3"),
        ("v3", "v4"),
        ("v4", "v5"),
        ("v1", "v3"),
        ("v2", "v4"),
    ],
    "color_constraints": {"v1": 2, "v2": 1, "v3": 1, "v4": 1, "v5": 3},
    "num_colors": 3,
}  # Should be False

example_input_3 = {
    "vertices": ["v1", "v2", "v3", "v4", "v5"],
    "edges": [
        ("v1", "v2"),
        ("v2", "v3"),
        ("v3", "v4"),
        ("v4", "v5"),
        ("v1", "v3"),
        ("v2", "v4"),
    ],
    "color_constraints": {"v1": 2, "v2": 1, "v3": 1, "v4": 2, "v5": 3},
    "num_colors": 3,
}  # should be True


# Returns the current milliseconds:
def millis():
    return round(1000 * time.time())


def powerset(iterable):
    s = list(iterable)
    list_all_combinations = []
    for r in range(len(s) + 1):
        list_all_combinations += list(combinations(s, r))
    return list_all_combinations


# The depth-first search restricted to the subgraph_set:
def dfs(v, visited, subgraph_set, g, k):
    if len(visited) > k:
        # Halt, there is no way to k-color the set of size larger than k:
        return

    visited.add(v)

    for u in g[v]:
        if u not in visited and u in subgraph_set:
            dfs(u, visited, subgraph_set, g, k)


# Builds the graph from the graph_info
def create_graph(graph_info):
    vertices: list[str]
    edges: list[tuple[str, str]]
    vertices, edges = graph_info['vertices'], graph_info['edges']
    v_to_idx: dict[str, int] = {v: idx for idx, v in enumerate(vertices)}  # idx_to_v is not needed, it's vertices
    color_map: dict[str, int] = graph_info['color_constraints']
    num_colors: int = graph_info['num_colors']

    # Create (undirected) graph:
    g = {v: set() for v in vertices}
    for u, v in edges:
        g[u].add(v)
        g[v].add(u)

    return vertices, edges, v_to_idx, color_map, num_colors, g


def find_colorful_subtree(graph_info) -> bool:
    vertices, edges, v_to_idx, color_map, num_colors, g = create_graph(graph_info)

    # DP table dp[v][S] = True if a subtree rooted at v is S-colorful
    # We encode S with integers (bitmask)
    dp = [[False for _ in range(1 << num_colors)] for _ in range(len(vertices))]

    # Initialize the DP table
    for v_idx, v in enumerate(vertices):
        color = color_map[v]
        dp[v_idx][1 << color - 1] = True

    # Recursive function to fill the DP table
    for subset in powerset(range(num_colors)):
        if len(subset) <= 1:
            continue
        # generate all s1, s2 such that s1 + s2 = subset and s1 & s2 = {}
        s: int = 0
        for color in subset:
            s |= 1 << color
        for left_subset in powerset(subset):
            if len(left_subset) == 0 or len(left_subset) == len(subset):
                continue
            left_mask: int = 0
            for color in left_subset:
                left_mask |= 1 << color
            right_mask: int = s ^ left_mask  # ^ -> XOR

            for v_idx, v in enumerate(vertices):
                if (1 << color_map[v] - 1) & left_mask != 0:
                    for u in g[v]:
                        if (1 << color_map[u] - 1) & right_mask == 0:
                            continue
                        if dp[v_idx][left_mask] and dp[v_to_idx[u]][right_mask]:
                            dp[v_idx][s] = True
                            break  # no need to check other neighbors, we found a colorful subtree rooted at v

    ans: bool = False
    for v_idx, v in enumerate(vertices):
        ans |= dp[v_idx][(1 << num_colors) - 1]

    return ans


def find_colorful_subtree_naive(graph_info) -> bool:
    vertices, edges, v_to_idx, color_map, num_colors, g = create_graph(graph_info)

    # we take a set of vertices (2^(|V|)) and check if it is colorful (O(|V|))
    for s in range(1 << len(vertices)):
        if bin(s).count('1') < num_colors:
            continue
        # Check if the set is colorful
        colors: set[int] = set()
        for v_idx, v in enumerate(vertices):
            if (1 << v_idx) & s:
                if color_map[v] in colors:
                    break
                colors.add(color_map[v])
        if len(colors) == num_colors:
            # Check if the set of vertices is connected
            visited: set[str] = set()

            def dfs(v: str):
                visited.add(v)
                for u in g[v]:
                    if u not in visited and (1 << v_to_idx[u]) & s:
                        dfs(u)

            for v_idx, v in enumerate(vertices):
                if (1 << v_idx) & s:
                    dfs(v)
                    break

            if len(visited) == bin(s).count('1'):
                return True

    return False


# Generates all the index combinations of size k
# of the set of size n. For example, it = IndexIterator(4, 2)
# will return:
# (0, 1)
# (0, 2)
# (0, 3)
# (1, 2)
# (1, 3)
# (2, 3)
class IndexIterator:
    def __init__(self, n, k):
        self.n = n
        self.k = k
        self.indices = []
        self.index_set = set()
        for i in range(k):
            self.indices.append(i)
            self.index_set.add(i)

    def __str__(self):
        return ','.join(str(x) for x in self.indices)

    def get_indices(self):
        return self.indices

    def get_index_set(self):
        return self.index_set

    def increment(self):
        if self.indices[self.k - 1] < self.n - 1:
            self.index_set.remove(self.indices[self.k - 1])
            self.index_set.add(self.indices[self.k - 1] + 1)
            self.indices[self.k - 1] += 1
            return True

        for i in range(self.k - 2, -1, -1):
            if self.indices[i] < self.indices[i + 1] - 1:
                self.index_set.remove(self.indices[i])
                self.index_set.add(self.indices[i] + 1)
                self.indices[i] += 1

                for j in range(i + 1, self.k):
                    self.index_set.remove(self.indices[j])
                    self.index_set.add(self.indices[j - 1] + 1)
                    self.indices[j] = self.indices[j - 1] + 1

                return True

        return False


# Computes the graph inverse:
def compute_graph_inverse(vertices):
    g = {}
    for idx in range(len(vertices)):
        g[idx] = vertices[idx]

    return g


# Checks whether the current subgraph is k-colorful:
def is_colorful(it, k, g, inverse_g, color_map):
    visited = set()
    subgraph_node_indices = it.get_indices()
    subgraph_node_set = set()
    initial_node = None

    for idx in subgraph_node_indices:
        subgraph_node_set.add(inverse_g[idx])

        if not initial_node:
            initial_node = inverse_g[idx]

    dfs(initial_node, visited, subgraph_node_set, g, k)

    if len(visited) != k:
        return False

    return subgraph_has_distinct_colors(visited, color_map, k)


# Check whether we can k-color the input subgraph:
def subgraph_has_distinct_colors(subgraph, color_map, k):
    fltr = set()

    for node in subgraph:
        fltr.add(color_map[node])

    return len(fltr) == k


# The actual colorful subgraph algorithm:
def coderodde_colorful_subgraph(graph_info):
    vertices, edges, v_to_idx, color_map, num_colors, g = create_graph(graph_info)
    it = IndexIterator(len(vertices), num_colors)
    inverse_g = compute_graph_inverse(vertices)

    while True:
        if is_colorful(it, num_colors, g, inverse_g, color_map):
            # Once here, the input graph is k-colorable:
            return True

        if not it.increment():
            # All k-subgraphs exhausted without a match:
            return False


iterations = 40000


start = millis()
for _ in range(iterations):
    assert find_colorful_subtree(example_input_1)
    assert not find_colorful_subtree(example_input_2)
    assert find_colorful_subtree(example_input_3)
end = millis()

print("find_colorful_subtree in %d milliseconds." % (end - start))

start = millis()
for _ in range(iterations):
    assert find_colorful_subtree_naive(example_input_1)
    assert not find_colorful_subtree_naive(example_input_2)
    assert find_colorful_subtree_naive(example_input_3)
end = millis()

print("find_colorful_subtree_naive in %d milliseconds." % (end - start))

start = millis()
for _ in range(iterations):
    assert coderodde_colorful_subgraph(example_input_1)
    assert not coderodde_colorful_subgraph(example_input_2)
    assert coderodde_colorful_subgraph(example_input_3)
end = millis()

print("coderodde_colorful_subgraph in %d milliseconds." % (end - start))


# Creates a demo graph:
def create_graph_info(vertices, edges, colors):
    input = {
        "vertices": [],
        "edges": [],
        "color_constraints": {},
        "num_colors": colors,
    }

    # Create vertices:
    for i in range(1, vertices + 1):
        input["vertices"].append("v" + str(i))

    edges_left = edges

    # Create edges:
    while edges_left:
        u = random.choice(input["vertices"])
        v = random.choice(input["vertices"])
        if u != v:
            # Don't allow self-loops!
            input["edges"].append((u, v))
            input["edges"].append((v, u))
            edges_left -= 1

    # Produce the color map:
    for i in range(vertices):
        input["color_constraints"][input["vertices"][i]] = random.randrange(colors) + 1

    return input


benchmark_graph = create_graph_info(15, 40, 13)

start = millis()
print("find_colorful_subtree(...) returned %r." % find_colorful_subtree(benchmark_graph))
end = millis()

print("find_colorful_subtree(...) in %d milliseconds." % (end - start))

start = millis()
print("find_colorful_subtree_naive(...) returned %r." % find_colorful_subtree_naive(benchmark_graph))
end = millis()

print("find_colorful_subtree_naive(...) in %d milliseconds." % (end - start))

start = millis()
print("coderodde_colorfuL_subgraph(...) returned %r." % coderodde_colorful_subgraph(benchmark_graph))
end = millis()

print("coderodde_colorful_subgraph(...) in %d milliseconds." % (end - start))

The output is like:

find_colorful_subtree in 4360 milliseconds.
find_colorful_subtree_naive in 2331 milliseconds.
coderodde_colorful_subgraph in 2483 milliseconds.
False
find_colorful_subtree() in 8078 milliseconds.
False
find_colorful_subtree_naive() in 9 milliseconds.
False
coderodde_colorful_subgraph() in 1 milliseconds.

However, don't be fooled, which algorithm is the fastest depends heavily on the input graph topology and color settings. What comes to my coderodde_colorful_subgraph(...), the closer \$k\$ is to \$\vert V \vert\$, the faster it runs as compared to the smart DP solution.

\$\endgroup\$
13
  • 1
    \$\begingroup\$ I'd assume the authors of the paper assumed |E| > |V| to get rid of the |V| in the complexity? But fair enough, that was imprecise. \$\endgroup\$ Apr 8 at 16:11
  • \$\begingroup\$ "The idea is to consider only k combinations of the nodes". My naive algorithm did not do that because I was only checking if bin(s).count('1') < num_colors after the for loop but adjusting it with if bin(s).count('1') != num_colors should help a lot (thanks!). I don't know if generating the k combinations (I don't know what algorithm is under the hood) really is faster than doing for s in range(1 << len(vertices)): then if bin(s).count('1') != num_colors: though? \$\endgroup\$ Apr 8 at 16:15
  • 1
    \$\begingroup\$ @FluidMechanicsPotentialFlows You are almost there. So generating all k-combinations of an n-set runs in (n choose k) k and we multiply by the time required by DFS checking for connectedness of the k-subgraph. \$\endgroup\$
    – coderodde
    Apr 8 at 16:58
  • 1
    \$\begingroup\$ It is for my own practice \$\endgroup\$ Apr 9 at 9:44
  • 1
    \$\begingroup\$ @FluidMechanicsPotentialFlows Remember that an algorithm may be efficient on paper but slow in practice, and vice versa. For example, Fibonacci heap is faster in theory than, say, binary heap, yet both are comparable in practice. Also, Simplex is exponential in theory, yet performs well in practice. \$\endgroup\$
    – coderodde
    Apr 9 at 10:18

Your Answer

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

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