Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,317
questions
0
votes
0answers
27 views
The Edge Cover Equilibrium Problem
Let the Edge Cover Equilibrium Problem be the following:
INPUT: a simple undirected graph $G$.
OUTPUT:
YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
-3
votes
0answers
28 views
Algorithm to decide percentage of data from previous node, current node and forward nodes
I have a graph-like structure, let's say there is one node $C$, who has 2 predecessors $A,B$ and 1 successor $D$. I have a value of $C$. Let's say value at $C=30$%. From this, I could infer that
I ...
1
vote
0answers
72 views
Is the edge cover polytope integral on graphs with self-loops?
It is well known that the edge cover polytope is integral on simple graphs. I am wondering whether this also holds for graphs with self-loops.
Here is a Linear Relaxation of the edge cover polytope, ...
-4
votes
0answers
74 views
Argument that Graph Isomorphism is polynomial via reduction to CNF
In short we found 3 invertible transformations which imply
that Graph Isomorphism is polynomial.
Meta reasoning: Isomorphism preserving transformation CNF to "sparse"
CNF is possible and ...
0
votes
0answers
48 views
Comparing two graphs when starting from a single edge
Let's assume that we are given two graphs $G_1$ and $G_2$ defined by the two following nicely drawn pictures. Black numbers label the nodes, red numbers show the edge weight between the nodes.
$G_1$ ...
3
votes
1answer
96 views
Isomorphism preserving transformation CNF to Graph?
In short we are interested in isomorphism preserving
transformation CNF to Graph.
Let $\phi_1,\phi_2$ be CNF formulas.
Define $\phi_1$ and $\phi_2$ to be isomorphic $\phi_1 \cong \phi_2$
if there ...
0
votes
0answers
101 views
Is the matching polytope integral?
In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf
they prove the integrality of the matching polytope using the integrality of the perfect matching polytope.
The ...
4
votes
1answer
125 views
Neighborly properties in a bipartite graph
Input: Let $G$ be a connected, bipartite graph with parts $A$ and $B$, each of size $n$. For a set of vertices $S$, let $N(S)$ be its set of neighbors.
Question: Decide whether there exists a subset $...
1
vote
0answers
68 views
Uniquely 4-colorable Maximal Planar Graph Conjecture?
My question is on Uniquely 4-colorable Maximal Planar Graph Conjecture mentioned in
On purely tree-colorable planar graphs (and other papers of same(?) team such as "Theory on Structure and ...
1
vote
0answers
42 views
Non-rigid isomorphic structures
In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is ...
-1
votes
0answers
33 views
Reduce a decision problem to an optimization problem
In this paper, the author shows that finding an edge coloring that minimizes the total sum on a multi-tree is NP-hard.
In theorem 3.1, the author does so by reducing from 3SAT. I find his proof quite ...
1
vote
1answer
92 views
On the paper “Quantum Computing Hamiltonian cycles”
The paper Quantum Computing Hamiltonian cycles claims:
An algorithm for quantum computing Hamiltonian cycles of simple,
cubic, bipartite graphs is discussed. It is shown that it is possible to
evolve ...
3
votes
2answers
99 views
3-colourability of Eulerian maximal planar graph
The following paragraph is from this answer by David Eppstein (emphasis mine).
A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd wheel surrounding a single ...
2
votes
1answer
102 views
Who proved that a triangulation is 3-colourable implies its dual is bipartite
Let $G$ be a maximal planar graph (also called a triangulation); i.e, $G$ is a planar graph every face of which is a triangle. It is well known that the following three statements are equivalent:
(i) $...
1
vote
0answers
58 views
Quantum error correction and graph codes
I was reading combinatorial approach towards quantum correction. A lot of work in this is on finding diagonal distance of a graph. Let me add definition of diagonal distance so that this remains self-...
9
votes
3answers
630 views
Number of connected components of a random nearest neighbor graph?
Let us sample some big number N points randomly uniformly on $[0,1]^d$.
Consider 1-nearest neighbor graph based on such data cloud. (Let us look on it as UNdirected graph).
Question What would the ...
9
votes
1answer
332 views
Is the following graph optimization problem approximable within a constant factor?
Let $G=(V,E)$ be an undirected graph, and let $\pi$ be a permutation of the vertices in $V$.
For a node $v\in V$, we denote by $\text{pred}_{\pi}(v)$ (respectively $\text{succ}_{\pi}(v)$) the set of ...
10
votes
1answer
131 views
Is there a planar 4-regular graph that is 3-acyclic colourable?
A colouring is said to be an acyclic colouring if there is no bicoloured cycle (i.e each cycle gets at least 3 colours).
Burstein proved that 4-regular graphs are 5-acyclic colourable. It seems to me ...
3
votes
0answers
105 views
Graph problems in P with unknown lower bounds
I am looking for references to interesting graph problems, which are known to be in P, but their precise big-O lower bounds are elusive. I would split this into 2 classes:
problems, where we know of ...
-2
votes
2answers
113 views
Proof that optimal solutions of LP Relaxation of independent set are half-integral
I saw somewhere that optimal solutions of LP Relaxation of independent set are half-integral, by what I mean the possible values of a solution are ${ \{0,0.5,1 \} }$. I'm looking for proof of that.
...
0
votes
0answers
33 views
Different version of approximation complexity and algorithm for densest-k-subgraph problem
In the densest-k-subgraph problem, we are given a graph $G =(V,E)$ and $k$, and we are asked to find a set $S \in V$ of vertices to maximize the number of edges in the induced graph of $S$, i.e. $|Ind[...
1
vote
1answer
91 views
Intuition behind the Charikar's LP formulation for densest subgraph problem
I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in this paper.
Just mentioning the LP for maximum density of a ...
9
votes
1answer
146 views
Tree decompositions of optimal width where every vertex is in a bounded number of bags?
Let $G$ be a graph on $n$ vertices whose maximum degree is at most $\Delta$ and whose treewidth is at most $k$.
Does there exist a function $f(k, \Delta)$, independent of $n$, such that it is possible ...
7
votes
1answer
699 views
Algorithm for finding a 3-cycle cover
Given: An undirected, unweighted graph
Looking for: A disjoint vertex cycle cover where every cycle has at least 3 edges
Is there any algorithm that solves this problem, possibly with some ...
4
votes
0answers
103 views
Network design with reachability pattern
We are given two sets of terminals $A$ and $B$. For each $a\in A$, we are also given $R_a\subseteq B$. Let $|A|+|B|=n$.
We want to find a directed acyclic graph $G$ where $A$ and $B$ are subsets of ...
2
votes
2answers
228 views
Is the maximum independent set in cubic planar graphs NP-complete?
In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation ...
3
votes
1answer
136 views
How to efficiently find a loop between two nodes in a directed graph?
Given two nodes in a directed graph, how can I find a loop (if exists) that pass these two nodes? The loop cannot pass a node more than once. And if there isn't such a loop, how to efficiently ...
3
votes
1answer
110 views
What is the complexity of this weighted b-edge matching problem?
I'm wondering about the complexity of the following variant of the Generalized Weighted b-edge Matching problem:
Input: An undirected multigraph $G = (V, E)$ without
loops, an edge partition $(E_1,...
1
vote
1answer
94 views
Reference request: Depth- (or Breadth-) first search with hints?
Consider the standard s-t reachability problem of finding a path between nodes $s$ and $t$ in a directed graph $G$. A DFS or BFS could solve it.
Would it be possible to pre-process the graph and ...
0
votes
0answers
28 views
Best known bounds on feedback arcset in high-girth directed graphs?
I asked this question over at MathOverflow, but thinking about it a little more I think it is a more natural fit here.
Let $G$ be a directed graph with $n$ vertices and $m$ edges such that every ...
-4
votes
1answer
50 views
Distinguish Graph from Tree using Adjacency Matrix
Given an adjacency matrix, is there a way to determine if the graph will be a tree or a graph (whether or not there is a cycle).
For example, given the adjacency matrix:
...
2
votes
0answers
76 views
Variation of edge-disjoint spanning trees
In a directed graph, I want to find 2 edge-disjoint spanning trees (arborescence), with the extra restrictions that edges in the 1st tree are not forward arcs in the 2nd tree. Are there existing ...
8
votes
0answers
165 views
Sublinear time path existence
Consider a graph $G = (V,E)$ with $N$ edges. Consider two vertices $u_1, v_1 \in V$. We wish to find whether there exists a path of length $4$ between these two vertices or not. This is easy to do in $...
1
vote
1answer
49 views
When can partial spectral sparsifiers be combined?
A few important papers about spectral sparsifiers and friends contain a technical idea that involves building many different sparsifiers that each "partially" solve the problem, and then combining ...
0
votes
2answers
115 views
List of NP-Complete graph problems/ properties?
Is there a good source to find various decision problems on graph and networks? For a project I'm doing it'd be useful to be able to look at lots of different problems. Is there a good source for ...
1
vote
1answer
56 views
Reachability Query for Tree
What is the best complexity for reachability queries on trees so far please? There is no constraint on the directions of the edges in the tree. According to Mikkel Thorup, there is an oracle of size $...
0
votes
1answer
137 views
Problems that are NP-hard to approximate even when the input graph is regular
Are there graph problems which are NP-hard to approximate even when the input graph is regular?
For instance, are there optimization problems that are NP-hard to approximate within $O(n^\epsilon)$ ...
0
votes
1answer
102 views
Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?
We conjecture that Hamiltonian cycle is fixed parameter tractable with parameter clique cover, given $k$-clique cover.
Let $G$ be connected simple graph.
$k$-clique cover of graph $G$ is partition ...
5
votes
1answer
130 views
Known property? Maximum radius of connected induced subgraph
I was wondering if the following graph property has a name and has been researched:
Consider any connected induced subgraph $H \subseteq G$.
Then $r(G)$ denotes the maximum radius of any such $H$.
I ...
-2
votes
1answer
168 views
Minimum vertex cover and odd cycles
Suppose we have a graph G without odd cycles. 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}$, ...
1
vote
1answer
153 views
Fast Computation of First k Eigenvectors of Graph Laplacian
I'm looking for references for the following; Given the unnormalized Laplacian matrix of a graph $L = D - A, ~ L \in \mathbb{R}^{n\times n}$
Algorithm(s) to efficiently estimate the first $k$ (...
3
votes
0answers
89 views
Isomorphic subforest problem
I recently read that the following problem is NP-Complete:
Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$?
The reference provide was to the textbook “Computers and ...
2
votes
0answers
96 views
How to approach the “traveling salesman problem” with cost changing every time salesman reaches a new city
Let's say instead of finding the shortest path we have to maximize the profit in a year of the salesman under the following constraints.
Salesman can go to a different city only on weekends, all ...
0
votes
1answer
63 views
Reduction graph to planar bounded treewidth and bounded diameter graph
We got reduction graph to planar bounded treewidth graph,
but this is unlikely to be true.
Let $H$, the planarizing gadget, be planar graph with four
distinguished vertices $u,u',v,v'$ on the outer ...
4
votes
1answer
126 views
Hardness of finding if a vertex lies on a simple directed path between two vertices
Given a directed graph $G = (V, E)$ and three vertices $u, v, w \in V$. Is it NP-Hard to find whether there is a simple path from $u$ to $v$ passing through $w$?
I found a couple of hardness ...
2
votes
1answer
50 views
Maximum subgraph problem with unknown complexity
Let $Q$ be a polynomial time decidable graph property. In a graph let us call a subgraph $S$ a $Q$-subgraph, if $S$ has the property $Q$. Consider the following optimization problem:
Maximum $Q$-...
5
votes
1answer
187 views
Is this a known problem, and is it #P-complete?
Let $G=(V,E)$ be an undirected graph. What I call a selection function of $G$ is a partial function $f:V \to E$ such that for every node $v$, if $f(v)$ is defined then it is one of the adjacent edges ...
1
vote
1answer
64 views
Existence of graphs of every order related to Barnette’s conjecture
Consider the class C3CBP of $3$-connected cubic bipartite planar graphs. They form the class on which the (in)famous Barnette’s conjecture is based. My interest in C3CBP graphs is somewhat orthogonal ...
9
votes
2answers
117 views
Complexity of finding an edge set yielding specified vertex degrees
I'm trying to figure out if the following two problems are known in general to be in P or NP-complete:
Q1: Given a graph $G=(V,E)$ and integers $d_i,\,1\leq\,i\leq|V|$, does there exist a subset $E'\...
6
votes
2answers
146 views
$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$
Consider this graph partitioning problem: Let $G = (V, E)$ be a simple undirected graph and $0 \leq \epsilon \leq 1, M \geq 0$ be constants. Are there disjoint subsets $V_1, V_2$ with $V = V_1 \cup ...
