All Questions
Tagged with complexity-theory graphs
371
questions
0
votes
1answer
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 ...
0
votes
1answer
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. ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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$). ...
0
votes
2answers
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 ...
0
votes
0answers
32 views
A relaxation-free variant of Dijkstra's shortest path algorithm
I have come up with a relaxation-free variant of Dijkstra's shortest path algorithm, and I would like to see if it's correct. Here is the pseudocode for finding the shortest distance from a node $\...
0
votes
2answers
71 views
Reduction between CLIQUE to SUBSET SUM
I have a question from a test that I failed to pass, I failed to do the question.
The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the ...
0
votes
1answer
30 views
Reduction from the Clique problem to the Odd Clique problem
I have a question that is not clear to me, and I have not been able to answer it from a test I had.
This is the question:
Let's look at the problem $Oclique$ , In it we get a graph $G = (V,E)$ , And ...
1
vote
0answers
22 views
Research on exact-cover problem and graph theory for NP-complete problems? [closed]
Sorry for the vagueness, but I'm trying to study the latest progress on the exact cover problem and using graphs for NP-complete problems. Googling around has not been very helpful. I understand the ...
0
votes
0answers
36 views
Build a Turing machine to prove that a problem is $NL$
If we the language $A$, which is defined like this:
$$A = \{\langle G,s,t \rangle \} \mid \text{ There is a maximum path in graph $G$ that begin in $s$} \} $$
I want to build a Turing Machine that ...
0
votes
1answer
85 views
Counting strongly connected components in a directed graph in $NL$
Define $K\_SCC = \{ \langle G, k \rangle \,:\, G \text{ has at least $k$ strongly connected components} \}$
I want to show that $K\_SCC \in NSPACE(\log n)$, using that $st-CONN$ and $\overline{st-CONN}...
3
votes
1answer
39 views
Is there a way to study precisely the complexity with respect to the size of vertex set for some graph problem?
Suppose there is graph problem $L$ such that the instance $x$ of $L$ is a simple graph with $n$ vertices and $m$ edges.
In the Turing machine model, we can encode a graph using $O(n^2)$ cells or $O((m+...
1
vote
1answer
35 views
Polynomially Equivalent Pairs of Minimization-Maximization Problems in Weighted Graphs
I am studying computational complexity using Papadimitrious's book: "Computational Complexity". I am trying to solve Problem 9.5.14, about polynomially equivalent minimization-maximization ...
3
votes
0answers
52 views
Minimum Vertex Cover of 2 vertex disjoint odd cycles that have edges between them
Consider the graph $G$, which is comprised of 2 vertex disjoint odd cycles ($C_1$, $C_2$) where $|C_1|$ and $|C_2| \geq 5$. $G$ is sub-cubic and connected, with edges in between the cycles. Because $G$...
0
votes
0answers
33 views
Looking for prior occurrences of $k$-CNF efficiently translated to coloring?
Has anyone else ever translated 3-cnf (4-cnf) on $N$ variables and $M$ clauses
into 4 coloring on $O(M)$ vertices? By taking two variables from a clause,
the four boolean combinations correspond to ...
0
votes
1answer
33 views
Space complexity of a variant of st-connectivity
Consider a variant of STCON, called 2STCON, which is defined like this:
$$2STCON = \{\langle G,u,v \rangle \} \mid \text{$G$ is a graph with } \mathit{two} \text{ paths from $u$ to $v$} \} $$
This ...
2
votes
1answer
49 views
How is Hypergraph Isomorphism (HI) reduced to Graph Isomorphism (GI) in polynomial time?
This question states that the problem of Hyper-graph Isomorphism is equivalent to Graph isomorphism. I have not been able to find a description of the reduction so I am wondering how that might work ...
3
votes
1answer
64 views
Why do we use DAG rather than trees to represent search space of a search problem?
I saw people use DAGs to represent the search space of a search problems like the travelling salesman problem. Why is this better than the tree representation? Is the reason to save memory space on ...
0
votes
1answer
44 views
Vertex cover of minimal graph
I'm looking for algorithm that, for given undirected graph $G=(V,E)$, find graph $G'=(V,E')$ with minimal amount of edges that have same vertex cover as G. I mean, vertices $U$ are vertex cover of $G$ ...
3
votes
0answers
42 views
Hardness of an instance of a problem independent of algorithms?
The paper “Where the really hard problems are” (https://www.ijcai.org/Proceedings/91-1/Papers/052.pdf) and others that cite it provide evidence that lots of algorithms for many NP complete problems (...
1
vote
1answer
43 views
What is the complexity class of finding vertex cover number of a simple graph?
Suppose we have a simple graph $G$. We know that finding the minimum vertex covering set for $G$ is in the NP-hard class. But, what about the complexity class of finding the size of the set, i.e., the ...
1
vote
1answer
14 views
Is it possible to compute the minimum vertex covering set in quasi-polynomial time, by knowing the vertex cover number?
If we know the vertex cover number for a simple graph $G$ denoted by $\tau(G)$, is it possible to find the minimum vertex cover set for $G$ in quasi-polynomial time? As I found, we cannot find any ...
1
vote
2answers
32 views
Given a list of vertices in a binary tree output minimal sublist with the same lowest common ancestor
The input: a binary tree and a list $L$ of vertices in that tree.
The output: a sublist of $L$ of minimal length that has the same lowest common ancestor as $L$. If there is several sublists of ...
2
votes
2answers
104 views
Find maximal clique consisting of at least half of the vertices
Assume that we are given an undirected graph $G$ of n vertices. For this graph, we also know that there is a clique of size $c$, for some $c\geq \lfloor n/2 + 1\rfloor$. In other words, the majority ...
0
votes
1answer
52 views
Reduce Clique to N-Degree-Clique
I want to show that there is a polynomial-time reduction from the standard $\text{Clique}$ problem to the $\text{N-Degree-Clique}$ problem, where:
$$ \text{N-Degree-Clique} = \{ \langle G, k\rangle: \...
0
votes
1answer
88 views
4 Vertex Cover Problem is not NP Complete why?
With Given Graph $G$ why finding that $G$ has a vertex cover of at most $4$ is in $P$ and Not in NP Complete. it means there us poly-time algorithm for this problem !!?
8
votes
1answer
1k views
Is there a simple argument why graph isomorphism is not NP-complete?
I need to provide one simple evidence that graph isomorphism (GI) is not NP-complete.
I saw a number of papers on google scholar and answers on StackExchange. However, I have very limited knowledge of ...
2
votes
2answers
50 views
Parall execution of algorithms that solves polynomically disjoint subsets each of a NP-hard problem
I was thinking in the following approach for solving a problem that is believe to be a NP-hard problems today in polynomial time, assuming the following:
There exists a believed-today NP-hard problem ...
0
votes
1answer
57 views
Bottleneck TSP with repeated nodes
I am aware that the traveling salesman problem (TSP) and the bottleneck TSP problem is NP-hard for complete directed graphs. I am also aware that regular TSP that allows a path with repeating is also ...
0
votes
1answer
251 views
3SAT and directed graph
Given a 3SAT instance (a Boolean expression in three conjunctural normal form), we draw a directed graph, where for each Boolean variable $x_{i}$ we have the nodes $x_{i}$ and $!x_{i}$; for each ...
6
votes
0answers
535 views
What could we say about that conjecture that yields P != NP?
Let $F$ be the set of all Boolean formulae.
We say that a Boolean formula $\varphi$ is positive (=monotone) if
$\forall \alpha\in F,i\leq n$, if $\alpha\wedge\neg x_i\models\varphi$, then $\alpha\...
2
votes
0answers
185 views
Minimum vertex cover and odd cycles [closed]
Suppose we have a graph $G$. Consider the minimum vertex cover problem of $G$ formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $...
1
vote
3answers
2k views
Greedy algorithm for vertex cover
Given a graph $G(V, E)$, consider the following algorithm:
Let $d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $d\geq 1$)
Let $v$ be one of the vertices with ...
2
votes
0answers
107 views
Reducing Dominant Set Problem to SAT
I am trying to solve a problem and I am really struggling, I would appreciate any help.
Given a graph $G$ and an integer $k$ , recognize whether $G$ contains dominating set $X$ with no more than $k$ ...
0
votes
1answer
684 views
Worst Case for AVL Tree Balancing after Deletion
After deleting a node in an AVL tree, self-balancing (zig-zag rotation or the left-right balancing) maintains O(logn) time that is not guaranteed in other unbalanced trees (like BST).
The Balancing ...
21
votes
9answers
5k views
Is Group Theory useful in Computer Science in areas other than cryptography?
I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot ...
4
votes
1answer
221 views
What is the goal of studying all those NP-complete problems?
So i'm currently reading a lot of things about graph NP-complete problems, and it seems that the goal of a lot of researchers is to find new results about their complexity, results like "...
1
vote
1answer
110 views
Why minimum vertex cover problem is in NP
I am referring to the definition of the minimum vertex cover problem from the book Approximation Algorithms by Vijay V. Vazirani (page 23):
Is the size of the minimum vertex cover in $G$ at most $k$?
...
0
votes
1answer
97 views
Reducing 3-coloring problem to trio representatives
A group of students is divided into trios - groups of 3 members. Each student can be assigned to more than more trio. We want to assign their representatives, by choosing exactly one member of each ...
1
vote
0answers
41 views
Dividing students into 4 groups based on preferences is NP-complete
Given a set of students $H$ of size $n$, and a set $E \subseteq H \times H $ of pairs of students that dislike each other, we want to determine whether it's possible to divide them into $4$ groups ...
3
votes
0answers
49 views
Is there a *natural* problem that is NP-hard on trees, but in P on non-trees?
It seems intuitive that any natural problem that is NP-hard on trees, should be hard on graphs that are not trees. But perhaps this is wrong?
Question: Is there some natural decision problem on ...
0
votes
1answer
383 views
What time complexity is a reachability algorithm?
I've read there are ways you can determine all reachable pairs using Strongly Connected Components. But, I want to calculate all reachable nodes on the fly - so I don't have to store a massive ...
1
vote
2answers
90 views
Is $\frac{n}{3}$-CLIQUE NP-complete?
Consider the problem
$\frac{n}{3}$-CLIQUE:
determining whether a graph contains a clique with at least $n/3$ vertices.
I want to prove it is NP-complete using a polynomial transformation from CLIQUE.
...
