0
$\begingroup$

given a simple, finite and symmetric graph $G(V,E)$ with $n$ vertices and at least $n$ edges

Question:

how can the smallest set of vertices $W\subset V$ be calculated for which the graph induced by $V\setminus W$ is connected and 2-regular, i.e. a single cycle.


Remark:
if we don't insist on a single cycle, we get a generalization of the maximal independent set ($MIS$) problem by means of the following generalized restatement of the

$MIS$ problem:
calculate the largest subset of the vertices whose induced subgraph is $r$-regular when $r=0$

The solutions for arbitrary values of $r$ can then be stated as calculating the maximal regular independent subgraph ($max\, RISG$)
For $r=1$ we would have a maximal independent matching problem and for $r=2$ a relaxed version this question's problem

Improve this question
$\endgroup$
7
  • $\begingroup$ Ssince the graph is finite, the whole question is finite, and can be solved by exhaustive search. But perhaps you want something more computationally efficient. But then you run into the problem of determining whether $G$ is Hamiltonian, that is, has a cycle visiting every vertex, and that question is NP-complete. $\endgroup$
    – Gerry Myerson
    Commented Nov 8 at 2:10
  • $\begingroup$ @GerryMyerson Not sure Hamiltonicity arises here. The only time we are looking at all nodes is when $W=\emptyset$, in which case it is easy to check whether the induced subgraph (which is the same as $G$) is a cycle. $\endgroup$
    – RobPratt
    Commented Nov 8 at 2:59
  • $\begingroup$ @RobPratt Hamiltonicitx doesn't apply and if we remove none of the vertices, we do not necessarly have a connected 2-regular graph $\endgroup$
    – Manfred Weis
    Commented Nov 8 at 4:36
  • $\begingroup$ @ManfredWeis I agree, and checking that is $O(n)$, $\endgroup$
    – RobPratt
    Commented Nov 8 at 4:39
  • $\begingroup$ OK, I missed the bit about the "induced subgraph". My apologies. $\endgroup$
    – Gerry Myerson
    Commented Nov 8 at 5:47

1 Answer 1

Reset to default
1
$\begingroup$

This is the $r=2$ case of the maximum $r$-regular induced connected subgraph problem ($r$-MaxRICS), which is NP-hard for fixed $r$: https://kyutech.repo.nii.ac.jp/record/2000071/files/E96.D_443.pdf

Improve this answer
$\endgroup$
1
  • $\begingroup$ That's exactly what I was hoping for $\endgroup$
    – Manfred Weis
    Commented Nov 9 at 15:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .