Yota Otachi
  • Member for 11 years, 3 months
  • Last seen this week
1 answers
3 votes
126 views
Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph
Accepted answer
8 votes

The famous graph (the complement of the disjoint union of $n/3$ triangles) with $3^{n/3}$ maximal cliques is $K_1 \cup K_2$-free, and thus has none of $2C_4$, $C_5$, $P_5$ as an induced subgraph. ...

View answer
1 answers
2 votes
141 views
Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices
Accepted answer
3 votes

The problem is polynomial-time solvable. Observe that we have to pick exactly one vertex from each color class to form a $k$-clique. If there is a vertex $x \in V_{i}$ that has no neighbor in some $V_{...

View answer
1 answers
5 votes
200 views
Is this a known problem, and is it #P-complete?
Accepted answer
9 votes

To Question 1: The graphs induced by such edge sets are known as pseudoforests. As your proof of the membership to #P implies, an edge set is the image of a selection function if and only if the graph ...

View answer
1 answers
6 votes
336 views
Naive definition of treewidth
Accepted answer
9 votes

Your parameter "naive treewidth" is known as tree-partition-width in the literature. It is known that if a graph has constant treewidth and constant maximum degree, then it has constant tree-partition-...

View answer
2 answers
6 votes
179 views
Given a set of distances (no info regarding what points the distances correspond to) from a complete graph, is the realization of the graph unique?
Accepted answer
8 votes

I think the following example with four points answers your question (though it gives multi-sets of distances). See Reconstructing Sets From Interpoint Distances by Skiena, Smith, and Lemke for more ...

View answer
1 answers
16 votes
732 views
Complexity of recognizing vertex-transitive graphs
Accepted answer
14 votes

I don't have a complete answer, but I think both problems are open. The paper by Jajcay, Malnič, Marušič [3] is related to your first question. They provide some tools to test ...

View answer
3 answers
16 votes
457 views
Smallest set that intersects some given sets
Accepted answer
25 votes

Your first problem is the hypergraph transversal problem (aka the HITTING SET problem). The second problem is the FEEDBACK VERTEX SET problem. Both the problems are NP-complete.

View answer
1 answers
15 votes
480 views
Imperfect subgraph isomorphism
Accepted answer
7 votes

Your problem is Maximum Common Edge Subgraph Problem (Max CES) defined as follows: given two graphs $G$ and $G'$, find a graph $H$ with the maximum number of edges that is isomorphic to a subgraph of $...

View answer
3 answers
25 votes
534 views
Complexity of "is a graph a product"
12 votes

There is a linear-time algorithm for determining the prime factors of connected graphs with respect to the Cartesian product. See the paper by Imrich and Peterin.

View answer
1 answers
14 votes
348 views
On the complexity of Bandwidth Minimization
Accepted answer
16 votes

The bandwidth problem is $W[t]$-hard for all $t$. It was shown by Bodlaender et al. in "Beyond NP-completeness for problems of bounded width." See the paper. On the other hand, it is also known that ...

View answer
2 answers
12 votes
816 views
What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?
Accepted answer
13 votes

The pathwidth of $P^3_k$ can be determined as a corollary to some known results. FitzGerald [2] showed that the bandwidth of $P^3_k$ is $\lfloor \frac{3}{4} k^{2} + \frac{1}{2} k \rfloor$. Harper [3] ...

View answer