Colorful Subgraph Dynamic Programming Solution and a Naive One

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.