Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,319
questions
16
votes
1answer
916 views
Online transitive closure better than O(N^2) per edge addition
I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this:
...
16
votes
1answer
662 views
Complexity of recognizing vertex-transitive graphs
I am not knowledgeable in the area of complexity theory involving groups so I apologize if this is a well known result.
Question 1. Let $G$ be a simple undirected graph of order $n$. What is the
...
16
votes
1answer
756 views
Reference for (odd-hole,antihole)-free graphs?
X-free graphs are those that contain no graph from X as an induced subgraph. A hole is a cycle with at least 4 vertices. An odd-hole is a hole with an odd number of vertices. An antihole is the ...
16
votes
1answer
398 views
Strongly Regular Graph and GI-Completeness
It is not known if graph isomorphism (GI) for strongly regular graphs (SRGs) is in P. Are there any hints that it might or might not be GI-Complete? Are there any strong consequences in such cases? (...
16
votes
1answer
678 views
Making a minimum-width tree decomposition lean in polynomial time
As is well known, a tree decomposition of a graph $G$ consists of a tree $T$ with an associated bag $T_v \subseteq V(G)$ for each vertex $v \in V(T)$, which satisfies the following conditions:
Every ...
16
votes
1answer
954 views
Number of Hamiltonian cycles on random graphs
We assume that $G\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n}$.
Then the following fact is well known:
\begin{eqnarray}
Pr [G\mbox{ has a Hamiltonian cycle}]=
\begin{cases}
1 & (c(n)\...
16
votes
1answer
1k views
NP-hardness of a graph partition problem?
I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic?
Here $E$ is ...
16
votes
1answer
435 views
What is the complexity of this graph problem?
Given a simple undirected graph $G$, find a subset $A\neq \emptyset$ of vertices, such that
for any vertex $x\in A$ at least half of the neighbors of $x$ are also in $A$, and
the size of $A$ is ...
16
votes
1answer
544 views
Sensitivity of Graph Properties
In [1], Turan shows that the sensitivity (called "critical complexity" in the paper) of a graph property is strictly greater than $\lfloor {1\over 4} m \rfloor$ where $m$ is the number of vertices in ...
16
votes
1answer
731 views
Reference for mixed graph acyclicity testing algorithm?
A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction ...
16
votes
0answers
256 views
When does adding edges decrease the cover time of a graph?
When first learning about random walks on a graph $G$, one may have an intuitive feeling that adding edges to $G$ will decrease its cover time $C(G)$. However, this is not the case. The path graph $...
15
votes
6answers
487 views
Global properties of hereditary classes?
A hereditary class of structures (e.g. graphs) is one that is closed under induced substructures, or equivalently, is closed under vertex removal.
Classes of graphs that exclude a minor have nice ...
15
votes
2answers
927 views
Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?
The $k$-cycle problem is as follows:
Instance: An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges.
Question: Does there exist a (proper) $k$-cycle in $G$?
Background: For any ...
15
votes
5answers
869 views
References for Modular Decomposition
What are good papers/books to better understand the power of Modular Decomposition and its properties?
I'm particularly interested in algorithmic aspects of Modular Decomposition. I have heard that ...
15
votes
3answers
2k views
Complexity of edge coloring in planar graphs
3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable".
What is the complexity of 3-edge coloring of cubic ...
15
votes
3answers
1k views
Subgraph isomorphism with a tree
If we have a large (directed) graph $G$ and a smaller rooted tree $H$, what is the best known complexity for finding subgraphs of $G$ isomorphic to $H$? I am aware of results for subtree isomorphism ...
15
votes
1answer
632 views
Is this dense version of Kruskal's algorithm well-known?
About a year ago, a friend and I thought of a way to implement Kruskal's algorithm for dense graphs in better than the usual $O(m \log m)$ bound (without assuming pre-sorted edges). Specifically, we ...
15
votes
1answer
796 views
Modular Decomposition and Clique-width
I am trying to understand some concepts about Modular decomposition and Clique-width graphs.
In this paper ("On P4-tidy graphs"), there is a proof of how to solve optimization problems like clique-...
15
votes
1answer
491 views
Drawing graphs with few “sharp” vertices?
For a planar embedding of a planar graph on a plane with straight edges, define a vertex as a sharp vertex if the maximum angle between two consecutive edges around it is more than 180. Or in other ...
15
votes
1answer
737 views
Hardness of Computing Weisfeiler-Lehman labels
The 1-dim Weisfeiler-Lehman algorithm (WL) is commonly known as canonical labeling or color refinement algorithm. It works as follows :
The initial coloring $C_0$ is uniform, $C_0(v) = 1$ for all ...
15
votes
2answers
673 views
GI-hard graph problem not known to be $NP$-complete
Graph Isomorphism ($GI$) is good candidate for $NP$-intermediate problem. $NP$-intermediate problems exist unless $P=NP$. I'm looking for natural problem that is hard for $GI$ under Karp reduction (A ...
15
votes
1answer
766 views
Decomposing k-connected graphs into (k+1)-connected components
A connected graph can be decomposed into its biconnected components. This block cutpoint tree is unique. Similarly, biconnected graphs can be decomposed into triconnected components. The corresponding ...
15
votes
1answer
475 views
Imperfect subgraph isomorphism
Consider the following problem: Given a query graph $G = (V, E)$ and a reference graph $G' = (V', E')$, we want to find the injective mapping $f : V \rightarrow V'$ which minimizes the number of edges ...
15
votes
1answer
443 views
Graph decompositions for combining “local” functions of vertex labelings
Suppose we want to find
$$\sum_x \prod_{ij \in E} f(x_i,x_j)$$
or
$$\max_x \prod_{ij \in E} f(x_i,x_j)$$
Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a ...
15
votes
1answer
321 views
What can we prove with infinite graphs that we cannot prove without them?
This is a follow-up question to this one about infinite graphs.
Answers and comments to that question list objects and situations which are naturally modeled by infinite graphs. But there are also ...
15
votes
1answer
492 views
Decomposing graphs of genus one
Planar graphs are $K_{3,3}$-free. Such graphs can be decomposed into tri-connected components, which are known to be either planar or $K_5$ components.
Is there such a "nice" decomposition of ...
15
votes
0answers
556 views
Is it NP-hard to find (the root of) a small decision tree for a monotone boolean function?
Last year I spent some time trying to prove or disprove the following:
Conjecture. Consider a graph $G$ and define a 2-DNF formula $\phi$ that contains a term $x \land y$ iff $x\mathrel{-\!-}y$ is ...
15
votes
0answers
219 views
Mixing properties of random walks on graphs
I have a question about this paper (not behind a pay wall) on the Cheeger inequality for graphs.
One of the main ideas of the paper is that random walks on graphs can be used to find sets with small ...
15
votes
0answers
1k views
What is the fastest deterministic algorithm for incremental DAG reachability?
As the title. The incremental algorithm maintains the reachability information of a DAG when it undergoes a series of edge insertions (but no deletions). And the algorithm supports constant query (if ...
14
votes
4answers
2k views
Counting the number of vertex covers: when is it hard?
Consider the #P-complete problem of counting the number of vertex covers of a given graph $G = (V, E)$.
I'd like to know if there is any result showing how the hardness of such problem varies with ...
14
votes
2answers
2k views
Justification for the Hungarian method (Kuhn-Munkres)
I wrote an implementation of the Kuhn-Munkres algorithm for the minimum-weight bipartite perfect matching problem based on lecture notes I found here and there on the web. It works really well, even ...
14
votes
2answers
4k views
Optimal algorithm for finding the girth of a sparse graph?
I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity.
I thought about some modification on Tarjan's algorithm for ...
14
votes
2answers
2k views
Generalization of the Hungarian algorithm to general undirected graphs?
The Hungarian algorithm is a combinatorial optimization algorithm which solves the maximum weight bipartite matching problem in polynomial time and anticipated the later development of the important ...
14
votes
2answers
481 views
Approaches to GI inspired by knot problem
GI and Knot Problem both are problem of deciding structural equivalence of mathematical objects. Are there any results establishing connections between them? Nice connections of knot problem to ...
14
votes
1answer
3k views
Is the longest trail problem easier than the longest path problem?
The longest path problem is NP-hard. The (typical?) proof relies on a reduction of the Hamiltonian path problem (which is NP-complete). Note that here the path is taken to be (node-)simple. That is, ...
14
votes
4answers
714 views
P-complete problems on trees
This question is related to one of my previous questions, NP-hard problems on trees.
I am looking for problems that are P-complete on trees.
14
votes
4answers
324 views
Does the infinite graph of diagonals have an infinite component?
Suppose we connect the points of $V = \mathbb{Z}^2$ using the set of undirected edges $E$ such that either $(i, j)$ is connected to $(i + 1, j + 1)$, or $(i + 1, j)$ is connected to $(i, j + 1)$, ...
14
votes
1answer
1k views
Conductance and diameter in regular graphs
Given an undirected, regular graph $G=(V,E)$, what is the relationship between its diameter - defined as the largest distance between two nodes - and its conductance, defined as $$\min_{S \subset V} ~\...
14
votes
2answers
2k views
Number of mincuts of a graph without using Karger's algorithm
We know that Karger's mincut algorithm can be used to prove (in a non-constructive way) that the maximum number of possible mincuts a graph can have is $n \choose 2$.
I was wondering if we could ...
14
votes
2answers
418 views
A graph parameter possibly related to treewidth
I am interested in graphs on $n$ vertices which can be produced via the following process.
Start with an arbitrary graph $G$ on $k\le n$ vertices. Label all the vertices in $G$ as unused.
Produce a ...
14
votes
1answer
316 views
Generating Graphs with Trivial Automorphisms
I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism.
It is "commonplace" (yet controversial!) to assume the existence of BPP ...
14
votes
1answer
413 views
How expensive may it be to destroy all long s-t paths in a DAG?
We consider DAGs (directed acyclic graphs) with one source node $s$ and one target node $t$; parallel edges joining the same pair of vertices are allowed. A $k$-cut is a set of edges whose removal ...
14
votes
1answer
428 views
Hitting odd cycles
Is there anything known about the following problem?
Does it make sense at all?
What is it called?
Is it trivially equivalent to some other problem?
What is the time-complexity?
Given an undirected (...
14
votes
2answers
550 views
Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices
What is the complexity of the following problem?
Input:
$H$ a Hamiltonian path in $K_n$
$R \subseteq [n]^2$ a subset of pairs of vertices
a positive integer $k$
Query: is there a matching $M$ such ...
14
votes
0answers
349 views
Finding all-pairs anti-distance
Thanks for a great forum. This is my first post here. I am working on a signal processing application and the core of one the main algorithms reduces to a graph theoretical problem.
Let $G=(V,E)$ ...
14
votes
0answers
413 views
Question on Products of Graphs
Let $S_{n}(G)$, $C_{n}(G)$, $T_{n}(G)$ be the $n$-fold Strong Product, Cartesian Product and Tensor Product of a graph $G$ on $|V|$ vertices.
Let the chromatic number ($\chi(G)$) and the independence ...
14
votes
0answers
485 views
Bi-partite expander graphs
My question relates to bi-partite expander graphs, defined as bi-partite graphs on $n$ left vertices, $m$ right vertices, constant left-degree $k$, such that
For any linear-sized subset $S$ of the ...
14
votes
0answers
508 views
Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)
Recently while working on a problem, I had to go through some of the literature on nested dissection. I happen to have one (maybe two?) questions related to the same.
First, I will define a few ...
14
votes
1answer
339 views
Space-approximation Trade-off
In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(...
13
votes
4answers
3k views
LP relaxation of independent set
I've tried the following LP relaxation of maximum independent set
$$\max \sum_i x_i$$
$$\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E$$
$$x_i\ge 0$$
I get $1/2$ for every variable for every cubic ...
