Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,320
questions
1
vote
0answers
139 views
+100
Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?
In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the ...
5
votes
1answer
114 views
+50
Complexity of finding the most likely edge
Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes.
Now consider the following random process. First sample a uniformly random ...
0
votes
1answer
42 views
Sample graph dataset for testing algorithms
I hope I'm addressing the right community. For a project for my students, I need to find some weighted graphs (oriented or not) to benchmark their algorithms (shortest paths, flows...).
There are a ...
1
vote
0answers
25 views
Minimum graph cycle basis respect to non-empty pairwise intersection of cycles
I'm trying to understand the following problem if anyone can help I'll be very grateful
Instance: undirected, unweighted, connected graph graph $G=(V,E)$.
Question: find a minimum cycle basis $B = \{...
2
votes
0answers
47 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
74 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
77 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
50 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
97 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
104 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 ...
3
votes
2answers
100 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 ...
1
vote
2answers
731 views
Does this notation have a special meaning?
I am currently reading a paper and I don't know how to interpret this notation you can see on the screenshot.
http://moxn.brainex.de/pub/dfg.png
Do the pointy angle brackets have a special meaning ...
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 ...
9
votes
3answers
631 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 ...
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 ...
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
1answer
93 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 ...
7
votes
4answers
978 views
Trees: complexity of counting the number of vertex covers
Which is the complexity of counting the number of vertex covers of trees? Is it still #P-complete, as for general graphs?
1
vote
0answers
59 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-...
13
votes
3answers
938 views
Relation between tree-width and clique number
Are there any nice graph classes for which the tree-width $tw(G)$ is upper-bounded by a function of the clique number $\omega(G)$, i.e. $tw(G)\leq f(\omega(G))$?
For example, it is a classic fact ...
7
votes
2answers
593 views
Is this vertex ordering optimization NP-Hard?
Could you help me to prove that the following problem is NP-hard?
Problem. Given an undirected graph $G=(V,E)$, find an ordering of the nodes such that $\sum\limits_{v\in V}|succ(v)|\times|pred(v)|$ ...
9
votes
1answer
333 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
132 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 ...
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 ...
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
114 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 ...
7
votes
1answer
700 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 ...
29
votes
2answers
1k views
Why is “topological sorting” topological?
Why is "topological sorting" called "topological"? Is it just because it determines an order without altering any vertices or edges -- like a doughnut and coffee cup are topologically equivalent? Why ...
6
votes
1answer
529 views
Ordering of a DAG minimizing some definition of cost
Consider a DAG $(V,A)$ with a topological ordering $(v_1,v_2,\ldots,v_n)$. I define the cost of this ordering as the maximum over all $1\leq i\leq n$ of $|\{j\leq i
\mid \exists k>i: (v_j,v_k)\in A\...
20
votes
2answers
1k views
Is feedback vertex set problem is solvable in polynomial time for 3-degree bounded graphs?
Feedback Vertex Set is NP-complete for general graphs. It is known to be NP-complete for degree-8 bounded graphs due to a reduction from vertex cover.
The Wikipedia article says that it is poly-time ...
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 ...
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 ...
9
votes
1answer
257 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$. ...
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 ...
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 ...
25
votes
1answer
627 views
Is there a problem that is easy for cubic graphs but hard for graphs with maximum degree 3?
Cubic graphs are graphs where every vertex has degree 3. They have been extensively studied and I'm aware that several NP-hard problems remain NP-hard even restricted to subclasses of cubic graphs, ...
19
votes
1answer
688 views
Rapidly mixing Markov chains on 3-colorings of a cycle
The Glauber dynamics is a Markov chain on the colorings of a graph in which at each step one attempts to recolor a randomly chosen vertex with a random color. It does not mix for the 3-colorings of a ...
3
votes
1answer
111 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
5answers
2k views
Finding outer face in plane graph (embedded planar graph)
I have a planar graph, for which I have computed a combinatorial embedding and coordinates in the plane. So all my arcs are now oriented in the plane, respective to their end vertices.
Computing a ...
-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:
...
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 ...
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 ...
1
vote
1answer
154 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$ (...
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
116 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 ...
