# All Questions

371 questions
Filter by
Sorted by
Tagged with
60 views

### How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time

This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani. Specifically, the problem statement is: Give a linear-time algorithm that ...
17 views

### Maximal edge weight clique of given size

Let $G$ be an undirected fully connected weighted graph with $N=|V|$ vertices. Given $M<N$ we wish to choose $M$ vertices such that the sum of weights between the chosen vertices is maximal, i.e. ...
75 views

### Prove finding a spanning tree with no more than 50 leaves is NP-hard

This is a homework question. Consider the problem of finding if an undirected graph $G$ can have a spanning tree with no more than 50 leaves. Is this problem NP-hard? I think it is and I'm trying to ...
25 views

### Finding the homomorphism between two homomorphic graphs: what is the name of this problem?

The "graph homomorphism problem" can be stated as: given two graphs $G$ and $H$, determine if there exists a homomorphism $f$ such that $f: G \rightarrow H$. This is a famous problem that is ...
23 views

### Attempting to verify the colorability using Wigderson's Algorithm

The algorithm of Wigderson (see here) can color a graph that is known to be $3$-colorable in $O\left( \sqrt{\left| V \right|} \right)$ colors. This is done in $O\left( |V| + |E|\right)$ time. For ...
59 views

### Currently best approximation for graph coloring

As we all know it is $NPH$ to check whether $G=(V,E)$ is $k$-colorable or not. It is also hard to find the chromatic number of $G$. But I'd like to ask what are some good (or best known) approximation ...
58 views

### Square of a directed graph $G=\left< V, E\right>$

I have this question from CLRS book please. Question: The square of a directed graph $G=\left< V, E\right>$ is the graph $G=\left< V, E^2\right>$ such that $(u,w) \in E^2$ iff for some ...
24 views

### Finding maximum clique given, for each edge, union of all cliques containing it

For every edge $e\in E$ of a graph $G=(V,E)$ we know the union $U_{e}$ of the edges of all cliques that contain $e$. Can we determine, in polynomial time, for a given edge $e_{0}\in E$, the size of ...
48 views

### Why is Independent Set "at least" and Vertex Cover "at most" k

The decision version of the Independent Set and Vertex Cover problems are phrased as: Given a graph G and a number k, does G contain an independent set of size at least k? Given a graph G and a ...
40 views

### What if have a algorithm that could generate a NFA of 42 states of any binary string of 2^32 length?

For example, if we have a true algorithm that could generate any NFA of at most 42 states from any binary string of 2^32 length. So, this algorithm can not just recognize the string but just recreate ...
23 views

### Complexity of checking graph separation

Let $G=(V,E)$ be an undirected graph and $A,B,C\subset V$ disjoint subsets of $V$. I want to check whether or not $A$ and $B$ are separated by $C$ (i.e. every path from $A$ to $B$ passes through $C$). ...
126 views

### Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k

I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G. My algorithm is as follows: Generate all subgraphs of size k, and check ...
32 views