All Questions
Tagged with complexity-theory graphs
349
questions
3
votes
1answer
51 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
35 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
36 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
9 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
9 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
29 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
71 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
42 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
78 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 !!?
7
votes
1answer
927 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
35 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
74 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
525 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\...
1
vote
0answers
97 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 $...
0
votes
3answers
858 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
43 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
128 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 ...
22
votes
9answers
4k 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
213 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
44 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
45 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
40 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 ...
0
votes
0answers
18 views
Reference on PCP theorem
Can someone recommend a reference on the PCP theorem that explains how it works via examples rather than formal CS language?
Specifically, I'm looking for the example on how graph colouring can be ...
3
votes
0answers
45 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
145 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
71 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.
...
1
vote
0answers
188 views
Example of *small* non monotone circuit such that any equivalent monotone circuit has greater size?
A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT ...
2
votes
1answer
76 views
Is it assumed that lower bounds on the size of monotone circuits apply to general Boolean circuits too?
A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT ...
2
votes
1answer
53 views
Vertex cover problem modification such that every vertex is connected to the set, NP-Hard?
Being new to complexity problems, I've met a question that is quite similar to the Vertex Cover Problem and I am not sure if this one is NP-Hard. We know that the vertex cover problem is the following:...
2
votes
1answer
43 views
Does this problem map to the Set Packing problem?
Let $G(m,n)$ be A bipartite graph $G$ with paritions $m$ and $n$ with the property that partition $\mathit n$ has two types of nodes (type1 or type2).
Given $G(m,n)$ and $k \in \mathbb Z+$:
Does $\...
1
vote
2answers
86 views
Proving NP-completeness of a surveilled graph problem
So suppose I have a graph consisting of a tuple $(V,E,A,g)$ where $V$ denotes vertices, $E$ denotes edges, $A$ denotes a subset of $V$ (i.e. $A \subseteq V$), and $g:A\rightarrow\mathbb{N}$ is a ...
2
votes
0answers
58 views
Efficient algorithm for enumerating minimal vertex separators
Let $G$ be a non-empty connected undirected graph, which is not a complete graph. We treat $G$ as a set, writing $G \setminus \{v\}$ for vertices $v$, etc; subsets of $G$ should be understood as ...
4
votes
1answer
249 views
Maximum matching in a bipartite graph
Given a bipartite graph $G=(V_1 \cup V_2, E)$ and a set $V' \in (V_1 \cup V_2)$. What is the complexity of finding a maximum matching in $G$ that uses only $x$ vertices from $V'$?
1
vote
0answers
52 views
Minimum-cut with balanced and limited number of nodes in each partition: Does this have an efficient solution or even a name?
I'd like to remove the minimum number of edges from an undirected unweighted graph to partition the nodes into an arbitrary number of connected components $S_1$, $S_2$,$S_3$,... $S_k$ while maximizing ...
0
votes
0answers
80 views
Sliding Puzzle w/ multiple solutions
I am trying to write an algorithm which produces a solution to a modified n by n sliding puzzle (assuming that an end state is reachable from the given start state). The change is as follows: tiles ...
0
votes
1answer
56 views
Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC
i don't understand the following:
If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting ...
2
votes
1answer
169 views
Find and prove a linear algorithm that identifies all cycles and the length in a graph where each vertex has exactly one outgoing edge
Consider a directed graph on n vertices, where each vertex has exactly
one outgoing edge. This graph consists of a collection of cycles as
well as additional vertices that have paths to the cycles,...
2
votes
0answers
85 views
Class of languages recognizable by n-bit formulas of size at most $T(n)$
A Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT nodes
fan-...
2
votes
0answers
26 views
planar max cut graph with constrains
Given a planar graph $G=(V, E)$
I am looking for a max cut algorithm with the following conditions : some vertices are in one of the partition sets?
Is the algo is still polynomial ?
I mean a ...
0
votes
1answer
34 views
Dominating set in bounded degeneracy and bounded degree graphs
I believe Minimum Dominating Set (MDS) is NP-hard for bounded
degeneracy and their subset bounded degree graphs, but
a paper appear to suggest tractability.
Enumeration of Minimal Dominating Sets and ...
2
votes
1answer
124 views
Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?
Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k)
polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a ...
1
vote
2answers
232 views
Clique-problem for planar graph
I have to show, that the clique problem in planar graphs is in P. I found the answer here here. However I don't get the conclusion
This follows already from Kuratowski's theorem: a clique is at ...
4
votes
0answers
30 views
Strongly connected subgraph that contains no negative cycles
Is there an efficient algorithm that solves the following decision problem:
Given a strongly connected weighted directed graph $G$, defined by its transition matrix, is there a strongly connected ...
4
votes
2answers
36 views
Complexity of list coloring $K_n$ with $n$ colors
The list coloring problem is, given a set $L(v)$ colors for each vertex $v \in G$, is there a proper vertex coloring, $c$, of $G$, such that $c(v) \in L(v), \forall v$.
I was wondering, for complete ...
3
votes
1answer
304 views
O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?
I came up with this O(V+E) algorithm for calculating the chromatic number X(g) of a graph g represented by an adjacency list:
Initialize an array of integers "colors" with V elements being 1
Using ...
3
votes
2answers
131 views
Coloring an interval graph with weights
I have an interval graph $G=(V,E)$ and a set of colors $C=\{c_1,c_2,...,c_m\}$, when a color $c_i$ is assigned to a vertex $v_j$, we have a score $u_{ij}\geq 0$. The objective is to find a coloring of ...
5
votes
1answer
87 views
Partition into paths in a Directed Acyclic Graphs
I have a directed acyclic graph $G=(V,A)$, I want to cover the vertices of $G$ with a minimum number of paths such that each vertex $v_i$ is covered by $b_i$ different paths.
When $b_i=1$ for all the ...
1
vote
0answers
45 views
Is Dots and Boxes complementary to the game of Go?
I've read that La Pipopipette is known to be NP-hard. I have not yet found analysis specifying an exact complexity class for Dots and Boxes, or for some variations in the analysis of Go.
Here's a ...
2
votes
1answer
51 views
Finding a vertex coverage that is also an independent set
Given a graph $G$ and integer $k$, find a vertex coverage set of size $k$ that is also an independent set. I need to either prove this problem is np-complete or find a polynomial solution. Any idea?
