Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,404
questions
4
votes
2answers
228 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
117 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
112 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-...
10
votes
3answers
799 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
498 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
188 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
123 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
185 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
113 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
160 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
754 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 ...
5
votes
0answers
110 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
314 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 ...
2
votes
1answer
144 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
120 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
124 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 ...
-4
votes
1answer
179 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
78 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
170 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
52 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
149 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
59 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
142 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)$ ...
1
vote
1answer
134 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
149 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
205 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
285 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
98 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
144 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
68 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
133 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
59 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
195 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
72 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
126 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
158 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 ...
14
votes
0answers
155 views
NP-Hardness of 4-cycle packing problem in complete bipartite digraph?
A directed complete bipartite graph is a bipartite graph where there is exactly one directed edge between any two vertices from its two different parts. In other words, it's an orientation of a ...
7
votes
0answers
147 views
Algebraic methods for testing planarity
Mac Lane's planarity criterion states that a graph is planar if and only if it has a cycle basis such that each edge is contained in at most two cycles, we call such a basis a 2-basis. A 2-basis of a ...
6
votes
1answer
298 views
Complexity of finding the largest induced subgraph with all even degrees
What is the complexity of the following problem?
Instance: Simple, undirected graph $G$, and a positive integer $k$.
Question: Does $G$ have an induced subgraph on at least $k$ vertices, such that ...
5
votes
0answers
140 views
How much does treewidth changes after removal of a path?
Let $G$ be a graph such that $\mathrm{tw}(G)=t$. Let $t' = \min\limits_{u,v \in V(G)} \max\limits_{P \text{ is a path from } u \text{ to } v} \mathrm{tw}(G - P)$. Then how small $t'$ can be?
My ...
7
votes
2answers
436 views
Computing the edge orbits of a graph (and discussing definitions)
A (vertex) automorphism in a graph $G=(V,E)$ is a permutation $\sigma$ of the vertices that preserves adjacency, namely $\sigma(u) \sigma(v) \in E$ if and only if $uv \in E$. The automorphisms of a ...
-4
votes
1answer
121 views
10
votes
1answer
283 views
Lighting up all elements of a poset by toggling upsets
I consider the following game on a finite poset $(P, <)$. At each point of the game, I have a set of elements $S$ of the poset which are "on", and all others are "off". Initially $S = \emptyset$. ...
2
votes
0answers
92 views
How hard is it to determine ex(n,G)?
Define the extremal Turán function $ex(n,G)$ of a graph $G$ as the most edges a graph on $n$ vertices can have without having a subgraph that is isomorphic to $G$. This function is known ...
1
vote
1answer
230 views
Finding simple fixed length paths in directed graphs
Is there an efficient algorithm to enumerate unique simple fixed-length paths (of size $k$) in directed graphs? What would be its time complexity?
0
votes
1answer
273 views
Find the shortest s-t trail(edge disjoint path) in a graph with negative weight edges
A walk in a graph is a finite or infinite sequence of edges which joins a sequence of vertices. A trail is a walk in which all edges are distinct. Note that a trial may visit a vertex multiple times ...
1
vote
1answer
262 views
Breaking cycles in network graph by adding nodes and rerouting edges
I have a quite "common" need : making a directed graph (with one or several cycles) a directed acyclic graph (DAG).
But the way I want to achieve it is, I guess, way more specific : I would like to ...
9
votes
1answer
143 views
The source of the modular decomposition graph
When introducing graph modular decomposition, most authors use the 11-vertex graph, which I copy from wikipedia.
The question is who is (are) the original designer of it. (I'm not asking who drew ...
0
votes
1answer
134 views
Dividing a complete graph into two cliques with maximal sum of edge weights
Problem: Considering a complete weighted graph $G$ with $n$ vertices, where $n\in2\mathbb Z$ is an even number, remove edges in such a way that you end up with two cliques of graph $G$, each having $\...
