Questions tagged [graph-theory]

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

Filter by
Sorted by
Tagged with
5 votes
1 answer
103 views

Upperbound for max degree of k-tree completion

Definitions: For a graph $G$, a $k$-tree completion of $G$ is a $k$-tree obtained by adding edges to $G$ (if $G$ has a $k$-tree completion, $G$ is said to be a partial $k$-tree). The least integer $k$ ...
user avatar
3 votes
0 answers
113 views

Minimum feedback arc set for dense directed graph

This is really a matrix problem, but the theory I believe lies in graphs. Consider some matrix $A$ and permutation matrix $P$, where we define $\tilde{A}:= PAP^T$. I want to pick $P$ such that if $\...
user avatar
5 votes
1 answer
109 views

Series-parallel DAG characterization

According to this Wikipage series-parallel graphs are characterized like this: 2-connected series-parallel graphs are characterized by having no subgraph homeomorphic to $K_4$. I couldn't find a ...
user avatar
  • 153
3 votes
1 answer
102 views

Decomposing Single Crossing Minor Free graphs

We know that for a single-crossing graph H of size h, there exists a constant ch whose value depends only on h, such that every four-connected component of an H-minor-free graph is either a planar ...
user avatar
4 votes
0 answers
86 views

Complexity of Encoding a Matroid Flow Problem in a Matrix

Context: Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$. We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
user avatar
  • 454
1 vote
0 answers
56 views

Complement of Multi-colored Clique with an extra condition

In the problem Multi-colored clique, we ask for a $k$-clique of the input graph $G$ where $G$ is guaranteed to be $k$-colorable. In the complement problem Independent Set given Clique Partition, we ...
user avatar
5 votes
1 answer
84 views

Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

Let $G=(V,E)$ be graph. Recall that a cut of $G$ is (or can uniquely be identified with) a pair $(A,B)$ of nonempty subsets of $V$ which partition it. Given a cut $(A,B)$, let $E(A,B) := \{(a,b) \in ...
user avatar
  • 217
2 votes
1 answer
170 views

Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices

I am interested in the MulitColoredClique problem with an additional restriction. (Def.: A $k$-coloring $V_1,V_2,\dots,V_k$ of a graph $G$ is a partition of the vertex set of $G$ into $k$ independent ...
user avatar
6 votes
0 answers
119 views

Computational complexity of finding paths with specified product in a (group-labeled) directed graph

This question came up in the analysis of the puzzle game Swish. One way of representing the solvability problem is this: given a directed graph $G$ where each edge of the graph is labeled with an ...
user avatar
0 votes
1 answer
146 views

Graphs-like data structure with weighted vertices

I am searching for literature related to a graph-like data structure where vertices are weighted instead of edges. Formally, we can define a weighted-(edge)-graph $G=(V,E, w(\cdot))$ as a tuple of ...
user avatar
  • 3
5 votes
1 answer
425 views

Isomorphic graph embeddings in the Euclidean Space

Given an undirected and unweighted graph $G = (V, E)$, is it possible to find a mapping $f: V \rightarrow \mathbb{R}^k$ for some $k$ such that for every $i, j \in V$, $\|f(i) - f(j)\|_2^2 = \Delta(i, ...
user avatar
  • 181
-1 votes
1 answer
82 views

Al-Mubaid's Similarity Measure for Ontological Concepts

Al-Mubaid et al. proposed a semantic similarity measure in their research paper [1]. They see ontologies as connected graphs but refer to clusters within ontology graphs without ever defining what ...
user avatar
2 votes
1 answer
110 views

Complexity of acyclicity of a "nondeterministic" graph

By "nondeterministic" I mean the graph is a collection of sets of "candidate" edges sharing a single destination: $E \subseteq 2^V \times V$. The problem is whether it is possible ...
user avatar
  • 123
2 votes
1 answer
233 views

MaxCut instance with smallest max cut

Let us look at all 4-regular undirected graphs with $n$ nodes and edge weight equals to 1 for all edges. Out of these graphs, I would like to find the MaxCut instance with least number of edges in its ...
user avatar
1 vote
0 answers
225 views

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 ...
user avatar
5 votes
1 answer
179 views

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 ...
user avatar
  • 3,920
0 votes
1 answer
97 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 ...
user avatar
1 vote
0 answers
45 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 = \{...
user avatar
2 votes
0 answers
52 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 ...
user avatar
1 vote
0 answers
112 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, ...
user avatar
0 votes
0 answers
133 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$ ...
user avatar
4 votes
1 answer
206 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 ...
user avatar
  • 1,955
1 vote
0 answers
152 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 ...
user avatar
4 votes
1 answer
142 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 $...
user avatar
4 votes
0 answers
145 views

Uniquely 4-colorable Planar Graph Conjecture?

My question is on Uniquely 4-colorable Planar Graph Conjecture mentioned in On purely tree-colorable planar graphs (and other papers of same(?) team such as "Theory on Structure and Coloring of ...
user avatar
1 vote
0 answers
48 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 ...
user avatar
  • 387
1 vote
1 answer
154 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 ...
user avatar
  • 1,955
4 votes
2 answers
441 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 ...
user avatar
2 votes
1 answer
133 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) $...
user avatar
1 vote
0 answers
119 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-...
user avatar
  • 387
10 votes
3 answers
1k 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 ...
user avatar
10 votes
1 answer
548 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 ...
user avatar
  • 533
10 votes
1 answer
249 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 ...
user avatar
3 votes
0 answers
126 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 ...
user avatar
  • 723
-2 votes
2 answers
367 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. ...
user avatar
0 votes
0 answers
35 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[...
user avatar
1 vote
1 answer
190 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 ...
user avatar
  • 23
10 votes
1 answer
183 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 ...
user avatar
  • 161
7 votes
1 answer
884 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 ...
user avatar
5 votes
0 answers
113 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 ...
user avatar
  • 4,256
2 votes
2 answers
482 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 ...
user avatar
  • 3,420
2 votes
1 answer
161 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 ...
user avatar
3 votes
1 answer
136 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,...
user avatar
1 vote
1 answer
129 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 ...
user avatar
  • 509
-4 votes
1 answer
407 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: ...
user avatar
2 votes
0 answers
79 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 ...
user avatar
8 votes
0 answers
175 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 $...
user avatar
  • 1,015
1 vote
1 answer
64 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 ...
user avatar
  • 2,293
0 votes
2 answers
192 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 ...
user avatar
1 vote
1 answer
68 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 $...
user avatar
  • 13

1 2 3
4
5
30