# All Questions

Tagged with graph-theory computational-complexity

156
questions

**2**

votes

**1**answer

70 views

### How does the complexity of calculating the Permanent imply the NP completeness of directed 3-cycle cover?

In their paper Two Approximation Algorithms for 3-Cycle Covers of Markus Bl?ser and Bodo Manthey it is stated that:
"...deciding whether an unweighted directed graph has a 3-cycle cover is already NP-...

**1**

vote

**0**answers

38 views

### Coloration of an interval graph with constraints [on hold]

Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...

**0**

votes

**0**answers

34 views

### Algorithmic complexity of deciding the existence of regular $\mathrm{f}$-factors in graphs

Finding regular $\mathrm{f}$-factors in undirected simple graphs can be reduced to finding a perfect matching by utilizing the gadgets of Tutte or of Lovász and Plummer; there are several algorithms ...

**2**

votes

**1**answer

119 views

### Edge coloring graphs is in P?

It is known that there exist polynomial time algorithm to approximate the Lovasz number or the supremum of Shannon capacity of graphs.
By Vizing's theorem, the graph $G$ has only two chromatic ...

**0**

votes

**0**answers

61 views

### Proving Vizing's and Brooks' theorem using the polynomial approach

It is known that the graph polynomial defined by $\prod_{i<j}(x_i-x_j)$ where the vertices $x_k\ \ , \ \ k=\{1,2\ldots,n\}$ are ordered with respect to some order; can be used to verify the proper ...

**4**

votes

**1**answer

123 views

### Graphs with Hermitian Unitary Edge Weights

Very recently, Hao Huang proved the Sensitivity Conjecture, which had been open for 30 years or so. Huang's proof is surprisingly short and easy. Here is Huang's preprint, a discussion on Scott ...

**3**

votes

**2**answers

98 views

### Strong chromatic index of some cubic graphs

Edit 2019 June 26 New computer evidence forces us to revise our guesses relating strong chromatic index and girth
Edit 2019 June 25 Some mistakes have been corrected. Question 2 has changed.
...

**2**

votes

**0**answers

17 views

### Complexity of weighted fractional edge coloring

Given an edge-weighted multigraph $G=(V,E)$ with a positive, rational weight function $(w(e): e \in E)$, the weighted fractional edge coloring problem (WFECP) is to compute ($\min 1^T x$ subject to $...

**1**

vote

**0**answers

59 views

### Succinct circuits and NEXPTIME-complete problems

I am fascinated by a recent fact I was reading: Succinct Circuits are simple machines used to descibe graphs in exponentially less space, which leads to the downside that solving a problem on that ...

**3**

votes

**1**answer

125 views

### Representation of Subgraph Counts using Polynomial of Adjacency Matrix

We consider a graph $G$ of size $d$ with adjacency matrix $A$, whose entries take value in $\{0,1\}$. We are interested in the number of a certain connected subgraph $S$ of size $k$ in $G$. For ...

**-4**

votes

**1**answer

200 views

### What is the computationally simplest way to universally index the set of simple graphs?

If given a simple, integer-labeled, but not necessarily connected, graph $G := (V,E)$ consisting of at least one vertex, i.e. $\lvert \rvert V \lvert \rvert \geq 1$, then is there a function to ...

**1**

vote

**1**answer

58 views

### The complexity on calculation of the Graev metric on the free Boolean group of a metric space

For a set $X$ by $B(X)$ we denote the family of all finite subsets of $X$ endowed with the operation $\oplus$ of symmetric difference. This operation turns $B(X)$ into a Boolean group, which can be ...

**2**

votes

**0**answers

31 views

### Flat or linkless embeddings of graph with fixed projection

The problem of finding whether a given planar diagram of a graph, with over- and under-crossings, is a linkless embedding or not has unknown complexity (Kawarabayashi et al., 2010). My first question ...

**0**

votes

**1**answer

83 views

### Is there any solution that currently exists for the graph automorphism problem in the general case?

I was reading the Wikipedia pages on the graph automorphism, but I could not find any solution to the problem (Not even a brute force one). So, is it indeed true that no solutions exist for the ...

**1**

vote

**0**answers

31 views

### Is there an algorithm for this constrained Hypergraph optimization problem?

I'm currently developing an algorithm for computing knot coloring invariants and got to the following question:
Given a set $S$ and a certain hyper-graph $H \subseteq S^3 $, find a decomposition $S = ...