4
votes
1answer
126 views

Complexity of the decision version of determining a min-cut

I was wondering what the complexity of the following problem is: Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$. Question: Is there an $s$-$t$ cut of capacity at most ...
7
votes
4answers
202 views

Recovering a point embedding from a graph with edges weighted by point distance

Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the ...
5
votes
1answer
58 views

Easy infinite subclass of cubic graphs for Hamiltonian cycle problem

I know that Hamiltonian cycle problem is $NP$-complete for 2-connected planar bipartite cubic graphs. I'm interested in non-trivial infinite subclass of cubic graphs where the Hamiltonian cycle ...
4
votes
1answer
35 views

First Order interpretation of arbitrary structures as a graph

I am currently trying to get some intuition on the concept of First Order reductions, and have come across this exercise question by Immerman, dubbed "Everything is a Graph". Given some arbitrary ...
1
vote
0answers
61 views

Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time?

Assumptions: given a graph with N nodes, and two specific nodes A and B the graph is undirected and no edge has a negative cost there exists at least one Hamiltonian path with A and B as an end ...
1
vote
1answer
55 views

To show that a graph-problem is in $L$ or $NL$

Consider the following problem: $$A=\left\{ (G(V,E),s,t)\mid\text{conditions 1, 2, 3 and 4 hold} \right\}$$ $G$ is a directed graph. $s,t\in V$. There is a simple path from $s$ to $t$ (a simple ...
4
votes
1answer
58 views

Complexity of calculating independence number of a hypergraph

Let $G$ be a "hypergraph", a collection of vertices $V=\{v_1,v_2,\ldots,v_n\}$ and a collection of "hyperedges" $E=\{e_1,e_2,\ldots,e_m\}$, where $e_i\subseteq V$ and unlike normal edges, an edge may ...
0
votes
1answer
51 views

Relation between digraph and NP-Complete problem

Can there be any relations regarding the number of nodes available in a digraph so that to qualify it as NP-Complete problem. If we consider this problem for instance: Input: A digraph $G=(V,E)$ and ...
3
votes
1answer
168 views

Proving NP-completeness of a graph coloring problem

Given a graph $G=(V,E)$ and a set of colors $k<V$. Find a assignment of colors to vertices that minimizes the number of adjacent vertices in conflict. (Two adjacent vertices are in conflict if they ...
2
votes
1answer
108 views

Why is determining the size of a maximum independent set or a clique in P?

I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard. With respect to ...
2
votes
1answer
68 views

Reducing 3SAT to Triangle Cover Graph

The Triangle Cover Graph problem is this: Given a graph $G = (V,E)$ and an integer $k$, does there exist a set of at most $k$ vertices of $G$ such that every triangle contained in $G$ also ...
2
votes
0answers
100 views

Intractable properties of Two-factor in connected bridgeless cubic graphs

Petersen's Theorem states that every cubic, bridgeless graph $G(V, E)$ contains a 2-factor $F$ (and therefore a perfect matching $E-F$). Alternatively, 2-factor is a set of vertex disjoint cycles that ...
2
votes
1answer
552 views

Counting and finding all perfect/maximum matchings in general graphs

Recently i've been dealing with a problem that led me to the following questions: Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph? Is there a good algorithm ...
2
votes
1answer
61 views

Reduction from max-cut to min-cut

Algorithms for the finding of an MST in a graph can be applied for both maximum and minimum spanning trees. It is well known, however, that the finding of a max-cut in a graph is an NP-hard problem ...
7
votes
4answers
159 views

Problems that are NP but polynomial on graphs of bounded treewidth

I heard here that the Hamiltonian cycle problem is polynomial on graphs of bounded treewidth. I am interested in examples/references to different problems which is essentially hard but having ...
9
votes
2answers
126 views

Hard computational problem on special class of bipartite graphs

I am interested in the properties of a class of bipartite graphs $G(X \cup Y, E)$ where all nodes in $X$ are 3-regular, all nodes in $Y$ are 2-regular, and $|X|=|2Y/3|$. First, Is this a well known ...
1
vote
1answer
31 views

Complexity class of Determining Hamiltonian cycle

I Know that determining Hamiltonian cycle in a graph is NP complete. For the sake of my clarification, I just want to know that whether the problem remains NP complete with following restrictions ? ...
9
votes
1answer
213 views

$O(n^{k-1}$) algorithm for K-clique problem

Clique problem is a well known $NP$-complete problem where the size of the required clique is part of the input. However, k-clique problem has a trivial polynomial time algorithm ($O(n^k)$ when $k$ is ...
7
votes
4answers
106 views

Negative weight cycle vs maximum weight cycle

I'm having trouble understanding why it's easy to detect negative-weight cycles (Bellman Ford) but hard to find the maximum weight cycle in an undirected graph. If we negate the weight of each edge, ...
7
votes
2answers
177 views

Software for testing graph homomorphism

I have graphs $G_k$ and $H_k$ with $|\mathcal{V}(G_k)|=|\mathcal{V}(H_k)|^{2k}=n^{2k}$ with $k\in\Bbb N$ that pass sanity checks such as no-homomorphism lemma. Are there free and easy to use tools to ...
2
votes
2answers
105 views

Direct reduction from Near-Clique to Clique

An undirected graph is a Near-Clique if adding one more edge would make it a clique. Formally, a graph $G=(V,E)$ contains a near-clique of size $k$ if there exists $S\subseteq V$ and $u,v\in S$ ...
6
votes
2answers
101 views

Courcelle's Theorem: Looking for papers

I am looking for an easy and introductory paper on the proof of Courcelle's Theorem. I am also interested in its connection to parameterized complexity regarding the treewidth. I am only a beginner ...
2
votes
1answer
54 views

Is there a graph product that is multiplicative in independence number?

I know that Stable set cannot be approximated to constant factor. I saw a simple proof using OR product sometime back. I am unable to recall it. If anyone here knows what I am talking about could help ...
2
votes
1answer
68 views

What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero?

Suppose we are given an M×N matrix, with some elements are zero, some non-zero. We know the co-ordinates of non-zero elements. Now, if I am allowed to multiply a whole row or a whole column by zero ...
1
vote
0answers
55 views

Counting modified perfect matchings

Consider a bipartite graph with vertex set partitioned into $X=\{u_1,u_2,u_3\}$ and $Y=\{v_1,v_2,v_3\}$. Consider the graph has the following edges: $\{u_1,v_1\}$, $\{u_2,v_2\}$, $\{u_2,v_3\}$, ...
5
votes
1answer
137 views

Complexity of finding a spanning tree that minimizes the maximum interference

Given $n$ nodes in the plane, connect the nodes by a spanning tree. For each node $v$ we construct a disk centered at $v$ with radius equal to the distance to $v$’s furthest neighbor in the spanning ...
4
votes
1answer
52 views

Max cut in cubic graphs

The following question is related to the max cut problem in cubic graphs. In this survey paper Theorem 6.5 states A maximal cut of a cubic graph can be computed in polynomial time Browsing ...
7
votes
1answer
231 views

Find which vertices to delete from graph to get smallest largest component

Given a graph $G = (V, E)$, find $k$ vertices $\{v^*_1,\dots,v^*_k\}$, which removal would result in a graph with smallest largest component. I assume for large $n = |V|$ and large $k$ the problem ...
3
votes
1answer
176 views

Coordinated Attack Problem On The Arbitrary Graph

Let consider a general version of Two Generals' Problem, when there are $n$ generals located on the arbitrary graph and they should agree on exactly the same value whether to attack or not to attack. ...
-3
votes
3answers
116 views

Does reachability belong to P?

Reachability is defined as follows: a digraph $G = (V, E)$ and two vertices $v,w \in V$. Is there a directed path from $v$ to $w$ in $G$? Is it possible to write a polynomial time algorithm for it? ...
4
votes
1answer
461 views

Longest path in grid like graph

This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness: Find the length of the longest ...
1
vote
1answer
80 views

Is there a program to solve a metric TSP for 80 edges at optimum?

i'm going to use the Christofides heuristic algorithm in order to solve a TSP for about 80 edges. Eventually i should have a solution, that is within the factor 1.5 of the optimum. But when i'm ...
1
vote
1answer
448 views

Show that Vertex-Cover is NP-complete, using Stable-Set

My task is to give proof, the Vertex-Cover problem is NP-complete, assuming it's already shown that the Stable-Set problem is NP-complete, too. My approach: i know, Stable-Set is NP-complete, and all ...
1
vote
3answers
140 views

k-path problem - P, NP or NPC?

I need to determine which complexity class this problem belongs to: Given a graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of length $k$ exist between thesee two ...
2
votes
0answers
54 views

End-Of-The-Line Augmented Problem of PPAD

Famous PPAD class of problems is formally defined by specifying one of its complete problems, known as End-Of-The-Line: End-Of-The-Line Problem: $G$ is a (possibly exponentially large) directed ...
3
votes
1answer
144 views

How to reduce INDEPENDENT SET to INDEPENDENT SET SIZE?

Suppose you are given a polynomial-time algorithm for the following problem related to INDEPENDENT SET: INDEPENDENT SET VALUE Input: An undirected graph G. Output:The size of the largest ...
0
votes
2answers
361 views

Can the edges of a graph be assigned directions such that all nodes in a given subset have in- or outdegree 0, and every other node indegree > 0?

In a directed graph, the indegree of a node is the number of incoming edges and the outdegree is the number of outgoing edges. Show that the following problem is NP-complete. Given an undirected graph ...
0
votes
3answers
858 views

How to check whether a graph is connected in polynomial time?

I have to solve the following problem: Consider the problem Connected: Input: An unweighted, undirected graph $G$. Output: True if and only if $G$ is connected. Show that Connected ...
2
votes
1answer
45 views

complexity of finding the hampath of length $k$ in a graph with $n$ vertexes where $k < n$

A simple question: What would be the complexity of finding whether a hampath of length $k$ exists in a graph with $n$ vertexes where $k < n$? Would this be in NP-complete or just NP?
5
votes
0answers
61 views

Decomposition of graphs that uses centers

Do you know of any kind of decomposition of graphs that involves centers, especially in the context of parametrized complexity? If so, please provide some reference. If not, do you see any reason ...
2
votes
1answer
239 views

How to analyze the Steiner tree problem?

I have a problem where I am supposed to analyze the Steiner tree problem by doing the following 3 steps. 1) Look up what the Steiner tree problem is. 2) Find a ...
3
votes
1answer
191 views

Prove finding a near clique is NP-complete

An undirected graph is a near clique if adding an additional edge would make it a clique. Formally, a graph $G = (V,E)$ contains a near clique of size $k$ where $k$ is a positive integer in $G$ if ...
2
votes
0answers
58 views

Complexity of computing the first bits of a minimal permuted adjacency matrix

Given any graph $G$ on $V(G)=\{1,\dots,n\}$ and its adjacency matrix $$A(G)=\left(\matrix{ A_{1,1} & A_{1,2} & \dots & A_{1,n}\\ A_{2,1} & A_{2,2} & \dots & A_{2,n}\\ ...
0
votes
0answers
44 views

The name of “finding the path of a graph that is a variant of hamiltonian path”

Suppose that there is some graph, with $n$ vertexes. We wish to find the hamiltonian path, but we make the graph being searched a little different. There is a person A that travels each (undirected) ...
3
votes
3answers
238 views

Find node that splits tree in half

Given a tree $T = (V , F)$, find an algorithm which finds $u \in V$, so in the graph $T = (V \setminus \{u\} , F)$ the size of each connected component is $\lceil |V| / 2 \rceil$ at most. What is ...
1
vote
2answers
65 views

Prove that $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete

I need to prove that the following problem $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete. Given a finite set of variables $V$, a finite set of inequalities of the form $x \le y$ (where $x, y \in ...
1
vote
1answer
56 views

Prove that 2-Colourability is in L from Undir-Reachability is in L

Let Undir-Reachability be the following problem: given an undirected graph G and two specified vertices s and t in G, is there a path from s to t in G? I need to prove that the 2-Colourability is in ...
2
votes
0answers
95 views

Travelling salesman problem with detours

I am interested if there exists a following version of the travelling salesman problem: INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each ...
2
votes
2answers
2k views

How to understand the reduction from 3-Coloring problem to general $k$-Coloring problem?

3-Coloring problem can be proved NP-Complete making use of the reduction from 3SAT Graph Coloring (from 3SAT). As a consequence, 4-Coloring problem is NP-Complete using the reduction from 3-Coloring: ...
1
vote
1answer
72 views

For what values of A and B is the gap-VC-[A,B] problem NP-HARD?

For which values $A,B$ is the problem $\mathsf{gap\mathord-VC}\mathord-[A,B]$ NP-hard? VC is the vertex cover problem. I am given three options: $B=\frac{3}{4},A=\frac{1}{2}$ or ...