Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,512
questions
3
votes
0
answers
190
views
Separation Oracle for Inverse Bipartite Matching Polytope
The $N$x$N$ bipartite matching problem can be written as finding a configuration of variables ${\mathbf y}^* = \{y^*_1, \ldots, y^*_N\}$, $y_i \in \{1, \ldots, N\}$ such that
$${\mathbf y}^* = \arg\...
- 671
10
votes
2
answers
231
views
When does an FO property kill off NL-hardness?
Context: We consider only digraphs. Let CYCLE be the language of graphs with a cycle; it is an NL-complete problem. Let HASEDGE be the language of graphs with at least one edge. Then trivially, $\...
- 3,916
13
votes
4
answers
4k
views
The number of cliques in a graph: the Moon and Moser 1965 result
I'm looking for the full text of the Moon and Moser 1965 clique result On Cliques in Graphs (there exist graphs with a number of maximal cliques exponential in $n$). My university's paywall doesn't ...
8
votes
1
answer
650
views
Minimum degree of the "tree graph"
Given a graph $G$, define the tree graph $T(G)$ as a graph whose vertices are the spanning trees of $G$, and there is an edge between two trees if one can be obtained from the other by replacing a ...
- 91
10
votes
3
answers
370
views
Refinements of pair approximation for network analysis
When considering interactions on networks, it is usually very hard to calculate the dynamics analytically, and approximations are employed. Mean-field approximations usually end up ignoring the ...
- 10.1k
5
votes
2
answers
1k
views
Is there an efficient algorithm to determine the parity of the longest path in a graph?
Finding the longest path in a graph is intractable problem. The decision version is $NP$-complete. However, Given a graph, Is there an efficient algorithm to determine the parity of the longest path ...
- 20.7k
12
votes
1
answer
316
views
Optimal preprocessing for certain types of queries
Suppose we have a semigroup $(S,\circ)$ with elements $S=\lbrace s_1,s_2,\dots,s_n\rbrace$. Our goal is to compute products $s_i\circ s_{i+1}\circ \cdots\circ s_j$.
In their paper "Optimal ...
- 221
13
votes
2
answers
583
views
Decentralized algorithm for determining influential nodes in social networks
In this paper by Kempe-Kleinberg-Tardos, the Authors propose a greedy algorithms based on submodular functions to determine the $k$ most influential nodes in a graph, with applications to social ...
- 203
13
votes
1
answer
488
views
Parallel algorithms for reachability in directed planar graphs
Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors.
What is the best known parallel algorithm for st-connectivity ...
- 10.5k
1
vote
0
answers
360
views
Discovering a graph with minimal oracle queries
I have a transitive DAG G which is a subgraph of an unknown DAG R. (The nodes are the same in G and R, but R may have edges not in G.) I can determine the presence of a given edge in R by an oracle ...
- 1,697
1
vote
0
answers
451
views
Cycles in a directed graph
Wondering if we can prove the following or if it is already proved where can I get the proof.
Let $v_1, v_2, v_3, \ldots, v_n$ and $t$ be $n+1$ vertexes in a directed graph. $v_1, v_2, v_3, \ldots, ...
- 21
5
votes
1
answer
498
views
Place n points in a box as far away from each other as possible
Can you suggest an optimal or heuristic algorithm for placing points on a 2D plane (within a constrained space) such that minimum distance between any two points is maximized.
In other words, I'm ...
- 151
9
votes
3
answers
1k
views
Finding all cycles
I have a finite set $S$, a function $f:S\to S$, and a total order $<$ on $S$. I want to find the number of distinct cycles in $S$.
For a given element $s\in S$ I can use Floyd's algorithm (or ...
- 1,697
27
votes
3
answers
888
views
The complexity of determining if a fixed graph is a minor of another
The result by Robertson and Seymour demonstrates an $O(n^3)$ algorithm for testing whether a fixed graph $G$ is a minor of $H$. I have two and a half questions on this topic:
1) It appears that there ...
- 779
2
votes
1
answer
547
views
Lower and upper bounds on the diameter of 3-regular graphs obtained after reducing practical real world problem instances to #3-regular Vertex Cover
In the paper The diameter of random regular graphs, Bollobás and Fernandez De La Vega give asymptotic lower and upper bounds on the diameter $d$ of random $r$-regular graphs. Roughly, the lower bound ...
- 6,695
6
votes
1
answer
242
views
Complexity of finding weighted edge-disjunctive triangles in a graph
Given a simple graph, in which the edges are weighted with values from the set $\{-1,1\}$. Three pairwise adjacent edges define a triangle. A triangle is called valid, iff two edges have positive ...
8
votes
1
answer
612
views
An interesting variant of maximum matching problem
Given a graph $G(V,E)$, the classic maximum matching problem is choosing the maximum subset of edges $M$ s.t., for each edge $(u,v) \in M$, $d(u)=d(v)=1$.
Has anybody studied the following variant? ...
- 1,433
4
votes
0
answers
105
views
Are there any conditions for which ($k$-)apexness is preserved under $Y-\Delta$ transformations?
Lately, something I've been interested in is finding the set of forbidden minors for the apex graphs. One thing I tried to do was to look at the graphs which were known, and try to find a pattern in ...
- 779
4
votes
0
answers
193
views
Expansion of constant-size sets
My question refers to the expansion of constant size sets of an expander graph.
Suppose we are given an expander graph with Cheeger constant $\alpha$.
What can be said about the edge expansion of sets ...
- 1,224
2
votes
1
answer
249
views
What is a totally ordered sort of sets of a partial order called?
Given a DAG, which can represent a partial order and has at least one topological sort.
For example the graph
>B
/ \
A >D
\ /
>C
has two ...
- 998
1
vote
1
answer
686
views
Bipartite vertex cover with a Very Important Vertex
I know that I can find the minimum vertex cover of a bipartite graph by first finding the maximum matching and then using Konig's Theorem to turn this matching into a vertex cover of the same order.
...
- 113
11
votes
1
answer
673
views
Complexity of Unique s-t-Connectivity
I would like to know whether the following problem can be decided in $\mathsf{NL}$ (nondeterministic logspace):
Given a directed graph $G$ with two distinguished vertices $s$ and $t$, is there a ...
- 4,420
3
votes
1
answer
355
views
Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits?
Sorry for not-precise question. :-(
There are several papers concerning exact counting (maximum) independent sets in general graphs. Actually, they concerns counting of solutions of 2SAT. The best of ...
- 1,433
3
votes
2
answers
945
views
Is there a list of forbidden subgraphs for comparability graphs?
The "graph classes: a survey" mentioned Trotter and other authors have presented a list of forbidden subgraph of comparability graph. But the google book( where I read graph classes: a survey) do not ...
- 1,433
9
votes
3
answers
3k
views
Approximation algorithms for dominating set problem
I am working on approximation algorithms for minimum dominating set problem. In particular, I am interested in graphs classes restricted by forbidden induced subgraphs.
Since the domination problem ...
- 531
3
votes
1
answer
642
views
My exact divide-conquer algorithm for counting antichain in a poset?
This post is a little lengthy, thank your for your patience for reading. ^_^
As known, counting antichains in a poset is #P-complete, so it is NP-hard to get the exact answer. Following is my simple ...
- 1,433
6
votes
2
answers
585
views
Incremental drawing of large graphs
I have the following problem:
I'm developing a software for data visualization where I get a graph structure and represent it in 3D space. So far, I've been using force-based algorithms to draw graphs ...
1
vote
0
answers
5k
views
Two color Graph Coloring problem with solution involving BFS [closed]
The question appears in Cormen's Introduction to Algorithms.
There are two types of professional wrestlers: "babyfaces"("good guys") and "heels"("bad guys"). Between any pair of professional wrestlers,...
- 11
28
votes
2
answers
1k
views
Maximal/maximum independent sets
Is there something known about the class of graphs with the property that all maximal independent sets have the same cardinality and are therefore maximum ISs?
For example, take a set of points in ...
- 1,306
7
votes
1
answer
3k
views
Minimum path edge-cover or minimum flow with unit capacities and DAGs
I have a directed acyclic graph (DAG) such that there can only be at most one edge between any two nodes (ie, only one (i,j) can exist between i and j). I need to find the the smallest set of paths ...
- 181
6
votes
2
answers
328
views
Is any chordal graph an incomparability graph?
I was confused by Wikipedia's definitions of "chordal graph", "interval graph", "string graph", "comparability graph", "incomparability graph" and the complements of these.
Wikipedia says "The ...
- 1,433
3
votes
1
answer
944
views
measures for a DAG (directed acyclic graph)?
Recently, I want to devise some kernelization (in the framework of parameterized complexity) for problem on DAG. So, find a proper parameter is essential.
Well, is there a measure for the importance ...
- 1,433
12
votes
0
answers
356
views
Directed Sparsest Cut on Planar Graphs?
The (uniform) directed sparsest cut problem asks for a cut $(S,\bar{S})$ in a directed graph $G=(V,E)$ which minimize the ratio $\frac{\delta_{out}(S) }{|S||\bar{S}|}$, where $\delta_{out}$ is the ...
- 426
10
votes
1
answer
255
views
Finding a matching whose contraction minimizes the number of arcs in a graph
Given a mixed graph $G=(V,E,A)$ with edges $E$ and arcs $A$, find a matching in $E$ that minimizes the number of arcs in $G/M$, where $G/M$ is obtained from $G$ by contracting matched vertices and ...
- 1,440
14
votes
0
answers
414
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 ...
- 2,208
4
votes
1
answer
259
views
Laying paths on a network using minimum number of links/edges
Consider an undirected graph G(V,E), where each edge $e\in E$ has capacity $c(e)$. Also given is a traffic matrix $T_{ij}$ representing the amount of traffic flowing from vertex $i$ to $j$. The goal ...
- 41
2
votes
1
answer
871
views
What is a multicast graph?
Martin Fowler in his blog post on "The LMAX Architecture" tried to describe the component called Disruptor as a multicast graph of queues
At a crude level you can think of a Disruptor as a ...
- 131
2
votes
1
answer
183
views
Decomposing complete graphs into clique-free graphs of certain size
Modified in accordance with Tsuyoshi's comment which seems to generalize.
Let $K_{m}$ be a complete graph on $m$ vertices. Is there a way to partition the graphs in to sets of graphs that have no ...
- 2,208
6
votes
1
answer
98
views
Planar Graphs and Skew Binary Subspaces
Let $G$ be a planar triangulation on $3m$ edges and $m+2$ vertices. Let $A$ be the binary matrix obtained from the incidence matrix of $G$ by deleting a row (equivalently the rows of $A$ form a basis ...
3
votes
1
answer
264
views
Standard/Formal name for the graph
Given a connected graph $G =(V_1,V_2,E)$, such that there are no edges among the vertices in set $V_1$, however the other set $V_2$ can have edges in itself. There is actually a restriction for $V_2$, ...
- 715
12
votes
1
answer
2k
views
Citation showing minors are topological minors for subcubic graphs
If $G$ is a graph with maximum degree 3 and is a minor of $H$, then $G$ is a topological minor of $H$.
Wikipedia cites this result from Diestel's "Graph Theory". It's listed as Prop 1.7.4 in the ...
- 343
1
vote
0
answers
289
views
How to quantify the tree-like-ness of a graph?
What are good measures of tree-like-ness of a graph and algorithms for calculating them?
- 119
24
votes
2
answers
569
views
Relation between hardness of recognition of a graph class and forbidden subgraph characterization
I'm considering graph classes that can be characterized by forbidden subgraphs.
If a graph class has a finite set of forbidden subgraphs, then there is a trivial polynomial time recognition algorithm ...
- 1,785
14
votes
1
answer
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} ~\...
- 775
14
votes
0
answers
494
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 ...
- 1,224
2
votes
3
answers
3k
views
Animate a graphviz graph
I'm exploring some graph algorithms, and would like to animate the graph change over time (e.g. when adding a heap node or balancing a tree).
Is there a nice way to animate a sequence of ...
- 123
3
votes
0
answers
204
views
Name for relationship where one graph is a minor usually implies another is?
Let $G$ and $H$ be graphs with the following relationship: for some $k$, after you perform at least $k$ arbitrary subdivisions of the edges of $G$ (or the edges produced through subdivision), $H$ must ...
- 343
5
votes
2
answers
5k
views
Any relation between the size of maximum independent set and the chromatic number on graph of bounded degree?
Consider an connected undirected graph $G$ with $n$ vertices and maximum degree $\Delta$. Assume $G$ contains a maximum independent set of size $k$. Is there any relation between the chromatic number $...
- 901
9
votes
2
answers
373
views
Can I bound the cardinality of a set if testing for membership in it is known to be NP-complete?
I would like to have a bound on the cardinality of the set of unit disk graphs with $N$ vertices. It is known that checking whether a graph is a member of this set is NP-hard. Does this lead to any ...
- 103
5
votes
2
answers
1k
views
Number of edges in $K_4$-free graphs
What can be the upper bound on the number of edges in a graph of $n$ vertices such that the graph does not have $K_4$ as a minor? Is there some relevant paper/book that I can look into it or it would ...
- 715